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:

  1. 13/12 - Enunciado do Trabalho 04 no run.codes.
  2. 06/12 - Enunciado do Trabalho 03.
  3. 29/10 - Enunciado do Trabalho 02.
  4. 16/10 - Trabalho 01 no run.codes.
  5. 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:

Material de Apoio: