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

De CoteiaWiki
(→‎Avisos:)
(→‎Notas)
 
(33 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 16: Linha 16:
  
 
=== <font color = "green"> Avisos: </font> ===
 
=== <font color = "green"> Avisos: </font> ===
 +
 +
- 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 e Gabarito da Provinha 1 divulgados nos links abaixo (16/5)
  
−
-   Notas da 1a. Prova disponíveis no link Notas (19/4).  
+
- Notas da 1a. Prova disponíveis no link Notas (19/4).  
  
−
- Gabarito da 1a. prova, no link Gabaritos (25/4).
+
- Gabarito da 1a. prova, no link Gabaritos (25/4).
  
 
=== <font color = "green"> Avaliação: </font> ===
 
=== <font color = "green"> Avaliação: </font> ===
Linha 61: Linha 71:
 
#- ''4 Maio'' - Gramáticas Regulares (2) e Gramáticas Livres de Contexto
 
#- ''4 Maio'' - Gramáticas Regulares (2) e Gramáticas Livres de Contexto
 
#- ''11 Maio'' - Linguagens Livres de Contexto: propriedades (1)
 
#- ''11 Maio'' - Linguagens Livres de Contexto: propriedades (1)
−
 
+
#- ''18 Maio'' - Linguagens Livres de Contexto: propriedades (2);Automatos a Pilha
−
<!--#- ''18 Maio'' - --Automatos a Pilha e Linguagens Livres de Contexto -->
+
#- ''25 maio'' - 2a. Prova
−
<!--#- ''25 Maio'' -   Indecidibilidade e Máquinas de Turing -->
+
#- ''1 junho'' - Autômatos a Pilha - cont.;Gramática e Linguagem Livre de Contexto; Automatos Linearmente Limitados
−
<!--#- ''1 Junho'' - '''2a. Prova''' Poder Computacional das Máquinas de Turing-->
+
#- ''8 junho'' - Máquinas de Turing
−
<!--#- ''8 Junho'' - Indecidibilidade -->
+
#- ''15 junho'' - Decidibilidade
−
<!--#- ''15 Junho'' - Intratabilidade OU SEMINARIOS 1-->
+
#- ''22 junho'' - Intratabilidade
−
<!--#- ''22 Junho'' - OU SEMINARIOS 2
+
#- ''29 junho'' - 3a. Prova
−
<!--#- ''29 Junho'' - '''3a. Prova''' OU SEMINARIOS 3-->
 
  
 
=== <font color = "green"> Slides das Aulas </font> ===
 
=== <font color = "green"> Slides das Aulas </font> ===
Linha 113: Linha 122:
 
'''Aula 7 - 4/5/2011'''
 
'''Aula 7 - 4/5/2011'''
  
−
[[Arquivo:GramaticaRegular.pdf]]
+
Linguagens Livres de Contexto
  
 
[[Arquivo:GLCeLLC.pdf]]
 
[[Arquivo:GLCeLLC.pdf]]
  
 
'''Aula 8 - 11/5/2011'''
 
'''Aula 8 - 11/5/2011'''
 +
 +
Propriedades de LLC
  
 
[[Arquivo:PropLLC.pdf]]
 
[[Arquivo:PropLLC.pdf]]
  
−
<!--'''Aula 8 - 11/6/2011'''-->
+
'''Aulas 9 e 11- 18/5 e 1/6/2011'''
−
<!--Propriedades das Linguagens Livres de Contexto-->
+
 
−
<!--[[Arquivo:PropLLC.pdf]]-->
+
Autômatos a Pilha
−
<!--Autômatos a Pilha-->
+
 
−
<!--[[Arquivo:GNACPx.pdf]]-->
+
[[Arquivo:GNACPx.pdf]]
 +
 
 +
Gramática Sensível ao Contexto, Linguagem Sensível ao Contexto e Automatos Linearmente Limitados
 +
 
 +
[[Arquivo:SensivelContexto.pdf]]
 +
 
 +
'''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
 +
 
 +
[[Arquivo:DecidInformal2011.pdf]]
 +
 
 +
Versão mais formal: [[Arquivo:DecidFormal2011.pdf]]
 +
 
 +
'''Aula 14 - 22/6/2011'''
 +
 
 +
Teoria da Intratabilidade
 +
 
 +
[[Arquivo:GNIntratreduzido.pdf]]
  
  
−
<!--'''Aula 9 - 18/6/2011'''-->
 
−
<!--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'''-->
 
<!--'''Aula 10 - 23/6/2010'''-->
 
<!--Intratabilidade-->
 
<!--Intratabilidade-->
Linha 179: Linha 205:
  
 
- Lista 6- Decidibilidade: [[Arquivo:GNLista6Decidib.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)
 +
 +
[[Arquivo:Listas.rar]]
  
 
=== <font color = "green"> Notas </font> ===
 
=== <font color = "green"> Notas </font> ===
Linha 184: Linha 214:
 
<!--- Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]]-->
 
