Teoria da Computação
Período letivo 2017.1:
Aulas de reposição:
- 28/07 (sala 24), 04/08 (sala 14), 18/08 (sala 14), 25/08 (sala 14) e 01/09 (sala 14)
- Sextas-feiras, das 14:00 às 16:00 hs
- Campus Juazeiro
Calendário de final de período:
- 05/10 - Prova 3
- 17/10 - Prova final
Simuladores:
- Máquina Norma
- Máquina de Post
- 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:
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:
- Último Teorema de Fermat:
- 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:
Aulas ministradas:
Aula 01 - 20/06 - Apresentação e motivação.
Aula 02 - 22/06 - Programas e máquinas.
Aula 03 - 27/06 - Computação. Função Computada. Equivalência forte de programas.
Aula 04 - 29/06 - Equivalência forte de programas e a relação entre as várias classes de programas. Equivalência de programas. Equivalência de máquinas. Máquina de Traços.
Aula 05 - 04/07 - Equivalência de programas em Máquinas de Traços. Instruções rotuladas compostas. União disjunta de conjuntos.
Aula 06 - 06/07 - Cadeias de conjuntos. Simplificação de ciclos infinitos. Rótulos consistentes. Rótulos fortemente equivalentes. Algoritmo de verificação, exemplo e exercício. Visão geral sobre Máquinas Universais.
Aula 07 - 25/07 - Hipótese de Turing-Church. Teorema Fundamental da Aritmética. Máquina Norma como Máquina Universal.
Aula 08 - 27/07 - Máquina Norma como Máquina Universal. Máquina de Turing.
Aula 09 - 28/07 - Exemplos de Máquinas de Turing. MN <-> MT.
Aula 10 - 01/08 - Prova 1.
Aula 11 - 03/08 - Máquina de Post. MP <-> MT. Máquina com Pilhas.
Aula 12 - 04/08 - Autômato com Duas Pilhas. ADP <-> MT. MT com várias trilhas. MT não-determinística.
Aula 13 - 08/08 - MT com múltiplas fitas de entrada. MT com fita limitada à esquerda.
Aula 14 - 15/08 - Problemas decidíveis e indecidíveis. Exemplos.
Aula 15 - 17/08 - Codificação de MTs. Método Diagonal de Cantor. Linguagem Ld. Complemento de linguagens.
Aula 16 - 18/08 - Máquina de Turing Universal. Linguagem Lu. Redutibilidade e aplicações.
Aula 17 - 22/08 - Problema da parada. Le e Lne. Teorema de Rice. ALL.
Aula 18 - 24/08 - Configurações de um ALL. Problema indecidíveis. Histórias de computação. PCP.
Aula 19 - 25/08 - Redução Lu -> MPCP e redução MPCP -> PCP.
Aula 20 - 29/08 - Prova 2.
Aula 21 - 31/08 - Problemas indecidíveis relacionados com GLCs e LLCs. Introdução à Complexidade.
Aula 22 - 01/09 - Big-O: definição, exemplos e propriedades. Medição do tempo de execução.
Aula 23 - 05/09 - A classe P. A classe NP.
Aula 24 - 12/09 - Redutibilidade. NP completude.
Aula 25 - 14/09 - Exemplos e estratégias. Introdução ao Cálculo Lambda.
Aula 26 - 19/09 - Linguagem lambda. Substituições. Exercícios.
Aula 27 - 21/09 - Conversão alfa. Redução beta. Exercícios. Teorema de Church-Rosser.
Aula 28 - 26/09 - Exercícios. Numerais de Church. Exercícios.
Aula 29 - 28/09 - Booleanos de Church. Teorema do Ponto Fixo. Definições recursivas.
Aula 30 - 05/10 - Prova 3.