Národní úložiště šedé literatury Nalezeno 3 záznamů.  Hledání trvalo 0.00 vteřin. 
pp-elimination of quantifiers in module theories
Novák, Jindřich ; Šaroch, Jan (vedoucí práce) ; Ježil, Ondřej (oponent)
Cílem této práce je dokázat Baur-Monkovu větu a tím ukázat, že úplné teorie modulů připouštějí eliminaci kvantifikátorů až na (booleovské kom- binace) existenčních formulí. Za tímto účelem se čtenář po stručném úvodu v kapitole 1 seznámí v kapitole 2 s pojmem pozitivně-primitivní formule v jazyce pravých R-modulů a s jeho úzkým vztahem s komutativními grupami, jejich rozkladovými třídami a svazy. Kapitola 3 nejprve položí technické základy pro důkaz Baur-Monkovy věty, který je uveden v oddíle 3.3, a to ve svých úvodních dvou podkapitolách, které obsahují potřebné kombinatorické a grupově-teoretické výsledky, konkrétně Neumannovo lemma a variaci na princip inkluze a exkluze. Kapitola 4 uzavírá zde obsaženou matematickou práci stručným přehledem některých bezprostředních důsledků Baur-Monkovy věty a dřívějších výsledků.
Pseudofinite structures and limits
Ježil, Ondřej ; Krajíček, Jan (vedoucí práce) ; Šaroch, Jan (oponent)
Pro třídu instancí výpočetního problému definujeme limitní objekt, vzhledem k nějaké výpočetně omezené třídě funkcí. Klíčová metoda zde je forcing s náhodnými proměnnými, kde za množinu elementárních jevů bereme instance nestandardní velikosti. Studujeme obecnou teorii těchto limit, v práci nazývaných široké limity, a jejich spojitost s klasickými problémy jako je nalezení velké kliky a nebo s kombinatorickými problémy přidruženými k třídám NP vyhledávacích problémů PPA a PPAD. Nášimi hlavními výsledky jsou určité 0-1 zákony pro tyto limity a existence kliky významné velikosti v široké limitě grafů sestávajících z jedné velké kliky. 1
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

Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.