Elementos de Teoria da Computação

Objetivos

Introduzir o conceito de algoritmo e de modelo de computação, nomeadamente de autómato finito e infinito (autómato de pilha e máquina de Turing). Estudar a hierarquia das linguagens. Resolver problemas algorítmicos através de circuitos booleanos e classificar a sua complexidade em termos de tamanho e profundidade dos circuitos.

Programa

Autómatos finitos; linguagens regulares, expressões regulares e gramáticas regulares. Autómatos de
pilha; linguagens e gramáticas livres de contexto. Conceito de algoritmo segundo Turing. Máquinas de
Turing. Universalidade. Máquinas de registos. Postulado de Church-Turing. Hierarquia de Chomsky.
Problemas decidíveis e indecidíveis. Medidas de eficiência dos algoritmos. Recursos limitados de
tempo e de espaço. Classes de complexidade e problemas completos. Circuitos booleanos e famílias de
circuitos. Circuitos booleanos sequenciais. Circuitos booleanos combinatórios. Discussão da
equivalência entre máquinas de Turing e famílias de circuitos booleanos. Alternação. Problemas
completos para classes de circuitos booleanos.

Métodos de Ensino

Exame/testes, possivelmente com nota mínima, complementado com componente de avaliação contínua.

Bibliografia

Elements of the Theory of Computation, Harry R. Lewis e Christos H. Papadimitriou, 2015, 2ª Ed. Dorling Kindesley Pearson Education; Introduction to the Theory of Computation. Cengage Learning, Terceira edição, Michael Sipser, 2014, 3ª ed.; Computability and Complexity Theory, Steven Homer e Alan L. Selman, 2014, 2ª ed. Springer; Circuit Complexity and NeuralNetworks, Ian Parberry, 1994, MIT Press; The Nature of Computation, Christopher Moore and Stephen Merteen, 2011, OxfordUniversity Press.

Método de Avaliação

Conforme Métodos de Ensino - 100 %