Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação

IF689 - Informática Teórica

Descrição:

Você sabe o que é:

computabilidade? problema de `decisão'? decidibilidade? linguagem decidida por autômato? problema da parada? máquina de Turing? tese de Church-Turing? sistema de Post? função computável? função factivelmente computável? problema intratável?

De que trata o curso?

A noção de procedimento efetivo, que deu origem às primeiras "máquinas abstratas de computação efetiva" (como, por exemplo, a chamada Máquina de Turing, o primeiro modelo de computador programável por software, e que deu origem à chamada Tese de Church que afirma que qualquer função efetivamente computável pode ser computável por uma Máquina de Turing apropriadamente definida) está intimamente ligada à noção de "dedução em um sistema formal (simbólico)", como concebido por Gottlob Frege, o mentor da Lógica Moderna, justamente porque esta última veio como a implementação do sonho do filósofo Leibniz (século XVII) de criar uma máquina de verificação da validade de argumentos.

Bibliografia Básica

  • Introdução à Teoria da Computação, Michael Sipser, Thomson Pioneira, ISBN 8522104999, 2007. (Tradução brasileira de Introduction to the Theory of Computation, Michael Sipser, Second Edition, PWS Publishing Company, February 2005, ISBN 0-534-95097-3.)

    Bibliografia Suplementar

  • Introdução à Teoria dos Autômatos, Linguagens e Computação, John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Editora Campus, Outubro 2002, ISBN 85-352-1072-5. (Tradução brasileira de: Introduction to Automata Theory, Languages, and Computation, 2/E, Addison-Wesley, 2001, ISBN: 0-201-44124-1. Página de apoio: http://www-db.stanford.edu/~ullman/ialc.html)
  • Elements of the Theory of Computation (Second Edition), Harry R. Lewis and Christos Papadimitriou, Prentice-Hall, 1998, ISBN: 0-13-262478-8.
  • Automata and Computability, Dexter Kozen, Springer, 1997, ISBN: 0-387-94907-0.
  • Computational Complexity, Christos Papadimitriou, Addison Wesley, 1994, ISBN: 0-201-53082-1.

    Semestres

    Última atualização: 09 de Agosto de 2010, 10:45am GMT-3