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.

Teoria da Computação

Licenciatura (5 anos) em Engenharia Informática e de Computadores - Taguspark

Programa

Linguagens regulares: autómatos finitos deterministas, equivalência e minimização de autómatos finitos deterministas, autómatos finitos não deterministas, gramáticas, expressões regulares. Lógica clássica: sintaxe, semântica, cálculo de Smullyan, cálculo de Gentzen, resolução e cálculo de Hilbert. Computabilidade: máquina URM, funções parciais recursivas, conjuntos recursivos e conjuntos recursivamente enumeráveis, existência de funções não computáveis, problemas clássicos da computabilidade e da decidibilidade (problema da paragem inter alia). Importância da noção de complexidade computacional.

Teoria da Computação

Licenciatura (5 anos) em Engenharia de Redes de Comunicação e de Informação

Programa

Linguagens regulares: autómatos finitos deterministas, equivalência e minimização de autómatos finitos deterministas, autómatos finitos não deterministas, gramáticas, expressões regulares. Lógica clássica: sintaxe, semântica, cálculo de Smullyan, cálculo de Gentzen, resolução e cálculo de Hilbert. Computabilidade: máquina URM, funções parciais recursivas, conjuntos recursivos e conjuntos recursivamente enumeráveis, existência de funções não computáveis, problemas clássicos da computabilidade e da decidibilidade (problema da paragem inter alia). Importância da noção de complexidade computacional.