Análise e Projeto de Algoritmos I - Turma 01 - 2021s2
Informações:
- Prof: Pedro H. D. B. Hokama - IMC
- Aulas: Terças das 13:30 até 15:20 e Quintas das 15:45 até 17:35
- Link das aulas: https://meet.google.com/dqg-mvdz-kig (obrigatório o uso de uma conta @unifei.edu.br)
- Atendimento: quinta após a aula.
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.
Noticias:
- 21/12 - Divulgado as notas finais. Parabéns! Para quem precisar: vistas dia 22/12 as 18hs no link da aula.
- 09/12 - Divulgado o enunciado do Trabalho 06 no run.codes.
- 02/12 - Divulgado o enunciado do Trabalho 05 no run.codes.
- 15/11 - Divulgado o enunciado do Trabalho 04 no run.codes.
- 24/10 - Divulgado o enunciado do Trabalho 03 no run.codes.
- 10/10 - Divulgado o enunciado do Trabalho 02 no run.codes.
- 05/10 - Divulgado o enunciado do Trabalho 01 no run.codes.
- 11/08 - Página da disciplina no Ar
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.
Aulas:
- 09/12 - Complexidade do Algoritmo de Kruskal (com balanceamento da árvore, union-find e compressão de caminhos). Slides (cont. aula 20) - Video (necessário uma conta @unifei.edu.br)
- 07/12 - Complexidade do Algoritmo de Prim. Algoritmo de Kruskal. Slides - Video (necessário uma conta @unifei.edu.br)
- 02/12 - Trabalho 05
- 30/11 - Árvore Geradora de Custo Mínimo (AGM) e Algoritmo de Prim. Slides - Video (necessário uma conta @unifei.edu.br)
- 25/11 - Código de Huffman. Slides - Video (necessário uma conta @unifei.edu.br)
- 23/11 - Revisão Grafos
- 18/11 - Algoritmos Gulosos e Problema do Escalonamento Ponderado. Slides - Video (necessário uma conta @unifei.edu.br)
- 16/11 - Representação de Grafos. Video (necessário uma conta @unifei.edu.br)
- 11/11 - Algoritmo de Dijkstra. Slides - Video (necessário uma conta @unifei.edu.br)
- 09/11 - Componentes Fortemente Conexas, Algoritmo de Kosaraju. Slides - Video (necessário uma conta @unifei.edu.br)
- 04/11 - I Semana de Programação Unifei - Sem aula
- 28/10 - Componentes Conexas usando BFS, Busca em Profundidade (DFS) e Ordenação topológica usando DFS. Slides - Video (necessário uma conta @unifei.edu.br)
- 26/10 - Busca em Largura (BFS). Slides - Video (necessário uma conta @unifei.edu.br)
- 21/10 - Análise do Algoritmo de Karger para Cortes Mínimos. Slides - Video (necessário uma conta @unifei.edu.br)
- 19/10 - Grafos e o Problema do Corte Mínimo. Slides - Video (necessário uma conta @unifei.edu.br)
- 14/10 - Plantão Trabalhos 01 e 02
- 07/10 - Problema da Seleção e Limitante Inferior para Ordenação. Slides - Video (necessário uma conta @unifei.edu.br)
- 05/10 - QuickSort - Complexidade. Slides - Video (necessário uma conta @unifei.edu.br)
- 30/09 - QuickSort - Corretude. Slides - Video (necessário uma conta @unifei.edu.br)
- 28/09 - Teorema Mestre. Slides - Video (necessário uma conta @unifei.edu.br)
- 23/09 - Divisão e Conquista - Multiplicação de Matrizes - Algoritmo de Strassen. Slides - Video (necessário uma conta @unifei.edu.br)
- 16/09 - Divisão e Conquista - Contagem de Inversões. Slides - Video (necessário uma conta @unifei.edu.br)
- 14/09 - Análise Assintótica. Slides - Texto - Video (necessário uma conta @unifei.edu.br)
Exercícios do CLRS: 3.1-1, 3.1-2, 3.1-3, 3.1-4, 3.1-6, 3.1-7, 3.1-8, 3.2-3; Problemas 3-1, 3-2, 3-3, 3-4; - 09/09 - Introdução Análise Assintótica. Slides - Video (necessário uma conta @unifei.edu.br)
- 02/09 - MergeSort - Árvore de Recursão. Slides - Video (necessário uma conta @unifei.edu.br)
- 31/08 - Introdução e Karatsuba. Slides - Video (necessário uma conta @unifei.edu.br)
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.
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)