Relações estruturais

26 março 2010, 14:30 • José Félix Costa

Proposição : Caracterização das classes DTIME, NTIME, DSPACE e NSPACE: sejam s(n) >= 1, s'(n) >= 1, t(n) >= n+1 e t'(n) >= n+1 funções totais;
(a) DTIME(t) incl. NTIME(t) e DSPACE(s) incl. NSPACE(s),
(b) DTIME(t) incl. DSPACE(t) e NTIME(t) incl.NSPACE(t),
(c) Se s' in O(s), então DSPACE(s') incl. DSPACE(s) e NSPACE(s') incl. NSPACE(s),
(d) Se s' in Teta(s), então DSPACE(s') = DSPACE(s) e NSPACE(s') = NSPACE(s),
(e) Se t' in O(t) e n in o(t), então DTIME(t') incl. DTIME(t) e NTIME(t') incl. NTIME(t),
(f) Se t' in Teta(t) e n in o(t), então DTIME(t') = DTIME(t),
(g) Se s é construtível e s(n) >= log n, então NSPACE(s) incl. DTIME(2^O(s)),
(h) Se t é construtível, então NTIME(t) incl. DSPACE(t),
(i) Se s é construtível e s(n) >= log n, então DSPACE(s) incl. DTIME(2^O(s)),
(j) Se t é construtível, então NTIME(t) incl. DTIME(2^O(t)).

{
Atenção : Estudar o algoritmo de Dijkstra do menor percurso num grafo.
}

Cálculo do número de configurações de uma MT

23 março 2010, 14:00 • José Félix Costa

Relação entre recursos de espaço e recursos de tempo: recursos limitados de tempo impõem recursos limitados de espaço e, reciprocamente, recursos limitados de espaço impõem recursos limitados de tempo.
Cálculo de um majorante do número de configurações de uma máquina de Turing.
Exercício : Mostre que se M1 é uma máquina de Turing que reconhece o conjunto A em espaço s construtível, tal que s(n) >= log n, então existe uma máquina M2 que decide A em espaço s (pára para todos os inputs).

DTIME(t), NTIME(t), DSPACE(s) e NSPACE(s)

23 março 2010, 12:30 • José Félix Costa

Teorema da compressão das fitas : Se A é decidível por uma máquina de Turing determinística (não determinística) M em espaço s e c é um número real, tal que 0 < c < 1, então A é decidível por uma máquina de Turing determinística (não determinística) N em espaço c s.
Teorema de 'speedup' linear : Se A é o conjunto decidível por uma máquina de Turing determinística em tempo t, com n in o(t(n)) e 0 < c < 1, então A é decidível por uma máquina de Turing determinística M' em tempo c t.
Proposição : Se M é uma máquina de Turing determinística que decide A em tempo t, então existe uma máquina de Turing determinística com duas fitas, que decide A em tempo O(t.log t).
Funções construtíveis no tempo e funções construtíveis no espaço.
Exemplos de funções construtíveis no tempo: \lambda n. n^k, para k > 1, \lambda n. n!, \lambda n. 2^kn, para k >= 1, \lambda n. 2^n^k, para k >= 1, \lambda n. n.|log n|^k, para k >= 1, \lambda n. n.log*n.
Proposição : Se f é uma função tal que existe um \lambda > 0 tal que, a partir de certa ordem, f(n) >= (1 + \lambda).n, então f é construtível no tempo se e só se f pode ser calculada em tempo O(f).
Proposição : Para toda a função recursiva f, existe uma função recursiva g construtível no tempo e tal que, para todo o n, g(n) > f(n).
Proposição : f é construtível no espaço se e só se f pode ser calculada em espaço O(f).
Definição de DTIME(t), NTIME(t), DSPACE(s) e NSPACE(s), para funções totais t(n) >= n+1 e s(n) >= 1.
Extensão destes conceitos a classes de funções.

Máquinas de Turing

19 março 2010, 14:30 • José Félix Costa

Máquinas de Turing.
Tempo de execução e espaço de trabalho das máquinas de Turing: tempo de computação de uma máquina determinística relativamente a um input, tempo de execução de uma máquina determinística, tempo de computação de uma máquina não determinística relativamente a um input, tempo de execução de uma máquina não determinística, espaço de computação de máquinas determinísticas e não determinísticas relativamente a um input, espaço de trabalho de máquinas determinísticas e não determinísticas.
Linguagem decidida por uma máquina (determinística, não determinística) em (tempo, espaço) f.

Autómato finito determinístico

16 março 2010, 14:00 • José Félix Costa

TPC:
Exercício : Indique um autómato de pilha que reconheça a linguagem {w0w: w in {1}*}.
Exercício : Indique um autómato de pilha que reconheça a linguagem {w: w in {0,1}* tal que o nº de 0s é igual ao nº de 1s}.
Exercício : Indique um autómato de pilha que reconheça a linguagem {a^i b^j c^k: i,j,k >= 0 e (i = j ou j = k)}.