<!--- Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]]-->
  
−
- Notas da 1a. Prova (19/4/2011) e Provinha 1 (11/5) [[Arquivo:NotasTC2011.pdf]]
+
<!--- Notas até a 5a. provinha (22/6/2011) [[Arquivo:NotasTC2011.pdf]]-->
  
 
=== <font color = "green"> Gabaritos </font> ===
 
=== <font color = "green"> Gabaritos </font> ===
  
 
- Gabarito Prova 1: [[Arquivo:GabaritoProva1.pdf]]
 
- Gabarito Prova 1: [[Arquivo:GabaritoProva1.pdf]]
 +
 +
- Gabarito Prova 2: [[Arquivo:GabaritoProva2.pdf]]
  
 
- Gabarito Provinha 1: [[Arquivo:Provinha1_11mai.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]]

Edição atual tal como às 12h40min de 11 de agosto de 2011

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:

  1. - 16 Mar – Apresentação da Disciplina e Noções de Complexidade
  2. - 23 Março – Análise de Algoritmos; Tipos de Provas; Conceitos de Linguagens
  3. - 30 Março – Autômatos Finitos Determinísticos e Não Determinísticos(1)
  4. - 6 Abril – Autômatos Finitos Não-Determinísticos (2); Expressões Regulares
  5. - 13 Abril - 1a. Prova
  6. - 20 Abril - Semana Santa
  7. - 27 Abril - Propriedades de Decisão das LR. Minimização de AF. Gramáticas Regulares (1)
  8. - 4 Maio - Gramáticas Regulares (2) e Gramáticas Livres de Contexto
  9. - 11 Maio - Linguagens Livres de Contexto: propriedades (1)
  10. - 18 Maio - Linguagens Livres de Contexto: propriedades (2);Automatos a Pilha
  11. - 25 maio - 2a. Prova
  12. - 1 junho - Autômatos a Pilha - cont.;Gramática e Linguagem Livre de Contexto; Automatos Linearmente Limitados
  13. - 8 junho - Máquinas de Turing
  14. - 15 junho - Decidibilidade
  15. - 22 junho - Intratabilidade
  16. - 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:

Arquivo:Tiposdeprova.pdf

Arquivo:ConceitosBasicosx.pdf

Aulas 3 e 4 - 30/3 e 6/4/2011

Automatos Finitos Determinísticos e Não Determinísticos:

Arquivo:AFD.pdf

Arquivo:AulaAFNDx.pdf

Aula 4 - 6/4/2011

Expressões Regulares:

Arquivo:ERLinguagens.pdf

Aula 5 - 13/4/2011 - 1a. Prova

Aula 6 - 27/4/2011

Propriedades das Linguagens Regulares, Minimização de AFD e Gramáticas Regulares

Arquivo:PropriedadesLRx.pdf

Arquivo:MinimizacaoAFD.pdf

Arquivo:GramaticaRegular.pdf

Aula 7 - 4/5/2011

Linguagens Livres de Contexto

Arquivo:GLCeLLC.pdf

Aula 8 - 11/5/2011

Propriedades de LLC

Arquivo:PropLLC.pdf

Aulas 9 e 11- 18/5 e 1/6/2011

Autômatos a Pilha

Arquivo:GNACPx.pdf

Gramática Sensível ao Contexto, Linguagem Sensível ao Contexto e Automatos Linearmente Limitados

Arquivo:SensivelContexto.pdf

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

Arquivo:DecidInformal2011.pdf

Versão mais formal: Arquivo:DecidFormal2011.pdf

Aula 14 - 22/6/2011

Teoria da Intratabilidade

Arquivo:GNIntratreduzido.pdf


Material Extra de Referência

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

Gabaritos das Listas de Exercícios (atenção: o conteúdo não foi corrigido; use-o apenas como apoio)

Arquivo:Listas.rar

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

Disponível em "http://wiki.icmc.usp.br/index.php?title=SCE-5832(gracan1)&oldid=19209"