FenixEdu™

Disciplina

Introdução à Computabilidade e Complexidade

Área

Área Científica de Lógica e Computação > Lógica e Computação

Activa nos planos curriculares

GENI > GENI > 1º Ciclo > Área Principal > Percursos > Fundamentos para Matemática Aplicada > Introdução à Computabilidade e Complexidade

LMAC 2021 > LMAC 2021 > 1º Ciclo > Área Principal > Introdução à Computabilidade e Complexidade

MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Teoria da Computação > Introdução à Computabilidade e Complexidade

LMAC 2006 > LMAC 2006 > 1º Ciclo > Tronco Comum > Introdução à Computabilidade e Complexidade

Nível

Fichas (4 valores) + Exame final (16 valores).

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

Aula Teórica (T): 3.0 h/semana

Aula de Problemas (PB): 3.0 h/semana

Trabalho Autónomo: 126.0 h/semestre

Créditos ECTS:

Objectivos

Entender os limites do que é computável na teoria e na prática. Dominar os conceitos, técnicas e resultados fundamentais da teoria da computabilidade. Conhecer diversos modelos de computação e entender a sua equivalência. Conhecer as noções básicas da teoria da complexidade.

Programa

Parte I: Computação em Mathematica Funções computáveis, conjuntos decidíveis, conjuntos listáveis, problemas decidíveis e problemas semidecidíveis. Critérios de listabilidade. Teorema da projecção. Teorema de Post. Gödelizações. Resultados de robustez. Funções universais. Existência de conjuntos listáveis indecidíveis. Enumeração das funções computáveis. Propriedade s-m-n. Conjuntos universais. Enumeração dos conjuntos listáveis. Teoremas de Rice, Rice-Shapiro e da recursão. Existência de vírus. Teorema de Myhill-Shepherdson. Redutibilidade-m. Conjuntos completos-m, conjuntos produtivos e conjuntos criativos. Teorema de Myhill. Redutibilidade-T. Oráculos. Computabilidade relativa. Teorema de Friedberg-Muchnik. Hierarquia aritmética. Parte II: Modelos de computação abstractos Aplicações recursivas primitivas. Aplicações recursivas. Aplicação de Ackermann. Funções recursivas. Teorema da normalização de Kleene. Ábacos. Máquinas de Turing. Máquinas modulares. Funções e conjuntos Diofantinos. Postulado de Church-Turing. Parte III: Elementos de teoria da complexidade Medidas e classes de complexidade. Classes P, NP e PSPACE. Completude-NP. Teorema de Cook-Levin.