Dr. techn. Ing. Jan Legerský

Dr. techn. Ing. Jan Legerský

doc. Ing. Ivan Šimeček, Ph.D.

Katedra softwarového inženýrství

Tato bakalářská práce se zaměřuje na návrh a implementaci multiplatformní desktopové aplikace, která poskytuje grafické uživatelské rozhraní pro knihovnu PyRigi. PyRigi je open-source nástroj v Pythonu pro výzkum restrukturální teorii tuhosti a pohyblivosti, ale v současné době funguje pouze jako knihovna Pythonu nebo rozhraní příkazového řádku. Cílem této práce je zpřístupnit jeho funkcionalitu širšímu publiku tím, že nabídne interaktivní prostředí pro kreslení, úpravy a vizuální analýzu grafů a konstrukcí. Aplikace podporuje konstrukci grafů, konfiguraci parametrů, analýzu tuhosti, vizualizaci infinitesimálnich pohybů a výpočet NAC-barvení. Návrh klade důraz na responzivitu, použitelnost a rozšiřitelnost. PyQt6 byl vybrán jako primární framework díky svým nativním multiplatformním možnostem, efektivnímu grafickému enginu a bezproblémové integraci s Pythonem a PyRigi. Výsledkem je uživatelsky přívětivá aplikace, která propojuje interaktivní geometrii s algoritmy teorie tuhosti, čímž eliminuje potřebu uživatelů psát kód pro standardní analýzy. Práce se také zabývá architekturou, balením a omezeními vyplývajícími z výpočetní složitosti určitých algoritmů.

Práce na DSpace

Dr. techn. Ing. Jan Legerský

Dr. rer. nat. Rodrigo Augusto da Silva Alves

Katedra aplikované matematiky

Tato práce se zaměřuje na aplikaci zpětnovazebného učení v teorii strukturální tuhosti. Cílem této práce je znovu implementovat evoluční algoritmus hlubokého zpětnovazebného učení, deep cross-entropy method, a aplikovat ji v teorii strukturální tuhosti. V roce 2021 Adam Zsolt Wagner využil tento algoritmus k vyvrácení některých hypotéz pomocí nalezení protipříkladů. Tento algoritmus maximalizuje určitou hodnotící funkci a hlavním cílem této práce je najít minimálně tuhý graf s vysokým počtem realizací v rovině. Teorie strukturální tuhosti je odvětvím matematiky, které studuje grafy a vlastnost tuhosti. Realizace grafu je zobrazení vrcholů do roviny. Dvojice realizace a grafu je považována za tuhou, pokud ji nelze spojitě deformovat se zachováním délek hran. Rigidita je vlastnost grafu při použití generické realizace. Existující implementace počítající počet realizací pro daný minimálně tuhý graf je využita v této práci. Počty realizací byly již dříve spočítány pro všechny minimálně tuhé grafy s maximálně 14 vrcholy. Pro větší grafy existují pouze dolní odhady maximálního počtu. Všechny nejlepší známé grafy s až 15 vrcholy byly v této práci nalezeny v podstatně kratším čase. Výsledkem této práce je několik efektivních reimplementací deep cross-entropy method ve formě Python skriptů. Dvě reimplementace byly vytvořeny pro reprodukci Wagnerových výsledků a jsou obecné, takže je lze použít i pro jiné problémy. Bylo ukázáno, že jsou přibližně 50krát rychlejší než původní implementace vytvořená Wagnerem. Další dvě implementace byly vytvořeny na konstrukci minimálně tuhých grafů s vysokým počtem realizací. Všechny implementace jsou paralelizované a snadno spustitelné na serveru s vysokým počtem CPU jader, což umožňuje využít veškeré dostupné výpočetní proštředky.

Práce na DSpace

Dr. techn. Ing. Jan Legerský

Ing. Hanka Řada, Ph.D.

Katedra aplikované matematiky

