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.