MAT 2 07 - Teoria e Fundamentos da Computação

Regente

Objectivos

Desenvolver o raciocínio matemático rigoroso. Dominar os instrumentos matemáticos necessários para compreender os limites da computação e os fundamentos de alguns paradigmas da programação

Sinopse

Módulo 1: Máquina de registos URM e funções URM-computáveis; geração de funções computáveis; outras abordagens à computabilidade e a tese de Church; programas universais; decidibilidade, total e parcial, e indecidibilidade; conjuntos recursivos e recursivamente enumeráveis. Módulo 2 - Lógicas modais proposicionais e de primeira ordem (breve revisão); lógicas modais de acção; lógica associada à programação imperativa, cálculo de Hoare e demonstração da correcção parcial; correcção total. Módulo 3 - Especificações equacionais de tipos de dados abstractos; semântica inicial; cálculo equacional; reescrita.