SCE-5832(gracan)

SCE5832 -TEORIA DA COMPUTAÇÃO

• Local: Sala (3010) - Horário: QUA - 9 - 12h
• Profa. Graça Nunes; gracan [arroba] icmc.usp.br; Sala: 4-201

Bibliografia Básica

• Hopcroft, J. E., Ullman, J. D. Formal Languages and Their Relation to Automata.

Addison-Wesley Publishing Company, 1969.

• Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.

3rd. edition. Addison-Wesley, 2007.

• Moll, R. N., Arbib, M. A., and Kfoury, A. J. An Introduction to Formal Language Theory.

Springer-Verlag, 1988.

• Sipser, M. Introduction to the Theory of Computation. Second Edition, Thomson, 2006.
• Rosa, J.L.G. Linguagens Formais e Autômatos. LTC, 2010.

Avisos:

- Data de Início das aulas: 08/março

Avaliação:

3 Provas de igual peso:

05 de maio

02 de junho

30 de junho

Seja MP a média aritmética das 3 provas, e seja CF o conceito final.

CF = A se 8 MP 10;

CF = B se 7 MP< 8;

CF = C se 5 MP <7;

CF = R, caso contrário.

Será exigida freqüência em 70% das aulas ministradas (incluindo dias de provas).

No caso de o aluno ficar distante de até 0,25 de um conceito maior, a entrega das listas de exercícios resolvidas permitirá a mudança de nível.

Aula a aula:

1. - 10 Mar – Apresentação da Disciplina (Prof. João Luis Rosa)
2. - 17 Março – Noções de Complexidade
3. - 24 Março – Conceitos de Linguagens Formais. Autômatos Finitos (1)
4. - 31 Março – Semana Santa - não há aula
5. - 7 Abril - Autômatos Finitos Determinísticos e Não-Determinísticos (2)
6. - 14 Abril - Expressões Regulares e Propriedades (Lema do Bombeamento)
7. - 28 Abril - 1a. Prova
8. - 5 Maio – Propriedades de Decisão das LR. Minimização de AF.
9. - 12 Maio - Gramáticas Livres de Contexto e Autômatos a Pilha
10. - 19 Maio - Linguagens Livres de Contexto
11. - 26 Maio - 2a. Prova
12. - 2 Junho - Indecidibilidade e Máquinas de Turing
13. - 9 Junho - Poder Computacional das Máquinas de Turing
14. - 16 Junho - Indecidibilidade
15. - 23 Junho - Intratabilidade
16. - 30 Junho - 3a. Prova

Links e referências

• A questão P=NP

• Aulas de Teoria da Computação do MIT

Linguagens Livres de Contexto e Automatos a Pilha (Prof. João Rosa)

Arquivo:LLC&APJoao.pdf

Linguagens Sensíveis ao Contexto, Linguagens Recursivamente Enumeraveis e Maquinas de Turing (Prof. João Rosa)

Arquivo:LSC&MTJoao.pdf

Listas de Exercícios

- Lista 0- Análise de Algoritmos: Arquivo:GNLista0AnaliseAlg.pdf

- Lista 1- Automatos Finitos: Arquivo:GNLista1AFDeAFND.pdf

- Lista 2- Gramáticas Livres de Contexto: Arquivo:GNLista2GLC.pdf

- Lista 3- Automatos a Pilha: Arquivo:GNLista3AP.pdf

- Lista 4- Linguagens Livres de Contexto: Arquivo:GNLista4LLC.pdf

- Lista 5- Máquinas de Turing: Arquivo:GNLista5MT.pdf

- Lista 6- Decidibilidade: Arquivo:GNLista6Decidib.pdf