Clique para ir ao início Universidade de Brasília - UnB
Decanato de Ensino de Graduação - DEG
Secretaria de Administração Acadêmica - SAA
MatrículaWeb
GRADUAÇÃO
  Seja bem-vindo(a).
  Para ter acesso ao menu de Aluno, faça o login.
MatrículaWeb  clique aqui para fazer o login.
 


Período Atual
2017/2


Disciplina - Listagem de Ementa/Programa
Disciplina: 113859 - ANALISE DE ALGORITMOS
(Ver Oferta)

Graduação

Curso
Oferta
Telefones
Calendário
Mensagem da SAA
Benefícios DAC


Órgão: MAT - Departamento de Matemática.
Código: 113859
Denominação: ANALISE DE ALGORITMOS
Nível: Graduação
Vigência: 1962/1
Pré-req: MAT-113034 Cálculo 1 E
CIC-113913 INTRODUCAO A CIEN COMPUTACAO OU
MAT-113034 Cálculo 1 E
CIC-116301 COMPUTACAO BASICA
Ementa:

- FUNDAMENTOS MATEMÁTICOS DA ANÁLISE DE ALGORITMOS;

- TÉCNICAS ALGORÍTMICAS;

- ALGORÍTMOS EFICIENTES PARA BUSCA, ORDENAÇÃO, RECONHECIMENTO DE PADRÕES EM PALAVRAS, OPERAÇÕES SOBRE GRAFOS, OPERAÇÕES ALGÉBRICAS SOBRE MATRIZES E POLINÔMIOS, ETC;

- FUNDAMENTOS DE COMPLEXIDADE COMPUTACIONAL: CLASSES P E NP, PROBLEMAS NP-COMPLETOS.

Programa:

1. FUNDAMENTOS MATEMÁTICOS: CRITÉRIOS DE AVALIAÇÃO DE ALGORITMOS (CORREÇÃO, COMPLEXIDADE TEMPO E ESPAÇO, OTIMALIDADE); ANÁLISE DE ALGORITMOS NO PIOR E NO CASO MÉDIO; CLASSIFICAÇÃO DE FUNÇÕES PELO SEU CRESCIMENTO ASSINTÓTICOS; MÉTODOS DE AVALIAÇÃO DE RELAÇÃO DE RECURRÊNCIA E ANÁLISE PROBABÍLISTICO E COMBINATÓRIO.

2. TÉCNICAS ALGORÍTIMICAS: NOTAÇÃO ALGORÍTMICA E ESTRUTURAS DE DADOS; ALGORITMOS VORAZES; INDUÇÃO E RECURSIVIDADE; TÉCNICA DE DIVISÃO E CONQUISTA.

