Projeto e Análise de Algoritmos
Grupo de e-mail
Grupo de e-mail
Inscreva-se: https://groups.google.com/forum/#!forum/paa-ufal.
Nos comunicaremos por esse canal.
Github
Github
https://github.com/r0drigopaes/paa
Google Classroom
Google Classroom
- 2017.2: código: qhtc92d
Avaliação
Avaliação
Serão 2 notas: AB1 e AB2.
Cada AB será composta por: 0.35 * prova teórica + 0.35 * prova prática + 0.15 * exercícios do huxley + 0.15 exercícios no google classroom
Planejamento das aulas
Planejamento das aulas
2018.2: https://docs.google.com/spreadsheets/d/1N12ZgEA3KpT1pjV2k19BLEN_TowQ-w7xpj5sjyjTwlI/edit?usp=sharing
Slides
Slides
AB1
- Introdução.
- Eficiência
- Dividir e conquistar
- Quicksort
- Segment tree
- Comparação como modelo computacional
- Counting Sort
- Exercícios de dividir e conquistar
- Recorrências
- Teorema Mestre
- Grafos parte 1
- Método Guloso
- Dijkstra
- Minimum Spanning Tree
AB2
- Programação Dinâmica (vídeo-aulas no youtube)
- Grafos parte 2
- Ordenação topológica
- Vídeo Aulas
- Parte 1: https://youtu.be/8JIR4ITnD_Y
- Parte 2: https://youtu.be/hI3TUGexJQo
- Slides
- Vídeo Aulas
- Pontos de articulação e pontes
- Single pair shortest path - Bellman Ford (arestas negativas)
- All pair shortest path - Floyd-Warshall
- Fluxo Máximo (Ford-Fulkerson)
- Ordenação topológica
- Problemas NP-Completos e Reduções
- CIRCUIT-SAT e outros
- Algoritmo de aproximação para o TSP
Referências
- Livro
- Curso de PAA do MIT
- Curso de PAA da pós-graduação da PUC-Rio
- Problemas NP completos
- Teoria: https://www.youtube.com/watch?v=moPtwq_cVH8
- Resumo da teoria: https://www.youtube.com/watch?v=YX40hbAHx3s
- Exemplos de problemas: https://www.youtube.com/watch?v=eHZifpgyH_4