|
Možnosti zvýšení výkonu přírodou inspirovaných globálních optimalizačních metod
Pátek, Zdeněk ; Rytíř, Pavel (vedoucí práce) ; Bálek, Martin (oponent)
Tato práce se zabývá optimalizací funkcí reálných proměnných pomocí přírodou inspirovaných metod. Obsahuje popis vybraných globálních optimalizačních metod (Differential Evolution, Self-Organizing Migrating Algorithm, Steady-State Evolutionary Algorithm, Particle Swarm Optimization, Gregarious Particle Swarm Optimizer a Hybrid Particle Swarm with Differential Evolution Operator). Nalezl jsem čtyři zlepšení těchto metod, zjistil jejich vhodná nastavení parametrů a porovnal je na vybraných testovacích funkcích. Experimentální výsledky prokázaly, že popsaná zlepšení mohou zvýšit výkon přírodou inspirovaných optimalizačních metod.
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (vedoucí práce) ; Serra, Oriol (oponent) ; Kaiser, Tomáš (oponent)
V práci se zabýváme dvou-dimenzionálními simpliciálními komplexy a lineárními kódy. Řekneme, že lineární kód C nad tělesem F je trojúhelníkově reprezentovatelný, pokud exis- tuje dvou-dimenzionální simpliciální komplex ∆ takový, že kód C je propíchnutým kódem jádra ker ∆ incidenční matice simpliciálního komplexu ∆ nad F a dim C = dim ker ∆. Tento simpliciální komplex nazveme geometrickou reprezentací kódu C. Dokážeme, že každý lineární kód nad prvotělesem je trojúhelníkově reprezentovatelný. Pro konečná prvotělesa sestrojíme geometrickou reprezentaci takovou, že váhový polynom kódu C je dán jednoduchou formulí váhového polynomu prostoru cyklů simpliciálního kom- plexu ∆. Tedy geometrická reprezentace kódu C určuje jeho váhový polynom. Naše motivace pochází z teorie pfaffiánovských orientací grafů, která poskytuje polyno- miální algoritmus pro výpočet váhového polynomu prostoru řezů grafu s omezeným rodem. Tento algoritmus využívá geometrických vlastností nakreslení grafu na orientovatelnou ri- emannovskou plochu. Prostor řezů je lineární kód a odpovídající graf je jeho užitečnou geometrickou reprezentací. Dále studujeme vnořitelnost geometrických reprezentací do euklidovských prostorů. Ukážeme, že každý binární lineární kód má geometrickou reprezentaci v R4 . Charakte- rizujeme binární lineární kódy, které...
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (vedoucí práce) ; Rytíř, Pavel (oponent)
V práci studujeme dva problémy pokrytí klikami, které mají zajímavé aplikace při reprezentaci tzv. k -bendovými průnikovými grafy: problém stupně pokrytí hran klikami a problém vrstevnatého pokrytí hran klikami. Zaměřujeme se na složitost těchto problémů a polynomiální algoritmy pro omezené třídy grafů. Hlavními výsledky práce je NP-úplnost problému vrstevnatého pokrytí hran klikami, polynomiální algoritmus pro tento problém na podtřídě grafů bez diamantů a také některé horní odhady pro konkrétní třídy grafů.
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (vedoucí práce) ; Serra, Oriol (oponent) ; Kaiser, Tomáš (oponent)
V práci se zabýváme dvou-dimenzionálními simpliciálními komplexy a lineárními kódy. Řekneme, že lineární kód C nad tělesem F je trojúhelníkově reprezentovatelný, pokud exis- tuje dvou-dimenzionální simpliciální komplex ∆ takový, že kód C je propíchnutým kódem jádra ker ∆ incidenční matice simpliciálního komplexu ∆ nad F a dim C = dim ker ∆. Tento simpliciální komplex nazveme geometrickou reprezentací kódu C. Dokážeme, že každý lineární kód nad prvotělesem je trojúhelníkově reprezentovatelný. Pro konečná prvotělesa sestrojíme geometrickou reprezentaci takovou, že váhový polynom kódu C je dán jednoduchou formulí váhového polynomu prostoru cyklů simpliciálního kom- plexu ∆. Tedy geometrická reprezentace kódu C určuje jeho váhový polynom. Naše motivace pochází z teorie pfaffiánovských orientací grafů, která poskytuje polyno- miální algoritmus pro výpočet váhového polynomu prostoru řezů grafu s omezeným rodem. Tento algoritmus využívá geometrických vlastností nakreslení grafu na orientovatelnou ri- emannovskou plochu. Prostor řezů je lineární kód a odpovídající graf je jeho užitečnou geometrickou reprezentací. Dále studujeme vnořitelnost geometrických reprezentací do euklidovských prostorů. Ukážeme, že každý binární lineární kód má geometrickou reprezentaci v R4 . Charakte- rizujeme binární lineární kódy, které...
|
|
Mřížky a kódy
Rytíř, Pavel ; Loebl, Martin (vedoucí práce) ; Pangrác, Ondřej (oponent)
Diplomová práce zkoumá trojúhelníkové kon gurace, binární matroidy a mřížky generované binárními kódy. Zkoumáme domněnku, zdali mřížka generovaná kódovými slovy binárního kódu má bázi skládající se pouze z kódových slov. Domněnku dokážeme pro matroidy s dobrou uchovou dekompozicí. Prostudujeme operaci hranové kontrakce trojúhelníkové kon gurace. Hlavní dopad kontrakce na cyklus a acyklickou trojúhelníkovou kon guraci. Dokážeme, že pro každý graf existuje trojúhelníková kon gurace s kostrou která obsahuje tento graf jako minor. Pro každý binární matroid sestrojíme trojúhelníkovou kon guraci, která obsahuje tento matroid jako minor. Navíc dokážeme, že mezi prostory cyklů kon gurace a matroidu existuje bijekce. Tato bijekce zobrazuje kružnice matroidu na kružnice kon gurace.
|
|
Možnosti zvýšení výkonu přírodou inspirovaných globálních optimalizačních metod
Pátek, Zdeněk ; Bálek, Martin (oponent) ; Rytíř, Pavel (vedoucí práce)
Tato práce se zabývá optimalizací funkcí reálných proměnných pomocí přírodou inspirovaných metod. Obsahuje popis vybraných globálních optimalizačních metod (Differential Evolution, Self-Organizing Migrating Algorithm, Steady-State Evolutionary Algorithm, Particle Swarm Optimization, Gregarious Particle Swarm Optimizer a Hybrid Particle Swarm with Differential Evolution Operator). Nalezl jsem čtyři zlepšení těchto metod, zjistil jejich vhodná nastavení parametrů a porovnal je na vybraných testovacích funkcích. Experimentální výsledky prokázaly, že popsaná zlepšení mohou zvýšit výkon přírodou inspirovaných optimalizačních metod.
|