Professor responsável

• Paulo Fonseca

Monitor

• Mateus Alves da Silva (mas8)

Horário e sala

• Quarta-feira 13h-15h (Sala D005)
• Sexta-feira 13h-15h (Sala D005)

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

Básica

1. Michael Sipser. Introdução à Teoria da Computação, Cengage Learning, 2007.

Suplementar

1. John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman. Introdução à Teoria dos Autômatos, Linguagens e Computação, Ed. Campus, 2002
2. Harry R. Lewis, Christos Papadimitriou. Elements of the Theory of Computation (2nd Ed.), Prentice-Hall, 1998
3. Dexter Kozen. Automata and Computability, Springer, 1997
4. Christos Papadimitriou. Computational Complexity, Addison Wesley, 1994

Avaliação

Três unidades, cada unidade correspondendo a uma parte da ementa. A média do curso (MC) será calculada como

MC = (M1+M2+M3) / 3

A média de cada unidade (M1, M2, M3) será dada por uma prova escrita obrigatória, com nota de 0 a 10, mais atividades extras de monitoria que podem somar até 1 (um) ponto extra à média da unidade.

Segunda chamada

• Sobre todo o conteúdo da disciplina
• Mediante solicitação formal junto à Secretaria de graduação

Ética acadêmica

Os alunos são encorajados a discutirem entre si e aprenderem uns com os outros, porém não é permitido compartilhar os trabalhos total ou parcialmente. Os alunos devem proteger o sigilo dos seus trabalhos, com atenção especial a códigos depositados em repositórios públicos (e.g. GitHub, PasteBin, etc). O plágio não será tolerado e trabalhos contendo cópia irregular terão nota zero, independente de quem tenha sido o autor original.

Exercícios selecionados