Projeto e Análise de Algoritmos - Turma 01 - 2023s2
Informações:
Noticias:
- 15/12 - Divulgado notas finais
- 08/12 - Divulgado notas Trabalho 2 e notas finais parciais
- 27/11 - Disponibilizado (por email) enunciado do trabalho 2, entrega até 03/12 valendo 2 pontos.
- 04/11 - Atualizado Slides da disciplinas até 04/11.
- 19/10 - Divulgado notas Trabalho 1 e notas Prova 1
- 05/10 - Disponibilizado enunciado do trabalho 1, entrega até 13/10 valendo 2 pontos.
- 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:
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.