Análise e Projeto de Algoritmos (2018)
Horário: Terças e Quintas das 11:00 às 13:00
Sala 319
Programa do Curso
- Problemas e Algoritmos. Complexidade de Algoritmos. Algoritmos ótimos. Limites Inferiores de Problemas: Máximos e Mínimos de Listas.
- Recursividade e Recorrências. Busca Binária. Torre de Hanói. Método da Divisão-e-Conquista: Min-Max e outros exemplos.
- Algoritmos de Ordenação: Selection Sort, Bubblesort, Mergesort, Quicksort. Limite inferior para Ordenação.
- Método Guloso e Aplicações: Árvore Geradora Mínima, Escalonamento, Códigos de Huffman.
- Programação Dinâmica - Problema da Mochila, Sequência Ótima de Multiplicação de Matrizes, Distância Mínima de Edição, Caixeiro Viajante.
- Backtracking - Algoritmo Geral e Aplicações: Permutações, Problema das Damas, Coloração de Vértices, Passeio de Cavalo.
- Problemas de Decisão e Otimização. As Classes P e NP.
- Problemas NP-Completos Clássicos. Provas de NP- Completude.
- Algoritmos Aproximativos. Algoritmos Randomizados.
Bibliografia
Listas:
- Lista 0 Entrega: (02/10/2018)
- Lista 0.b Entrega: (02/10/2018)
- Lista 1 Entrega: (02/10/2018)
- Lista 2 (Exercícios 15, 18, 20, 21)
Material Complementar:
-
Graph algorithms
- (Slides) J.A.Bondy and U.S.R.Murty, Graph Theory with Applications, North-Holland, 1976
- http://book.huihoo.com/pdf/graph-theory-With-applications/pdf/GTWA.pdf
- http://www.math.ualberta.ca/~nastos/m322/GTWA.pdf
- http://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf
(This book is out of print. Students are asked to download their personal copy from the web pages:)
Datas:
- Prova 1 - 02/10/2018