Análise de Algoritmos (IM471)

Informações

Código: IM471

Pré-requisito:

Grafos e Algoritmos

Ementa

Eficiência computacional. Técnicas de algoritmos. Ineficiência computacional. NP-completude. Algoritmos aproximativos.

Objetivos

(a) Avaliar a complexidade computacional de algoritmos;

(b) Aplicar técnicas de algoritmos para solução de problemas;

(c) Saber provar ineficiência de problemas intratáveis;

(d) Aplicar técnicas randomizadas e aproximativas para solucionar problemas.

Conteúdo Programático

Sumario

1. Complexidade de Algoritmos
2. Técnicas de Algoritmos e Problemas
3. Complexidade Computacional
4. Algoritmos Randomizados
5. Algoritmos Aproximativos

Tópicos de Aula

01. Complexidade de Algoritmos

• Notação O, Theta, Omega
• Complexidade de pior, médio e melhor caso
• Algoritmos ótimos
• Relação de recorrência

02. Técnicas de Algoritmos e Problemas

• Dividir para Conquistar
• Busca binária
• Mergesort
• Multiplicação de Matrizes (Algoritmo de Strassen)
• Algoritmos Gulosos
• Algoritmo de Huffman
• Árvore geradora mínima: Kruskal, Prim
• Programação Dinâmica
• Distância de Edição
• Árvore Binária de Busca
• Caminhos mais curtos

03. Complexidade Computacional

• Classes P e NP
• 2-SAT, 3-SAT, SAT
• Teorema de Cook
• Problemas NP-completos
• Reduções de NP completude

04. Algoritmos Randomizados

• Algoritmos de Monte Carlos
• Algoritmos de Las Vegas

05. Algoritmos Aproximativos

• Problema do Caixeiro Viajante
• Set Cover

Referencia Bibliográfica

Bibliografia Básica

1. Dasgupta, S., Papadimitriou, C. H., Vazirani, U. Algorithms. Science Engineering & Math, 2007.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms. The MIT Press, 2009.
3. Figueiredo, C. M. H., Fonseca, G., Lemos, M., de Sá, V. G. Introdução aos Algoritmos Randomizados, Impa, 2007.

Bibliografia Complementar

1. Garey, M. R., Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
2. Szwarcfiter, J. L., Markenzon, L. Estruturas de Dados e Seus Algoritmos, LTC Editora, 2010.
3. Szwarcfiter, J. L. Teoria Computacional de Grafos, Elsevier, 2018.
4. Kleinberg, J., Tardos, E., Tardos, I. Algorithm Design, Addison-Wesley Professional, 2005.

Postado em 21/11/2013 - 08:41 - Atualizado em 15/08/2023 - 14:45