Scc-205(sandra)B

De CoteiaWiki

SCC-205 - TEORIA DA COMPUTAÇÃO E LINGUAGENS FORMAIS (TURMA B)

  • Local: Sala (4-005) - Horários: TERÇAS E QUINTAS - 10:10 - 11:50h
  • Profa. Sandra Aluisio; sandra [arroba] icmc.usp.br; Sala: 4-208

Material de Referência

http://wiki.icmc.usp.br/index.php/Scc-205(sandra)#Links_no_MERLOT

Material de Apoio do Livro Texto de Ramos, Neto & Vega, 2009 (Linguagens Formais: Teoria, Modelagem e implementação): [1]

LIVROS TEXTOS

  • Rosa, J.L.G. Linguagens Formais e Autômatos. Editora LTC, 2010.
  • Hopcroft, Motwani & Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001. Errata do livro em: http://www-db.stanford.edu/~ullman/ialc.html#errata.
  • Marcus Vinícius Midena Ramos, João José Neto & Ítalo Santiago Veja: Linguagens Formais - Teoria, Modelagem e Implementação, Editora: Bookman, 2009.
  • Divério & Menezes. Teoria da Computação – Máquinas Universais e Computabilidade. Série Livros Didáticos 5, IF UFRGS, 2ª edição, 2000, editora SagraLuzzatto.
  • Menezes, P.B. Linguagens Formais e Autômatos. Série Livros didáticos 3, IF UFRGS, 5ª edição, 2008, Editora Bookman. e-Book de Linguagens Formais & Autômatos.
  • Sipser, M. Introduction to the Theory of Computation. PWS, 1997. (2a edição). Errata do livro em: http://www-math.mit.edu/~sipser/itoc-errs1.2.html
  • Harel, D. Algorithmics – The Spirit of Computing. Addison-Wesley Publishing Company, 1992 (2ª edição). (Existem 3 edições similares do livro na Biblioteca do ICMC: a primeira, a sua versão reduzida e a segunda edição que traz exercícios).

BIBLIOGRAFIA COMPLEMENTAR

  • Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1995. (Biblioteca Central).
  • Cormen, T.H. Leiserson, C.E. and Rivest, R.L. Introduction to Algorithms. The Mit Press. 1990. (1ª edição). Capítulos 1, 2, 3, 4, 36, 37.
  • Savage, J.E. Models of Computation – Exploring the Power of Computing. Addison-Wesley, 1998.
  • Toscani & Veloso. Complexidade de Algoritmos. Série Livros Didáticos 13, IF UFRGS, 1ª edição, 2001, editora SagraLuzzatto.
  • Garey & Johnson. Computers and Intractability – a guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
  • Jones, N. D. Computability and complexity – from a Programming Perspective. The Mit Press, 1997.
  • Drobot, V. Formal Languages and Automata Theory. Computer Science Press, 1989.
  • Sedgewick, R. and Flajolet, P. An Introduction to the Analysis of algorithms. Addison-Wesley P. Company, 1996.
  • Sudkamp, T. A. Languages and Machines – An Introduction to the Theory of Computer Science, 2a edition. Addison-Wesley, 1998.
  • Kozen, D.C. Automata and Computability. Springer-Verlag, 1997.

Avisos: Média FINAL e FREQUÊNCIAS disponível. Houve reprovação por FALTAS.
REC dia 13/2/2012 das 14-16 h SALA 3011.

Avaliação:

3 Provas:

P1: 13 de setembro

P2: 20 de outubro

P3: 24 de novembro

SUB: 1/12 (necessariamente substitui a menor nota das provas anteriores)

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

Frequência:

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

