Cronograma de Complexidade

Março

Abril

• 3 de abril (Aula 7):
  • Complexidade de espaço (sec 2.5).
  • A classe SPACE(f(n)).
  • Modelo RAM: definição (sec 1.2 do Aho, Hopcroft & Ullman).
  • Lista 1.
  Exercício: Demonstre os dois teoremas abaixo.
  Teorema: Se L está em SPACE(f(n)) então existe uma MT com 3 fitas e entrada e saída que decide L e opera em espaço f(n).
  Teorema: Se L está em SPACE(f(n)) então, para todo eps>0, L está em SPACE(c+eps.f(n)), para alguma constante c.
• 5 de abril (Aula 8):
  • Complexidade de tempo no Modelo RAM (sec 1.3 do AHU).
  • Equivalência entre o modelo RAM e MTs (sec 1.7 do AHU).
• 10 de abril (Aula 9):
  • Máquinas de Turing não-determinísticas.
• 12 de abril (Aula 10):
  • Mais sobre máquinas de Turing não-determinísticas.
• 17 de abril (Aula 9):
  • Computação quântica.
• 19 de abril
  • Primeira prova [ps] [pdf]
• 24 de abril (Aula 10)
  • Máquinas de Turing Universais
  • O problema da parada e a linguagem H
  • RE x R
• 26 de abril (Aula 11)
  • H não é recursiva e outros bichos.