Programa

Teoria da Computação

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

Programa

Computabilidade Máquinas de Turing determinísticas, não determinísticas e enumeradoras. Funções computáveis. Conjuntos recursivamente enumeráveis. Oráculos. Reduções. O problema da terminação (introdução à técnica da diagonalização). Teorema de Kleene. Vírus. O teorema de Rice e suas aplicações. O postulado de Church-Turing. Complexidade Recursos computacionais. Construtividade das funções. Teoremas de hierarquia (emprego da diagonalização). Teorema de Savitch. Classes computacionais: P, PSPACE, NP, EXPTIME, BPP. Relações estruturais. Conjuntos completos. Construção da hierarquia polinomial. Relativização.