Sumários

AT25 - Introdução à complexidade

15 Dezembro 2011, 11: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 e EXP. Exemplos. Redutibilidade polinomial. Noção de completude-NP. Exemplos.

Apresentação da estrutura do exame.


AP14 Redutibilidade

13 Dezembro 2011, 14:30 Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre redutibilidade e classficação de conjuntos e seus complementares.
Ficha 8.


AT24 - Redutibilidade-T

13 Dezembro 2011, 11:00 Amilcar Sernadas

Conclusão da aula anterior: lema técnico sobre produtividade; equivalência entre criatividade e completude-m (teorema de Myhill).

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

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


AP13 Redutibilidade

6 Dezembro 2011, 14:30 Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre redutibilidade e classificação de conjuntos.


AT23 - Não listabilidade efectiva e construção de Post

6 Dezembro 2011, 11:00 Amilcar Sernadas

Motivação e definição de conjunto produtivo e de conjunto criativo. Resultado fundamental de relacionamento da completude-m com a não listabilidade efectiva. Motivação e definição de conjunto imune e de conjunto simples. Construção de Post: existência de conjunto simples. Não imunidade de conjunto efectivamente não listável. Não completude-m de conjunto simples.