Teoria da Computação

Período letivo 2020.3:

• Campus Juazeiro
• Terças, das 16:00 às 18:00 hs (sala virtual do Google Meet)
• Quintas, das 16:00 às 18:00 hs (sala virtual do Google Meet)
• Informações gerais
• Programa da disciplina

Simuladores:

• Máquina Norma
  • Sem créditos e sem documentação (UFRGS?)
  • Download
  • Descrição da sintaxe utilizada para escrever programas para o simulador
• Máquina de Post
  • Desenvolvido por Tiarajú Asmuz Divério e Luís Francisco Ramos Lima (UFRGS)
  • Download
  • http://www.inf.ufrgs.br/~hgmc (parece que está fora do ar)
• Máquina de Turing - JFLAP
  • Simulador gráfico e interativo para experimentação com gramáticas, expressões regulares e autômatos:
  • Download (renomeie para "JFLAP.jar" caso o seu S.O. modifique o nome para "JFLAP.zip")
  • Site
• Máquina de Turing - Implementação "real"
  • Dispositivo eletromecânico que reproduz o comportamento da Máquina de Turing;
  • Site
• Calculadora lambda do Prof. Dr. Carl Burch do Hendrix College
  • Efetua reduções e obtém forma normal.
  • Site

Máquinas de Turing (salvar como .jff e depois abrir no JFLAP):

• \{ww^R | w \in {a,b}^*\} determinística, baixar
• \{ww | w \in {a,b}^*\} não-determinística, baixar
• \{a^ib^jc^k | i=j ou j=k\} não-determinística, baixar
• \{a^ib^j | i>=1, j>=i e j par\} determinística, baixar
• \{a^ib^j | i>1, j>=i e j par\} determinística, baixar
• \{mwn | |w|_a=|w|_b=|w|_c\} determinística, baixar

Slides:

• Programas, máquinas e equivalências
• Máquinas universais
• Decidibilidade
• Complexidade
• Cálculo lambda

Material complementar:

• Artigo "A Teoria da Computação e o Profissional de Informática", João José Neto, RECET, Outubro de 2009
• Livro "Foundations of Computer Science" de A.V. Aho e J.D. Ullman, disponível para download gratuito na página dos autores
  • Capítulo 3 - The Running Time of Programs
• P versus NP:
  • Clay Mathematics Institute (problemas do milênio)
  • P versus NP problem (Wikipedia)
  • "The Status of the P Versus NP Problem" (artigo), Lance Fortnow, CACM, Setembro de 2009
  • Deolalikar P vs NP paper (Wikipedia)
  • Gödel´s Lost Letter and P=NP (blog sobre teoria da computação de R. J. Lipton)
• Último Teorema de Fermat:
  • Wikipedia (inglês)
  • Wikipedia (português)
  • Edição em português do livro de Simon Singh
  • Fermat´s Last Theorem, documentário de Simon Singh para a BBC (1996, 48m59s).
• Equivalência de Máquinas Universais: Demonstração, Análise e Simulação, trabalho de Conclusão de Curso de Débora Pandolfi Alves, com orientação da Profa. Dra. Ana Paula Lüdtke Ferreira (UNISINOS, 2007).
• Documentário Dangerous Knowledge, de David Malone para a BBC, sobre as vidas e obras de Cantor, Boltzmann, Gödel e Turing.

Avaliações:

• Prova 1 (resolução)
• Prova 2 (resolução)
• Prova 3 (resolução)

Aulas ministradas: