|
|
On-line algoritmy barvení bipartitních grafů
Chludil, Josef ; Gavenčiak, Tomáš (oponent) ; Pangrác, Ondřej (vedoucí práce)
Instancí problému on-line barvení grafu je graf a pořadí jeho vrcholů, algoritmus potom barví popořadě vrcholy a jako informaci zná graf indukovaný předchozími vrcholy. Přirozeným algoritmem je First Fit, který obarví vrchol první přípustnou barvou. Tento algoritmus má ale slabiny, poměr mezi nalezeným a optimálním řešením může být až lineární vzhledem k počtu vrcholů grafu, a to i pro grafy bipartitní. Pro ty je ale znám algoritmus s logaritmickým aproximačním faktorem.
|
|
|
Procházky v grafech a genetické algoritmy
Szépe, Peter ; Bajer, Lukáš (oponent) ; Pangrác, Ondřej (vedoucí práce)
Název práce: Procházky v grafech a genetické algoritmy Autor:Peter Sépe Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalárské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Řešíme optimalizační úlohy nalezení maximálního tahu mezi dvěma vrcholy v orintovaném grafu s omezením na délku tohoto tahu. Je dán orientovaný graf, startovní a cílový vrchol, délková funkce na hranách a váhová funkce na vrcholech grafu a parametr omezení délky cesty L. Úkolem je najít tah ze startovního do cílového vrcholu celkové délky nejvýše L maximalizující součet vah navštívených vrcholů (každý se započítává pouze jednou).Tato úloha je NP-těžká a ani aproximační algoritmy nedávají příliš dobré výsledky. Proto je třeba pro praktické aplikace použít heuristické přístupy. Klícová slova: optimalizace, evolučné algoritmy, genetické algoritmy, grafy, procházky v grafech
|
|
|
Implementace hry Dots and Boxes
Balko, Martin ; Šámal, Robert (oponent) ; Pangrác, Ondřej (vedoucí práce)
Název práce: Implementace hry Dots and Boxes Jméno autora: Martin Balko Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalářské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Předložená práce se zabývá analýzou populární logické hry Dots and Boxes a jejích zobecněných verzí. Zaměřuje se také na nejrůznější metody a algoritmy řešení umělé inteligence protivníků. Výsledkem práce je implementace rozšířené verze této hry, ve které je možné editovat vlastní hrací plochy, hrát proti více soupeřům na několika úrovních obtížnosti a používat různá ohodnocení map. Klíčová slova: Dots and Boxes, Nimstring, Pokročilé počítání řetězů
|
|
|
Rovinná nakreslení grafů
Macošek, Jan ; Pangrác, Ondřej (vedoucí práce) ; Bálek, Martin (oponent)
Tento text se společně s přiloženým programem soustřeďuje na problematiku rovinných nakreslení grafů: Nejprve poskytuje souhrn základních vědomostí tohoto oboru, poté se zabývá testováním rovinnosti, hledáním rovinného vnoření a následným rovinným nakreslením grafu pomocí úseček Schnyderovým algoritmem. U toho je navíc zkoumán vliv různých strategií potřebné triangulace grafu a také dopad klíčového výběru vnější stěny na výsledné nakreslení z hlediska různých kritérií. Vše je doplněno obrázky jednotlivých nakreslení grafů získanými pomocí přiloženého programu. Powered by TCPDF (www.tcpdf.org)
|
|
|
Hra minolovka - výpočetní složitost a implementace hledání řešení
Hoder, Kryštof ; Fiala, Jiří (vedoucí práce) ; Pangrác, Ondřej (oponent)
V předložené práci studujeme vytváření stromových rozkladů grafu se speciálním zřetelem na grafy užitečné při hraní hry Minolovka. Zároveň formalizujeme postup hry a zavádíme potřebnou terminologii. Na základě tohoto jsme našli širokou množinu konfigurací hry, o jejichž konzistentnosti lze rozhodovat v polynomiálním čase - že problém je v obecnosti NP-úplný bylo ukázáno již dříve v jiných pracech. Taktéž popisujeme algoritmy, které klasifikují konfigurace a případně v polynomiálním čase rozhodnou o jejich konzistentnosti.
|
|
|
Bioinformatika - vývojové stromy
Hoferek, Ondřej ; Bálek, Martin (oponent) ; Pangrác, Ondřej (vedoucí práce)
Předložená práce se zabývá jedním z hlavních úkolů bioinformatiky: konstrukcí vývojových stromů. Zaměřuje se zejména na metody UPGMA a Neighbour-joining, které slouží pro konstrukci stromů na základě matice vzdáleností mezi genovými či proteinovými sekvencemi. Výsledkem práce je implementace těchto metod v programu s příjemným uživatelským prostředím umožňujícím výsledky metod porovnávat.
|
|
|
OCR ručně kreslených chemických strukturních vzorců
Zajíc, Vítězslav ; Pangrác, Ondřej (oponent) ; Bálek, Martin (vedoucí práce)
Práce se zabývá metodami a algoritmy použitými ve vypracovaném programu na rozpoznávání ručně kreslených chemických strukturních vzorců. Popisuje předzpracování vstupního obrazu pomocí Gaussova filtru, rozpoznávání čar v obraze pomocí hledání sousedních tmavých pixelů. Ukazuje nevhodnost Houghovy transformace pro rozpoznávání čar. Věnuje se hledání co nejpřesnější aproximace nalezených čar pomocí co nejméně úseček. Zavádí pohled na strukturní vzorec jako na graf a popisuje algoritmus vytváření vrcholů a hran grafu z rozpoznaných úseček za použití jednoduchých pravidel, které zkoumají délku úseček a jejich okolí. Obsahuje kapitolu věnující se rozpoznávání písmen heteroatomů a funkčních skupin pomocí porovnávání vůči předloze. Součástí práce je i samotný program.
|
|
|
Vizualizace algoritmů lineární algebry
Jakubík, Miroslav ; Hladík, Milan (oponent) ; Pangrác, Ondřej (vedoucí práce)
Predložená práca sa zameriava na problematiku implementácie algoritmov lineárnej algebry. Tieto algoritmy nie sú príliš zložité, problém nastáva v tom, že počítač môže počas výpočtu pracovať s extrémnymi hodnotami (veľké čísla, zlomky s veľkým menovateľom, …) aj keď zadanie takéto hodnoty neobsahuje. Preto ak chceme prezentovať medzivýsledky výpočtu, je vhodné, aby počítač postupoval ľudským postupom počítania a snažil sa takýmto extrémnym hodnotám vyhnúť.
|
|
|
Rozpoznávání vzorů momentovou metodou
Staněk, Jan ; Pangrác, Ondřej (oponent) ; Bálek, Martin (vedoucí práce)
Tato práce a přiložený program jsou zaměřeny na momentovou metodu používanou při rozpoznávání vzorů. Text obsahuje základní informace o metodě, jejích výhodách, omezeních, úpravách a rozšířeních. Práce je zaměřena především na poslední krok procesu rozpoznávání vzorů, tedy na vlastní výpočet momentů obrázku a tvorbu rozhodovacího stromu momentů z předem předpřipravené skupiny vzorů. Důraz je kladen na variabilitu při tvorbě rozhodovacího stromu a následný rozbor a porovnání výsledků získaných při různém nastavení procesních podmínek. Program je vytvořen v programovacím jazyce Java.
|
|
|
Algoritmy pro průnikové grafy
Štěrba, David ; Fiala, Jiří (vedoucí práce) ; Pangrác, Ondřej (oponent)
Cílem této práce je předvést techniky řešení problémů hledání maximální nezávislé množiny na průnikových grafech disku v rovině. V průnikovém grafu disku odpovídají vrcholum disky a dva vrcholy jsou sousední, právě když příslušné disky mají neprázdný pruůnik. Hlavní část práce je věnována aproximačním algoritmům a heuristikám (posouvání mřížky, zakázaný podgraf, omezené okolí vrcholu). Podáme přehled tříd diskových grafů (obecné a jednotkové diskové grafy, grafy s omezeným poloměrem disku). Tyto třídy se studují a modelují se na nich praktické problémy. Krátce zmíníme příklady možného praktického využití (značkování map, facility placement). Součástí práce je program, který demonstruje vybrané algoritmy a heuristiky.
|
host ::
RSS.