Teoria da Computação

Período letivo 2010.1:

• Campus Juazeiro, sala 27
• Terças e quintas, das 10:00 às 12:00hs
• Programa da disciplina
• PUD

Atenção para o calendário de final de semestre:

• 08/06, terça-feira, não haverá aula;
• 10/06, quinta-feira, não haverá aula;
• 15/06, terça-feira, aula normal;
• 17/06, quinta-feira, aula normal;
• 22/06, terça-feira, aula normal;
• 29/06, terça-feira, aula normal;
• 05/07, segunda-feira (8:00hs), prova 2;
• 06/07, terça-feira, prova final.

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 - um 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á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

Slides:

• Programas, máquinas e equivalências
• Máquinas universais
• Decidibilidade
• Complexidade

Material complementar:

• Livro "Foundations of Computer Sicence" de A.V. Aho e J.D. Ullman, disponível para download gratuito na página dos autores (capítulo 3).
• Artigo "The Status of the P Versus NP Problem", Lance Fortnow, CACM, Setembro de 2009.
• Artigo "A Teoria da Computação e o Profissional de Informática", João José Neto, RECET, Outubro de 2009.

Avaliações:

• Prova 1 (resolução)
• Prova 2 (resolução)
• Prova final (resolução)
• Notas - NOVO! (com prova final)

Aula 01 - 04/03 - Apresentação e motivação. Programas.

Aula 02 - 09/03 - Programas. Máquinas. Computações

Aula 03 - 11/03 - Funções computadas. Equivalência de programas e máquinas.

Aula 04 - 16/03 - Máquina de Traços.

Aula 05 - 18/03 - Instruções rotuladas compostas. Verificação da equivalência forte de programas monolíticos.

Aula 06 - 23/03 - Exercícios.

Aula 07 - 25/03 - Algoritmos. Máquinas Universais. Hipótese de Church. Máquina Norma.

Aula 08 - 30/03 - Máquina Norma. Máquina de Turing.

Aula 09 - 06/04 - Máquina de Turing. Máquina de Turing <= Máquina Norma.

Aula 10 - 08/04 - Máquina Norma <= Máquina de Turing. Máquina de Post. Máquina com Pilhas.

Aula 11 - 13/04 - Autômatos com duas pilhas. MT com múltiplas trilhas. MT não-determinísticas.

Aula 12 - 20/04 - MT não-detreminísticas. MT com múltiplas fitas.

Aula 13 - 22/04 - MT com fita limitada à esquerda.

Aula 14 - 27/04 - Exercícios.

Aula 15 - 29/04 - Introdução à decidibilidade. Problemas decidíveis.

Aula 16 - 30/04 - Prova 1.

Aula 17 - 04/05 - Linguagem Ld. Complemento de linguagens. Máquina de Turing Universal.

Aula 18 - 07/05 - Linguagem Lu. Redutibilidade. Problema da Parada.

Aula 19 - 11/05 - Complemento de linguagens. Linguagens Le e Lne.

Aula 20 - 13/05 - Teorema de Rice. Reduções via histórias de computação. Linguagens Vall e TODASglc.

Aula 21 - 18/05 - Introdução PCP. Redução MPCP > PCP.

Aula 22 - 20/05 - Redução Lu > MPCP.

Aula 23 - 25/05 - Problemas indecidíveis relacionados com LLCs. Introdução à complexidade.

Aula 24 - 27/05 - Medição do tempo de execução de algoritmos.

Aula 25 - 01/06 - Classes P e NP. Exemplos.

Aula 26 - 15/06 - Reduções de tempo polinomial.

Aula 27 - 17/06 - NP-completude e NP-hard.

Aula 28 - 22/06 - Problemas NP-completos e estratégias.

Aula 29 - 29/06 - Discussão de artigos. Revisão para a prova.

Aula 30 - 05/07 - Prova 2.

06/07 - Prova final.