|
|
Problém spektra
Poláková, Kristýna ; Krajíček, Jan (vedoucí práce) ; Jeřábek, Emil (oponent)
V této práci studujeme problém spektra, který předložil v roce 1952 H. Scholz. Definujeme základní pojmy, které s tímto problémem souvisí. Sledujeme jeho další vývoj a především souvislosti s množinami z třídy výpočetní složitosti NE. Definujeme zobecněná spektra. Představíme příklady množin přirozených čísel, která jsou spektra.
|
|
|
Spectrum problem
Ježil, Ondřej ; Krajíček, Jan (vedoucí práce) ; Šaroch, Jan (oponent)
V této práci se věnujeme spektrům sentencí prvního řádu. Nejprve předvedeme kon- strukci několika zajímavých příkladů spekter a poté ukážeme, že je třída všech spekter uzavřena na několik jednoduchých množinových a algebraických operací. Poté definu- jeme novou třídu definovatelných operací, která zobecní předchozí konstrukce. Hlavním výsledkem práce je důkaz toho, že je třída těchto funkcí uzavřena na určitý druh iterace. Toto nám ve spojení s Cobhamovou charakterizací FP nabízí nový důkaz Faginovy věty a také Jonesovy-Selmenovy charakterizace spekter jako NE množin. 1
|
|
|
Problém spektra
Poláková, Kristýna ; Krajíček, Jan (vedoucí práce) ; Jeřábek, Emil (oponent)
V této práci studujeme problém spektra, který předložil v roce 1952 H. Scholz. Definujeme základní pojmy, které s tímto problémem souvisí. Sledujeme jeho další vývoj a především souvislosti s množinami z třídy výpočetní složitosti NE. Definujeme zobecněná spektra. Představíme příklady množin přirozených čísel, která jsou spektra.
|
host ::
RSS.