3. ALGORITMOS EFICIENTES: ORDENAÇÃO: MAXSORT, BUBBLESORT, ORDENAÇÃO POR INSERÇÃO; MÉTODOS DE ORDENAÇÃO BASEADOS NA TÉCNICA DE DIVISÃO E CONQUISTA (QUICKSORT E MERGESORT); HEAPSORT; USO DE ÁRVORES DE DERIVAÇÃO PARA OCMPUTAR O LIMITE INFERIOR PARA ORDENAÇÃO POR COMPARAÇÃO DE CHAVES; ORDENAÇÃO ÓTIMA; SHELLSORT E RAXSORT; ORDENAÇÃO EM MEMÓRIA SECUNDÁRIA. BUSCA EM LISTAS DESORDENADAS E ORDENADAS : BUSCA SEQÜENCIAL; BUSCA BINÁRIA (OPTIMALIDADE); BUSCA DA MEDIANA EM LISTAS ORDENADAS; ARGUMENTAÇÃO DO ADVERSÁRIO PARA COMPUTAR LIMITES INFERIORES PARA O PROBLEMA DE BUSCA. RECONHECIMENTO DE PALAVRAS; ALGORITMOS DE KNUTH-MORRIS-PLATT E BOYER-MOORE PARA RECONHECIMENTO LINEAR DE PALAVRAS; USO DE ÁRVORES DE SUFIXOS NO RECONHECIMENTO DE PADRÕES EM PALAVRAS. PROGRAMAÇÃO DINÂMICA: FUNDAMENTO ESSENCIAL DA TÉCNICA: ELIMINAÇÃO DE REDUNDÂNCIAS NAS SOLUÇÕES RECURSIVAS VIA CONSTRUÇÃO DE TABELAS DINÂMICAS; EXEMPLOS DE SOLUÇÃO DE PROBLEMAS VIA PROGRAMAÇÃO DINÂMICA: RECONHECIMENTO APROXIMADO DE PALAVRAS ALINHAMENTO DE SEQÜÊNCIAS, CÁLCULO DA MÁXIMA SUBSEQÜÊNCIA COMUM, CÁLCULO DA FATORAÇÃO ÓTIMA PARA MULTIPLICAÇÃO DE SEQÜÊNCIAS DE MATRIZES, CONSTRUÇÃO DE ÁRVORES DE PESQUISA BINÁRIA ÓTIMOS, ETC. ALGORITMOS PARA GRAFOS: PESQUISA EM GRAFOS; CAMINHOS MÍNIMOS; ÁRVORES DE GERAÇÃO MINIMAL; COMPONENTES FORTEMENTE CONEXOS; FLUXO MÁXIMO; ETC. ALGORITMOS ALGÉBRICOS: AVALIAÇÃO DE POLINÔMIOS PELO MÉTODOS DE HORNER (OTIMALIDADE); MULTIPLICAÇÃO DE MATRIZES PELOS MÉTODOS DE WINOGRAD E DE STRASSEN; TRANSFORMAÇÃO RÁPIDA DE FOURIER E CONVOLUÇÃO E APLICAÇÕES (MULTIPLICAÇÃO DE POLINÔMIOS).

4. FUNDAMENTOS DA TEORIA DE COMPLEXIDADE: CLASSIFICAÇÃO COMPUTACIONAL DE PROBLEMAS; CLASSES DE COMPLEXIDADE P; CLASSE DE COMPLEXIDADE NP; PROBLEMAS NP-COMPLETOS; ALGORITMOS APROXIMADOS: EMPACOTAMENTO EM CAIXAS, PROBLEMA DA MOCHILA, SUMA DE SUBCONJUNTOS, COLORAÇÃO DE GRAFOS, PROBLEMA DO CAIXEIRO VIAJANTE, ETC.

Bibliografia:

SARA BAASE, ALLEN VAN GELDER 3a. ED.

COMPUTER ALGORITHMS - INTRODUCTION TO DESING AND ANALYSIS ADDISON WESLEY 2000



ALFRED V. AHO, JOHN E. HOPCROFT, JEFFREY D. ULLMAN

THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS (SERIES IN COMPUTER SCIENCE AND INFORMATION PROCESSING)

ADDISON WESLEY 1974



JOHN KLEINBERG, EVA TARDOS

ALGORITHM DESIGN

ADDISON WESLEY 2005



LAIRA VIEIRA TOSCANI, PAULO A. S. VELOSO

COMPLEXIDADE DE ALGORITMOS

SAGRA 2001



THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD, CLIFFORD 2ª ED.

INTRODUCTION TO ALGORITHMS

MIT PRESS 2001



DONALD E. KNUTH 2ª ED.

THE ART OF COMPUTER PROGRAMMING VOL. 3: SORTING AND SERCHING

ADDISON WESLEY 1998



NIVIO ZIVIANI 2ª ED.

PROJETO DE ALGORITMOS COM IMPLEMENTAÇÕES EM PASCAL E C

THOMSON 2004

© 2017 CPD - Centro de Informática
UnB - Universidade de Brasília