Elementos de Teoria da Computação

Código

01061482

Créditos ECTS

3

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

As aulas são  teórico/práticas em que se apresentam os conceitos com recurso a exemplos e à resolução de exercícios. 

A plataforma de e-Learning Moodle da UAc (em http://moodle.uac.pt) é utilizada como repositório de material pedagógico e didático de apoio à aprendizagem, bem como de plataforma de agendamento, divulgação e promoção de atividades complementares e de gestão dos elementos de avaliação.

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. Cengage Learning
  • Computability and Complexity Theory: Steven Homer e Alan L. Selman 2014 2ª ed. Springer
  • Circuit Complexity and Neural Networks: Ian Parberry 1994 MIT Press
  • The Nature of Computation: Christopher Moore and Stephen Merteen 2011 Oxford University Press

Método de Avaliação