Análise e Síntese de Algoritmos (2018)

Horário: Sexta-feira das 09:00 às 13:00

Sala 317

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: (06/04/2018)
• Lista 0.b
Entrega: (13/04/2018)
• Lista 1
Entrega: (27/04/2018)
• Lista 2 (Exercícios 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21)
Entrega: (11/05/2018)
• Lista 3
Entrega: (15/06/2018)

Material Complementar:

Graph algorithms
• (Slides)
J.A.Bondy and U.S.R.Murty, Graph Theory with Applications, North-Holland, 1976
(This book is out of print. Students are asked to download their personal copy from the web pages:)
• 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

Notas:

Provas
• Prova 1
• Prova 2
• Prova 3 e Média Final