Prof. Marcus Ramos - Teoria da Computação

Teoria da Computação

Período letivo 2021.1 (2020.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)
A partir do dia 11/05 o novo endereço da nossa sala de aula virtual será https://meet.google.com/fqn-uzcr-znz
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:

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
- 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 - 02/03/2021 - Apresentação da disciplina (aula ao vivo)
Aula 02 - 04/03/2021 - Programas e máquinas (aula gravada e plantão de dúvidas)
Aula 03 - 09/03/2021 - Programa para máquina e computação (aula gravada e plantão de dúvidas)
Aula 04 - 11/03/2021 - Função computada e equivalência forte de programas (aula gravada e plantão de dúvidas)
Aula 05 - 16/03/2021 - Paradigmas de programação e equivalência forte (aula gravada e plantão de dúvidas)
Aula 06 - 18/03/2021 - Equivalências. Máquina de Traços. Instruções rotuladas compostas (aula ao vivo)
Aula 07 - 23/03/2021 - Verificação da equivalência forte de programas, exemplo e exercício (aula ao vivo)
Aula 08 - 25/03/2021 - Máquinas Universais, algoritmo, Hipótese de Church, Teorema Fundamental da Aritmética e codificação de dados estruturados. Máquina Norma (aula gravada e plantão de dúvidas)
Aula 09 - 30/03/2021 - Máquina Norma como Máquina Universal por meio de evidências internas (aula ao vivo)
Aula 10 - 06/04/2021 - Máquina de Turing (aula ao vivo)
Aula 11 - 08/07/2021 - Máquina de Turing. Linguagens (aula ao vivo)
Aula 12 - 13/04/2021 - Máquina Norma simula Máquina de Turing (aula ao vivo)
Aula 13 - 15/04/2021 - Máquina de Turing simula Máquina Norma. Máquina de Post (aula ao vivo)
Aula 14 - 20/04/2021 - Prova 1 (AVA, de 16/04 00:00h até 21/04 23:59h)
Aula 15 - 22/04/2021 - Máquina de Turing simula Máquina de Post e vice-versa. Máquina com Pilhas (aula ao vivo)
Aula 16 - 27/04/2021 - Autômato com Duas Pilhas. Equivalência do Autômato com Duas Pilhas com a Máquina de Turing (aula ao vivo)
Aula 17 - 29/04/2021 - Máquina de Turing com várias trilhas. Máquina de Turing não-determinística (e simulação em Máquina de Turing determinística) (aula ao vivo)
Aula 18 - 04/05/2021 - Tempo de execução da MT determinística que simula a MT não-determinística. MT com várias fitas de entrada (aula ao vivo)
Aula 19 - 06/05/2021 - MT que nunca escreve brancos. MT com fita limitada à esquerda (aula ao vivo)
Aula 20 - 11/05/2021 - Problemas decidíveis (aula ao vivo)
Aula 21 - 13/05/2021 - Problemas decidíveis e indecidíveis. Codificação de Máquinas de Turing. Linguagem L_d (aula ao vivo)
Aula 22 - 18/05/2021 - Complemento de linguagens. Máquina de Turing Universal. Linguagem Universal (aula ao vivo)
Aula 23 - 20/05/2021 - Redutibilidade. Problema da parada (aula ao vivo)
Aula 24 - 25/05/2021 - Linguagens Le e Lne. Teorema de Rice. Autômato Linearmente Limitado. Histórias de computação (aula ao vivo)
Aula 25 - 27/05/2021 - PCP e MPCP. Redução de MPCP para PCP (aula ao vivo)
Aula 26 - 01/06/2021 - Redução de Lu para MPCP aula ao vivo)
Aula 27 - 08/06/2021 - Problemas indecidíveis de gramáticas e linguagens livres de contexto (aula ao vivo)
Aula 28 - 10/06/2021 - Prova 2 (AVA, de 10/06 00:00h até 13/06 23:59h)
Aula 29 -
Aula 30 -