Material das Aulas

Onde encontrar

O material da disciplina pode ser encontrado no Moodle ou no reposiótio GitHub.

Conteúdo

• Aula 00
  • Apresentação do Curso
• Aula 01
  • Análise de Algoritmos
  • Crescimento de Funções
  • Notações Assintóticas
• Aula 02
  • Cálculo do Tempo de Execução
  • Comparando Algoritmos
  • Classes de Comportamento Assintótico
• Aula 03
  • Análise de Algoritmos Recursivos
  • Recorrências
• Aula 04
  • O Teorema Mestre
  • Notação Assintótica em Funções
• Aula 05
  • Indução Matemática
  • Indução Matemática e Algoritmos
• Aula 06
  • Listas
    • Descrição
    • Formas de Implementação
    • Operações e Complexidade
    • Exemplos
• Aula 07
  • Pilhas
    • Descrição
    • Formas de Implementação
    • Operações e Complexidade
    • Exemplos
  • Filas
    • Descrição
    • Formas de Implementação
    • Operações e Complexidade
    • Exemplos
• Aula 08
  • Filas de Prioridades 
    • Descrição
    • Formas de Implementação
    • Operações e Complexidade
    • Exemplos
• Aula 09
  • Conjuntos
    • Descrição
    • Formas de Implementação
    • Operações e Complexidade
    • Exemplos
• Aula 10
  • Mapas
    • Descrição
    • Formas de Implementação
    • Operações e Complexidade
    • Exemplos
• Aula 11
  • Introdução a genéricos em C++
  • Standard Templates Library: Contêineres, Iteradores e algoritmos
• Aula 12
  • Introdução a genéricos em Java
  • Java Collections Framework: Contêineres, Iteradores e algoritmos
• Aula 13
  • Problema Computacional
  • Problemas Combinatórios
  • Paradigmas de Projeto de Algoritmos
  • Busca Completa
  • Busca Aleatória
• Aula 14
  • Algoritmos Recursivos
• Aula 15, Código 8 Rainhas
  • Backtracking
• Aula 16
  • Algoritmos Gulosos
• Aula 17
  • Divisão e Conquista
• Aula 18
  • Divisão e Conquista parte II
    • Impacto do Balanceamento
    • Busca Binária pela Solução
• Aula 19
  • Programação Dinâmica, códigos de exemplo
    • Top-Down vs. Bottom-Up
    • Exemplo de Projeto
• Aula 20
  • Programação Dinâmica parte II
    • Problema da Mochila 0-1
    • Longest Increasing Subsequence
    • Coin Change
    • Maximum Subarray Problem (Max 1d Range Sum)
    • Max 2d Range Sum
    • String Alignment
• Aula 21
  • Algoritmos Aproximados
    • Relação de aproximação
    • Esquema de aproximação
    • Problema de cobertura de conjuntos
    • Algoritmos aleatorizados
    • MAX-3SAT
• Aula 22
  • Teoria da Complexidade Computacional
  • Máquinas de Turing
  • Classe P
  • Classe NP
• Aula 23
  • Classe NP-Completo
  • Reduções entre Problemas
  • 3-SAT <= Clique
  • Clique <=Cobertura de Vértices
  • Ciclo Hamiltoniano <= Caixeiro Viajante
  • SAT <= 3SAT (adicional)
• Aula 24
  • Discussão P vs. NP
  • P =? NP Poll

Listas de Exercícios

• Lista de exercícios 01
• Lista de exercícios 02
• Lista de exercícios 03
• Lista de exercícios 04

Slides de Tópicos Abordados em Semestres Anteriores

• Problema do Caixeiro Viajante e Algoritmo de Christofides
• Busca em texto e Algoritmo Rabin-Karp
• Algoritmo Knuth-Morris-Pratt (KMP)