Teoria computacional

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