Mudanças entre as edições de "SCC-505(gracan)"
(→Listas de Exercícios) |
(→Listas de Exercícios) |
||
| Linha 113: | Linha 113: | ||
Lista de Exercícios sobre Gramáticas Regulares: [[Arquivo:ListaGR.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 Finitos: [[Arquivo:ListaAFs.pdf]] |
Edição das 14h32min de 30 de maio de 2011
Índice
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:
- Data de Início das aulas: 21/fevereiro
- Notas da 1a. Prova: divulgadas em 2/4/2011: seção Notas
- ATENÇÃO: As notas da 1a. prova foram corrigidas de modo a considerar correta a questão 1.B, qualquer que fosse a alternativa escolhida, dado que mais de uma alternativa estava correta. Verifique sua nota novamente no link NOTAS.
- Disponível o gabarito da 2a. Prova no link "Gabaritos"
- Disponíveis notas da 2a. Prova no link "Notas"
Avaliação:
3 Provas:
P1: 1o. de abril (peso 1)
P2: 13 de maio (peso 2)
P3: 17 de junho ou 1o. de julho (24 de junho não tem aula) (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:
- - 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
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
Aula 5: Máquinas de Turing (1)
Arquivo:AulaMaquinadeTuring.pdf
Aulas 7 e 8: cont. Máquinas de Turing (2)
Aula 9: Computabilidade e Decidibilidade
Aulas 10, 12, 13: Linguagens e Gramáticas - Hierarquia de Chomsky
Aula 14: Automatos Finitos
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
Notas
Notas da 1a. e 2a. Provas (19/5/2011): Arquivo:NotasITCSCC505.pdf
Gabaritos
Gabarito da 2a. Prova: Arquivo:GabaritoProva2.pdf
