Programa

Teoria da Computação

Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda

Programa

Autómatos finitos determinísticos e não determinísticos. Linguagens e gramáticas regulares, expressões regulares. Autómatos de pilha. Linguagens e gramáticas livres de contexto. Lemas de bombagem. Hierarquia de Chomsky. Máquinas de Turing determinísticas e não determinísticas. Funções computáveis. Linguagens reconhecíveis e decidíveis. Postulado de Church-Turing. Propriedades de fecho das linguagens decidíveis e reconhecíveis. Conjuntos e cardinalidade. Representação canónica de máquinas de Turing. Existência de linguagens indecidíveis. Indecidibilidade do problema da terminação (introdução à técnica da diagonalização). Reduções computáveis. Teorema de Rice e aplicações. Teorema da recursão e vírus auto-replicáveis. Recursos computacionais. Classes de complexidade: P, PSPACE, NP, EXPTIME. Relações estruturais. Teorema de Savitch. Reduções polinomiais. P versus NP e linguagens NP-completas. Teorema de Cook-Levin. Teoremas de hierarquia. Separação de classes de complexidade.