Mudanças entre as edições de "SCE-5832(gracan)"

De CoteiaWiki
(Links e referências)
(Notas)
Linha 176: Linha 176:
 
=== <font color = "green"> Notas </font> ===
 
=== <font color = "green"> Notas </font> ===
  
- Notas 1a. e 2a. provas (10 junho 2010): [[Arquivo:NotasTC.pdf]]
+
- Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]]

Edição das 10h38min de 1 de julho de 2010

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:

  1. - 10 Mar – Apresentação da Disciplina (Prof. João Luis Rosa)
  2. - 17 Março – Noções de Complexidade
  3. - 24 Março – Conceitos de Linguagens Formais. Autômatos Finitos (1)
  4. - 31 Março – Semana Santa - não há aula
  5. - 7 Abril - Autômatos Finitos Determinísticos e Não-Determinísticos (2)
  6. - 14 Abril - Expressões Regulares e Propriedades (Lema do Bombeamento)
  7. - 28 Abril - 1a. Prova
  8. - 5 Maio – Propriedades de Decisão das LR. Minimização de AF.
  9. - 12 Maio - Gramáticas Livres de Contexto e Autômatos a Pilha
  10. - 19 Maio - Linguagens Livres de Contexto
  11. - 26 Maio - 2a. Prova
  12. - 2 Junho - Indecidibilidade e Máquinas de Turing
  13. - 9 Junho - Poder Computacional das Máquinas de Turing
  14. - 16 Junho - Indecidibilidade
  15. - 23 Junho - Intratabilidade
  16. - 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:

Arquivo:Tiposdeprova.pdf

Conceitos Básicos - Linguagens e Problemas:

Arquivo:ConceitosBasicos.pdf

Automatos Finitos Determinísticos:

Arquivo:AFD.pdf

Aula 3 - 06/4/2010

Automatos Finitos Não-Determinísticos:

Arquivo:AulaAFND.pdf

Aula 4 - 13/4/2010

Expressões Regulares:

Arquivo:ERLinguagens.pdf

Propriedades de Linguagens Regulares:

Arquivo:PropriedadesLRx.pdf

Minimização de Autômatos Finitos:

Arquivo:MinimizacaoAFD.pdf

Aula 5 - 12/5/2010

Gramáticas Livres de Contexto

Arquivo:GLC.pdf

Autômatos a Pilha

Arquivo:GNACPx.pdf

Aula 6 - 19/5/2010

Propriedades das Linguagens Livres de Contexto

Arquivo:PropLLC.pdf

Aula 7 - 26/5/2010

Gramáticas

Arquivo:Gramaticas.pdf

Aulas 8 e 9 - 09 e 16/06/2010

Decidibilidade e Máquinas de Turing

Arquivo:Decidibilidade.pdf

Arquivo:MT1.pdf

Arquivo:MT2.pdf

Arquivo:Indecidibilidade.pdf

Aula 10 - 23/6/2010

Intratabilidade

Arquivo:Intratabilidade.pdf

Links e referências

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

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