Programa

Elementos de Teoria da Computação

Licenciatura Bolonha em Engenharia Eletrotécnica e de Computadores

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.