Mudanças entre as edições de "SCE-5832(gracan)"
(→Slides das Aulas) |
(→Notas) |
||
| (34 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
| Linha 1: | Linha 1: | ||
=== <font color = "green"> SCE5832 -TEORIA DA COMPUTAÇÃO </font>=== | === <font color = "green"> SCE5832 -TEORIA DA COMPUTAÇÃO </font>=== | ||
| − | * Local: Sala ( | + | * Local: Sala (3010) - Horário: QUA - 9 - 12h |
| − | * Profa. '''Graça Nunes'''; gracan [arroba] icmc.usp.br; Sala: 4-201 | + | * 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. | ||
=== <font color = "green"> Avisos: </font> === | === <font color = "green"> Avisos: </font> === | ||
- Data de Início das aulas: 08/março | - Data de Início das aulas: 08/março | ||
| + | |||
| + | === <font color = "green"> Avaliação: </font> === | ||
| + | |||
| + | 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. | ||
=== <font color = "green"> Aula a aula: </font> === | === <font color = "green"> Aula a aula: </font> === | ||
| Linha 26: | Linha 61: | ||
#- ''30 Junho'' - '''3a. Prova''' | #- ''30 Junho'' - '''3a. Prova''' | ||
| − | === <font color = "green"> | + | === <font color = "green"> Links e referências </font> === |
| − | + | * [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm A questão P=NP] | |
| + | |||
| + | * [http://www.aduni.org/courses/theory/index.php?view=cw 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]] | ||
=== <font color = "green"> Listas de Exercícios </font> === | === <font color = "green"> Listas de Exercícios </font> === | ||
| Linha 45: | Linha 90: | ||
- Lista 6- Decidibilidade: [[Arquivo:GNLista6Decidib.pdf]] | - Lista 6- Decidibilidade: [[Arquivo:GNLista6Decidib.pdf]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Edição atual tal como às 12h29min de 15 de março de 2011
Índice
[ocultar]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
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
