|
|
Heuristics for Length Bounded Cuts
Madaj, Pavel ; Kolman, Petr (vedoucí práce) ; Koutecký, Martin (oponent)
Táto práca sa zaoberá problémom nájdenia minimálneho dľžkovo obmedzeného rezu v grafe. Najprv poskytneme stručný prehľad problému a jeho aplikácií. Potom zhrnieme známe teoretické výsledky a aproximačné algoritmy. Skúmame existujúce formulácie li- neárnych programov pre tento problém a navrhujeme novú. Stručná diskusia o potenciál- nych ťažkých príkladoch, ktoré sú využité na testovanie našich formulácií, je tiež zahrnutá. Zameriavame sa na správanie našej navrhovanej rodiny lineárnych programov a porovná- vame ju s existujúcou prirodzenou formuláciou. Taktiež porovnávame výkonnosť rôznych heuristík a aproximačných algoritmov v praxi skúmaním ich správania sa na veľkej sade malých instancií. 1
|
|
|
Efficient representation of k-mer sets
Milyutina, Ekaterina ; Veselý, Pavel (vedoucí práce) ; Kolman, Petr (oponent)
In this thesis we explore and compare various methods for efficient k-mer set representation. We evaluate traditional de Bruijn graph representation techniques against greedy approximation algorithms for the Shortest Superstring Problem. We describe the linear- time implementation of the well-known Greedy algorithm by Ukkonen [1990] and extend it to another related algorithm, called TGreedy. In addition, we test selected algorithms on a bacterial genome and pangenome to highlight the differences in the size of their output representation and the computational resources used, providing an insight into their respective efficiencies.
|
|
|
Approximation and Online Algorithms
Tichý, Tomáš ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent) ; van Stee, Rob (oponent)
This thesis presents results of our research in the area of optimization problems with incomplete information-our research is focused on the online scheduling problems. Our research is based on the worst-case analysis of studied problems and algorithms; thus we use methods of the competitive analysis during our research. Althrough there are many "real-world" industrial and theoretical applications of the online scheduling problems there are still so many open problems with so simple description. Therefore it is important, interesting and also challenging to study the online scheduling problems and their simplified variants as well. In this thesis we have shown the following our results of our research on the online scheduling problems: A 1.58-competitive online algorithm for the problem of randomized scheduling of unit jobs on a single processor, where the jobs are arriving over time and the total weight of processed jobs ismaximized. A lower bound 1.172 on the competitive ratio for the problem of randomized scheduling of 2-uniform unit jobs on a single processor, where the jobs are arriving over time andthe totalweight of processed jobs is maximized. A lower bound 1.25 on the competitive ratio for the problem of randomized scheduling of s-uniform unit jobs on a single processor where s is tending to...
|
|
|
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.
|
host ::
RSS.