Análise e Projeto de Algoritmos I - Turma 01 - 2022s2
Informações:
- Prof: Pedro H. D. B. Hokama - IMC
- Aulas: Segundas e Quartas-Feiras das 13:30 até 15:20 na sala B.4.2.12
- Atendimento: segunda após a aula.
Noticias:
- 13/12 - Enunciado do Trabalho 04 no run.codes.
- 06/12 - Enunciado do Trabalho 03.
- 29/10 - Enunciado do Trabalho 02.
- 16/10 - Trabalho 01 no run.codes.
- 22/08 - Página da disciplina no Ar
Aulas:
- 12/12 - Análise do Algoritmo de Kruskal, Union-Find, Compressão de Caminhos (cont).
- 07/12 - Problema da Árvore Geradora Mínima. Algoritmo de Kruskal. Slides
- 30/11 - Problema da Árvore Geradora Mínima. Algoritmo de Prim. Slides
- 21/11 - Código de Huffman. Slides
- 16/11 - Algoritmos Gulosos, Problema do Escalonamento Ponderado. Slides
- 09/11 - Caminhos mais curtos de Única Fonte - Algoritmo de Dijkstra Slides
- 07/11 - Componentes Fortemente Conexas usando DFS - Algoritmo de Kosaraju. Slides
- 31/10 - Trabalho 02
- 26/10 - Busca em Profundidade (DFS) Slides
- 24/10 - Trabalho 01
- 19/10 - Busca em Largura (BFS) Slides
- 17/10 - Análise do Algoritmo de Karger Slides
- 10/10 - Problema do Corte Mínimo, Algoritmo de Karger Slides
- 05/10 - Problema da Seleção, Algoritmo Aleatorizado e Um limitante inferior para algoritmos de ordenação baseados em comparações. Slides
- 03/10 - QuickSort Análise da Esperança da Tempo de Execução Slides
- 28/09 - QuickSort Análise da Corretude Slides
- 26/09 - Teorema Mestre Slides
- 21/09 - SEPROG II
- 19/09 - SEPROG II
- 14/09 - Cont. Princípios da Análise de Algoritmos. Notação Omega e Theta Slides
- 12/09 - Divisão e Conquista: Problema de Multiplicação de Matrizes, Algoritmo de Strassen Slides
- 05/09 - Divisão e Conquista: O paradigma, Problema de Comparação de Listas, Problema de Contagem de Inversões Slides
- 31/08 - Princípios da Análise de Algoritmos. Notação Big-Oh Slides
- 29/08 - Divisão e conquista: MergeSort. Slides
- 24/08 - Introdução e Karatsuba. Slides
Conteúdo:
Análise de algoritmos, Análise Assintótica, Fórmulas de Recorrência, Divisão e Conquista, Algoritmos Gulosos, Aleatorização, Programação dinâmica e tópicos especiais.
Critérios de Avaliação:
- Pt média da prova do bimestre t de 0 a 10.
- Tt média do bimestre t das notas nos trabálhos práticos
- Nota do bimestre t, Nt = Tt x Pt / 10
- Comprometimento: Se em todas as aulas a presença de alunos superar 50%, Pt = 10 para todos.
- Bônus: até 1 ponto pode ser somado em Nt por participações excepcionais.
- Média parcial M = (N1 + N2) / 2
- Se frequência menor que 75% o aluno reprovou-se.
- Senão se, M maior ou igual a 6, o aluno aprovou-se.
- Senão se, M menor que 6, o aluno faz uma Sub que substitui a menor entre N1 e N2.
- Em caso de plágio, fraude, tentativa de burlar os sistemas, nota zero será aplicado na disciplina a todos os envolvidos e estarão automaticamente reprovado.
Referências bibliográficas:
- ROUGHGARDEN, Tim. Algorithms Illuminated: book series.
- CORMEN, Thomas H et al. Algoritmos: teoria e prática. 3a ed. Rio de Janeiro: Campus, 2012. 926 p. ISBN 978-85-352-3699-6.
- DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algoritmos. São Paulo: McGraw Hill, 2009. 320 p. ISBN 978-85-7726-032-4.
Material de Apoio:
- Lintzmayer, Carla N.; Mota, Guilherme O.; Análise de Algoritmos e Estruturas de Dados (em elaboração) link.
- Curso Algorithms 1 de Tim Roughgarden (Stanford)
- Curso Algorithms 2 de Tim Roughgarden (Stanford)