Prof. Marcus Ramos - Teoria da Computação

Teoria da Computação

Período letivo 2022.2 (2022.1 no SIGA):

Campus Juazeiro
Terças, das 16:00 às 18:00 hs, sala 15
Quintas, das 16:00 às 18:00 hs, sala 15
As aulas de reposição em 2022 (três no total) acontecerão nos dias 18/11, 25/11 e 16/12, sextas-feiras, das 16:00h às 18:00h, no Laboratório de Programação Avançada
As aulas de reposição em 2023 (quatro no total) acontecerão em dias, horário e local a serem informados
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
- Site
Outra opção de calculadora lambda
- 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:

Artigos:
- Goto (Wikipedia)
- Go To Statement Considered Harmful (Dijkstra, 1968, CACM)
- Structured Programming (Wikipedia)
- Structured Programming Theorem (Wikipedia)
- Flow Diagrams, Turing Machines and Languages with only Two Formation Rules (Böhm & Jacopini, 1966, CACM)
- Notes on Structured Programming (Dijkstra, 1968, TU Eindhoven)
- Structured Programming with goto Statements (Knuth, 1974, Computing Surveys)
Aulas gravadas

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:

Aulas ministradas:

Aula 01 - 18/10/2022 - Apresentação e motivação.
Aula 02 - 20/10/2022 - Programas monolíticos e iterativos.
Aula 03 - 25/10/2022 - Programas recursivos. Computação e função computada.
Aula 04 - 27/10/2022 - Equivalência forte de programas monolíticos, iterativos e recursivos. Poder computacional.
Aula 05 - 01/11/2022 - Máquinas de traços.
Aula 06 - 03/11/2022 - Instruções rotuladas compostas e cadeias de conjntos.
Aula 07 - 08/11/2022 - Algoritmo de verificação da equivalência forte de programas. Exemplo e exercício.
Aula 08 - 10/11/2022 - Máquinas universais. Hipótese de Church. Teorema fundamental da aritmética. Máquina Norma. Máquina Norma como máquina universal.
Aula 09 - 17/11/2022 - Máquina Norma como máquina universal (continuação).
Aula 10 - 18/11/2002 - (reposição) - Máquinas de Turing. Exemplos. Linguagens recursivamente enumerável e recursiva.
Aula 11 - 25/11/2022 - (reposição) - Equivalência entre Máquina de Turing e Máquna Norma.
Aula 12 - 29/11/2022 - Prova 1.
Aula 13 - 01/12/2022 - Máquina de Post. Equivalência entre Máquina de Turing e Máquina de Post. Máquina com Pilhas.
Aula 14 - 06/12/2022 - Máquina com Pilhas.
Aula 15 - 08/12/2022 - Autômato com Duas Pilhas. Equivalência com Máquina de Turing.
Aula 16 - 13/12/2022 - Múltiplas trilhas. Não-determinismo.
Aula 17 - 15/12/2022 - Múltiplas fitas. Não escrever brancos. Fita limitada à esquerda.
Aula 18 - 16/12/2022 - (reposição) - Introdução à decidibilidade. Problemas decidíveis.
Aula 19 - 20/12/2022 - Codificação de Máquinas de Turing. Método Diagonal de Cantor, Linguagem Ld.
Aula 20 - 22/12/2022 - Complemento de linguagens.

AFASTAMENTO PARA TRATAMENTO DE SAÙDE

Aula 21 - 17/01/2023 - Prova 2.

Atividade 1:
Aula 22 - 24/01/2023 - Máquina de Turing Universal e Linguagem Lu.
Aula 23 - 26/01/2023 - Redutblidade, Problema da Parada e Linguagens Le e Lne.

Atividade 2:
Aula 24 - 31/01/2023 - Teorema de Rice, Autômato Linearmente Limitado, Histórias de Computação e Problemas Indecidíveis.
Aula 25 - 02/02/2023 - PCP.

Atividade 3:
Aula 26 - 07/02/2023 - Problemas relacionados com GLCs e LLCs.
Aula 27 - 09/02/2023 - Introdução à Complexidade, Medição do Tempo de Execução.

Atividade 4:
Aula 28 - 14/02/2023 - As classes P e NP.
Aula 29 - 16/02/2023 - Redutibilidade em tempo polinomial e NP-Completude.