Teoria da Computação

Período letivo 2024.2 (2024.1 no SIGA):

• Campus Juazeiro
• Terças, das 16:00 às 18:00 hs, sala TBD
• Quintas, das 16:00 às 18:00 hs, sala TBD
• 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
  • Site
• Outra opção de calculadora lambda
  • 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:

• Artigos:
  • Goto (Wikipedia)
  • Go To Statement Considered Harmful (Dijkstra, 1968, CACM)
  • "Go To Considered Harmful" Considered Harmful (Rubin, 1987, CACM)
  • Flow Diagrams, Turing Machines and Languages with only Two Formation Rules (Böhm & Jacopini, 1966, CACM)
  • Böhm and Jacopini's Reduction of Flow Charts (Cooper, 1967)
  • The translation of 'goto' programas to 'while' programs (Ashcroft & Manna, 1971)
  • Structured Programming (Wikipedia)
  • Structured Programming (Dahl & Dijkstra & Hoare, 1972)
  • Structured Programming with goto Statements (Knuth, 1974, Computing Surveys)
  • Structured Programming Theorem (Wikipedia)
  • Program development by stepwise refinement(Wirth, 1971)
  • On the composition of well-structured programs (Wirth, 1974)
  • On Folk Theorems (Harel, 1980)
• Aulas gravadas
• 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 final

Aulas ministradas: