Mudanças entre as edições de "SCC-505(gracan)"

De CoteiaWiki
m (Protegeu "SCC-505(gracan)" ([edit=sysop] (indefinido) [move=sysop] (indefinido)) [p. progressiva])
(→‎Notas)
 
(73 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 1: Linha 1:
−
=== <font color = "green"> SCE5832 -TEORIA DA COMPUTAÇÃO  </font>===
+
=== <font color = "green"> SCC-505 - INTRODUÇÃO À TEORIA DA COMPUTAÇÃO  </font>===
−
* Local:  Sala (3010) - Horário: QUA - 9 - 12h
+
* Local:  Sala (5003) - Horário: SEXTA - 19 - 20:40h
 
* 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 6: Linha 6:
  
 
* Hopcroft, J. E., Ullman, J. D. Formal Languages and Their Relation to Automata.
 
* Hopcroft, J. E., Ullman, J. D. Formal Languages and Their Relation to Automata.
−
Addison-Wesley Publishing Company, 1969.
+
Addison-Wesley Publishing Company, 1979.
 +
* Hopcroft, J. E., Ullman, J. D. and Motwani, R. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da 2a. edição.
 +
Editora Campus, 2001.
 
* Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.
 
* Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.
 
3rd. edition. Addison-Wesley, 2007.
 
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.
 
* Sipser, M. Introduction to the Theory of Computation. Second Edition, Thomson, 2006.
 
* Rosa, J.L.G. Linguagens Formais e Autômatos. LTC, 2010.
 
* Rosa, J.L.G. Linguagens Formais e Autômatos. LTC, 2010.
  
 
=== <font color = "green"> Avisos: </font> ===
 
=== <font color = "green"> Avisos: </font> ===
−
-    Data de Início das aulas: 08/março
 
  
−
=== <font color = "green"> Avaliação: </font> ===
+
'''- Notas da Recuperação no link "Notas"'''
  
−
3 Provas de igual peso:
+
- Disponíveis notas finais e frequência no link "Notas"
  
−
05 de maio
+
- Revisão de provas: dia 22/6 (das 14 as 16h) ou dia 27/6 (das 14 as 16h) na sala da professora (4-201)
  
−
02 de junho
+
=== <font color = "green"> Prova de Recuperação: </font> ===
  
−
30 de junho
+
'''Dia 3 de agosto, 4a. feira, 19h, Sala 3-012'''
  
 +
Apenas alunos com frequência mínima de 70% e média mínima 3,0 poderão fazer a Rec, conforme norma da USP.
  
−
Seja MP a média aritmética das 3 provas, e seja CF o conceito final.
+
=== <font color = "green"> Avaliação: </font> ===
  
−
CF = A se 8 MP 10;
+
3 Provas:
  
−
CF = B se 7 MP< 8;
+
P1: 1o. de abril (peso 1)
  
−
CF = C se 5 MP <7;
+
P2: 13 de maio (peso 2)
  
−
CF = R, caso contrário.
+
P3: 17 de junho (peso 3)
  
−
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.
+
Média Final = (P1 + (P2 * 2) + (P3 * 3)) / 6
  
−
=== <font color = "green"> Aula a aula: </font> ===
+
<!--Seja MP a média aritmética das 3 provas, e seja CF o conceito final. -->
  
−
#- ''10 Mar'' – Apresentação da Disciplina (Prof. João Luis Rosa)
+
Será exigida frequência em 70% das aulas ministradas (incluindo dias de provas).
−
#-'' 17 Março'' – Noções de Complexidade
 
−
#- ''24 Março'' – Conceitos de Linguagens Formais. Autômatos Finitos (1)
 
−
#- ''31 Março'' – Semana Santa - não há aula
 
−
#- ''7 Abril'' -  Autômatos Finitos Determinísticos e Não-Determinísticos (2)
 
−
#- ''14 Abril'' - Expressões Regulares e Propriedades (Lema do Bombeamento)
 
−
#- ''28 Abril'' - '''1a. Prova'''
 
−
#- ''5 Maio'' – Propriedades de Decisão das LR. Minimização de AF.
 
−
#- ''12 Maio'' - Gramáticas Livres de Contexto e Autômatos a Pilha
 
−
#- ''19 Maio'' -  Linguagens Livres de Contexto
 
−
#- ''26 Maio'' - '''2a. Prova'''
 
−
#- ''2 Junho'' -  Indecidibilidade e Máquinas de Turing
 
−
#- ''9 Junho'' -  Poder Computacional das Máquinas de Turing
 
−
#- ''16 Junho'' -  Indecidibilidade
 
−
#- ''23 Junho'' - Intratabilidade
 
−
#- ''30 Junho'' - '''3a. Prova'''
 
  
−
=== <font color = "green"> Slides das Aulas </font> ===
+
=== <font color = "green"> Material HTML de Referência </font> ===
  
−
<!-- como colocar arquivo:  [[Arquivo:Teste.pdf]] -->
+
* [http://www.icmc.usp.br/~gracan/teoria/Teoria.html Tópicos em Teoria da Computação]
−
'''Aula 1 - 17/3/2010''' - Análise de Algoritmos:
 
  
−
[[Arquivo:Analisealgoritmos1.pdf]]
+
=== <font color = "green"> Aula a aula: </font> ===
  
−
[[Arquivo:Analisealgoritmos2.pdf]]
+
#- ''25 fev'' - Apresentação do curso; Procedimentos e Algoritmos
 +
#- ''4 mar'' - Provando propriedades de procedimentos; Complexidade de Algoritmos
 +
#- ''11 mar''- Complexidade de Algoritmos; Problemas Tratáveis e Intratáveis
 +
#- ''18 mar'' - Problemas P e NP
 +
#- ''25 mar'' - Máquinas de Turing (1)
 +
#- ''01 abr'' - 1a. Prova (peso 1)
 +
#- ''8 abr'' - Correção da prova e Máquinas de Turing (2)
 +
#- ''15 abr'' - cont. Máquinas de Turing (2)
 +
#- ''29 abr'' - Computabilidade e Decidibilidade
 +
#- ''06 mai'' - Linguagens e Gramáticas - Hierarquia de Chomsky
 +
#- ''13 mai'' - 2a. Prova (peso 2)
 +
#- ''20 mai'' - Linguagens Livres de Contexto (cont.)
 +
#- ''27 mai'' - Linguagens Regulares
 +
#- ''3 jun'' - Autômatos Finitos
 +
#- ''10jun'' - Automatos com Pilha & LLC; Aut. Linearmente Limitado & LSC
  
−
'''Aula 2 - 24/3/2010'''
+
=== <font color = "green"> Slides Extras das Aulas </font> ===
  
−
Tipos de Prova de Teoremas:
+
<!-- como colocar arquivo: [[Arquivo:Teste.pdf]] -->
  
−
[[Arquivo:Tiposdeprova.pdf]]
+
Aula 2: Análise de Algoritmos:  
  
−
Conceitos Básicos - Linguagens e Problemas:
+
[[Arquivo:Analisealgoritmos1.pdf]]
  
−
[[Arquivo:ConceitosBasicos.pdf]]  
+
[[Arquivo:Analisealgoritmos2.pdf]]
  
−
Automatos Finitos Determinísticos:
+
Aulas 3 e 4: Complexidade de Algoritmos e Problemas P e NP:  
  
−
[[Arquivo:AFD.pdf]]
+
[[Arquivo:Complexidade_Graça.pdf]]
  
−
'''Aula 3 - 06/4/2010'''
+
[[Arquivo:ConceitosBasicosx.pdf]]
  
−
Automatos Finitos Não-Determinísticos:
+
Aula 5: Máquinas de Turing (1)
  
−
[[Arquivo:AulaAFND.pdf]]
+
[[Arquivo:AulaMaquinadeTuring.pdf]]
  
−
'''Aula 4 - 13/4/2010'''
+
Aulas 7 e 8: cont. Máquinas de Turing (2)
  
−
Expressões Regulares:
+
[[Arquivo:Aula2MT.pdf]]
  
−
[[Arquivo:ERLinguagens.pdf]]
+
Aula 9: Computabilidade e Decidibilidade
  
−
Propriedades de Linguagens Regulares:
+
[[Arquivo:CompeDecid.pdf]]
  
−
[[Arquivo:PropriedadesLRx.pdf]]
+
Aulas 10, 12, 13: Linguagens e Gramáticas - Hierarquia de Chomsky
  
−
Minimização de Autômatos Finitos:
+
[[Arquivo:LingGramaticas.pdf]]
  
−
[[Arquivo:MinimizacaoAFD.pdf]]
+
Aula 14: Automatos Finitos (LR)
  
−
'''Aula 5 - 12/5/2010'''
+
[[Arquivo:AFinitos.pdf]]
  
−
Gramáticas Livres de Contexto
+
Aula 15: Automatos a Pilha(LLC) e Automatos Linearmente Limitados (LSC)
  
−
[[Arquivo:GLC.pdf]]
+
[[Arquivo:APeALL2011.pdf]]
  
−
Autômatos a Pilha
+
=== <font color = "green"> Links para Leituras Complementares </font> ===
  
−
[[Arquivo:GNACPx.pdf]]
+
Livro Algorithms and Complexity, by Herbert S. Wilf, 1994, 1st Edition: http://www.math.upenn.edu/~wilf/AlgComp3.html
  
−
'''Aula 6 - 19/5/2010'''
+
=== <font color = "green"> Listas de Exercícios </font> ===
 +
 +
Lista de Exercícios sobre Análise de Algoritmos: [[Arquivo:ListaAnaliseAlgoritmos.pdf]]
  
−
Propriedades das Linguagens Livres de Contexto
+
Lista de Exercícios sobre Máquinas de Turing: [[Arquivo:ListaMaquinaTuring2011.pdf]]
  
−
[[Arquivo:PropLLC.pdf]]
+
Lista de Exercícios sobre Gramáticas Livres de Contexto: [[Arquivo:ListaGLC.pdf]]
  
−
'''Aula 7 - 26/5/2010'''
+
Lista de Exercícios sobre Gramáticas Regulares: [[Arquivo:ListaGR.pdf]]
  
−
Gramáticas
+
Lista de Exercícios sobre Automatos Finitos: [[Arquivo:ListaAFs.pdf]]
  
−
[[Arquivo:Gramaticas.pdf]]
+
Lista de Exercícios sobre Automatos a Pilha: [[Arquivo:ListaAP2011.pdf]]
  
−
'''Aulas 8 e 9 - 09 e 16/06/2010'''
+
<!--- 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]]-->
  
