|
|
Teorie grafů - implementace vybraných problémů
Stráník, František ; Rajmic, Pavel (oponent) ; Koutný, Martin (vedoucí práce)
Tato práce je zaměřena na seznámení se základními problémy z oblasti teorie grafů. Jsou zde popsány základní pojmy i složitější problémy. Jedna část práce je zaměřena na práci s jednotlivými typy grafů. Začíná se s jednosměrně vázaným seznamem, přes obousměrně vázaný seznam až po stromy, které reprezentují nejjednodušší grafové struktury. Další část práce se potom věnuje grafu jako celku a popisuje složitější problémy a jejich řešení. Mezi tyto problémy patří vyhledávání v grafech pomocí metod DFS (Depth First Search) a BFS (Breadth First Search). Dále potom hledání nejkratší cesty za pomoci specifických algoritmů jako jsou: Dijkstrův algoritmus, Floyd-Warshallův algoritmus a Bellman-Fordův algoritmus. Poslední část je věnována problematice vyhledávaní minimálních koster grafu s využití metod Kruskalova haldového algoritmu, Jarníkova (Primova) algoritmu a Borůvkova algoritmu.
|
|
|
NP vyhledávací problémy a redukce mezi nimi
Ševčíková, Renáta ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
NP vyhledávací problémy a redukce mezi nimi Renáta Ševčíková V předložené práci studujeme třídu Total NP vyhledávacích problémů. Větší pozornost je věnována studiu podtříd této třídy a redukcí mezi nimi. Kombinujeme známé metody: vyhledávací stromy a jejich vztah k redukcím, důkaz sporem pomocí Nullstellensatz důkazového systému a dolní odhad na stupeň tohoto důkazu pomocí designů, abychom ukázali, že dvě třídy relativi- zovaných NP vyhledávacích problémů založených na Mod-p počítacím principu a Mod-q počítacím principu, kde p a q jsou různá prvočísla, nejsou mezi sebou redukovatelné. Práce je ukončena novým výsledkem separace pro p = 2 a q = 3.
|
|
|
NP vyhledávací problémy a redukce mezi nimi
Ševčíková, Renáta ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
NP vyhledávací problémy a redukce mezi nimi Renáta Ševčíková V předložené práci studujeme třídu Total NP vyhledávacích problémů. Větší pozornost je věnována studiu podtříd této třídy a redukcí mezi nimi. Kombinujeme známé metody: vyhledávací stromy a jejich vztah k redukcím, důkaz sporem pomocí Nullstellensatz důkazového systému a dolní odhad na stupeň tohoto důkazu pomocí designů, abychom ukázali, že dvě třídy relativi- zovaných NP vyhledávacích problémů založených na Mod-p počítacím principu a Mod-q počítacím principu, kde p a q jsou různá prvočísla, nejsou mezi sebou redukovatelné. Práce je ukončena novým výsledkem separace pro p = 2 a q = 3.
|
|
|
Teorie grafů - implementace vybraných problémů
Stráník, František ; Rajmic, Pavel (oponent) ; Koutný, Martin (vedoucí práce)
Tato práce je zaměřena na seznámení se základními problémy z oblasti teorie grafů. Jsou zde popsány základní pojmy i složitější problémy. Jedna část práce je zaměřena na práci s jednotlivými typy grafů. Začíná se s jednosměrně vázaným seznamem, přes obousměrně vázaný seznam až po stromy, které reprezentují nejjednodušší grafové struktury. Další část práce se potom věnuje grafu jako celku a popisuje složitější problémy a jejich řešení. Mezi tyto problémy patří vyhledávání v grafech pomocí metod DFS (Depth First Search) a BFS (Breadth First Search). Dále potom hledání nejkratší cesty za pomoci specifických algoritmů jako jsou: Dijkstrův algoritmus, Floyd-Warshallův algoritmus a Bellman-Fordův algoritmus. Poslední část je věnována problematice vyhledávaní minimálních koster grafu s využití metod Kruskalova haldového algoritmu, Jarníkova (Primova) algoritmu a Borůvkova algoritmu.
|
host ::
RSS.