Teoria da Computação
Período letivo 2013.1:
- Campus Juazeiro, sala 15
- Terças, das 16:00 às 18:00 hs
- Quintas, das 16:00 às 18:00 hs
- Programa da disciplina
- PUD
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:
- Prova 1 (resolução)
- Prova 2 (resolução)
- Prova final
Aulas ministradas:
Aula 01 - 2013-05-28 - Apresentação da disciplina. Motivação e objetivos.
Aula 02 - 2013-06-04 - Programa, máquina e programa para uma máquina.
Aula 03 - 2013-06-06 - Computação, função computada e equivalência forte de programas.
Aula 04 - 2013-06-11 - Classes de programas e classes de quivalência. Equivalência de programas numa máquina. Equivalência de máquinas. Máquina de Traços.
Aula 05 - 2013-06-13 - Máquina de Traços. Instruções rotuladas compostas. Verificação da equivalência forte de programas.
Aula 06 - 2013-06-18 - Agoritmo de verificação da equivalência forte de programas. Exercício.
Aula 07 - 2013-06-25 - Márquinas universais. Máquina Norma.
Afastamento para doutorado a partir do dia 1º de julho de 2013. As aulas terão continuidade com professor substituto contratado pela universidade.