Národní úložiště šedé literatury Nalezeno 18 záznamů.  1 - 10další  přejít na záznam: Hledání trvalo 0.00 vteřin. 
Tennenbaum phenomena in models of arithmetic
Kriško, Lukáš ; Thapen, Neil (vedoucí práce) ; Bulín, Jakub (oponent)
Hlavným cieľom tohto textu je skúmať, či už prezentovaním známych výsledkov alebo našich vlastných, niektoré aritmetické funkcie a relácie z pohľadu ich rekurzívnosti v spočetných neštandardných modeloch Peanovej aritmetiky, skratkou PA, alebo niekt- orého jej slabšieho fragmentu ako I∆0 alebo IΣ1. V prvej časti prezentujeme Tennenbaumovu vetu, ktorá je známym výsledkom danej oblasti. Veta tvrdí, že v každom neštandardnom modeli M, Peanovej aritmetiky, s doménou N nemôže byť +M ani ×M rekurzívnou funkciou. Navyše, prezentujeme daný výsledok pre + v silnejšie podobe a to pre teóriu I∆0, daný výsledok pochádza od K. McAloona. Aby sme ukázali že nie je všetko stratené, prezentujem ďalší známy výsledok tvrdiaci, že relácia < a funkcia nasledovník, S, môžu byť simultánne rekurzívne v nejakom neštandardnom modeli PA s doménou N. V druhej časti prezentujeme naše vlastné výsledky ktoré sme dostali pýtaním sa otázok o rekurzívnosti funkcií x div y, celočíselné delenie, a x mod y, zvyšok po celočíselnom delení, v modeloch PA. Taktiež častokrát uvažujeme reštrikcie x div y a x mod y na x div n a x mod n, kde n je štandardné číslo. Aby sme spomenuli niekoľko výsledkov ku ktorým sme prišli, ukázali sme, že neexistuje neštandardný model PA kde by boli obe funkcie x div n a x mod n rekurzívne. Ďalej, nemôže existovať...
Čtverce v posloupnostech čísel
Hudcová, Barbora ; Holub, Štěpán (vedoucí práce) ; Bulín, Jakub (oponent)
V této práci vycházíme z článku, kde bylo zkonstruováno první nekonečné slovo nad konečnou abecedou, které se vyhýbá aditivním třetím mocninám. Ukazujeme konstrukce dalších slov se stejnou vlastností. Dále na jednom z těchto slov ilustrujeme hlavní myš- lenku důkazu, že se dané slovo vyhýbá aditivním třetím mocninám. 1
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
Homomorphisms into unary algebras
Škrobánek, Jiří ; Barto, Libor (vedoucí práce) ; Bulín, Jakub (oponent)
Tato práce se zabývá výpočetní složitostí problému splnitelnosti omezení (CSP) nad strukturami s unárními operacemi (unárními algebrami). Zaměřujeme se na speciální třídu CSP, takzvané reverzní problémy. Představíme nový důkaz klasifikace složitosti reverzních problémů, jenž využije algebraického přístupu založeného na zkoumání polymorfismů. Ukážeme, že některé reverzní problémy připouštějí polymorfismus téměř úplné shody (a jsou tedy řešitelné v polynomiálním čase). Zato ostatní reverzní problémy nepřipouštějí polymorfismus slabé téměř úplné shody - WNU (a jsou tedy NP-úplné).
Higher commutators in loop theory
Semanišinová, Žaneta ; Stanovský, David (vedoucí práce) ; Bulín, Jakub (oponent)
Práca sa venuje supernilpotencii v lupách. Vychádzame z troch ekvivalentných definícií vyšších komutátorov v Mal'cevských algebrách, a to podľa Aichingera a Mudrinského, Bulatova a Opršala. V práci skúmame identity, ktoré platia v 1-, 2- a 3-supernilpotentných lupách. Ďalej ukážeme, že k-supernilpotentná lupa má k- nilpotentnú multiplikačnú grupu. V závere prezentujeme výsledky algoritmického testovania supernilpotencie v neasociatívnych lupách malých rádov.
Algebraický přístup k CSP
Bulín, Jakub
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
Minimum 0-Extensions of Graph Metrics
Dvořák, Martin ; Bulín, Jakub (vedoucí práce) ; Majerech, Vladan (oponent)
Uvažujeme Minimum 0-Extension problém pro pevně-daný neori- entovaný graf s kladnými vahami hran. Studujeme výpočetní složitost jeho rozhodovací varianty v závislosti na vlastnostech toho pevně-daného grafu, konkrétně s ohledem na to, zda je tento graf modulární a zda je orientovatelný ve smyslu, jak ho definoval Karzanov [Eur. J. Comb., 19/1 (1998)]. Na tento problém se díváme z pohledu Finite-Valued CSP, což nám umožňuje využít bohatství teorie, která byla vyvinuta pro důkaz jejich dichotomie. V rámci spodního odhadu složitosti, nejprve zkonstruujeme explicitní re- dukci z Max-Cut problému, čímž získáme NP-těžkost pro nemodulární grafy. Pro neorientovatelné grafy vyjádříme funkci, která splní určitou podmínku, jež zaručí existenci implicitní redukce z Max-Cut problému. Co se týče pozi- tivních výsledků, pomocí symetrických zlomkových polymorfismů ukážeme, že některé speciální případy pro vážené modulární orientovatelné grafy lze řešit technikou zvanou Basic LP Relaxation, konkrétně Minimum 0-Extension problém pro grafy typu cesta a pro grafy typu obdélník. 1
Permutation group algorithms
Plšková, Petra ; Bulín, Jakub (vedoucí práce) ; Růžička, Pavel (oponent)
Schreier Simsov algoritmus je základným algoritmom pre permutačné grupy. Jeho úlohou je nájsť bázu a silne generujúcu množinu. Reprezentácia grupy pomocou bázy a silne generujúcej množiny je základom pre veľa ďalších algoritmov. Cieľom tejto práce je poskytnúť čitateľovi detailnejší popis tohto algoritmu. V práci uvedieme jeho pseudo- kód, vrátane pseudokódov algoritmov riešiacich čiastkové problémy. Časovú a priestorovú zložitosť spočítame vzhľadom k uvedeným pseudokódom. Obdobne popíšeme efektívnu Monte Carlo verziu Schreier Simsovho algoritmu, ktorej časová zložitosť je skoro line- árna. Detailne popíšeme dve vylepšenia algoritmov pre čiastkové problémy, na ktorých je táto verzia založená. Korektnosť deterministickej aj Monte Carlo verzie je podložená teoretickými poznatkami. 1
Image reconstruction using graphical models
Ficová, Klára ; Kazda, Alexandr (vedoucí práce) ; Bulín, Jakub (oponent)
Grafické modely slúžia na reprezentáciu pravdepodobnostných vzťahov medzi náhodnými veličinami pomocou grafu . Ponúkajú dobrý spôsob na vyjadrenie reálnych situácií a preto sa často využívajú v strojovom učení a štatistickom uvažovaní. Cieľom práce je popísať a implementovať spôsoby, ako grafickým mo- delom odstrániť z obrazu šum. Za grafický model zvolíme faktorgraf, v ktorom reprezentujeme ako vrcholy pixely v obraze a interakcie medzi nimi. Pomocou algoritmov popísaných na grafe budeme hľadať najpravdepodobnejší pôvodný obraz. Bližšie sa budeme venovať algoritmu belief propagation, ktorý je založený na vzájomnom posielaní správ medzi susednými vrcholmi. Teoretické metódy aplikujeme na obrazy so šumom a porovnáme výsledky. 1

Národní úložiště šedé literatury : Nalezeno 18 záznamů.   1 - 10další  přejít na záznam:
Viz též: podobná jména autorů
1 BULÍN, Jiří
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.