Sumários

AT27 - Completude-NP

16 Dezembro 2010, 13:00 Amilcar Sernadas

Redutibilidade polinomial. Noção de completude-NP. Exemplos.

Ficha 7.


AP13 - Redutibilidade

15 Dezembro 2010, 09:30 Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre conjuntos efectivamente não listáveis, produtivos, m-completos, criativos e imunes.

Ficha 8.

Aula dada na sexta feira dia 17 de Dezembro das 11h00 às 12h30 na sala P8 por motivo de no horário normal de quarta feira dia 15 de Dezembro das 9h30 às 11h00 a docente ter estado no júri das provas de doutoramento em Matemática do Mestre Pedro Baltazar.


AT26 - Classes de complexidade P e NP

14 Dezembro 2010, 15:30 Amilcar Sernadas

Complementos sobre máquinas de Turing. Inter-emulação polinomial de diversas variantes. Existência de máquina de Turing universal eficiente. Teorema da aceleração linear. Classes de complexidade DTIME(T), P, NP, EXP e NTIME(T). Exemplos.


AP12 - Funções recursivas à Kleene

10 Dezembro 2010, 11:00 Maria Cristina De Sales Viana Serôdio Sernadas

Aula de substituição da aula de 8 de Dezembro (feriado).

Exercícios sobre funções recursivas à Kleene.


AT25 - Redutibilidade-T

9 Dezembro 2010, 13:00 Amilcar Sernadas

Introdução à computabilidade relativa e à redutibilidade-T: resultados básicos.

Introdução à teoria da complexidade: objecto, problemas e notação básica.