Sorry, this entry is only available in Brazilian Portuguese. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
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:
- 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. - 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.
- Linguagens Regulares
- Teoria da computabilidade
A tese de Church-Turing, Variantes da máquina de Turing, Definição de algoritmo, Decidíibilidade, Redutibilidade. - 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.