SCE-5832(gracan1)
Í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 da Provina 5 divulgadas (22/6)
- Notas da Provinha 4 divulgadas (17/6)
- Notas e Gabarito da Provinha 3 divulgados nos links abaixo (9/6)
- 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
- - 8 junho - Máquinas de Turing
- - 15 junho - Decidibilidade
- - 22 junho - Intratabilidade
- - 29 junho - 3a. Prova
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
Aula 12 - 8/6/2011
Máquinas de Turing e Linguagens Recursivamente Enumeráveis
Arquivo:Aula10MaqTuring2011.pdf
Aula 13 - 15/6/2011
Problemas Decidíveis e Indecidíveis
Versão mais formal: Arquivo:DecidFormal2011.pdf
Aula 14 - 22/6/2011
Teoria da Intratabilidade
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
Gabaritos das Listas de Exercícios (atenção: o conteúdo não foi corrigido; use-o apenas como apoio)
Notas
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
- Gabarito Provinha 3: Arquivo:Provinha3 8jun.pdf
- Gabarito Provinha 4: Arquivo:Provinha4gab.pdf
- Gabarito Provinha 5: Arquivo:Provinha5gab.pdf
