SCC-505(gracan)

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

• Tópicos em Teoria da Computação

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