|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (vedoucí práce) ; Pergel, Martin (oponent)
Práce se zabývá algoritmem Sivia (Set Inverter via Interval Analysis) pro řešení spojitého problému splňování omezujících podmínek pomocí intervalo- vých metod a propagačních technik. Prezentovány jsou základní vlastnosti al- goritmu, a také oprava uváděného odhadu jeho složitosti. Dále jsou navrhnuta vylepšení týkající se testování splnění omezujících podmínek a optimalizace poč- tu intervalových boxů popisujících získané řešení problému. Představeny jsou též tzv. kontraktory používané pro zvýšení efektivity algoritmu Sivia prostřednic- tvím redukce zpracovávaných intervalových boxů. Uvedené algoritmy byly im- plementované jako knihovna funkcí jazyka Matlab tvořící solver nelineárních podmínek s možností jednoduché vizualizace získaného řešení. Součástí práce je také porovnání základních kontraktorů na konkrétních příkladech.
|
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent) ; Bulatov, Andrei (oponent)
CSP, grafy a algebry Jakub Bulín Abstrakt Tato práce sestává ze tří článků v oblasti algebraického přístupu k problému splňování podmínek (CSP). V prvním článku, se spoluautory Deli'cem, Jacksonem a Nivenem, studujeme redukci CSP na orientované grafy. Pro každou relační strukturu A konstruujeme orientovaný graf D(A) takový, že CSP(A) a CSP(D(A)) jsou logspace ekvivalentní a většina rele- vantních vlastností se přenáší z A na D(A). Důsledkem je, že algebraické hypotézy charekterizující CSP řešitelné v P, NL a L jsou ekvivalentní je- jich restrikcím na orientované grafy. Ve druhém článku dokazujeme, že pro danou core relační strukturu A s konečnou šířkou a B ⊆ A lze algorit- micky rozhodnout, zda je B absorbující podalgebra algebry polymorfismů A. Jako vedlejší produkt získáváme, že Jónssonova absorpce se v tomto případě shoduje s obvyklou absorpcí. Ve třetím článku, za použití mod- erních algebraických nástrojů (např. teorie absorpce a pointující operace), potvrzujeme hypotézu o dichotomii CSP pro tzv. speciální orientované stromy. Konkrétně, core speciální stromy řešitelné v P mají konečnou šířku. Klíčová slova: problém splňování omezení, algebra polymorfismů, ab- sorbující podalgebra, konečná...
|
|
|
Vývoj aplikace pro řešení úloh lineárního programování pomocí nástroje Microsoft Solver Foundation
VYSUŠIL, Pavel
Práce popisuje vývoj počítačové aplikace, hry Sudoku, obsahující modul pro automatické vyřešení úlohy. Ten je navržen na základě matematického modelu definovaného jako úloha lineárního programování a řešen metodou Simplex. Při implementaci úlohy byl použit nástroj pro matematické modelování Microsoft Solver Foundation. Popsány jsou teoretické základy potřebné pro implementaci problému, včetně vytvoření matematického modelu, technologie použité při vývoji a vlastní struktura a fungování aplikace.
|
|
|
Rozvrhování zdrojů na letišti jako časově omezený rozvrhovací problém
Vandas, Marek ; Petříčková, Zuzana (vedoucí práce) ; Pangrác, Ondřej (oponent)
V této práci jsou identifikovány požadavky na bezpečný pozemní letištní provoz, který se skládá z přidělování ranvejí, taxi operací a přidělování bran. Je ukázáno, jak je možné tento problém modelovat jako problém splňování omezujících podmínek a vyřešit jej pomocí technik rozvrhování. Součástí práce je aplikace, která tyto techniky ilustruje a umožňuje následnou vizualizaci výsledků. Pro účely této aplikace byl vytvořen obecný řešič podmínek, který je snadno rozšiřitelný a využitelný i na jiný druh problémů. Další výhodou tohoto řešiče je, že umožňuje snadnou změnu prohledávací strategie.
|
|
|
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.
|
|
|
Grafické animace metod řešení úloh
Macek, Jiří ; Jurka, Pavel (oponent) ; Zbořil, František (vedoucí práce)
Pro automatizované řešení problémů výpočetní technikou se používají různé implementace umělé inteligence. Tato práce se zabývá některými typickými metodami, popisuje jejich vlastnosti, porovnává je a uvádí možný způsob algoritmizace a implementace. Cílem je vytvoření aplikace, která názorným způsobem demonstruje na vybraných úlohách metody jejich řešení.
|
|
|
Harmonizace melodie na základě pravidel
Kuchár, Pavol ; Žák, Pavel (oponent) ; Fapšo, Michal (vedoucí práce)
Bakalářská práce se věnuje počítačem podporovanému přístupu ke tvorbě hudby. Vytvořený program implementuje vybraná pravidla z hudební teorie a pomocí CSP vymezuje vhodné tóny pro harmonizaci zadané melodie. Výsledek je nakonec zobrazen v notovém zápisu a hudebně demonstrován prostřednictvím MIDI souboru.
|
|
|
Automatická tvorba varhanní předehry k církevním písním
Maňák, Ondřej ; Černocký, Jan (oponent) ; Fapšo, Michal (vedoucí práce)
Tato diplomová práce se zabývá problematikou automatické tvorby varhanních předeher k církevním písním z teoretického i praktického hlediska. Varhanní předehra je krátký úvod k liturgickému zpěvu. Vzhledem k tomu, že ji lze popsat pomocí konečné množiny pravidel, nabízí se k její tvorbě využít principů úloh s omezujícími podmínkami. Efektivním prostředkem pro vývoj systému potom může být programovací jazyk C++ a knihovna Gecode.
|
|
|
Automatické jazzové aranžmá
Chadim, Petr ; Karafiát, Martin (oponent) ; Fapšo, Michal (vedoucí práce)
Práce pojednává o aranžování melodie, která je doplněna jazzovými akordy. Zabývá se vytvořením dalších harmonických hlasů pomocí metody blokové harmonizace. Rozdělení na cílové a přechodové noty je provedeno pomocí techniky programování s omezujícími podmínkami (CSP). Přechodové noty jsou reharmonizovány dominantním septakordem nebo paralelním akordem. Pomocí CSP je také vytvořen basový part. Pro řešení CSP je použita knihovna Gecode. Harmonické hlasy jsou aranžovány čtyřhlasou úzkou harmonií. Výsledek aplikace slouží jako pomůcka pro hudebního aranžéra.
|
host ::
RSS.