−
Decidibilidade e Máquinas de Turing
+
=== <font color = "green"> Notas </font> ===
−
 
 
−
[[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> ===
+
Notas Recuperação (3/8/2011): [[Arquivo:NotasRec.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]
 
−
 
−
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> ===
 
−
 
−
- 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]]
 
−
 
−
=== <font color = "green"> Notas </font> ===
 
  
−
- Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]]
+
<!--Notas Finais e Frequência (21/6/2011): [[Arquivo:NotasITCSCC505.pdf]]-->

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

SCC-505 - INTRODUÇÃO À TEORIA DA COMPUTAÇÃO

  • Local: Sala (5003) - Horário: SEXTA - 19 - 20:40h
  • 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, 1979.

  • Hopcroft, J. E., Ullman, J. D. and Motwani, R. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da 2a. edição.

Editora Campus, 2001.

  • Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.

3rd. edition. Addison-Wesley, 2007.

  • 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 Recuperação no link "Notas"

- Disponíveis notas finais e frequência no link "Notas"

- Revisão de provas: dia 22/6 (das 14 as 16h) ou dia 27/6 (das 14 as 16h) na sala da professora (4-201)

Prova de Recuperação:

Dia 3 de agosto, 4a. feira, 19h, Sala 3-012

Apenas alunos com frequência mínima de 70% e média mínima 3,0 poderão fazer a Rec, conforme norma da USP.

