Mudanças entre as edições de "SCE-5832(gracan)"
(→Links e referências) |
(→Notas) |
||
| Linha 176: | Linha 176: | ||
=== <font color = "green"> Notas </font> === | === <font color = "green"> Notas </font> === | ||
| − | - Notas | + | - Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]] |
Edição das 10h38min de 1 de julho de 2010
Índice
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:
- - 10 Mar – Apresentação da Disciplina (Prof. João Luis Rosa)
- - 17 Março – Noções de Complexidade
- - 24 Março – Conceitos de Linguagens Formais. Autômatos Finitos (1)
- - 31 Março – Semana Santa - não há aula
- - 7 Abril - Autômatos Finitos Determinísticos e Não-Determinísticos (2)
- - 14 Abril - Expressões Regulares e Propriedades (Lema do Bombeamento)
- - 28 Abril - 1a. Prova
- - 5 Maio – Propriedades de Decisão das LR. Minimização de AF.
- - 12 Maio - Gramáticas Livres de Contexto e Autômatos a Pilha
- - 19 Maio - Linguagens Livres de Contexto
- - 26 Maio - 2a. Prova
- - 2 Junho - Indecidibilidade e Máquinas de Turing
- - 9 Junho - Poder Computacional das Máquinas de Turing
- - 16 Junho - Indecidibilidade
- - 23 Junho - Intratabilidade
- - 30 Junho - 3a. Prova
Slides das Aulas
Aula 1 - 17/3/2010 - Análise de Algoritmos:
Arquivo:Analisealgoritmos1.pdf
Arquivo:Analisealgoritmos2.pdf
Aula 2 - 24/3/2010
Tipos de Prova de Teoremas:
Conceitos Básicos - Linguagens e Problemas:
Automatos Finitos Determinísticos:
Aula 3 - 06/4/2010
Automatos Finitos Não-Determinísticos:
Aula 4 - 13/4/2010
Expressões Regulares:
Propriedades de Linguagens Regulares:
Minimização de Autômatos Finitos:
Aula 5 - 12/5/2010
Gramáticas Livres de Contexto
Autômatos a Pilha
Aula 6 - 19/5/2010
Propriedades das Linguagens Livres de Contexto
Aula 7 - 26/5/2010
Gramáticas
Aulas 8 e 9 - 09 e 16/06/2010
Decidibilidade e Máquinas de Turing
Aula 10 - 23/6/2010
Intratabilidade
Links e referências
Linguagens Livres de Contexto e Automatos a Pilha (Prof. João Rosa)
Linguagens Sensíveis ao Contexto, Linguagens Recursivamente Enumeraveis e Maquinas de Turing (Prof. João Rosa)
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
Notas
- Notas todas as provas (01 julho 2010): Arquivo:NotasTC01jul.pdf
