doc. RNDr. Dušan Knop, Ph.D.

Tajemník Akademického senátu

Závěrečné práce

Bakalářské práce

Ověřená binární halda

Autor
Luboš Zápotočný
Rok
2022
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
RNDr. Radek Hušek, Ph.D.
Anotace
Tato práce popisuje implementaci binární minimové haldy a formální důkazy korektnosti jednotlivých operací. Ověřená binární halda je následně použita v Dijkstrově algoritmu pro hledání nejkratší cesty v grafu.

Nové modely ve vícevrstevném přiřazování

Autor
Kryštof Razima
Rok
2022
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
RNDr. Jiřina Scholtzová, Ph.D.
Anotace
Přiřazovací problém je problémem na pomezí matematické a ekonomické teorie. Přiřazovací problém se skládá z agentů a položek, agenti vyjadřují své preference k položkám a cílem je najít (určitým způsobem) optimální přiřazení. Problém přiřazení je velmi dynamický problém, protože může být vzato v úvahu mnoho dalších aspektů. V tomto příkladu mají agenti více seznamů preferencí, jak je předesláno v Parameterized Analysis of Assignment Under Multiple Preferences. My jsme však k problému přistoupili jinak než v článku, motivováni množstvím výzkumů, které již byly provedeny v oblasti problému přiřazení jednoho preferenčního profilu, uvádíme syntézu jednoho profilu z více profilů. Stejně jako představení algoritmu pro nalezení Pareto optimálního řešení na takových profilech. Vzhledem k tomu, že námi prezentované profily umožňují rovnost mezi dvěma položkami (což znamená, že žádná z nich není preferována před druhou), museli jsme zvolit poněkud odlišný přístup. Hlavním cílem bylo najít algoritmické řešení se složitostí alespoň v polynomiálním čase, což se podařilo. Zabýváme se také různými aspekty spravedlnosti při takovém zadání. Následující řešení by měla být přínosná nejen pro Přiřazovací problém s více preferencemi, neboť představují nový pohled na nedávno publikovaný problém, ale také pro Přiřazovací problém s nestriktními profily.

Férová řešení pro problém Target Set Selection

Autor
Bruno Kraus
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
Ing. Šimon Schierreich
Anotace
Target Set Selection je NP-těžký problém klíčový v oblasti virálního marketingu. Pro danou sociální síť se problém Target Set Selection zabývá minimální velikostí množiny agentů, jejichž působení nakonec ovlivní každého v dané sociální síti. V této práci představujeme Fair Target Set Selection problém, jehož řešení uspokojuje férovou cenu. Férová cena vynucuje férové rozdělovení target setu omezením maximalního počtu agentů v okolí nějakého agenta v řešení. V této práci studujeme parametrizovanou složitost Fair Target Set Selection a ukazujeme jeho W[1]-těžkost vůči parametrům treewidth, feedback vertex set number a treedepth, W[2]-těžkost pro jeho přirozený parametr férovou cenu. Jako pozitivní výsledek ukazujeme FPT algoritmus při parametrizeci kombinovaným paremetrem vertex cover number a férová cena. Naše další výsledky se dostavují při zohlednění speciálních případů thresholdové funkce. Dokazujeme NP-těžkost pro Fair Target Set Selection a to i tehdy, když jsou všechny thresholdy rovny konstantě c >= 3. Na závěr předkládáme argumenty, proč se domníváme, že Fair Target Set Selection s majoritními tresholdy lze řešit na stromech v polynomiálním čase.

Stabilita Hedonických her se strukturovanými preferencemi

