Mudanças entre as edições de "SCE-5832(gracan1)"
(→Slides das Aulas) |
(→Slides das Aulas) |
||
| Linha 131: | Linha 131: | ||
[[Arquivo:PropLLC.pdf]] | [[Arquivo:PropLLC.pdf]] | ||
| − | '''Aulas 9 e | + | '''Aulas 9 e 11- 18/5 e 1/6/2011''' |
Autômatos a Pilha | Autômatos a Pilha | ||
Edição das 19h27min de 31 de maio de 2011
Índice
SCE5832 -TEORIA DA COMPUTAÇÃO
- Local: Sala (3012) - 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.
- Menezes, P. F. Blauth . Linguagens Formais e Autômatos. 5. ed. Porto Alegre: Editora Sagra Luzzatto, 2005. v. 1. 232 p
- 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:
- Notas e Gabarito da Prova 2 divulgados.
- Notas e Gabarito da Provinha 2 divulgados nos links abaixo (19/5)
- Notas e Gabarito da Provinha 1 divulgados nos links abaixo (16/5)
- Notas da 1a. Prova disponíveis no link Notas (19/4).
- Gabarito da 1a. prova, no link Gabaritos (25/4).
Avaliação:
3 Provas de igual peso:
(1) 13 de abril
(2) 25 de maio
(3) Soma de 5 provinhas (no final das aulas) entre 11/5 e 22/6
SUBSTITUTIVA: 29 de junho (substitui a menor das 3 provas)
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:
- - 16 Mar – Apresentação da Disciplina e Noções de Complexidade
- - 23 Março – Análise de Algoritmos; Tipos de Provas; Conceitos de Linguagens
- - 30 Março – Autômatos Finitos Determinísticos e Não Determinísticos(1)
- - 6 Abril – Autômatos Finitos Não-Determinísticos (2); Expressões Regulares
- - 13 Abril - 1a. Prova
- - 20 Abril - Semana Santa
- - 27 Abril - Propriedades de Decisão das LR. Minimização de AF. Gramáticas Regulares (1)
- - 4 Maio - Gramáticas Regulares (2) e Gramáticas Livres de Contexto
- - 11 Maio - Linguagens Livres de Contexto: propriedades (1)
- - 18 Maio - Linguagens Livres de Contexto: propriedades (2);Automatos a Pilha
- - 25 maio - 2a. Prova
- - 1 junho - Autômatos a Pilha - cont.;Gramática e Linguagem Livre de Contexto; Automatos Linearmente Limitados
Slides das Aulas
Aula 1 - 16/3/2011 - Análise de Algoritmos:
Arquivo:Analisealgoritmos1.pdf
Arquivo:Analisealgoritmos2.pdf
Aula 2 - 23/3/2011 - Provas e Conceitos Básicos de Linguagens:
Aulas 3 e 4 - 30/3 e 6/4/2011
Automatos Finitos Determinísticos e Não Determinísticos:
Aula 4 - 6/4/2011
Expressões Regulares:
Aula 5 - 13/4/2011 - 1a. Prova
Aula 6 - 27/4/2011
Propriedades das Linguagens Regulares, Minimização de AFD e Gramáticas Regulares
Aula 7 - 4/5/2011
Linguagens Livres de Contexto
Aula 8 - 11/5/2011
Propriedades de LLC
Aulas 9 e 11- 18/5 e 1/6/2011
Autômatos a Pilha
Gramática Sensível ao Contexto, Linguagem Sensível ao Contexto e Automatos Linearmente Limitados
Material Extra de Referência
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 até a 2a. Prova (26/5/2011) Arquivo:NotasTC2011.pdf
Gabaritos
- Gabarito Prova 1: Arquivo:GabaritoProva1.pdf
- Gabarito Prova 2: Arquivo:GabaritoProva2.pdf
- Gabarito Provinha 1: Arquivo:Provinha1 11mai.pdf
- Gabarito Provinha 2: Arquivo:Provinha2 18mai.pdf
