Análise e Síntese de Algoritmos – 2023/1
IC/UFF
Programa do Curso
PRIMEIRA
PARTE
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.
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.
Avaliação
Duas provas + exercícios