PGCOMP/IC0004 - Algoritmos e Grafos

Material de estudos organizado pelo Prof. Marco Aurélio Thompson.

Aulas

  1. Algoritmos: Definição (s7)
  2. Problemas, Instâncias e Algoritmos (s8)
  3. Correção e Desempenho de Algoritmos (s9)
  4. O Problema da Parada: Conceito, Simulação e Prova por Contradição (s10-12)
  5. Leitura de Pseudocódigo
  6. Recursividade e Recursão
  7. Insertion Sort (Ordenação por Inserção) (s14)
  8. Invariante de Laço: Prova por Invariante e Correção do Insertion Sort (Ordenação por Inserção) (s15)
  9. Análise de Tempo: O Modelo RAM com Simulador do Tamanho da Entrada (s17)
  10. Revisão de Matemática: Funções
  11. Revisão de Matemática: Somatórios
  12. Análise de Complexidade: Cenários de Melhor Caso, Pior Caso e Caso Médio (s18)
  13. Análise do Insertion Sort (Ordenação por Inserção): Melhor Caso (s19)
  14. Análise do Insertion Sort (Ordenação por Inserção): Pior Caso (s20)
  15. Revisão de Matemática: Logaritmos
  16. Conversão entre Logaritmo, Potência e Raiz
  17. Notações Assintóticas: Definições Formais (s21)
  18. Visualização das Notações Assintóticas: Big O, Theta e Ômega (s22)
  19. Exercício 1: Álgebra Assintótica — Significado das Relações (s25)
  20. Exercício 1: Álgebra Assintótica — Somas Assintóticas (s25)
  21. Exercício 2: Demonstrações e Propriedades (s26)
  22. Bubble Sort (Ordenação da Bolha): Conceito e Pseudocódigo (s28)
  23. Bubble Sort (Ordenação da Bolha): Invariante e Correção (s28)
  24. Bubble Sort (Ordenação da Bolha): Complexidade (s28)
  25. Bubble Sort (Ordenação da Bolha): Otimização (s28)
  26. Selection Sort (Ordenação por Seleção): Conceito e Pseudocódigo (s29)
  27. Selection Sort (Ordenação por Seleção): Correção e Complexidade
  28. Revisão de Matemática: Matrizes
  29. Laços Aninhados
  30. Exercício: Complexidade de Matrizes e Laços Aninhados (s30)
  31. Análise do Laço Interno (while) (s31)
  32. Recursão, Recorrência e Relação entre Recursão e Recorrência
  33. Fórmulas de Recorrência (s35)
  34. Formulação: O Custo Passo a Passo (s36)
  35. Busca Binária
  36. Extraindo a Recorrência de Algoritmos: Busca Binária Iterativa (s38)
  37. Extraindo a Recorrência de Algoritmos: Busca Binária Recursiva (s39)
  38. Merge Sort (Ordenação por Intercalação)
  39. Merge Sort (Ordenação por Intercalação): Recorrência (s40)
  40. Merge Sort (Ordenação por Intercalação): Algoritmo 4 — Intercala (s41)
  41. Métodos de Solução de Recorrências (s43)
  42. Teorema Mestre (s55-59)
  43. Teorema Mestre: Limitações (s60)
  44. Método da Substituição (s44-49)
  45. Método da Árvore de Recursão (s50-54)
  46. Análise: A Função F(n) (s62)
  47. Remoção de Histórico (s64-66)
  48. Exercícios de Recorrência (s68)
  49. Divisão e Conquista (s71)
  50. Divisão e Conquista: Exemplo com Busca Binária (s72)
  51. Divisão e Conquista: Exemplo com Merge Sort (Ordenação por Intercalação) (s72)
  52. Outros Problemas Clássicos (s73)
  53. Potência Inteira de um Número (s75-77)
  54. Sequência de Fibonacci
  55. N-ésimo Termo da Sequência de Fibonacci: Solução Ingênua (s79-83)
  56. Torres de Hanói (s85-88)
  57. Multiplicação Tradicional de Matrizes (s90-92)
  58. Multiplicação de Matrizes: Algoritmo de Strassen (s93-95)
  59. Encontrar o k-ésimo Elemento numa Sequência (s97-99)
  60. A Rotina de Particionamento (Hoare) (s100)
  61. Algoritmo: Seleção do k-ésimo Menor (s101-105)
  62. Quick Sort (Ordenação Rápida) (s107-114)
  63. Exercícios de Divisão e Conquista (s117-118)
  64. Divisão e Conquista vs. Programação Dinâmica (s122)
  65. Prova Resolvida: 2018.1
  66. Prova Resolvida: 2025.1
  67. Prova Resolvida: 2025.2
  68. Prova Resolvida: 2026.1
  69. Exercícios Resolvidos: Custo e Extração da Recorrência
  70. Exercícios Resolvidos: Invariante de Laço
  71. Exercícios Resolvidos: Teorema Mestre
  72. Exercícios Resolvidos: Método da Árvore de Recursão
  73. Exercícios Resolvidos: Método da Substituição
  74. Exercícios Resolvidos: Remoção de Histórico
  75. Exercícios Resolvidos: Divisão e Conquista
  76. Exercícios Resolvidos: Potência Inteira de um Número
  77. Exercícios Resolvidos: Sequência de Fibonacci
  78. Exercícios Resolvidos: Torres de Hanói
  79. Exercícios Resolvidos: Multiplicação de Matrizes com Strassen
  80. Exercícios Resolvidos: K-ésimo Menor Elemento
  81. Exercícios Resolvidos: Particionamento de Hoare
  82. Exercícios Resolvidos: Quick Sort (Ordenação Rápida)
  83. Provas Formais

Ferramentas de Apoio

  1. Título da ferramenta

Bibliografia Oficial

  1. Título do livro

Bibliografia de Apoio

  1. Título do livro

Material Antigo

  1. Título do material