Scc-205(gracan)A

Índice

1 SCC-205 - TEORIA DA COMPUTAÇÃO E LINGUAGENS FORMAIS (TURMA A)
2 Avisos:
3 Bibliografia Básica
4 BIBLIOGRAFIA COMPLEMENTAR
5 Material HTML de Referência
6 Avaliação:
7 Frequência:
8 Aula a aula:
9 Slides das Aulas
10 Listas de Exercícios
11 Novas Listas de Exercícios com Gabarito
12 Notas
13 Gabaritos
14 Links para Leituras Complementares

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

Local: Sala (4-003) - Horários: TERÇAS E QUINTAS - 10:10 - 11:50h

Profa. Graça Nunes; gracan [arroba] icmc.usp.br; Sala: 4-201

Avisos:

Notas da 3a. prova divulgadas no link "Notas" (28/11/2011)

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.

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.

Material HTML de Referência

Tópicos em Teoria da Computação

Avaliação:

3 Provas:

P1: 13 de setembro

P2: 20 de outubro

P3: 24 de novembro

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

Obs.: Haverá uma prova substitutiva, no dia 1o. de dezembro, que necessariamente substitui a menor nota das provas anteriores.

Frequência:

Será exigida frequência em 70% das aulas ministradas (incluindo dias de provas). Abono de falta só ocorrerá com apresentação de atestado médico na próxima aula em que comparecer.

Aula a aula:

- 2/8 Organização do Curso; Critério de Avaliação; Motivação para o Curso
- 4/8 Visão Geral das Teorias tratadas no Curso – objetivos de estudo
- 9/8 Definição formal de procedimento e algoritmo. Verificação de Término.
- 11/8 Análise de complexidade de algoritmos (recordação)
- 16/8 Vocabulários, Cadeias, Linguagens, Reconhecedores e Gramáticas: Definições e Exemplos
- 18/8 Problemas X Linguagens. Computabilidade: a Tese de Church-Turing.
- 23/8 Máquinas de Turing (1)
- 25/8 Máquinas de Turing (1)cont.
- 30/8 Máquinas de Turing (1)cont.
- 1/9 Máquinas de Turing (2)Teoremas
- 5 a 10/9 (S.Patria) - não há aulas
- 13/9 1ª. Prova
- 15/9 Linguagens Decidíveis e Indecidíveis: a propriedades da parada e do algoritmo. O processo de redução
- 19 a 23/9 (Semana da Computação) - não há aulas
- 27/9 Teoria da Tratabilidade: problemas P e NP
- 29/9 Teoria da Tratabilidade: problemas P e NP
- 4/10 Hierarquia de Chomsky; Gramáticas Irrestritas e Linguagens Recursivamente Enumeráveis; Gramáticas e Linguagens Sensíveis ao Contexto: definições e exemplos
- 6/10 Linguagens e Gramáticas Livres de Contexto (1): definições e exemplos
- 11/10 Linguagens e Gramáticas Livres de Contexto (2)
- 13/10 Linguagens e Gramáticas Regulares (1): definições e exemplos
- 18/10 Autômatos Finitos e LR (1): definições e exemplos
- 20/10 2ª. Prova
- 24 a 28/10 (afastamento da professora)- não há aulas
- 1/11 Autômatos Finitos Não-Determinísticos
- 2 a 4/11 (Finados e Aniversário de São Carlos)- não há aulas
- 8/11 AFD & AFND; AFs e GRs
- 10/11 Implementação de AFs e Lema do Bombeamento para LR
- 17/11 Autômatos a Pilha & LLC
- 22/11 Propriedades de LLCs; Automatos Linearmente Limitados & LSC
- 24/11 3ª. Prova
- 1/12 Substitutiva (necessariamente substitui menor nota)