INF8281 – Teoria da Computação (2016.1)

Aulas são ministradas na UVA 18h20-20h20 Terças (604)

Material disponível no Portal do Aluno

Objetivo da Disciplina:

  • Propiciar conhecimento de Linguagens Formais e elementos de Teoria da Computação, bem como de suas aplicações em Sistemas de Informação. O papel desta disciplina é o de mostrar os formalismos envolvidos nas etapas de análise léxica e sintática de linguagens, bem como os fundamentos teóricos do processo de computação e suas limitações.

Ementa do Curso:

  • 1) Conceitos da teoria da computação
    • Introdução a teoria da computação
    • Quais problemas jamais poderão ser resolvidos por um computador, independente da sua velocidade ou memória?
    • Quais problemas podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar a solução impraticável?

  • 2) Problemática
    • Em que situações podem ser mais difícil resolver um problema?
    • Verificar cada uma das soluções manualmente?
    • Questões relativas aos requerimentos de tempo ou espaço (memória, em particular) de problemas específicos são investigadas pela teoria da complexidade computacional.

  • 3) Problemática II
    • Modelos genéricos de computação.
    • Expressões regulares.
    • Reconhecedores

  • 4) Recursividade
    • Aplicação da recursividade.
    • Teoria de Grafos
    • Compilador e Interpretador

Bibliografia:

  • Diverio, T.; Menezes, P. Teoria da Computação – Máquinas Universais e Computabilidade – 3ª Editora. – Vol. 5. Editora Bookman, 2011
  • Coelho, F., Pedro Neto, J. Teoria da Computação – Computabilidade e Complexidade. Editora Escolar, 2010.
  • Boolos, G.; Burgess, J.; Jeffrey, R. Computabilidade e Lógica. Editora Unesp, 2013.
  • Learning, T. Introdução à Teoria da Computação. 2ª Edição Norte Americana, 2012.
  • Menezes, P. Linguagens Formais e Autômatos – 6ª Edição. Editora Bookman, 2010.
  • Ullman, J.; Hopcroft, J.; Motwan, R. Introdução à Teoria de Autômatos, Linguagens e Computação. Editora Campus, 2011.
  • Sipser, M. Introdução à Teoria da Computação. Editora Thomson Pioneira, 2007.