Scc-205(sandra)B

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.

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

1. - 4/8 Visão Geral da Teoria da Complexidade Arquivo:AulaT Complex 2011.pdf
2. - 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