Ústředním tématem teorie strukturální tuhosti je studium minimálně tuhých grafů, které slouží jako základní matematické modely pro struktury, jež nelze spojitě deformovat se zachováním délek hran, a mají řadu praktických aplikací. Navzdory své tuhosti mohou tyto grafy stále připouštět více realizací se stejnými délkami hran v euklidovském prostoru. Nalezení minimálně tuhých grafů na n vrcholech s maximálním počtem realizací je výpočetně náročný problém, jelikož velikost prohledávaného prostoru roste super-exponenciálně s počtem vrcholů. V této práci je tato výzva řešena pomocí přístupu zpětnovazebného učení, který vyhledává minimálně tuhé grafy vykazující vzácné extremální vlastnosti. Konkrétně je algoritmus deep cross-entropy method zkombinován s enkodérem Graph Isomorphism Network k vytvoření permutačně ekvivariantního modelu strategie. Díky tomuto přístupu se podařilo dosáhnout nejlepších dosud známých dolních odhadů pro počet realizací v rovině. Dále byly stanoveny vylepšené dolní odhady pro počet realizací na sféře a pro počet NAC-obarvení. Kromě toho algoritmus nachází tyto extremální grafy řádově rychleji než předchozí metody, přičemž nevyžaduje téměř žádné expertní znalosti z oblasti teorie strukturální tuhosti.

Práce na DSpace

Dr. techn. Ing. Jan Legerský

Ing. Tomáš Kalvoda, Ph.D.

Katedra aplikované matematiky

Tato bakalářská práce se zabývá aproximací minimálního eukleidovského Steinerova stromu (MEST), což je NP-těžký optimalizační problém spočívající v nalezení nejkratšího spojení dané množiny bodů v rovině s možností zavedení dodatečných Steinerových bodů, které slouži jako přechodné body. Cílem práce je navrhnout a implementovat model založený na neurálních celulárních automatech (NCA), který je schopen aproximovat řešení tohoto problému prostřednictvím emergentní dynamiky, vznikající z lokálních interakcí. Nejprve jsou představeny teoretické základy Steinerových stromů a celulárních automatů, následně je diskutován koncept neurálních celulárních automatů jako diferenciovatelného modelu umožňujícího učení dynamiky systému pomocí metod gradientního učení. Následně je popsán navržený přístup k implementaci modelu a tréninku, včetně generování tréninkových dat. Navržený přístup nejprve reprezentuje vstupní graf ve formě vícerozměrné stavové mřížky, ve které jsou zakódovány pozice terminálů a konvexní obal grafu. Tato mřížka slouží jako vstup pro neurální celulární automat, který pak stavovou mřížku evolvuje do aproximovaného řešení. Model se učí aproximovat pozice Steinerových bodů, které představují klíčovou část řešení, zatímco samotná konstrukce výsledného stromu je realizována externě pomocí algoritmů minimální kostry. Ze stavové mřížky jsou pak extrahovány pozice Steinerových bodů, podle kterých je sestaven výsledný strom. Tréninková data jsou generována pomocí knihovny GeoSteiner, přičemž je využita banka vzorků a různé perturbace pro snahu o zvýšení výkonosti modelu. Výsledky ukazují, že navržený model je schopen aproximovat pozice Steinerových bodů v omezené míře.

Práce na DSpace

Dr. techn. Ing. Jan Legerský

Mgr. Michal Opler, Ph.D.

Katedra teoretické informatiky

Jednou z otázek v strukturální teorii tuhosti (Rigidity Theory) je, zda realizace vrcholů grafu do roviny je pohyblivá, tj. zda umožňuje spojitou deformaci neměnící délku hran. Pohyblivá realizace souvislého grafu v rovině existuje právě tehdy, když graf má NAC-obarvení, což je hranové obarvení dvěma barvami takové, že pro každý cyklus jsou všechny hrany obarveny stejnou barvou, nebo jsou každou barvou obarveny alespoň dvě hrany. Je NP-úplné rozhodnout, zda graf má NAC-obarvení, v práci ukazujeme, že problém je NP-úplný i pro grafy s maximálním stupněm pět. Představujeme značně rychlejší algoritmus i s jeho implementací na hledání NAC-obarvení společně s různými heuristikami. Srovnáváme ho s předchozími algoritmy a porovnáváme i heuristiky mezi sebou. Následně představujeme FPT algoritmus na počítání NAC-obarvení parametrizovaný stromovou šířkou. Navíc popisujeme vztahy se stabilními řezy grafu a implementujeme algoritmus pro jejich hledání v flexible grafech.

Práce na DSpace