|
|
Bottleneck identification for constraint relaxation in resource-constrained project scheduling
Nedbálek, Lukáš ; Švancara, Jiří (vedoucí práce) ; Bulín, Jakub (oponent)
Plánovači výroby často sestavují rozvrh výroby tak, že iterovavaně získávájí návrhy na rozvrh a upravují vstupní parametry za účelem vyhovět mnohým, často protichůdným, optimalizačním cílům. Cílem této práce je zaměřit se na problém snižování zpoždění, tzv. tardiness, vybrané zakázky v obdrženém rozvrhu, jakožto běžně řešený problém při plánování výroby. Zaměříme se na identifikaci tzv. úzkých hrdel daných rozvrhů za úče- lem relaxace omezujících podmínek souvisejících s těmito úzkými hrdly. Pro tento účel představíme dvě metody. První adaptuje existující přístupy z literatury v kombinaci s návrhy obecných relaxací podmínek. Druhá identifikuje potenciální zlepšení v relaxova- ných verzích problému a navrhuje relaxace zaměřující se na konkrétní zpožděnou zakázku. Numerické experimenty ukazují, že zatímco první metoda nachází dobrá zlepšující řešení za nízké ceny, druhá metoda je v nacházení zlepšujících řešení více konzistentní.
|
|
|
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
|
host ::
RSS.