Disciplina: DCC001 - ANALISE E PROJETO DE ALGORITMOS
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
Ementa
Fundamentos Matemáticos para Análise de Algoritmos; Análise Assintótica de Algoritmos; Paradigmas de Projeto de Algoritmos; Algoritmos Eficientes para Ordenação, Comparação de Sequências, Problemas em Grafos; Fundamentos de Complexidade Computacional, Redução entre Problemas, Classes P e NP, Problemas NP-Completos.
Conteúdo
1. FUNDAMENTOS MATEMÁTICOS PARA ANÁLISE DE ALGORITMOS: Indução Finita; Crescimento de funções; Notações Assintóticas; Relações de Recorrência; resolução por substituição (indução) e por iteração;
2. ANÁLISE ASSINTÓTICA DE ALGORITMOS: Modelos de computação; Cotas superiores e inferiores; Algoritmos ótimos;
3. PARADIGMAS DE PROJETO DE ALGORITMOS: Projeto por indução; Divisão-e-conquista; Algoritmos gulosos; Programação Dinâmica;
4. ALGORITMOS EFICIENTES: Algoritmos para ordenação: bubble-sort, insertion-sort, merge-sort, heap-sort, quick-sort; Cota inferior para ordenação por comparações; Seleção do k-ésimo e da mediana em tempo linear; Busca binária; Árvore de busca ótima e fatoração ótima para multiplicação de matrizes; Comparação de sequências: maior subsequência comum, algoritmo Knuth-Morris-Pratt para busca de substring; distância de edição; algoritmo Smith-Waterman; Conceito de Análise Amortizada (por exemplo, algoritmo KMP); Algoritmos em Grafos: busca em largura e profundidade; caminho mínimo e algoritmos de Dijkstra e Bellman-Ford; árvore espalhada mínima e algoritmos e Prim e Kruskal; todos os caminhos mínimos e algoritmo de Floyd-Warshall; fluxo máximo e algoritmo de Ford-Fulkerson; Algoritmos geométricos: envoltória convexa: algoritmo da Marcha de Jarvis; ordenação angular e o algoritmo Graham Scan; Cota inferior para envoltória convexa por redução;
5. FUNDAMENTOS DE COMPLEXIDADE COMPUTACIONAL: Redução entre problemas e transferência de cotas; Classe P; Algoritmos não-determinísticos; Verificação polinomial de solução; Classe NP; NP-Completude; Exemplos: SAT, Clique em grafos, Problema da mochila, Soma de subconjuntos, 3-coloração, Caminho e circuito hamiltonianos, Caixeiro viajante, e outros.
Bibliografia
AHO, A.V.; HOPCROFT, J.E.; ULLMAN, J.D. "The Design and Analysis of Computer Algorithms". Addison Wesley Pub. Co.,1974.
TERADA, Routo. "Desenvolvimento de Algoritmos e Estrutura de Dados". Makron Books, 1991.
CORMEN, LEISERSON, RIVEST, STEIN. Algoritmos. Elsevier, 2002.
CAMPELLO, Rui e MACULAN FILHO, Nelson. "Algoritmos e Heurísticas". Editora da UFF, 1994.
Bibliografia(continuação)
Não informado
Bibliografia complementar
Em aberto
