|
|
Akcelerace částicových rojů PSO pomocí GPU
Krézek, Vladimír ; Schwarz, Josef (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce se zabývá technikou PSO (Particle Swarm Optimization neboli Optimalizace pomocí částicových rojů), s jejíž pomocí je možné řešit komplexní problémy. Tuto techniku lze využít při řešení složitých kombinatorických problémů (obchodní cestující, úloha o batohu), návrh integrovaných obvodů a antén, v oborech jako je biomedicína, robotika, umělá inteligence nebo i finančnictví. Přestože je algoritmus PSO velice efektivní, čas nezbytný pro nalezení vhodného řešení reálných problémů často přesahuje hranice únosnosti. Cílem této práce je tedy urychlit běh tohoto algoritmu pomocí grafického adaptéru, který nabízí velmi vysoký výpočetní potenciál při zachování příznivé ceny a rozměru. Pro demonstrační účely a ověření kvality implementace byl zvolen problém rozhodnutelnosti systému logických formulí (SAT), jenž patří do třídy NP-úplných problémů. Redukcí časové náročnosti algoritmu PSO při řešení SAT problému jsme tedy schopni akcelerovat celou třídu úloh a řešit problémy, které byly dosud prakticky neřešitelné.
|
|
|
DNA výpočty a jejich aplikace
Fiala, Jan ; Petrlík, Jiří (oponent) ; Bidlo, Michal (vedoucí práce)
Tato práce se zabývá návrhem a implementací aplikace pro simulaci DNA výpočtů pro řešení vybraných problémů. DNA výpočty patří mezi nekonvenční výpočetní paradigmata, které se zásadně liší od konceptu elektronických počítačů. Hlavní myšlenkou DNA počítání je požití DNA jako média, kde může poměrně efektivně probíhat výpočet. I přesto, že DNA reakce jsou mnohem pomalejší než výpočetní takty dnešních křemíkových počítačů, má DNA počítání velmi slibnou budoucnost. DNA operace jsou založeny na dvou důležitých aspektech: masivní paralelismus DNA operací a princip komplementarity bází. Existuje mnoho důležitých problémů, pro které na konvenčních počítačích neexistuje algoritmus řešení v polynomiálním čase. Takto obtížné problémy se musí řešit prohledáváním celého stavového prostoru všech jejich řešení. Zde se ukazuje být masivní paralelismus DNA operací velmi důležitý, aby se snížila složitost hledání řešení.
|
|
|
Evoluční algoritmy v úloze booleovské splnitelnosti
Serédi, Silvester ; Vašíček, Zdeněk (oponent) ; Sekanina, Lukáš (vedoucí práce)
Cílem této diplomové práce je najít heuristiku řešící SAT problém pomocí evolučního algoritmu. Jsou zde uvedeny přístupy k řešení SAT problému a různé varianty k evolučním algoritmům, které jsou relevantní k danému tématu. Následně je popsaná implementace lineárního genetického programování hledající heuristiku pro řešení instancí SAT problému společne s vlastní implementací SAT solveru pracujíci s výstupem evolučně navrženého programu. Na závěr jsou shrnuty dosažené výsledky
|
|
|
DNA výpočty a jejich aplikace
Fiala, Jan ; Petrlík, Jiří (oponent) ; Bidlo, Michal (vedoucí práce)
Tato práce se zabývá návrhem a implementací aplikace pro simulaci DNA výpočtů pro řešení vybraných problémů. DNA výpočty patří mezi nekonvenční výpočetní paradigmata, které se zásadně liší od konceptu elektronických počítačů. Hlavní myšlenkou DNA počítání je požití DNA jako média, kde může poměrně efektivně probíhat výpočet. I přesto, že DNA reakce jsou mnohem pomalejší než výpočetní takty dnešních křemíkových počítačů, má DNA počítání velmi slibnou budoucnost. DNA operace jsou založeny na dvou důležitých aspektech: masivní paralelismus DNA operací a princip komplementarity bází. Existuje mnoho důležitých problémů, pro které na konvenčních počítačích neexistuje algoritmus řešení v polynomiálním čase. Takto obtížné problémy se musí řešit prohledáváním celého stavového prostoru všech jejich řešení. Zde se ukazuje být masivní paralelismus DNA operací velmi důležitý, aby se snížila složitost hledání řešení.
|
|
|
Evoluční algoritmy v úloze booleovské splnitelnosti
Serédi, Silvester ; Vašíček, Zdeněk (oponent) ; Sekanina, Lukáš (vedoucí práce)
Cílem této diplomové práce je najít heuristiku řešící SAT problém pomocí evolučního algoritmu. Jsou zde uvedeny přístupy k řešení SAT problému a různé varianty k evolučním algoritmům, které jsou relevantní k danému tématu. Následně je popsaná implementace lineárního genetického programování hledající heuristiku pro řešení instancí SAT problému společne s vlastní implementací SAT solveru pracujíci s výstupem evolučně navrženého programu. Na závěr jsou shrnuty dosažené výsledky
|
|
|
Akcelerace částicových rojů PSO pomocí GPU
Krézek, Vladimír ; Schwarz, Josef (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce se zabývá technikou PSO (Particle Swarm Optimization neboli Optimalizace pomocí částicových rojů), s jejíž pomocí je možné řešit komplexní problémy. Tuto techniku lze využít při řešení složitých kombinatorických problémů (obchodní cestující, úloha o batohu), návrh integrovaných obvodů a antén, v oborech jako je biomedicína, robotika, umělá inteligence nebo i finančnictví. Přestože je algoritmus PSO velice efektivní, čas nezbytný pro nalezení vhodného řešení reálných problémů často přesahuje hranice únosnosti. Cílem této práce je tedy urychlit běh tohoto algoritmu pomocí grafického adaptéru, který nabízí velmi vysoký výpočetní potenciál při zachování příznivé ceny a rozměru. Pro demonstrační účely a ověření kvality implementace byl zvolen problém rozhodnutelnosti systému logických formulí (SAT), jenž patří do třídy NP-úplných problémů. Redukcí časové náročnosti algoritmu PSO při řešení SAT problému jsme tedy schopni akcelerovat celou třídu úloh a řešit problémy, které byly dosud prakticky neřešitelné.
|
host ::
RSS.