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.