TEORIA DA COMPUTAÇÃO - 54685-02 - PPGCC

Semestre 2019/2

Professor Responsável: Ney Laert Vilar Calazans
Turma: 1
Sala: 516, Prédio 32
Horário: 4AB (das 8:00 às 9:40)

Cursos: Mestrado/Doutorado em Computação - PPGCC
ESCOLA POLITÉCNICA - PUCRS

Índice desta Página

Conteúdos das Aulas
Bibliografia
Avaliação - Em elaboração
Material de Apoio - Em elaboração
Programa da Disciplina

Avisos Importantes

20/08/19 - Disponibilizado gabarito da Prova P2, ver aqui ou na parte de Conteúdos, no dia da prova.
05/08/19 - Disponibilizada versão revisada da Apresentação sobre Parte I do livro do Cohen, ver abaixo em Material de Apoio
20/08/19 - Homepage atualizada para o semestre 2019/2.

Conteúdo das Aulas

Aula	Dia	Data	Hora	Descrição	Atividade	Recursos
1	QUA	14/08/2019	AB	Capítulos 1 e 2 do Cohen: Pano de Fundo e Linguagens.	Aula
2	QUA	21/08/2019	AB	Capítulos 3 e 4 do Cohen: Definições Recursivas e Expressões Regulares	Aula
3	QUA	28/08/2019	AB	Capítulos 5, 6 e 7 do Cohen: Autômatos Finitos, Grafos de Transição	Aula
4	QUA	04/09/2019	AB	Capítulos 7, 8, 9, 10, 11 e 12 do Cohen: Teorema de Kleene, Autômatos Finitos com Saída, Linguagens Regulares, Linguagens Não-Regulares, Decidibilidade	Aula
5	QUA	11/09/2019	AB	Revisão dos Capítulos 11 e 12 do Cohen: Linguagens Não-Regulares, Decidibilidade Parte II do Cohen: Teoria de Autômatos de Pilha Capítulos 13 e 17: Gramáticas Livre do Contexto e Autômatos de Pilha	Aula
6	QUA	18/09/2019	AB	Parte III do Cohen: Teoria de Turing Capítulos 24 e 25 e 26: Máquinas de Turing, Máquinas de Post	Aula
7	QUA	25/09/2019	AB	Parte III do Cohen: Teoria de Turing Capítulo 26: Teorema de Minsky	Aula
8	QUA	02/10/2019	AB	Aula de Exercícios, preparação para Prova P1	Aula
9	QUA	09/10/2019	AB	Prova P1: Versão A e Versão B	Prova
10	QUA	16/10/2019	AB	Capítulos 28, 30: Linguagens Recursivamente Enumeráveis, Hierarquia de Chomsky	Aula
11	QUA	23/10/2019	AB	Capítulos 30 e 31: Hierarquia de Chomsky e Computadores	Aula
12	QUA	30/10/2019	AB	Complexidade Computacional: Introdução Algumas apresentações sobre o tema 1) Introdução a Complexidade Computacional de Lance Fortnow (Un. of Michigan, 2006) 2) Teoria da Compexidade: A Questão P versus NP de Guppta & Lafferty (Un. Carnegie-Mellon)	Aula
13	QUA	06/11/2019	AB	Complexidade Computacional: Crescimento Assintótico Cap. 3 de Cormen et al. Cap. 1 de Garey & Johnson	Aula
14	QUA	13/11/2019	AB	Complexidade Computacional: Problemas e Classes Problemas de Decisão, Máquinas de Turing e a Classe P Cap. 2 de Garey & Johnson (até Seção 2.2)	Aula
15	QUA	20/11/2019	AB	Complexidade Computacional: Problemas e Classes A Classe NP Cap. 2 de Garey & Johnson (a partir da Seção 2.3)	Aula
16	QUA	27/11/2019	AB	Aula de Exercícios, preparação para Prova P2	Aula
17	QUA	04/12/2019	AB	Prova P2	Prova
	QUA	11/12/2019	AB		Aula

Bibliografia

BÁSICA

1. Cohen, D. I. A. Introduction to computer theory. Wiley & Sons, Inc. Revised Printing, 1991. Registro 004 C678ia.

2. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Bell Tel. Labs, 1979.

3. T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 3^rd edition, 2009.

COMPLEMENTAR

1. D. Harel. Algorithmics: The Spirit of Computing, 3^rd edition, 2004.

2. Michael Sipser, Introduction to the Theory of Computation, 2^nd edition, 2006.

3. Lewis, Papadimitriou. Elements of the Theory of Computation, 1981.

4. Aho, Alfred V. Foundations of computer science. Computer Science Press, 1998. Registro 004 A286fb.

Avaliação

Grau Final= (P1+P2)/2

Material de Apoio

1. Apresentação sobre a Parte I do Livro do Cohen (Referência Bibliográfica 4)

2. Apresentação sobre Partes II e III do Livro do Cohen (Referência Bibliográfica 4)

This page was last updated on December, 20th, 2019.

If you find problems in this page, please send an e-mail to ney.calazans at pucrs.br.
We will fix it in the shortest possible delay. Thanks for your help!