Programa

Teoria da Computação

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

Licenciatura Bolonha em Engenharia de Telecomunicações e Informática

Programa

Linguagens regulares e algébricas. Aplicação motivadora: reconhecimento de linguagens. Linguagens regulares, gramáticas regulares, expressões regulares, autómatos finitos, minimização de autómatos finitos deterministas. Linguagens algébricas, autómatos de pilha. Hierarquia de Chomsky. Computabilidade e decidibilidade. Aplicação motivadora: terminação de programas. Máquinas de Turing. Computador universal de registos com programas imperativos WHILE. Funções computáveis. Conjuntos recursivos e recursivamente enumeráveis. Postulado de Church-Markov-Turing. Enumeração de programas. Indecidibilidade do problema da terminação de programas. Teorema s-m-n e Teorema de Rice. Referência à noção de complexidade computacional. Lógica. Aplicação motivadora: correcção de programas. Cálculo de Hoare para a verificação da correcção parcial e total de programas imperativos. Elementos de lógica proposicional e de predicados: cálculo de Smullyan e resolução. Decidibilidade da lógica proposicional. Indecidibilidade da lógica de predicados.