Cronograma de Complexidade

Março

• 27 de fevereiro (Aula 0):
  • Apresentação
• 1 de março (Aula 1):
  • Introdução (parte do cap 1 do Papadimitriou)
  • Problemas de decisão x problemas de otimização
  • Algoritmos eficientes x práticos x polinomiais
• 6 de março (Aula 2):
  • Introdução (continuação do cap 1): reduções entre problemas e a questão "P = NP?"
  • Máquinas de Turing: definição e um exemplo (começo do cap 2)

  Exercício [entrega na aula de 15/3]: Suponha que máquinas de Turing possam remover e inserir símbolos da fita em vez de simplesmente trocar.
  a). Defina cuidadosamente a função de transição e a computação de tais máquinas.
  b). Mostre que tais máquinas podem ser simuladas por uma máquina de Turing com perda quadrática de eficiência (isto é, f(n) passos viram O(f(n)²) passos).

• 8 de março:
  • Não haverá aula.
• 13 de março (Aula 3):
  • Mais alguns exemplos: sucessor binário e palíndromes.
  • Linguagens e máquinas de Turing: linguagens recursivas e recursivamente enumeráveis.
  • Representação de objetos como strings. Problemas como linguagens.
• 15 de março (Aula 4):
  • Máquinas de Turings com k fitas.
  • A classe TIME(f(n)).
• 20 de março (Aula 5):
  • Dada uma máquina de Turing M com k fitas que opera em tempo f(n), existe uma máquina de Turing M' que opera em tempo O(f(n)²) tal que M(x)=M'(x) para toda entrada x (teorema 2.1).
• 22 de março (Aula 6):
  • Aceleração linear (sec 2.4)
  • A classe P
  • Uma outra MT que decide PALINDROME.
• 27 e 29 de março:
  • Semana santa.