Teoria da Computação

A disciplina de Teoria da Computação apresenta os principais conceitos das três áreas centrais da teoria da computação, a saber: (i) a teoria dos autômatos, (ii) a teoria da computabilidade e (iii) a teoria da complexidade. Essas áreas buscam responder quais são as capacidades e limitações fundamentais dos computadores. Em cada uma das três áreas essa questão é interpretada de forma diferente e as respostas variam conforme a interpretação.

Programa

A disciplina aborda os seguinte tópicos:

  1. Noções e terminologia matemáticas
    Conjuntos, Sequências e tuplas, Funções e relações, Grafos, Cadeias (i.e., palavras) e linguagens, Lógica booleana, Definições, teoremas e provas, Tipos de provas.
  2. Teoria dos autômatos
    • Linguagens Regulares
      Autômatos finitos determinísticos, Autômatos finitos não-determinísticos, Expressões e linguagens regulares, Gramáticas regulares, Propriedades das linguagens regulares.
    • Linguagens Livres de Contexto
      Gramáticas livres de contexto, Autômatos de pilha, Propriedades das linguagens livres de contexto.
    • Linguagens Turing-decidíveis e Turing-reconhecíveis
      Definição da Máquina de Turing, Computando com máquinas de Turing, Extensões da máquina de Turing.
  3. Teoria da computabilidade
    A tese de Church-Turing, Variantes da máquina de Turing, Definição de algoritmo, Decidíibilidade, Redutibilidade.
  4. Teoria da Complexidade
    A classe P, A classe NP, NP-completo, Intratabilidade.

Bibliografia

O curso está baseado nos livros Introdução à Teoria de Autômatos, Linguagens e Computação [1], Introdução à Teoria da Computação [2], Linguagens Formais e Autômatos [3], Introdução aos Fundamentos da Computação: Linguagens e Máquinas [4] e na disciplina Automata Theory [5].

   

[1] Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory, Languages, and Computation. 3a edição. Editora Pearson, 2006.
[2] Sipser M. Introdução à Teoria da Computação. 2a edição. Editora Cengage Learning, 2015.
[3] Menezes P.B. Linguagens Formais e Autômatos. 6a edição. Editora Bookman, 2010.
[4] Vieira N.J. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. Editora Cengage Learning, 2015.
[5] Ullman J.D. Automata Theory (CSX0005). StanfordOnline – edx.org.