|
|
Cache-oblivious Algorithms
Vaner, Michal ; Mareš, Martin (vedoucí práce) ; Falt, Zbyněk (oponent)
V této práci se zabýváme výpočetním modelem cache-oblivious algoritmů, který je inspirovaný chováním paměťové hierarchie současných počítačů. V tomto modelu studujeme některé grafové algoritmy a techniky jejich návrhu. Zabýváme se zejména procházením grafu, rozkladem na komponenty souvislosti a hledáni v inkluzi maximálního párování. Taktéž zkoumáme třídění a násobení matic jako podproblémy mnohých grafových algoritmů. Mimo dříve známých algoritmů uvádíme i několik nových. Jejich efektivitu posuzujeme jak asymptoticky, tak experimentálně na reálném hardwaru a srovnáváme je s klasickými algoritmy.
|
|
|
Desktop client for open social networks
Kasinec, Maroš ; Valla, Tomáš (vedoucí práce) ; Vaner, Michal (oponent)
Sociálne siete zažívajú v poslednej dekáde obrovský romach a ovplyvnili nielen spôsob on-line komunikácie a sociálnej interakcie ale tiež oblasť obchodu, médií či vládnych inštitúcií. Avšak ich hlavný nedostatok, uzvretý a centralizovaný charakter, ostáva nepovšimnutý medzi širokou verejnosťou. Táto práca pojednáva a hodnotí ich otvorené a decentralizované alternatívy a súčasne sa zameriava na jednu konkrétnu - buddycloud. Vďaka využitiu XMPP protokolu, buddycloud a jeho protokol Channel sa javí ako sľubný prístup pre otvorenie ekosystému sociálnych sietí. Umožňuje im komunikovať federatívnym spôsobom ako funguje dnes e-mailová sieť. Ako príspevok do projektu buddycloud táto práca predstavuje aplikáciu SocialDesktopClient, desktopový klient pre širokú škálu sociálnych sietí. Bližšie sa zaoberá modulárnym návrhom klienta a implementáciou protokolu Channel ako prvej sociálnej sieti.
|
|
|
Cache-oblivious Algorithms
Vaner, Michal ; Mareš, Martin (vedoucí práce) ; Falt, Zbyněk (oponent)
V této práci se zabýváme výpočetním modelem cache-oblivious algoritmů, který je inspirovaný chováním paměťové hierarchie současných počítačů. V tomto modelu studujeme některé grafové algoritmy a techniky jejich návrhu. Zabýváme se zejména procházením grafu, rozkladem na komponenty souvislosti a hledáni v inkluzi maximálního párování. Taktéž zkoumáme třídění a násobení matic jako podproblémy mnohých grafových algoritmů. Mimo dříve známých algoritmů uvádíme i několik nových. Jejich efektivitu posuzujeme jak asymptoticky, tak experimentálně na reálném hardwaru a srovnáváme je s klasickými algoritmy.
|
|
|
Částečné k-stromy na plochách
Vaner, Michal ; Valtr, Pavel (oponent) ; Kratochvíl, Jan (vedoucí práce)
V této práci je řešen následující problém: Je dán graf G neúplný k-strom vnořitelný do některé plochy. Je možné jej doplnit tak, aby vznikl úplný k-strom, který je do dané plochy stále vnořitelný? Jak je ukázáno, pro malá k (· 2) to jde na libovolné ploše. Naopak, pro k ¸ 4 lze na každé ploše najít graf, který doplnit nelze a pro dostatečně velké k již nelze doplnit žádný. Případ, kdy k = 3, je hraniční, nebot' existuje nekonečně mnoho vnořitelných úplných 3-stromů, ale nejsou vnořitelné všechny. Ví se, že takto rozšiřovat lze 3-stromy v rovině, zde je pro úplnost uveden prozatím nepublikovaný důkaz prof. Kratochvíla a prof. Thomase. V této práci je důkaz rozšířen na projektivní rovinu. Další plochy zatím prozkoumané nejsou.
|
host ::
RSS.