Análise e Síntese de Algoritmos - 2016

MINTER – IFMT e UFF

Prof. Fábio Protti
 


Programa do Curso

 

PRIMEIRA PARTE

04/04- Problemas e Algoritmos. Complexidade de Algoritmos. Algoritmos Ótimos. Limites Inferiores de Problemas: Máximos e Mínimos de Listas.

05/04- Recursividade e Recorrências. Busca Binária. Torre de Hanói. Método da Divisão-e-Conquista: Min-Max e outros exemplos.

06/04- Algoritmos de Ordenação: Selection Sort, Bubblesort, Mergesort, Quicksort. Limite inferior para Ordenação.

07/04- Método Guloso e Aplicações: Árvore Geradora Mínima, Escalonamento, Códigos de Huffman.

08/04- Programação Dinâmica - Problema da Mochila, Sequência Ótima de Multiplicação de Matrizes, Distância Mínima de Edição, Caixeiro Viajante.

 

SEGUNDA PARTE

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.

Resolução de exercícios sobre toda a matéria dada.

 

 

Lista de exercícios  (entregar por e-mail até o dia 27 de junho de 2016)

Pode ser feita em dupla com um colega.

Bibliografia – atenção: recomendo ler o Capítulo 7 da referência número 2 na seção “Língua Portuguesa”

Slides da palestra

Slides de algoritmos em grafos