SCE-5832(gracan1)
Índice
SCE5832 -TEORIA DA COMPUTAÇÃO
- Local: Sala ( ) - 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: 14 de março de 2011
Avaliação:
3 Provas de igual peso:
13 de abril
25 de maio
29 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:
- - 16 Mar – Apresentação da Disciplina e Noções de Complexidade
Slides das Aulas
Aula 1 - 16/3/2011 - Análise de Algoritmos:
Arquivo:Analisealgoritmos1.pdf
Arquivo:Analisealgoritmos2.pdf
Material Extra de Referência
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