Teoria da Computação

Período letivo 2021.3 (2021.1 no SIGA):

• 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:

• Artigos:
  • Goto (Wikipedia)
  • Go To Statement Considered Harmful (Dijkstra, 1968, CACM)
  • Structured Programming (Wikipedia)
  • Structured Programming Theorem (Wikipedia)
  • Flow Diagrams, Turing Machines and Languages with only Two Formation Rules (Böhm & Jacopini, 1966, CACM)
  • Notes on Structured Programming (Dijkstra, 1968, TU Eindhoven)
  • Structured Programming with goto Statements (Knuth, 1974, Computing Surveys)
• 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 3 (resolução)

• ---

  Aulas ministradas:

  Aula 01 - 30/11/2021 - Apresentação e motivação.
  Aula 02 - 02/12/2021 - Programas monolíticos. Programas iterativos.
  Aula 03 - 07/12/2021 - Programas recursivos. Máquinas. Programa para uma máquina.
  Aula 04 - 09/12/2021 - Computação. Função computada.
  Aula 05 - 14/12/2021 - Equivalência forte de programas, equivalência de máquinas.
  Aula 06 - 16/12/2021 - Máquina de traços, instruções rotuladas compostas.
  Aula 07 - 21/12/2021 - Algoritmo de verificação da equivalência forte de programas. Exemplo e exercício.
  Aula 08 - 11/01/2022 - Máquinas Universais. Algoritmo. Hipótese de Church. Teorema Fundamental da Aritmética. Máquina Norma.
  Aula 09 - 13/01/2022 - Máquina Norma é Universal por evidências internas - parte 1.
  Aula 10 - 18/01/2022 - Máquina Norma é Universal por evidências internas - parte 2. Máquina de Turing.
  Aula 11 - 20/01/2022 - Máquina de Turing. Máquina Norma é Universal por evidências externas - parte 1.
  Aula 12 - 25/01/2022 - Máquina Norma é Universal por evidências externas - parte 1. Máquina de Post.
  Aula 13 - 27/01/2022 - Máquina de Post é Universal. Máquina com Pilhas.
  Aula 14 - 01/02/2022 - Revisão para Prova 1.
  Aula 15 - 03/02/2022 - Prova 1.
  Aula 16 - 08/02/2022 - Autômato com Duas Pilhas. Autômato com Duas Pilhas simula Máquina de Turing.
  Aula 17 - 10/02/2022 - Máquina de Turing simula Autômato com Duas Pilhas. Máquina de Turing.
  Aula 18 - 15/02/2022 - MT com múltiplas trilhas. MT não-determinística.
  Aula 19 - 17/02/2022 - MT não-determinística. Tempo de execução da MT determinística equivalente.
  Aula 20 - 03/03/2022 - MT com múltiplas fitas. MT que nunca escreve brancos na fita.
  Aula 21 - 08/03/2022 - MT com fita limitada à esquerda.
  Aula 22 - 10/03/2022 - Introdução à decidibilidade. Linguagens e problemas.
  Aula 23 - 15/03/2022 - Problemas decidíveis. Lingagem Ld. Complemento de linguagens.
  Aula 24 - 17/03/2022 - Máquina de Turing Universal. Linguagem Lu.
  Aula 25 - 22/03/2022 - Redutibilidade.
  Aula 26 - 24/03/2022 - Problema da Parada.
  Aula 27 - 29/03/2022 - Linguagens Le e Lne. Teorema de Rice - enunciado e aplicações.
  Aula 28 - 31/03/2022 - Teorema de Rice - prova. Autômato Linearmente Limitado.