Teoria da Computação

Notas e faltas: disponíveis no SIGA.

Período letivo 2012.1:

• Campus Juazeiro, sala 13
• Terças, das 14:00 às 16:00 hs
• Quintas, das 14:00 às 16:00 hs
• Programa da disciplina
• PUD

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
• 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).

Avaliações:

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

Aulas ministradas:

2012-03-06 Apresentação da disciplina.

2012-03-08 Programas, máquinas e computação de programa monolítico.

2012-03-13 Computações, funções computadas e equivalência de programas e máquinas.

2012-03-15 Máquinas de Traços. Equivalência de programas em Máquinas de Traços. Instruções rotuladas compostas.

2012-03-20 Simplificação de ciclos infinitos. Verificação da equivalência forte de programas monolíticos. Máquinas Universais. Teorema Fundamental da Aritmética.

2012-03-22 Codificação de dados estruturados. Algoritmos. Hipótese de Church. Máquina Norma. Máquina de Turing.

2012-03-27 Máquina de Turing. Exemplos. Norma >= Turing.

2012-03-29 Norma >= Turing. Turing >= Norma. Máquina de Post.

2012-04-03 Turing <= Post. Post <= Turing. Máquina com Pilhas. Autômato com Duas Pilhas. Duas Pilhas <= Turing. Turing <= Duas Pilhas.

2012-04-10 Máquinas de Turing com múltiplas trilhas. Máquinas de Turing não-determinísticas.

2012-04-12 Máquinas de Turing com múltiplas fitas de entrada. Máquinas de Turing com fita limitada à esquerda.

2012-04-17 Decidibilidade. Problemas decidíveis.

2012-04-19 Linguagem Ld. Codificação de Máquinas de Turing. Propriedades das linguagens recursivas e RE.

2012-04-24 Máquina de Turing Universal. Linguagem Lu. Redutibilidade. Problema da Parada.

2012-05-03 Linguagens Le e Lne, Teorema de Rice e Autômatos Linearmente Limitados.

2012-05-08 Prova 1.

2012-05-10 Histórias de computação. Reduções com histórias de computação. PCP e MPCP. MPCP => PCP.

2012-05-15 Lu => MPCP. AMB(GLC).

2012-05-17 Problemas indecidíveis relacionados com LLCs e GLCs. Tempo de execução.

2012-05-22 Tempo de execução. Classes P e NP. Exemplos.

2012-05-24 Verificadores. Redutibilidade em tempo polinomial. SAT, 3SAT e CLIQUE.

2012-05-29 NP-completude. Problemas NP-hard. Exemplos.

2012-05-31 Exemplos de problemas NP-completos. Estratégias para problemas NP-completos. Leitura e discussão do artigo de Lance Fortnow, "The Status of the P Versus NP Problem".

2012-06-05 Linguagem lambda. Substituições.

2012-06-12 Substituições. Conversões alpha e reduções beta.

2012-06-14 Numerais de Church. Igualdade beta.

2012-06-19 Booleanos de Church. Ponto fixo e recursão.

2012-06-21 Teorema da Indecidibilidade de Scott-Curry.

2012-06-26 Revisão.

2012-06-28 Prova 2.

2012-07-03 Segunda chamada.

2012-07-10 Prova final.