|
|
Clustering techniques for ads monitoring
Dzetkulič, Tomáš ; Kolman, Petr (vedoucí práce) ; Kára, Jan (oponent)
Práca sa zaoberá možnosťami klastrovania inzercie so zameraním na realitnú inzerciu. V prvej časti práce definujeme čo to je klastrovanie, kde sa používa a aké sú typické požiadavky na klastrovacie algoritmy. Popíšeme existujúce klastrovacie metódy, ich vlastnosti a použitie. Posúdime ich vhodnosť pre oblasť inzercie a vyberieme najvhodnejší algoritmus pre klastrovanie rádovo miliónov inzerátov. V ďalšej časti detailne popíšeme interpretáciu inzerátu ako prvku vektorového priestoru s vysokou dimenziou a algoritmus klastrujúci prvky takéhoto vektorového priestoru založený na rodinách lokálnych hašovacích funkcií. Popíšeme jeho vlastnosti, časovú a pamäťovú zložitosť, jeho parametre a očakávané výsledky behu algoritmu. V implementačnej časti rozoberieme detaily implementácie v programovacom jazyku Java a navrhneme vhodné uloženie dát v relačnej databázi. V časti venovanej testom potom zhodnotíme výsledky behu algoritmu na reálnych dátach a porovnáme ich s očakávaným výstupom algoritmu. V závere práce posúdime možnosti ďalšieho rozšírenia použitej klastrovacej metódy.
|
|
|
Problém hledání optimální cesty v dopravních sítích při vícekriteriální metrice
Vodička, Jan ; Fiala, Jiří (vedoucí práce) ; Kolman, Petr (oponent)
V práci jsou popsány základní metody hledání optimální cesty v grafech se zaměřením na některé specifické vlastnosti dopravních sítí, zmíněny jsou existující postupy, které se jejich řešením zabývají. Je navržena nelineární cenová funkce, díky níž lze zohledňovat uživatelské preference jednotlivých kritérií cesty (délka, čas, cena, apod.). Nabídnuty jsou i potřebné modifikace vyhledávacích algoritmů. Je popsána metoda pro zohlednění dopravních manévrů libovolné délky, jež zvětšují množinu uzlů i hran grafu úměrně k počtu hran v množině manévrů. Prezentována je i obecná metoda eliminace množství hran, jež je nutné zahrnout do výpočtu optimální cesty mezi množinami uzlů v grafu. K tomu je využito předpočítaných množin hran. Výstupem předkládané diplomové práce jsou tři metody řešící specifické aspekty vyhledávání optimální cesty v dopravní síti. Zatímco při praktickém použití první z těchto metod se vyskytují omezení velikosti zpracovatelných dat, další dvě metody tvoří základ komerčního navigačního systému. Powered by TCPDF (www.tcpdf.org)
|
|
|
Poloautomatická analýza struktury textu
Šenkýř, Michal ; Kolman, Petr (vedoucí práce) ; Skopal, Tomáš (oponent)
Práce popisuje návrh a implementaci algoritmu, který na základě počáteční lidské nápovědy převádí data v HTML dokumentech vygenerovaných z databáze, avšak určených pro lidské čtení, do strukturovaného tvaru vhodného pro strojové čtení. Na vstupu se předpokládá přítomnost nějaké (nejčastěji grafické) struktury v dokumentu a poskytnutí několika vzorových, sémanticky označených, položek v dokumentu uživatelem. Na výstupu se poté očekává zachycení sémantické struktury dat v dokumentu. Součástí výsledné aplikace je editorová část, která obsahuje grafické nástroje pro snadné označení sémantiky vzorových položek, a serverová část, která obsahuje nástroje pro následné hromadné zpracování dokumentů. Aplikace byla testována na realitních inzertních webech a výsledky tohoto testování byly rozebrány na konci práce. Práce stručně představuje také jiné existující aplikace založené na podobném principu a poskytuje jejich srovnání.
|
|
|
Nejkratší cesty při vyhledávání dopravního spojení
Hronik, Jan ; Kolman, Petr (vedoucí práce) ; Škovroň, Petr (oponent)
Zabýváme se algoritmy pro hledání nejlepšího spojení podle jízdního řádu, přičemž pojmem nejlepší myslíme nejkratší vzhledem ke zvolenému ohodnocení cest (např. nejrychlejší, nejkratší na počet ujetých km, spojení s nejmenším počtem přestupů). Problém nejkratšího spojení v dopravní síti je formalizován a převeden na problém nejkratší cesty v grafu. K tomu je navržena reprezentace dopravní sítě pomocí orientovaného grafu. Dále je popsáno několik standardních algoritmů pro hledání nejkratších cest v grafu a jejich optimalizace pro použití při hledání dopravních spojení. Nakonec je porovnána výkonnost jednotlivých algoritmů při jejich použití na (1) vlakovou sít pro Českou republiku a (2) na náhodně vygenerovaný graf.
|
|
|
Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (vedoucí práce) ; Tiwary, Hans Raj (oponent)
Problémy hledání řezu v grafu mohou být popsány jako problémy, v kterých jsme žádáni rozdělit graf na 2 nebo více částí. V této práci podáváme přehled metod a konceptů používaných při hledání nejlepších řezů vzhledem k několika kritériím. Dokážeme dualitu mezi problémem hledání multi-komoditního toku a řídkého řezu z práce autorů Leighton a Rao (LR). Dokážeme ji pomocí algoritmu užívajícího lineárního programování a geometrického vnořování. Následně představíme práci autorů Arora, Rao a Vazirani (ARV) a jejich algoritmus založený na semidefinitním programování a také na geometrickém vnořování. Též vysvětlíme koncept expanzních toků poprvé představených v práci ARV. Další rozsáhlá sekce je věnovaná spektrální teorii. Prvky spektrální teorie a koncept expanzních toků se spojí v kapitole o algoritme využívajícího jednokommoditní toky. Nakonec ukážeme výsledky naši implementace varianty algoritmu využívajícího jednokomoditní toky a algoritmu vnořování dle LR. Powered by TCPDF (www.tcpdf.org)
|
|
|
Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Kráľ, Daniel (oponent)
Courcellova věta mluví o výpočetní složitosti rozhodovacích problémů defino- vaných formulemi monadické logiky druhého řádu nad relačními strukturami s omezenou stromovou šířkou. Pro pevnou stromovou šířku a vstupní formuli dává Courcellova věta algoritmus, který formuli rozhodne v lineárním čase nad strukturou dané stro- mové šířky. Práce podává samostatný důkaz Courcellovy věty pomocí metod teorie konečných modelů. Dále obsahuje důkazy všech potřebných prerekvizit hlavního důkazu, zejména v teorii konečných modelů široce využívané Ehrenfeuchtovy-Fraïssého věty. Práce též obsahuje implementaci algoritmu plynoucího z tohoto důkazu. Nakonec nastiňuje aktuální stav výzkumu dané oblasti a z něj plynoucí možnosti. 1
|
|
|
Délkově omezené řezy v grafech
Berg, Michal ; Kolman, Petr (vedoucí práce) ; Dvořák, Pavel (oponent)
V této práci se budeme zabývat problémem délkově omezeného řezu, nazývaného také L-omezený řez. Ukážeme kombinatorický algoritmus pro hledání minimálního L-omezeného řezu na grafech omezené stromové šířky založený na dynamickém programování. Následně také ukážeme, že se tento algoritmus dá použít i pro hledání L-omezeného řezu na rovinných grafech. Také se podíváme na problém (dG(s, t) + 1)-omezeného řezu. Je známé, že tento problém je NP-těžký na obecných grafech. Ale to, jestli je NP-těžký i na rovinných grafech se speciálními vrcholy na vnější stěně, je otevřený problém. Pokusíme se nastínit způsob, kterým bychom možná mohli ukázat, že tento problém je řešitelný v polynomiálním čase.
|
|
|
Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fellows, Michael R. (oponent) ; Tantau, Till (oponent)
Tato práce podává důkaz existence kompaktních rozšířených formulací pro širokou škálu polytopů souvisejících s problémem omezujících podmínek (CSP), grafovou monadickou logikou druhého řádu (MSO) a rozšířeními MSO, mají-li dané instance omezenou stromovou šířku. Ukážeme, že naše rozšířené formulace mají další užitečné vlastnosti a odkrýváme souvislosti mezi MSO a CSP. Docházíme tak k závěru, že kombinace MSO logiky, CSP a geometrie poskytuje rozšiřitelný rámec pro konstrukci kompaktních rozšířených formulací a parametrizovaných algoritmů pro grafy s omezenou stromovou šířkou. S použitím těchto nástrojů pak zcela zodpovíme otázku parametrizované složitosti různých rozšíření MSO na dvou třídách grafů, konkrétně grafech s omezenou stromovou šířkou a s omezenou různorodostí sousedství. Objevili jsme, že (ne)linearita těchto rozšíření určuje parametrizovanou složitost na grafech s omezenou různorodostí sousedství. Na závěr studujeme tzv. posunutou kombinatorickou optimalizaci, která tvoří nelineární optimalizační rámec zobecňující standardní kombinatorickou optimalizaci. V této oblasti poskytneme prvotní zjištění z perspektivy parametrizované složitosti.
|
|
|
Toky cestami omezené délky
Altmanová, Kateřina ; Kolman, Petr (vedoucí práce) ; Pangrác, Ondřej (oponent)
V bakalářské práci se zabýváme problémem k-omezeného toku, a tedy toku, který lze dekomponovat na cesty délky nejvýše k. Podáváme přehled o známých výsledcích v této oblasti a zmiňujeme také problém k-omezeného řezu, což je množina hran z tokové sítě, která po odebrání z tokové sítě způsobí, že nee- xistuje v takto pozměněné síti k-omezený tok. Hlavním cílem práce je detailní prozkoumání článku The Maximum k-flow in a Network od autorů V. Kou- bek a A. Říha, publikovaného ve sborníku konference Mathematical Foundations of Coputer Science 1981, str. 389-397 a podání vysvětlení složitých pasáží a do- plnění vynechaných důkazů. Cíl doplnit chybějící důkazy, v této práci naplněný není. Ukázalo, že v citovaném článku mají autoři zásadní chybu. Místo doka- zování vynechaných důkazů se zaměřujeme na popsání problému, proč původní algoritmus nefunguje. 1
|
|
|
Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent)
Abstrakt. Práce se věnuje problému preemptivního online rozvrhování paralelních úloh. Podává přehled předchozích výsledků pro tento problém. Pro některé speciální varianty problému, například pro úlohy na jeden a dva procesory, poskytuje nové výsledky, jak v podobě dolních odhadů, tak v podobě kompetitivních algoritmů. Je objevena chyba v dříve publikovaném dolním odhadu a opravena na správný dolní odhad. Je navržen algoritmus pro verzi problému se čtyřmi procesory a s úlohami na jeden a dva procesory, pro který je vyslovena hypotéza, že dosahuje nejlepšího možného kompetitivního poměru.
|
host ::
RSS.