Avaliação:

3 Provas:

P1: 1o. de abril (peso 1)

P2: 13 de maio (peso 2)

P3: 17 de junho (peso 3)


Média Final = (P1 + (P2 * 2) + (P3 * 3)) / 6


Será exigida frequência em 70% das aulas ministradas (incluindo dias de provas).

Material HTML de Referência

Aula a aula:

  1. - 25 fev - Apresentação do curso; Procedimentos e Algoritmos
  2. - 4 mar - Provando propriedades de procedimentos; Complexidade de Algoritmos
  3. - 11 mar- Complexidade de Algoritmos; Problemas Tratáveis e Intratáveis
  4. - 18 mar - Problemas P e NP
  5. - 25 mar - Máquinas de Turing (1)
  6. - 01 abr - 1a. Prova (peso 1)
  7. - 8 abr - Correção da prova e Máquinas de Turing (2)
  8. - 15 abr - cont. Máquinas de Turing (2)
  9. - 29 abr - Computabilidade e Decidibilidade
  10. - 06 mai - Linguagens e Gramáticas - Hierarquia de Chomsky
  11. - 13 mai - 2a. Prova (peso 2)
  12. - 20 mai - Linguagens Livres de Contexto (cont.)
  13. - 27 mai - Linguagens Regulares
  14. - 3 jun - Autômatos Finitos
  15. - 10jun - Automatos com Pilha & LLC; Aut. Linearmente Limitado & LSC

