Mudanças entre as edições de "SCE-5832(gracan1)"
De CoteiaWiki
m (Protegeu "SCE-5832(gracan1)" ([edit=sysop] (indefinido) [move=sysop] (indefinido)) [p. progressiva]) |
|||
| Linha 1: | Linha 1: | ||
=== <font color = "green"> SCE5832 -TEORIA DA COMPUTAÇÃO </font>=== | === <font color = "green"> SCE5832 -TEORIA DA COMPUTAÇÃO </font>=== | ||
| − | * Local: Sala ( | + | * Local: Sala ( ) - Horário: QUA - 9 - 12h |
* Profa. '''Graça Nunes'''; gracan [arroba] icmc.usp.br; Sala: 4-201 | * Profa. '''Graça Nunes'''; gracan [arroba] icmc.usp.br; Sala: 4-201 | ||
| Linha 15: | Linha 15: | ||
=== <font color = "green"> Avisos: </font> === | === <font color = "green"> Avisos: </font> === | ||
| − | - Data de Início das aulas: | + | - Data de Início das aulas: 14/março |
=== <font color = "green"> Avaliação: </font> === | === <font color = "green"> Avaliação: </font> === | ||
| Linha 44: | Linha 44: | ||
=== <font color = "green"> Aula a aula: </font> === | === <font color = "green"> Aula a aula: </font> === | ||
| − | #- '' | + | #- ''16 Mar'' – Apresentação da Disciplina e Noções de Complexidade |
| − | #-'' 17 Março'' – Noções de Complexidade | + | <!--#-'' 17 Março'' – Noções de Complexidade--> |
| − | #- ''24 Março'' – Conceitos de Linguagens Formais. Autômatos Finitos (1) | + | <!--#- ''24 Março'' – Conceitos de Linguagens Formais. Autômatos Finitos (1)--> |
| − | #- ''31 Março'' – Semana Santa - não há aula | + | <!--#- ''31 Março'' – Semana Santa - não há aula--> |
| − | #- ''7 Abril'' - Autômatos Finitos Determinísticos e Não-Determinísticos (2) | + | <!--#- ''7 Abril'' - Autômatos Finitos Determinísticos e Não-Determinísticos (2)--> |
| − | #- ''14 Abril'' - Expressões Regulares e Propriedades (Lema do Bombeamento) | + | <!--#- ''14 Abril'' - Expressões Regulares e Propriedades (Lema do Bombeamento)--> |
| − | #- ''28 Abril'' - '''1a. Prova''' | + | <!--#- ''28 Abril'' - '''1a. Prova'''--> |
| − | #- ''5 Maio'' – Propriedades de Decisão das LR. Minimização de AF. | + | <!--#- ''5 Maio'' – Propriedades de Decisão das LR. Minimização de AF.--> |
| − | #- ''12 Maio'' - Gramáticas Livres de Contexto e Autômatos a Pilha | + | <!--#- ''12 Maio'' - Gramáticas Livres de Contexto e Autômatos a Pilha--> |
| − | #- ''19 Maio'' - Linguagens Livres de Contexto | + | <!--#- ''19 Maio'' - Linguagens Livres de Contexto--> |
| − | #- ''26 Maio'' - '''2a. Prova''' | + | <!--#- ''26 Maio'' - '''2a. Prova'''--> |
| − | #- ''2 Junho'' - Indecidibilidade e Máquinas de Turing | + | <!--#- ''2 Junho'' - Indecidibilidade e Máquinas de Turing --> |
| − | #- ''9 Junho'' - Poder Computacional das Máquinas de Turing | + | <!--#- ''9 Junho'' - Poder Computacional das Máquinas de Turing--> |
| − | #- ''16 Junho'' - Indecidibilidade | + | <!--#- ''16 Junho'' - Indecidibilidade --> |
| − | #- ''23 Junho'' - Intratabilidade | + | <!--#- ''23 Junho'' - Intratabilidade--> |
| − | #- ''30 Junho'' - '''3a. Prova''' | + | <!--#- ''30 Junho'' - '''3a. Prova'''--> |
=== <font color = "green"> Slides das Aulas </font> === | === <font color = "green"> Slides das Aulas </font> === | ||
| Linha 70: | Linha 70: | ||
[[Arquivo:Analisealgoritmos2.pdf]] | [[Arquivo:Analisealgoritmos2.pdf]] | ||
| − | '''Aula 2 - 24/3/2010''' | + | <!--'''Aula 2 - 24/3/2010''' --> |
| − | + | <!--Tipos de Prova de Teoremas:--> | |
| − | Tipos de Prova de Teoremas: | + | <!--[[Arquivo:Tiposdeprova.pdf]] --> |
| − | + | <!--Conceitos Básicos - Linguagens e Problemas:--> | |
| − | [[Arquivo:Tiposdeprova.pdf]] | + | <!--[[Arquivo:ConceitosBasicos.pdf]]--> |
| − | + | <!--Automatos Finitos Determinísticos:--> | |
| − | Conceitos Básicos - Linguagens e Problemas: | + | <!--[[Arquivo:AFD.pdf]]--> |
| − | + | <!--'''Aula 3 - 06/4/2010'''--> | |
| − | [[Arquivo:ConceitosBasicos.pdf]] | + | <!--Automatos Finitos Não-Determinísticos:--> |
| − | + | <!--[[Arquivo:AulaAFND.pdf]]--> | |
| − | Automatos Finitos Determinísticos: | + | <!--'''Aula 4 - 13/4/2010'''--> |
| − | + | <!--Expressões Regulares:--> | |
| − | [[Arquivo:AFD.pdf]] | + | <!--[[Arquivo:ERLinguagens.pdf]]--> |
| − | + | <!--Propriedades de Linguagens Regulares:--> | |
| − | '''Aula 3 - 06/4/2010''' | + | <!--[[Arquivo:PropriedadesLRx.pdf]]--> |
| − | + | <!--Minimização de Autômatos Finitos:--> | |
| − | Automatos Finitos Não-Determinísticos: | + | <!--[[Arquivo:MinimizacaoAFD.pdf]]--> |
| − | + | <!--'''Aula 5 - 12/5/2010'''--> | |
| − | [[Arquivo:AulaAFND.pdf]] | + | <!--Gramáticas Livres de Contexto--> |
| − | + | <!--[[Arquivo:GLC.pdf]]--> | |
| − | '''Aula 4 - 13/4/2010''' | + | <!--Autômatos a Pilha--> |
| − | + | <!--[[Arquivo:GNACPx.pdf]]--> | |
| − | Expressões Regulares: | + | <!--'''Aula 6 - 19/5/2010'''--> |
| − | + | <!--Propriedades das Linguagens Livres de Contexto--> | |
| − | [[Arquivo:ERLinguagens.pdf]] | + | <!--[[Arquivo:PropLLC.pdf]]--> |
| − | + | <!--'''Aula 7 - 26/5/2010'''--> | |
| − | Propriedades de Linguagens Regulares: | + | <!--Gramáticas--> |
| − | + | <!--[[Arquivo:Gramaticas.pdf]]--> | |
| − | [[Arquivo:PropriedadesLRx.pdf]] | + | <!--'''Aulas 8 e 9 - 09 e 16/06/2010'''--> |
| − | + | <!--Decidibilidade e Máquinas de Turing--> | |
| − | Minimização de Autômatos Finitos: | + | <!--[[Arquivo:Decidibilidade.pdf]]--> |
| − | + | <!--[[Arquivo:MT1.pdf]]--> | |
| − | [[Arquivo:MinimizacaoAFD.pdf]] | + | <!--[[Arquivo:MT2.pdf]]--> |
| − | + | <!--[[Arquivo:Indecidibilidade.pdf]]--> | |
| − | '''Aula 5 - 12/5/2010''' | + | <!--'''Aula 10 - 23/6/2010'''--> |
| − | + | <!--Intratabilidade--> | |
| − | Gramáticas Livres de Contexto | + | <!--[[Arquivo:Intratabilidade.pdf]]--> |
| − | + | <!--=== <font color = "green"> Links e referências </font> ===--> | |
| − | [[Arquivo:GLC.pdf]] | + | <!--* [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm A questão P=NP]--> |
| − | + | <!--* [http://www.aduni.org/courses/theory/index.php?view=cw Aulas de Teoria da Computação do MIT]--> | |
| − | Autômatos a Pilha | + | <!--Linguagens Livres de Contexto e Automatos a Pilha (Prof. João Rosa)--> |
| − | + | <!--[[Arquivo:LLC&APJoao.pdf]]--> | |
| − | [[Arquivo:GNACPx.pdf]] | + | <!--Linguagens Sensíveis ao Contexto, Linguagens Recursivamente Enumeraveis e Maquinas de Turing (Prof. João Rosa)--> |
| − | + | <!--[[Arquivo:LSC&MTJoao.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]] | ||
| − | |||
| − | === <font color = "green"> Links e referências </font> === | ||
| − | |||
| − | * [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm A questão P=NP] | ||
| − | |||
| − | * [http://www.aduni.org/courses/theory/index.php?view=cw Aulas de Teoria da Computação do MIT] | ||
| − | |||
| − | 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]] | ||
=== <font color = "green"> Listas de Exercícios </font> === | === <font color = "green"> Listas de Exercícios </font> === | ||
| Linha 176: | Linha 133: | ||
=== <font color = "green"> Notas </font> === | === <font color = "green"> Notas </font> === | ||
| − | - Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]] | + | <!--- Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]]--> |
Edição das 10h12min de 14 de fevereiro de 2011
Í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/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:
- - 16 Mar – Apresentação da Disciplina e Noções de Complexidade
Slides das Aulas
Aula 1 - 17/3/2010 - Análise de Algoritmos:
Arquivo:Analisealgoritmos1.pdf
Arquivo:Analisealgoritmos2.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