Aula a aula:

  1. - 2/8 Organização do Curso; Critério de Avaliação; Motivação para o Curso Arquivo:Apres Curso SCC 205 2011.pdf
  2. - 2/8 Visão Geral da Teoria das LF e Automatos: Arquivo:AulaT LFA 2011.pdf
  3. - 4/8 Visão Geral da Teoria da Complexidade Arquivo:AulaT Complex 2011.pdf
  4. - 4/8 Visão Geral da Teoria da Computabilidade Arquivo:AulaT Comp 2011.pdf
  1. - 9/8 Gramáticas 0 Arquivo:Gramatica0 SCC 205.pdf
  2. - 11/8 Gramáticas 1 Arquivo:Gramatica1 SCC 205.pdf
  1. - 16/8 Gramáticas 2 Arquivo:Gramatica2 SCC 205.pdf
  2. - 16/8 Exercícios Resolvidos de Gramáticas Arquivo:Exer resolvidos G SCC 205.pdf
  3. - 18/8 Gramáticas 3 Arquivo:Gramatica3 205.pdf
  1. - 23/8 Gramáticas 4 Arquivo:Gramatica4 205.pdf
  2. - 23/8 Exercícios Resolvidos de Gramáticas Ambíguas Arquivo:Exer resolvidos GLC 205.pdf
  1. - 25/8 Autômatos Finitos Determinísticos (AFD) Arquivo:Aut1.pdf
  1. - 30/8 Autômatos Finitos Não Determinísticos (AFND) Arquivo:Aut2.pdf
  2. - 30/8 Autômatos Finitos ND com movimentos Nulos (AFND-lambda) Arquivo:Aut3 SCC 205 2011.pdf
  3. - 30/8 Exercícios Resolvidos sobre Autômatos Arquivo:Exer resolvidos A.pdf
  1. - 1/9 Expressões Regulares Arquivo:ER1 205 2011 .pdf
  2. - Vejam soluções do livro do H,M,U, 2001: http://infolab.stanford.edu/~ullman/ialcsols/sols.html

-- Prova 1 até aqui

  1. - 15/9 Operações Fechadas sobre LR Arquivo:Aut4.pdf
  1. - 27/9 Expressões Regulares 2 Arquivo:ER2 205 2011.pdf
  2. - 27/9 Lema do Bombeamento LR Arquivo:LB 2011.pdf
  1. - 29/9 ACP 1Arquivo:ACP parte1 2011.pdf
  1. - 4/10 ACP 2Arquivo:ACP parte2 SCC 205 2011.pdf
  2. - 6/10 MT 1Arquivo:MT1 SCC 205 2011.pdf
  1. - 11/10 MT 2 Arquivo:MT2 SCC 205 2011.pdf
  2. - 11/10 Pumping Lemma para LLC - PROVA Arquivo:Pumping Lema LLC prova.pdf
  3. - 11/10 Pumping Lemma para LLC - JOGO no JFLAP Arquivo:Pumping Lema LLC jogo.pdf
  1. - 13/10 MT 3 Arquivo:MT3 SCC 205 2011.pdf
  2. - 13/10 Alguns Exercícios Resolvidos sobre MT Arquivo:Ex resol MT SCC 205 2011.pdf

Teoria da Computabilidade: slides de suporte http://www.cs.virginia.edu/~evans/cs302/classes/

  1. - 1/11 MT4 Arquivo:MT4 2011.pdf
  2. - 8/11 Problemas Indecidíveis e Parcialmente Decidíveis Arquivo:Ind dec SCC 205 2011.pdf
  1. - 17/11 Teoria da Complexidade: as classes P, NP, co-NP e NP completas Arquivo:Complex tempo SCC 205 2011.pdf


Listas de Exercícios

  1. - 16/8 Lista 1 Arquivo:Lista 1 205.pdf
  1. - 25/8 Lista 2 Arquivo:Lista 2 205.pdf
  1. - 10/10 Lista 3 Arquivo:Lista 3 205.pdf
  1. - 8/11 Lista 4 Arquivo:Lista 4 205.pdf


Notas

  1. - Notas Prova 1 Arquivo:P1 SCC 205.pdf


  1. - Notas Prova 2 Arquivo:P2 SCC 205.pdf


  1. - Notas Prova 3 Arquivo:SCC 205 2011 P3.pdf
  1. - Notas da SUB Arquivo:SCC 205 Notas 2011.pdf
  1. - MÉDIA FINAL e FREQUÊNCIAS Arquivo:Notas SCC 205 2011 7 12.rar
  1. - Notas da REC no JUPITER: Podem fazer revisão da prova na primeira semana de aula.
  2. - Nota de Vitor Simões: 5.5
Disponível em "http://wiki.icmc.usp.br/index.php?title=Scc-205(sandra)B&oldid=21791"