Análise e Síntese de Algoritmos – 2025/2

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.

Avaliação

Três avaliações escritas: 24/9, 29/10 e 26/11.