Autor
Jan Šmolík
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
Ing. Václav Blažej
Anotace
Problém stabilních spolubydlících s podmínkami různorodosti spočívá v rozdělení agentů dvou typů do koalic pevné velikosti na základě jejich preferencí, které závisí pouze na počtu agentů stejného typu. V této práci se zabýváme stabilitou takových rozdělení v závislosti na velikosti koalice a struktuře preferenčních profilů agentů. Snažíme se uchopit problém v celé jeho šíři a vytvořit nadhled nad celou problematikou představením Hedonických her a jejich zajímavých podtříd. Představujeme nový randomizovaný algoritmus na rychlé hledání core stabilních řešení instancí tohoto problému a ukazujeme, jakých výsledků jsme pomocí algoritmu dosáhli. Nalezli jsme malou single-peaked instanci s prázdným core a ověřili jsme, že každá instance tohoto problému, kde velikost koalic = 3, preferenční relace všech agentů jsou single-peaked a počet agentů <= 30, velikost koalic = 3 a počet agentů <= 15, velikost koalic = 4, preferenční relace všech agentů jsou single-peaked a počet agentů = 8, má core stabilní řešení. Předkládáme argumenty, proč se domníváme, že každá instance, kde velikost koalic = 3, velikost koalic = 4 a preferenční relace všech agentů jsou single-peaked, má core stabilní řešení.

Kernelizace problému maximálního řezu

Autor
František Koutenský
Rok
2020
Typ
Bakalářská práce
Vedoucí
RNDr. Dušan Knop, Ph.D.
Oponenti
Ing. Radovan Červený
Anotace
Tato práce shrnuje dosavadní výzkum problému Max Cut a představuje nový kernelizační algoritmus pro Simple Max Cut problém parametrizovaný velikostí minimálního vrcholového pokrytí vstupního grafu G omezující velikost jádra funkcí O(vc(G)^4), kde vc(G) označuje velikost minimálního vrcholového pokrytí grafu G.

Certifikované algoritmy pro hledání minimální kostry

Autor
Tomáš Homola
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
prof. Ing. Pavel Tvrdík, CSc.
Anotace
Tato práce se zabývá úvodem do procesu deduktivní formální verifikace. Teoretická část práce seznámí čtenáře s frameworkem Frama-C pro modulární analýzu programů napsaných v jazyce C. Ten k verifikaci používá pluginy, automatické systémy pro dokazování teorémů a anotační jazyk ACSL. Dále jsou rozebrány důležité části verifikačního prostředí, jeho instalace a použití. Praktická část blíže seznámí čtenáře na ukázkových příkladech s použitými taktikami a metodami. Výsledkem práce je plně verifikovaný algoritmus pro hledání minimální kostry v grafu.

Diplomové práce

Součtové grafy

Autor
Šimon Schierreich
Rok
2020
Typ
Diplomová práce
Vedoucí
RNDr. Dušan Knop, Ph.D.
Oponenti
doc. Ing. Štěpán Starosta, Ph.D.
Anotace
Neorientovany graf G=(V,E) nazveme součtovym grafem, pokud existuje injektivni funkce s: V - N přiřazujici vrcholům kladna cela čisla tak, že pro každe dva vrcholy u,v [?] V plati, že jsou v grafu G spojeny hranou pravě tehdy, když existuje třeti vrchol w [?] V takovy, že s(w) = s(u) + s(v). Neni těžke nahlednout, že žadny souvisly graf nemůže byt součtovym grafem, jelikož vrchol s největšim priřazenym čislem nemůže mit žadneho souseda. Proto se snažime najit součtove čislo grafu G, což je minimalni počet izolovanych vrcholů, ktere je třeba ke grafu G připojit, abychom z něj součtovy graf udělali. Zminěny problem studujeme v cele jeho šíři. Nejdřive se věnujeme formalnimu zavedeni všech pojmů a studiu vlastnosti součtovych grafů. Pro vybrane třidy grafů pak uvadime deterministicke algoritmy, ktere z grafu G vytvoři součtovy graf za použiti minimalniho možneho počtu přidanych vrcholů. V posledni časti prace prezentujeme naš exaktni exponencialni algoritmus, ktery dokaže najit součtove čislo libovolneho grafu.