Sumários
TURMA 105: Argumentos de cardinalidade
4 dezembro 2012, 09:30 • José Félix Costa
Bijeção entre {0,1}* e N, ordem lexicográfica, enumeração de máquinas de Turing, bijeção entre o conjunto das partes infinitas de {0,1}* e R.
Método da diagonalização.
Argumentos de cardinalidade.
TPC
Exercício: Mostre, exibindo a respectiva bijecção, que os seguintes conjuntos são equipotentes:
(a) Os números naturais e os números inteiros;
(b) Os números reais e o intervalo ]0,1[;
(c) Os números reais e o intervalo ]0,+\infty[;
(d) Os intervalos ]0,1[ e [0,1[;
(e) Os intervalos ]0,1[ e ]0,1];
(f) Os pares de números naturais e os números naturais (usando uma bijecção de grau não superior ao segundo);
(g) As palavras binárias e os números naturais;
(h) As linguagens binárias infinitas e o intervalo ]0,1];
(i) As linguagens binárias infinitas e os números reais;
(j) As sequências binárias infinitas e os números reais.
Complexidade I
3 dezembro 2012, 11:00 • José Félix Costa
Prémio P vs. NP: 1 milhão.
Conjectura de Poincaré(resolvida em 2010): 1 milhão.
Introdução à complexidade computacional.
Estudo de uma função construtível no tempo: função de expressão n^2.
REPTO: Os alunos ficaram de apresentar máquinas de Turing para funções construtíveis no tempo, 2n, 3n, 4n, 5n.
Definição de TIME(t), NTIME(t), SPACE(s), NSPACE(s), para recursos t e s de tempo e espaço construtíveis, respectivamente.
Definição de classes de complexidade: P, NP, PSPACE, DEXT, NEXT e EXPTIME.
Conceito de função computável em tempo polinomial por uma máquina de Turing multifita.
P11-T3 Décima primeira aula prática (Turma 3)
3 dezembro 2012, 11:00 • Francisco Miguel Alves Campos de Sousa Dionísio
Cardinalidade. Resolveram-se os seguints exercícios:
a) Mostre que o conjunto das linguagens binárias não é equipotente a N (Teorema de Cantor depois de ver que {0,1}*~N)
b) Mostre que N*N é equipotente a N
c) Mostre que ]0,1] não é equipotente a N (absurdo com argumento diagonal)
d) Mostre que o conjunto das funções de N em {0,1,...,9} não é equipotente a N
e) Mostre que o conjunto das linguagens binárias infinitas é equipotente a R (feito via ]0,1]).
Complexidade I
3 dezembro 2012, 09:30 • José Félix Costa
Prémio P vs. NP: 1 milhão.
Conjectura de Poincaré(resolvida em 2010): 1 milhão.
Introdução à complexidade computacional.
Estudo de uma função construtível no tempo: função de expressão n^2.
REPTO: Os alunos ficaram de apresentar máquinas de Turing para funções construtíveis no tempo, 2n, 3n, 4n, 5n.
Definição de TIME(t), NTIME(t), SPACE(s), NSPACE(s), para recursos t e s de tempo e espaço construtíveis, respectivamente.
Definição de classes de complexidade: P, NP, PSPACE, DEXT, NEXT e EXPTIME.
Conceito de função computável em tempo polinomial por uma máquina de Turing multifita.
P11-T4 Décima primeira aula prática (Turma 4)
3 dezembro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio
Cardinalidade. Resolveram-se os seguints exercícios:
a) Mostre que o conjunto das linguagens binárias não é equipotente a N (Teorema de Cantor depois de ver que {0,1}*~N)
b) Mostre que N*N é equipotente a N
c) Mostre que ]0,1] não é equipotente a N (absurdo com argumento diagonal)
d) Mostre que o conjunto das funções de N em {0,1,...,9} não é equipotente a N
e) Mostre que o conjunto das linguagens binárias infinitas é equipotente a R (feito via ]0,1]).