Nome (e-mail) |
Horário de Atendimento |
Responsabilidade |
Carlos Eduardo A. da Cunha (ceac)
|
3as. 14 às 16hs |
Correções de listas e mini-provas
|
Carlos Eduardo dos S P Silva (cesps)
|
4as. e 6as. |
Correções de listas e mini-provas
|
Geraldo Fernandes da Silva Filho (gfsf)
|
? |
Correções de listas e mini-provas
|
Paulo Roberto (prsof)
|
? |
Correções de listas e mini-provas
|
Stelita Maria (sms)
|
- |
Aulas de revisão
|
Mariana Pinto Xavier (mpx)
|
- |
Aulas de Revisão
|
Francisco Valadares (famv)
|
- |
Projetos
|
Marcos Aurelio (maas)
|
- |
Projetos
|
Bibliografia Básica
Introdução à Teoria de Autômatos, Linguagens e Computação, John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Editora Campus, ISBN 85-352-1072-5, Outubro 2002.
(Tradução para o português de
Introduction to Automata Theory, Languages, and Computation, 2/E,
Addison-Wesley, 2001, ISBN: 0-201-44124-1. Página de apoio:
http://www-db.stanford.edu/~ullman/ialc.html)
Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company, 1997.
Bibliografia Suplementar
Elements of the Theory of Computation (Second Edition), Harry R. Lewis and Christos Papadimitriou, Prentice-Hall, 1998, ISBN: 0-13-262478-8.
Automata and Computability, Dexter Kozen, Springer, 1997, ISBN: 0-387-94907-0.
Computational Complexity, Christos Papadimitriou, Addison Wesley, 1994, ISBN: 0-201-53082-1.
Computability, Algorithms and Complexity, Ian Hodkinson,
Department of Computing, Imperial College London,
lecture notes, 1996.
Information.ps
ch1-2.ps
ch3.ps
ch4-5.ps
ch6-8.ps
ch9-10.ps
ch11-12.ps
Atenção: Apontadores Interessantes:
Entscheidungsproblem.
Zum Hilbertschen Aufbau der reelen Zahlen, por W. Ackermann, publicado em Mathematische Annalen 99:118-133, 1928.
Über die Erfüllbarkeit gewisser Zählausdrücke, por W. Ackermann,
publicado em Mathematische Annalen 100:638-649, 1928.
(generalização do Entscheidungsproblem)
On formally undecidable propositions of Principia Mathematica and related systems I, por K. Gödel, 1931.
Programação de Aulas
Aula |
Data |
Assunto |
Horas Acum. |
1 |
15-out |
Motivação: Problemas de Decisão
O Entscheidungsproblem
Alfabetos e Linguagens
|
02 |
2 |
19-out |
Autômatos Finitos
|
04 |
3 |
22-out |
Autômatos Finitos
Operações: Produto, Seqüenciamento
|
06 |
4 |
26-out |
Autômatos Finitos Não-Determinísticos
|
08 |
5 |
29-out |
Equivalência entre Autômatos
|
10 |
6 |
05-nov |
Expressões Regulares
De Expressões Regulares para Autômatos Finitos
|
12 |
7 |
09-nov |
De Autômatos Finitos para Expressões Regulares
|
14 |
8 |
12-nov |
Linguagens Não-Regulares
Lema do Bombeamento
|
16 |
9 |
16-nov |
Linguagens Regulares: Propriedades de Fechamento
|
18 |
10 |
19-nov |
Propriedades de Decisão para Linguagens Regulares
|
20 |
11 |
23-nov |
Primeira Prova |
22 |
12 |
26-nov |
Gramáticas Livres-de-Contexto
|
24 |
13 |
30-nov |
Árvores sintáticas
|
26 |
14 |
07-dez |
Autômatos a Pilha
|
28 |
15 |
10-dez |
Autômatos a Pilha (cont.)
|
30 |
16 |
14-dez |
Equivalência entre AP e LLC
|
32 |
17 |
17-dez |
Propriedades de Fechamento de Linguagens Livres-de-Contexto
Propriedades de Decisão de Linguagens Livres-de-Contexto
Forma Normal de Chomsky
|
34 |
18 |
21-dez |
Segunda Prova |
36 |
19 |
18-jan |
Máquinas de Turing
|
38 |
20 |
21-jan |
Máquinas de Turing
|
40 |
21 |
25-jan |
Máquinas de Turing Universais
|
42 |
22 |
28-jan |
Indecidibilidade e o Problema da Parada
|
44 |
23 |
01-fev |
Propriedades de Linguagens RE
Teorema de Rice
|
46 |
24 |
04-fev |
Máquinas de Turing
Algoritmos como Máquinas de Turing
Linguagens Recursivas e Recursivamente Enumeráveis
|
48 |
25 |
11-fev |
Variantes da Máquina de Turing
|
50 |
26 |
15-fev |
Máquinas de Turing Universais
Indecidibilidade e o Problema da Parada
|
52 |
27 |
18-fev |
Propriedades de Linguagens RE
|
54 |
28 |
22-02 |
Problema Indecidíveis sobre MT
Teorema de Rice
|
56 |
29 |
25-02 |
O Problema da Correspondência de Post
|
58 |
30 |
01-mar |
Problema Intratáveis
Tempo-polinomial não-determinístico
Reduções
|
60 |
31 |
04-mar |
Problemas NP-Completos
O Problema SAT
|
62 |
32 |
08-mar |
Exemplos
|
62 |
33 |
11-mar |
Terceira Prova
|
64 |
34 |
15-mar |
Segunda Chamada |
66 |
35 |
18-mar |
Prova Final |
68 |
ATENÇÃO: Newsgroup
Todas as mensagens relativas à disciplina são veiculadas
no grupo de notícias depto.cursos.grad.if689.
Última atualização: 23 de Março de 2005, 12:04hs