Professor

   Fred Freitas

Horário e sala

   Terca-feira 08h00 - 10h00 (Niate – 2º andar)

   Quinta-feira 10h00 - 12h00 (Niate – 2º andar)

Monitores

Ementa

   PARTE I - Linguagens formais e autômatos:
Autômatos finitos determinísticos (AFD) / Autômatos finitos não-determinísticos (AFN) / Linguagens regulares (proprieades e operações) / Expressões regulares (ER) / Equivalência AFD<=>AFN<=>ER / Linguagens não-regulares (Lema do bombeamento) / / Gramáticas Livres de Contexto (GLC) / Linguagens Livres de Contexto (proprieades e operações) / Ambiguidade de normalização de GLCs / Autõmatos com Pilha (AP) / Equivalência GLC<=>AP / Linguagens não-livres de contexto (Lema do bombeamento)

   PARTE II - Teoria da Computabilidade:
Máquinas de Turing (MT) / Variações das MT / Não-determinismo / Tese de Church-Turing / Linguagens recursivas e recursivamente enumeráveis / Decidibilidade / O Problema da Parada / Teorema de Rice / Redutibilidade.

   PARTE III - Teoria da Complexidade:
Complexidade de Tempo / Classes de complexidade / Redução polinomial / P vs. NP / NP-completude / Teorema de Cook-Levin / Complexidade de Espaço / Teorema de Savitch / PSPACE-completude.

Bibliografia

Bibliografia básica

1.     Michael Sipser. Introdução à Teoria da Computação, Cengage Learning, 2007, ISBN 8522104999.
(Tradução brasileira da 2ª. Ed. Norte-americana de Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 2005 )

Bibliografia Suplementar

1.     John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman. Introdução à Teoria dos Autômatos, Linguagens e Computação, Editora Campus, Outubro 2002, ISBN 85-352-1072-5.
(Tradução brasileira de: John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 2nd Ed., Addison-Wesley, 2001, ISBN: 0-201-44124-1. - Página de apoio )

2.     Harry R. Lewis, Christos Papadimitriou. Elements of the Theory of Computation (2nd Ed.), Prentice-Hall, 1998, ISBN: 0-13-262478-8.

3.     Dexter Kozen. Automata and Computability, Springer, 1997, ISBN: 0-387-94907-0.

4.     Christos Papadimitriou. Computational Complexity, Addison Wesley, 1994, ISBN: 0-201-53082-1.

Avaliação

A avaliação será feita em duas unidades. A média do curso (MC) será calculada como

MC = (M1+M2) / 2

onde:

   M1 = Média da 1a. Unidade

   M2 = Média da 2a. Unidade

A média de cada unidade será calculada a partir das notas de duas provas escritas, cada uma valendo 50% da média da unidade.

Segunda chamada

Ao final de cada unidade será realizada uma prova de segunda chamada que versará sobre todo o assunto da unidade. A segunda chamada só poderá ser realizada mediante solicitação formal junto a secretaria e só será deferida se a falta for devidamente justificada com documentação apropriada, conforme a Resolução n° 04/1994 .

Prova final

Se MC >= 7, o aluno está aprovado por média.

Se MC < 3, o aluno está reprovado por média.

Se 3 <= MC < 7, o aluno deverá fazer uma prova final (PF).

A prova final versará sobre o assunto de todo o curso.

A média final será calculada como

MF = (MC + PF) / 2.

Se MF >= 5, o aluno está aprovado.

Se MF < 5, o aluno está reprovado.

IMPORTANTE: As provas serão discutidas posteriormente (em horário a ser definido) e os alunos poderão solicitar revisão. Entretanto, não há margem "extra" de tolerância quanto às médias.

Podem ser oferecidas, no contexto da disciplina, atividades de monitoria fora do horário de aula mencionado acima. Essas atividades têm caráter complementar e de reforço e a participação dos alunos é altamente recomendada. Entretanto, a participação nessas aulas é opcional e não contam para efeito de contabilização de frequência.

Slides/notas de aula

Aula	Slides	Material suplementar
Aula 1	Alfabetos e linguagens	Motivação: Problemas de Decisão O Entscheidungsproblem Exibição do trailer do filme "Julia Robinson and Hilbert's Tenth Problem"
Aula 2	Autômatos finitos determinísticos e linguagens regulares	Autômatos finitos Linguagens regulares
Aula 3	Operações com linguagens regulares
Aula 4	Autômatos finitos não-determinísticos	Autômatos finitos não-determinísticos
Aula 5	Parte 1: De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos Parte 2: Fecho sob operações regulares (concatenação, estrela)
Aula 6	Parte 1: Expressões regulares Parte 2: Comversão ER <-> AF	Expressões Regulares
Aula 7	Linguagens Não-Regulares / Lema do Bombeamento	Lema do Bombeamento
Aula 8	Gramáticas Livre de Contexto  / Ambigüidade em gramáticas	Ambigüidade em gramáticas
Aula 9	Autômatos com Pilha / Autômatos com Pilha versus Gramáticas Livres-do-Contexto	Autômatos com pilha
Aula 10	Máquinas de Turing / Linguagens Turing-reconhecíveis	Máquinas de Turing Linguagens Turing-reconhecíveis
Aula 11	Variantes de Máquinas de Turing (várias fitas)
Aula 12	Máquinas de Turing Não-Determinísticas / Enumeradores
Aula 13	Decidibilidade	Decidibilidade
Aula 14	O Problema da Parada	O Problema da Parada
Aula 15	Redutibilidade	Redutibilidade
Aula 16	Redução por Histórias de Computação / PCP	Problema da Correspondência de Post
Aula 17	Complexidade de Tempo	Complexidade de Tempo Classe de Complexidade Complexity Zoo
Aula 18	P vs. NP	A Classe P A Classe NP P vs. NP
Aula 19	NP-completude	Redução Polinomial NP-completude SAT
Aula 20	Complexidade de Espaço	A Classe PSPACE Teorema de Savitch
Aula 21	PSPACE-completude

Provas