|
|
Distributed computing
Šišaj, Róbert ; Dvořák, Zdeněk (vedoucí práce) ; Novotný, Miroslav (oponent)
Cieľom práce je vytvorenie systému pre distribúciu výpočtov pre menšie siete LAN. Systém by mal tvoriť platformu pre rôzne aplikácie, ktorým umožní paralelné spracovanie výpočtovo náročných úloh (hľadanie prvočísel, renderovanie videosekvencií, úpravy fotografií, ...). Čitateľ sa zoznámi s tematikou distribuovaných systémov, dozvie sa o ich výhodách i nevýhodách a osvojí si základné pojmy z tejto oblasti. Súčasťou práce je porovnanie s podobnými existujúcimi systémami (SETI@home, distributed.net). Zahrnutá je aj analýza slabín navrhovaného systému a prípadné námety na jeho vylepšenie do budúcnosti.
|
|
| |
|
|
Functional Data Stuctures and Algorithms
Straka, Milan ; Dvořák, Zdeněk (vedoucí práce) ; Koucký, Michal (oponent) ; Brodal, Gerth (oponent)
Název práce: Funkcionální datové struktury a algoritmy Autor: Milan Straka Ústav: Informatický ústav Univerzity Karlovy Vedoucí doktorské práce: doc. Mgr. Zdeněk Dvořák, Ph.D, Informatický ústav Univerzity Karlovy Abstrakt: Funkcionální programování je rozšířené a stále více oblíbené programo- vací paradigma, které nachází své uplatnění i v průmyslových aplikacích. Datové struktury používané ve funkcionálních jazycích jsou převážně perzistentní, což znamená, že pokud jsou změněny, zachovávají své předchozí verze. Cílem této práce je rozšířit teorii perzistentních datových struktur a navrhnout efektivní implementace těchto datových struktur pro funkcionální jazyky. Bezpochyby nejpoužívanější datovou strukturou je pole. Ačkoli se jedná o vel- mi jednoduchou strukturu, neexistuje jeho perzistentní protějšek s konstantní složitostí přístupu k prvku. V této práci popíšeme zjednodušenou implementaci perzistentního pole s asymptoticky optimální amortizovanou časovou složitostí Θ(log log n) a především téměř optimální implementaci se složitostí v nejhorším případě. Také ukážeme, jak efektivně rozpoznat a uvolnit nepoužívané verze per- zistentního pole. Nejvýkonnější datové struktury nemusí být vždy ty, které jsou založeny na asymptoticky nejlepších strukturách. Z toho důvodu se také zaměříme na imple- mentaci...
|
|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Studujeme podmínky na stupně vrcholů, které vynucují, že daný graf obsahuje libovolný strom z dané třídy. Tento typ problémů zahrnuje některé známé problémy z oblasti extremální teorie grafů. Nejslavnějším z nich je domněnka Erdős-Sósové, která tvrdí, že každý graf s průměrným stupněm vyšším než k − 1 obsahuje libovolný strom na k + 1 vrcholech. Naše dva hlavní výsledky jsou následující. Dokazujeme přibližnou verzi domněnky Erdős-Sósové pro husté grafy a stromy se sublineárním maximál- ním stupněm. Dále studujeme přirozené zobecnění domněnky Loebl-Komlós- Sósové a opět dokážeme přibližnou verzi této domněnky pro husté grafy. Oba výsledky jsou založeny na takzvané regularity metodě. Druhý výsledek je společnou prací s T. Klimošovou a D. Piguet. 1
|
|
|
Nowhere-dense classes of graphs
Tůma, Vojtěch ; Dvořák, Zdeněk (vedoucí práce) ; Mareš, Martin (oponent)
V této práci se zabýváme řídkými třídami grafů a jejich vlastnostmi využitelnými pro návrh algoritmů a datových struktur. Speciálně se zaměřujeme na nedávno zavedené koncepty omezené expanse a stromové hloubky, které zavedli J. Nešetřil a P. Ossona de Mendez. V této práci nejprve podáme stručný úvod do prob- lematiky a shrneme důležité výsledky a nástroje z parametrisované složitosti a algoritmické teorie modelů. Hlavní část této práce, aplikace teoretických poznatků, přináší dva nové výsledky z oblasti dynamických datových struktur. První slouží k udržování dekomposice grafu s omezenou stromovou hloubkou, druhá počítá výskyty zadaného podgrafu v udržovaném grafu. Časová i prostorová složitost operací obou struk- tur je při použití na řídké třídy grafů nízká. 1
|
|
|
Generování grafů
Mohelníková, Lucie ; Dvořák, Zdeněk (vedoucí práce) ; Jelínek, Vít (oponent)
Název práce: Generování grafů Autor: Lucie Mohelníková Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: Mgr. Zdeněk Dvořák,Ph.D., Informatický ústav Univerzity Karlovy Abstrakt: Zabýváme se generováním grafů z vybraných tříd, zejména pak grafů nakreslených na plochách. Zaměřujeme se na metodu generování za pomoci dekontrakcí vrcholů, pro níž je zásádní identifikace počátečních (ireducibilních) grafů. Uvádíme přehled výsledků o ireducibilních triangulacích a kvadrangulacích různých ploch, zejména pak nízkého rodu (rovina, projektivní rovina, Kleinova láhev). Hlavním přínosem této práce je identifikace 21 ireducibilních triangulací toru, čímž dokazujeme výsledek Lawrencenka bez použití výpočetní techniky. Klíčová slova: ireducibilní, triangulace, torus
|
|
|
Immersions and edge-disjoint linkages
Klimošová, Tereza ; Dvořák, Zdeněk (vedoucí práce) ; Kráľ, Daniel (oponent)
Grafové imerze jsou přirozená analogie k intenzivně zkoumanému konceptu grafových minorů a topologických grafových minorů, ale teorie v této oblasti je mnohem méně rozvinutá. V práci se zabýváme hledáním postačujících podmínek pro existenci imerzí a vlastnostmi grafů, které neobsahují imerzi daného grafu. Dokazujeme, že velká stromová šířka hranově čtyřsouvislého grafu implikuje existenci imerze libovolného čtyřregulárního grafu na malém počtu vrcholů, a že velký maximální stupeň hranově třisouvislého grafu implikuje existenci imerze libovolného třiregulárního grafu na malém počtu vrcholů.
|
|
|
Meze pro vzdálenostně podmíněné značkování grafů
Kupec, Martin ; Fiala, Jiří (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Problém λ − L(p, q)-značkování je přiřadit vrcholům grafu značky {0, . . . , λ} tak, aby sousední vrcholy měly značky od sebe vzdálené alespoň p a vrcholy se společným sousedem značky od sebe vzdáleny alespoň q. Zabýváme se výpočení složitostí tohoto problému a stanovujeme hraniční hodnoty λ, p a q, pro které se tento problém stává NP těžký. Důkaz je veden promocí dvou různých redukcí. Jedna je z NAE-3SATu, druhá z problémů hranového dobarvení před- barveného grafu. 1
|
|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
|
|
Algorithms based on bounded expansion - implementation and evaluation
Rapavá, Jana ; Dvořák, Zdeněk (vedoucí práce) ; Knop, Dušan (oponent)
Tato bakalářská práce navazuje na větu, která říká, že mnoho tříd grafů - konkrétně třídy s omezenou expanzí - má vlastnosti zjednodušující rozhodování grafových problémů definovatelných v logice prvního řádu. Důležitým příkladem takového problému je izomorfismus podgrafů. Cílem této práce je implementovat a otestovat navrhnutý algoritmus pro tento problém (který má lineární časovou složitost vzhledem k velikosti grafu, ve kterém hledáme podgraf). Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.