Análise e Síntese de Algoritmos / Análise e Projetos de Algoritmos
Ementa:
Tratablidade: Complexidade de algoritmos; algoritmos ótimos; técnica de algoritmos Divisão e Conquista, Guloso e Programação Dinâmica; Complexidade Computacional e Classe de Problemas P, NP, Co-NP; SAT e variações; Reduções de NP-completude; Reduções polinomiais; Algoritmos Randomizados; Algoritmos Aproximativos
Bibliografia:
Dasgupta, S., Papadimitriou, C. H., Vazirani, U. Algorithms. Science Engineering & Math, 2007
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduciton to Algorithms. The MIT Press. 2009
Figueiredo, C. M. H., Fonseca, G., Lemos, M., de Sá, V. G., Introdução aos Algoritmos Randomizados, Impa, 2007
Garey, M. R., Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979
Szwarcfiter, J. L., Markenzon, L. Estruturas de Dados e Seus Algoritmos, LTC Editora; Edição: 3, 2010
Szwarcfiter, J. L. Teoria Computacional de Grafos, Elsevier; Edição: 1, 2018
Playlist:
Slides:
- Aula 0 - Apresentação do curso
- Aula 1 - Eficiência Computacional
- Aula 2 - Eficiência Computacional (parte II)
- Aula 3 - Algoritmos de Busca
- Aula 4 - Relação de Recorrência
- Aula 5 - Resolução de Relação de Recorrência
- Aula 6 - O Teorema Mestre
- Aula 7 - Divisão e Conquista
- Aula 8 - Algoritmos Gulosos
- Aula 9 - Algoritmo de Huffman
- Aula 10 - Programação Dinâmica
- Aula 11 - Distância de Edição
- Aula 12 - Tratabilidade
- Aula 13 - Tratabilidade (parte II)
- Aula 14 - Reduções Polinomiais
- Aula 15 - Circuit SAT
- Aula 16 - 3-coloração
- Aula 17 - Reduções Polinomiais (parte II)
- Aula 18 - Algoritmos Randomizados (Algoritmos de Monte Carlo)
- Aula 19 - Algoritmos Randomizados (Algoritmos de Las Vegas)
- Aula 20 - Algoritmos Aproximativos
Atividades:
- Lista 1
- Lista 2
- Lista 3
- Lista 4
- Lista 5
- Lista de problemas NP-completos
- Revisão de Técnicas de Demonstrações, Indução e Relação de Recorrência
Se você tem alguma dúvida ou sugestão, sinta-se à vontade em me mandar uma mensagem. email.