|
|
Nejkratší cesty v grafu
Krauter, Michal ; Křivka, Zbyněk (oponent) ; Masopust, Tomáš (vedoucí práce)
Tato práce se zabývá problematikou nejkratších cest v grafu. Hledání těchto cest patří mezi základní problémy teorie grafů s četnými praktickými aplikacemi. Problém hledání nejkratších cest lze rozdělit na dvě skupiny. V první z nich hledáme nejkratší cesty z jednoho konkrétního uzlu do všech ostatních uzlů a v druhé hledáme nejkratší cesty mezi všemi páry vrcholů grafu. U každé skupiny jsou v textu uvedeny principy a algoritmy, které problém řeší. Studovány a popsány jsou jak klasické, tak i nové efektivnější metody. Z každé skupiny jsou vybrány, implementovány a experimentálně porovnány některé algoritmy pro hledání nejkratších cest v grafu.
|
|
|
Correction of Invalid Trees with Respect to Regular Tree Grammars
Svoboda, Martin ; Holubová, Irena (vedoucí práce) ; Bača, Radim (oponent) ; Pardede, Eric (oponent)
XML dokumenty a související technologie reprezentují jednu z nejrozšířenějších cest údržby a výměny dat na Webu. Velké množství reálných dokumentů ale bohužel obsahuje nejrůznější formy nekonzistence, které brání jejich úspěšnému a automatizovanému zpracování. V této práci se konkrétně věnujeme problému strukturální nevalidity a její korekce. Máme-li tedy jeden potenciálně nevalidní XML dokument modelovaný jako strom a současně jeho schéma v jazycích DTD nebo XML Schema modelované jako regulární stromová gramatika, naším cílem je najít všechny minimální opravy tohoto stromu. Námi navržený model využívá rekurzivně vnořovaných struktur korekčních multigrafů, ve kterých hledáme nejkratší cesty. Za tímto účelem formálně představíme tři korekční strategie s rozdílnými úrovněmi aplikovaných optimalizací. S ohledem na provedené experimenty pak konkrétně Refinement strategie nejenom významně překonává všechny ostatní existující přístupy, ale zároveň garantuje důležité charakteristiky, které jiné přístupy zaručit nemohou. Powered by TCPDF (www.tcpdf.org)
|
|
|
Nejkratší cesty v grafu
Krauter, Michal ; Křivka, Zbyněk (oponent) ; Masopust, Tomáš (vedoucí práce)
Tato práce se zabývá problematikou nejkratších cest v grafu. Hledání těchto cest patří mezi základní problémy teorie grafů s četnými praktickými aplikacemi. Problém hledání nejkratších cest lze rozdělit na dvě skupiny. V první z nich hledáme nejkratší cesty z jednoho konkrétního uzlu do všech ostatních uzlů a v druhé hledáme nejkratší cesty mezi všemi páry vrcholů grafu. U každé skupiny jsou v textu uvedeny principy a algoritmy, které problém řeší. Studovány a popsány jsou jak klasické, tak i nové efektivnější metody. Z každé skupiny jsou vybrány, implementovány a experimentálně porovnány některé algoritmy pro hledání nejkratších cest v grafu.
|
host ::
RSS.