|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (vedoucí práce) ; Paulusma, Daniel (oponent) ; Šámal, Robert (oponent)
Název práce: Varianty problému obarvení Autor: Bernard Lidický Katedra: Katedra aplikované matematiky Vedoucí disertační práce: doc. RNDr. Jiří Fiala, Ph.D. Abstrakt: V této práci studujeme barvení grafů. Práce je rozdělena do tří částí, kde každá část se zabývá jinou variantou barvení. V první části se zabýváme 6-kritickými grafy na plochách a 6-kritickými grafy s malým počtem křížení. Hlavními výsledky jsou kompletní seznam 6-kritických grafů na Kleinově láhvi a 6-kritických grafů s křížícím číslem nejvýše čtyři. Druhá část je věnována vybíravosti rovinných grafů bez krátkých cyklů. Ukazu- jeme, že rovinné grafy bez 3-,7- a 8-cyklů jsou 3-vybíravé a že rovinné grafy bez trojúhelníků a s jistým omezením na 4-cykly jsou též 3-vybíravé. V poslední části se zaměřujeme na novější variantu barvení - vlnové barvení. Jde o koncept, který je motivovaný přiřazováním frekvencí a má zohlednit, že různé frekvence mají různý dosah. Zabýváme se pak zlepšováním odhadů nutného počtu barev k obarvení čtvercové a šestiúhelníkové mřížky. Klíčová slova: kritické grafy, seznamové barvení, vlnové barvení, rovinné grafy, krátké cykly
|
|
|
KBang
Čevora, Michal ; Lidický, Bernard (vedoucí práce) ; Dokulil, Jiří (oponent)
Cílem této práce je převést karetní hru Bang! do počítačové hry hratelné přes počítačovou sít'. Na začátku práce představuji základní koncepty hry Bang! a zabývám se řešením problémů spojených s implementací hry. V následujícím textu popisuji architekturu aplikace z hlediska serveru i klienta. Od obecné architektury se dostávám k popisu konkrétně implementace. Nejprve představím použitou knihovnu Qt, včetně důvodů pro její použití, poté popisuji implementaci všech částí projektu. V závěru práce se nachází uživatelská dokumentace.
|
|
|
Varianty problému obarvení
Lidický, Bernard
V předložené práci studujeme seznamové barvení rovinných grafů. Seznamové barvení je varianta problému barvení grafu, kde každý vrchol má přidělený svůj vlastní seznam možných barev. Říkáme, že graf je k-vybíravý, je-li možné nalézt dobré obarvení pokaždé, když všechny seznamy obsahují alespoň k barev. Je známo, že každý rovinný graf bez trojúhelníků je 4-vybíravý a každý rovinný bipartitní graf (t.j. bez lichých cyklů) je 3-vybíravý. Práce ukazuje postačující podmínky pro 3-vybíravost rovinných grafů bez trojúhelníků s omezeným výskytem krátkých cyklů.
|
|
|
Monkey Bank Robbers
Škoda, Dominik ; Lidický, Bernard (vedoucí práce) ; Cibulka, Josef (oponent)
Práce se týká vytvoření počítačové hry inspirované hrou RoboRally. Program následuje schéma klient-server a umožňuje hráčům hrát společně hru po internetu. Aplikace běžící na serveru spravuje jednotlivé hry a stará se o synchronizaci jed- notlivých hráčů. Program dále dovoluje implementovat umělou inteligenci, která se může připojovat do her s jinými hráči. Každý hráč si může vytvořit jakoukoliv mapu a hrát hru s kteroukoliv mapou. Projekt je navržen tak, aby se v budoucnu dal snadno rozšířit. Program je vytvořen v jazyce JAVA.
|
|
|
Hledání shluků v grafech
Navrátil, Jan ; Lidický, Bernard (vedoucí práce) ; Mareš, Martin (oponent)
Cílem práce je vytvořit aplikaci, která dokáže hledat shluky v grafech. Aplikace obsahuje na výběr několik modifikovaných algoritmů klasické shlukové analýzy a grafových algoritmů využívaných pro detekci komunit v komplexních sítích. Účelem práce není optimalizace implementace na rychlost ale možnost vyzkoušení a porovnání výsledků jednotlivých algoritmů a ověření, jestli jsou specializované grafové algoritmy skutečně vhodnější. Jádrem úkolu bylo tedy modifikovat algoritmy shlukové analýzy (byly vybrány čtyři, s řadou kombinovatelných nastavení) pro práci nad grafy a společně s algoritmy hledajícími komunity v sítích (dva, oba ve více variantách) je implementovat a prezentovat v rámci jedné aplikace.
|
|
|
MP3 editor
Löffelmann, Petr ; Mareš, Martin (vedoucí práce) ; Lidický, Bernard (oponent)
Název práce: MP3 editor Autor: Petr Löffelmann Katedra / Ústav: Katedra aplikované matematiky Abstrakt: Práce pojednává o digitalizovaném zvuku uloženém ve formátu MPEG 1 Layer III (MP3) a za svůj hlavní cíl si klade implementovat editační knihovnu, která bude nad MP3 soubory provádět vybrané úpravy. Text se v počátku zabývá obecným popisem metod používaných při kompresi zvuku do tohoto formátu, dále se věnuje struktuře MP3 souboru a následně rozebírá proces jeho dekomprese. V následujících částech se práce soustředí na popis implementace samotné editační knihovny a kroky, které musí být učiněny pro vykonání editačních operací. Dodatkem k práci je programátorská dokumentace knihovny a CD s její funkční verzí. Klíčová slova: MP3, editor, komprese
|
|
|
Elevator scheduling algorithms
Hlísta, Peter ; Cibulka, Josef (vedoucí práce) ; Lidický, Bernard (oponent)
Práca porovnáva rôzne systémy riešenia výťahov vo výškových budovách s použitím počítačovej simulácie. Tieto systémy sú porovnávané podľa rôznych kritérií, pričom základným kritériom je priemerný čas čakania na výťah. Ďalšími kritériami sú náklady na dopravu a najdlhší čas čakania na výťah. Použité algoritmy sú testované na väčšom počte ľudí než vo väčšine dostupnej literatúry, ktorá skúma zlepšenia väčšinou na dvoch, troch ľuďoch. Výsledky ukazujú, že má zmysel zaoberať sa každým testovaným algoritmom, pretože každý z nich má svoje výhody a nevýhody.
|
|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (vedoucí práce) ; Paulusma, Daniel (oponent) ; Šámal, Robert (oponent)
Název práce: Varianty problému obarvení Autor: Bernard Lidický Katedra: Katedra aplikované matematiky Vedoucí disertační práce: doc. RNDr. Jiří Fiala, Ph.D. Abstrakt: V této práci studujeme barvení grafů. Práce je rozdělena do tří částí, kde každá část se zabývá jinou variantou barvení. V první části se zabýváme 6-kritickými grafy na plochách a 6-kritickými grafy s malým počtem křížení. Hlavními výsledky jsou kompletní seznam 6-kritických grafů na Kleinově láhvi a 6-kritických grafů s křížícím číslem nejvýše čtyři. Druhá část je věnována vybíravosti rovinných grafů bez krátkých cyklů. Ukazu- jeme, že rovinné grafy bez 3-,7- a 8-cyklů jsou 3-vybíravé a že rovinné grafy bez trojúhelníků a s jistým omezením na 4-cykly jsou též 3-vybíravé. V poslední části se zaměřujeme na novější variantu barvení - vlnové barvení. Jde o koncept, který je motivovaný přiřazováním frekvencí a má zohlednit, že různé frekvence mají různý dosah. Zabýváme se pak zlepšováním odhadů nutného počtu barev k obarvení čtvercové a šestiúhelníkové mřížky. Klíčová slova: kritické grafy, seznamové barvení, vlnové barvení, rovinné grafy, krátké cykly
|
|
|
Metody řešení problému přiřazování frekvencí
Ježek, Lukáš ; Lidický, Bernard (oponent) ; Nejedlý, Pavel (vedoucí práce)
Bezdrátová komunikace je používána ve stále více situacích, například v mobilní telefonii, televizním a rádiovém vysílání, komunikaci satelitů, bezdrátových sítích (WLAN) nebo vojenských operacích. V každé z těchto situací je nutné řešit problém přiřazení frekvencí, aby se spolu komunikující strany domluvily (někdo jim zprostředkoval službu) a při "rozhovoru" nebyly rušeny jinými komunikujícími subjekty. Vzhledem k tomu, že počet způsobů a hlavně účastníků bezdrátové komunikace velmi rychle roste, je tento problém stále více aktuální a důležitý a je nutné jej umět kvalitně řešit. V této práci se nachází zadání problému spolu s přehledem používaných technik pro jeho řešení. Vybrané postupy jsou popsány detailněji a je u nich představen konkrétní algoritmus řešící problém přiřazování frekvencí. Tyto algoritmy jsou taktéž implementovány v přiloženém programu, který slouží k řešení zadaných problémů a také k porovnávání jednotlivých použitých algoritmů. V programu je implementován sekvenční algoritmus, algoritmus simulovaného žíhání, algoritmus tabu vyhledávání a dva genetické algoritmy.
|
|
|
Fotbal
Beneš, Jan ; Babilon, Robert (oponent) ; Lidický, Bernard (vedoucí práce)
Cílem práce bylo navrhnout a implementovat simulátor fotbalového utkání a porovnat výslednout implementaci s ostatními programy se stejnou funkcí. Byl navržen model, podle kterého hráči a brankáři hrají fotbalové utkání. Program je možno provozovat v interaktivním módu, kdy jsou hráči jednoho z týmů ovládáni uživatelem, nebo je možné sledovat fotbalové utkání umělých inteligencí. Dále je součástí simulace reálná fyzika fotbalovho míče a odrazů od břevna a tyčí.
|
host ::
RSS.