Projeto e Análise de Algoritmos - Turma 01 - 2023s2

Informações:

• Docente: Prof. Dr. Pedro H. D. B. Hokama - IMC
• Aulas: Terças das 13:30 até 15:20 e Quintas das 10:10 até 12:00 na sala C1103.

Noticias:

1. 15/12 - Divulgado notas finais
2. 08/12 - Divulgado notas Trabalho 2 e notas finais parciais
3. 27/11 - Disponibilizado (por email) enunciado do trabalho 2, entrega até 03/12 valendo 2 pontos.
4. 04/11 - Atualizado Slides da disciplinas até 04/11.
5. 19/10 - Divulgado notas Trabalho 1 e notas Prova 1
6. 05/10 - Disponibilizado enunciado do trabalho 1, entrega até 13/10 valendo 2 pontos.
7. 07/08 - Página da disciplina no Ar

Aulas:

• Código do algoritmo Branch-and-Bound para o problema da mochila. Instâncias resolvidas.
• Branch-and-bound
• Limitantes
• Algoritmo (1 - epsilon) aproximado para o problema da mochila
• Algoritmo 1/2 aproximado para o problema da mochila
• Algoritmo Guloso
• Algoritmo Exato para o TSP
• Algoritmo Exato para o problema da Cobertura por Vertices
• Reduções
• Problemas NP-Completos
• Classes de Complexidade P, NP, NP-Difícil e NP-Completo
• Programação Dinâmica para o Problema da Mochila
• Programação Dinâmica para o Problema do Conjunto Independente de Peso Máximo em Grafo Caminho
• 28/09 - Compressão de Texto, Código de Huffman.
• 25/09 - Problema do Corte Mínimo.
• 21/09 - Limite inferior para o problema de Ordenação.
• 18/09 - O problema da Seleção.
• 14/09 - Aleatorização.
• 10/09 - QuickSort.
• 31/08 - O Teorema Mestre.
• 28/08 - Divisão e Conquista: O problema da multiplicação de matrizes.
• 24/08 - Divisão e Conquista: O problema da contagem de inversões.
• 21/08 - Notação Omega, Theta, o pequeno, omega pequeno.
• 17/08 - Análise Asintótica, Notação O.
• 14/08 - Exercício.
• 09/08 - Análise do MergeSort.
• 07/08 - Apresentação, Introdução e Algoritmo de Karatsuba.

Critérios de Avaliação:

• Np = 0.2 * Tp + 0.8 * Pp

Referências bibliográficas e Material de Apoio:

• CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. (2012) Algoritmos - Teoria e Pratica, 3ª edição, GEN LTC.
• ROUGHGARDEN, T. (2017) Algorithms Illuminated (Parte 1 a 4), Soundlikeyourself Publishing.