Slides Extras das Aulas

Aula 2: Análise de Algoritmos:

Arquivo:Analisealgoritmos1.pdf

Arquivo:Analisealgoritmos2.pdf

Aulas 3 e 4: Complexidade de Algoritmos e Problemas P e NP:

Arquivo:Complexidade Graça.pdf

Arquivo:ConceitosBasicosx.pdf

Aula 5: Máquinas de Turing (1)

Arquivo:AulaMaquinadeTuring.pdf

Aulas 7 e 8: cont. Máquinas de Turing (2)

Arquivo:Aula2MT.pdf

Aula 9: Computabilidade e Decidibilidade

Arquivo:CompeDecid.pdf

Aulas 10, 12, 13: Linguagens e Gramáticas - Hierarquia de Chomsky

Arquivo:LingGramaticas.pdf

Aula 14: Automatos Finitos (LR)

Arquivo:AFinitos.pdf

Aula 15: Automatos a Pilha(LLC) e Automatos Linearmente Limitados (LSC)

Arquivo:APeALL2011.pdf

Links para Leituras Complementares

Livro Algorithms and Complexity, by Herbert S. Wilf, 1994, 1st Edition: http://www.math.upenn.edu/~wilf/AlgComp3.html

Listas de Exercícios

Lista de Exercícios sobre Análise de Algoritmos: Arquivo:ListaAnaliseAlgoritmos.pdf

Lista de Exercícios sobre Máquinas de Turing: Arquivo:ListaMaquinaTuring2011.pdf

Lista de Exercícios sobre Gramáticas Livres de Contexto: Arquivo:ListaGLC.pdf

Lista de Exercícios sobre Gramáticas Regulares: Arquivo:ListaGR.pdf

Lista de Exercícios sobre Automatos Finitos: Arquivo:ListaAFs.pdf

Lista de Exercícios sobre Automatos a Pilha: Arquivo:ListaAP2011.pdf


Notas

Notas Recuperação (3/8/2011): Arquivo:NotasRec.pdf


Disponível em "http://wiki.icmc.usp.br/index.php?title=SCC-505(gracan)&oldid=19212"