|
Výpočet triangulace s minimální váhou (MWT)
Charvát, Pavel ; Kolingerová, Ivana (vedoucí práce) ; Ferko, Andrej (oponent)
Pro výpočet MWT už dlouhou dobu není znám žádný polynomiální algoritmus a ani se neví, zda je NP. Tento stav zůstává podle našich zdrojů stále neznámý. V práci uvádíme přehled možných přístupů k problému, jako jsou modifikace zadání se známou složitostí nebo hledání nejrůznějších heuristik a aproximací, umožňujících v rozumném čase najít přesné nebo alespoň přibližné řešení, a porovnáváme jejich kvalitu v konkrétních situacích. Hlavní částí je popis a implementace efektivní heuristiky s (téměř?) lineární očekávanou složitostí pro rovnoměrně rozložené body v konvexní oblasti. Algoritmus modifikuje Drysdalův algoritmus hledání kandidátních hran GT a Beuroutiho výpočet modifikovaného LMT-skeletonu, u kterého navíc doplňujeme důkazy správnosti. MWT dokončíme z grafu kandidátních hran v O(n · d3 + n · d2+k), kde d je maximální stupeň vrcholu a k je největší počet vnitřních komponent nějaké stěny skeletonu. Dále navrhujeme novou aproximaci s polynomiální složitostí a (téměř?) lineární očekávanou složitostí, která se jen zřídka liší od optimální triangulace, a lze dokázat její nejhorší možný aproximační faktor O(1). Aproximace kombinuje heuristiku modifikovaného LMT-skeletonu s omezenou quasi-greedy triangulací a s triangulací minimální kostry. Minimální triangulace nakonec aplikujeme v praktickém problému výpočtu...
|
|
Dvourozměrné řezné problémy
Rada, Miroslav ; Fábry, Jan (vedoucí práce) ; Jablonský, Josef (oponent)
Práce se v úvodu zabývá typologií řezných problémů a jejich vztahem k problémům balícím. Tyto problémy jsou roztříděny podle Wascher a kol. (2005) pomocí pěti základních kritérií do tzv. "upřesněných typů problémů", které představují dostatečně podrobné a prakticky použitelné členění řezných úloh. Z široké palety algoritmů pro řešení řezných úloh se práce zabývá vybranými zajímavými reprezentanty. Stručně je popsán algoritmus Viswanathan-Bagchi (1991) pro exaktní řešení omezených dvojrozměrných ortogonálních úloh dělení materiálu gilotinovými řezy, jenž umožňuje zpracovat širokou škálu různých typů dodatečných omezení úlohy. Hlavní část práce se zabývá heuristickými algoritmy pro řešení ortogonálních úloh neomezeného rozměru. Podrobně je popsán algoritmus Best-fit podle Burke a kol (2004). V práci jsou zavedeny dvě modifikace tohoto algoritmu, které ve 42 z 89 testovacích úloh umožnily vylepšit řešení oproti původní verzi algoritmu, přičemž pouze v 10 případech bylo dosažené řešení horší. Při implementaci algoritmu jsou též zavedeny nové, efektivnější datové struktury a postupy, které umožnily vyřešit testovací úlohu s cca 50 000 obdélníky zhruba za 2,5 vteřiny.
|
|
Posouzení stylů vedení lidí a jejich dopadů na pracovní skupinu
Kinc, Petr
Bakalářská práce se zabývá problematikou vlivu manažerského stylu na vedené pracovníky a jeho dopadu na jejich celkovou spokojenost. Pomocí dat získaných dotazníkovým šetřením byl zjištěn styl vedení manažera a jeho vliv na zaměstnance. Na základě odpovědí zaměstnanců a jejich vedoucího byla zjištěna slabá a silná místa ve stylu vedení manažera. Následně byly doporučeny návrhy na úpravu stylu vedení manažera, které povedou k větší spokojenosti pracovního týmu.
|
|
Algoritmy pro procházení 2D bludiště
Chvíla, Lukáš ; Jelínek, Aleš (oponent) ; Žalud, Luděk (vedoucí práce)
Tato práce popisuje způsob automatického nalezení cesty ve 2D bludišti, které je zadáno formou bitmapových mřížek obsazenosti. Problém byl řešen v jazyce C# za pomoci algoritmu přímkové dekompozice, pomoci kterého je vytvořena síť potencionálních cest. Tento algoritmus předpokládá aproximaci překážek vektorovými polygony. Pro nalezení výsledné cesty je použit algoritmus A*. Výstupem je cesta popsaná úsečkami, kterou by po dalších úpravách bylo možné použít pro navigaci robota.
|
|
Dolování dat z webu
Ljubopytnov, Vladimír ; Húsek, Dušan (oponent) ; Pokorný, Jaroslav (vedoucí práce)
Tato práce se soustředí na zmapování současných poznatků v oblasti dolování dat z webu s důrazem na shlukování dokumentů. Nejpodrobněji je zkoumán algoritmus projektivního shlukování DOC, je uvedena jeho modifikace pro data s váženými dimenzemi. Algoritmus je aplikován při shlukování výsledků webového vyhledávače. Součástí práce je implementace Javovského shlukovacího balíčku s rozhraním pro vyhledávač Google a s nástrojem pro hodnocení kvality frází.
|
|
Analýza dopravního problému s omezenými proměnnými
Klasová, Petra ; Kalčevová, Jana (vedoucí práce) ; Šmídová, Milada (oponent)
Cílem této bakalářské práce je seznámit čtenáře s problematikou řešení dopravního problému s omezenými proměnnými, jednotlivými metodami výpočtu řešení a jejich praktickou aplikací na fiktivní příklady. Podstatou dopravního problému s omezenými proměnnými je optimální rozvržení dopravy množství nějaké komodity z dodavatelských míst odběratelům tak, aby byly splněny podmínky pro minimální a maximální dopravované množství. V typickém případě jde o snahu minimalizovat celkové náklady spojené s tímto rozvozem. V práci je představena modifikace metody severozápadního rohu, indexní metody a Vogelovy aproximační metody pro úlohy s omezenými proměnnými, stejně jako distribuční a modifikovaná distribuční metoda.
|
|
Umělé neuronové sítě a jejich použití v oblasti pojistných rizik
Macek, Karel ; Jiroutek, Pavel (oponent) ; Mrázová, Iveta (vedoucí práce)
Předložená práce zkoumá použitelnost neuronových sítí v oblasti pojistných rizik. Popisuje strukturu a funkci vícevrstvých perceptronových sítí, Kohonenových map a sítí typu Fuzzy ART a Fuzzy ARTMAP. Definuje pojem pojistného rizika a uvádí do problematiky tarifování pomocí zobecněných lineárních modelů. Shrnuje metody neuronových sítí pro redukci dimenze vstupního prostoru, extrakci znalostí a vizualizaci. Seznamuje s daty popisujícími dopravní nehody a prezentuje výsledky několika analýz, které na nich byly provedeny. Práci se podařilo teoreticky i experimentálně prokázat, že vícevrstvé perceptronové sítě mají větší výpočetní sílu, než zobecněné lineární modely. Modifikace vícevrstvé perceptronové sítě úspěšně odhadla distribuční funkci celkové výše škody. Pomocí analýzy provedené Kohonenovou mapou a následné vizualizace byly odhaleny v datech dva výrazné shluky. Analýza pomocí sítě typu Fuzzy ART byla prezentována jako součást nového algoritmu pro redukci vysoké dimenze vstupního prostoru. Nový algoritmus vycházející ze sítě typu ARTMAP odhalil skupinu nehod, kde je škoda nadprůměrná. Tato skupina je vymezená interpretovatelnými pravidly. Přílohu práce tvoří CD se skripty pro Matlab a MySQL, které byly pro analýzy použity.
|
|
Profesní zátěž členů výjezdových skupin zdravotnické záchranné služby
VELDA, Jakub
Tématem této bakalářské práce je problematika, týkající se profesní zátěže, se kterou se pracovníci zdravotnické záchranné služby na výjezdech setkávají. Záměrem této práce bylo zjistit, jaké faktory vnímají jako nejvíce zátěžové, jejich zkušenosti s kritickými situacemi a jakou formou se snaží se situacemi vyrovnat. Taktéž bylo cílem zjistit názor a popsat zkušenosti záchranářů s psychologickou pomocí a jejími modifikacemi. Realizace výzkumu proběhla kvalitativní formou prostřednictvím polostrukturovaných rozhovorů se členy výjezdových skupiny zdravotnických záchranných služeb Středočeského a Jihočeského kraje, pracujícími na pozici zdravotnický záchranář. Výzkumem bylo zjištěno, že se respondenti rozhovorů v souvislosti se svou profesí opravdu setkali s kritickými událostmi, kterými se cítili psychicky po určitou dobu výrazně ovlivněni. Respondenti také vnímají, že základy položené psychologické intervenci pro zaměstnance zdravotnických záchranných služeb v určitých krajích jsou dobrým předpokladem, aby i tato základní složka integrovaného záchranného systému měla pro své pracovníky zajištěno zázemí po psychické stránce a dopomohla svým zaměstnancům jak prevencí, tak i intervencí k duševní rovnováze, kterou vnímají jako jeden ze základních předpokladů správného plnění úkolů a povinností, které jsou obecně na pracovníky Zdravotnické záchranné služby kladeny. Možnou alternativou ke zlepšení této problematiky by mohlo být zakomponování legislativní povinnosti zaměstnavatele pečovat o psychickou stránku zaměstnance plnícího rizikové povolání.
|
|
Rozvrhovací úlohy typu Flow-shop
Dyntar, Tomáš ; Tegze, Miron (vedoucí práce) ; Červinka, Michal (oponent)
Je podán popis rozvrhování flow shop a lot streaming včetně příkladu. Dále jsou ukázány metody a algoritmy pro řešení různých verzí problému určení velikostí skupin pro přepravu mezi stroji v prostředí flow shop se dvěma stroji. Začne se s výpočtem úlohy se dvěma skupinami (diskrétní případ), třemi skupinami (spojitý případ) a pak je představen Trietschův polynomiální algoritmus pro libovolný počet skupin pro danou celkovou dobu trvání procesu, kdy se uvažuje konstantní či lineární doba na přepravu včetně variant s omezeným počtem přepravních zařízení či jejich omezenou kapacitou, kdy se uvažuje konstantní či lineární doba nastavení strojů. Dále je vytvořen model s přepravou i dobou nastavení a Trietschův algoritmus je příslušným způsobem upraven. Pro rozšíření výsledků případů s jedním strojem na případy s více stroji je navrženo užít větu R. G. Vicksona, která řeší problém s určením skupn v případě více jobů pomocí pojednání problému s určením velikosti skupin pro každý job samostatně a poté užitím Johnsonova algoritmu. Také je ukázán známý způsob k rozšíření výsledků na úlohu se třemi stroji prostřednictvím řešení vždy dvou sousedních strojů zvlášť nebo upravením Trietschova algoritmu pro tři stroje. Většina postupů je předvedena na příkladech.
|
|
Optimalizace tras při rozvozu zásilek
Ptáčková, Michaela ; Borovička, Adam (vedoucí práce) ; Čížek, Ondřej (oponent)
Tato diplomová práce se zabývá problematikou optimalizace tras při rozvozu zásilek. Tuto problematiku je možno řešit na základě úlohy obchodního cestujícího, jejíž matematický a ekonomický model, včetně jejich modifikací, je představen v teoretické části práce. Tyto úlohy lze řešit pomocí exaktních metod, heuristických a metaheuristických algoritmů. V teoretické části je popsána úloha obchodního cestujícího, úloha obchodního cestujícího s časovými okny, úloha obchodního cestujícího s více časovými okny a dynamická úloha obchodního cestujícího včetně možností jejich řešení. V praktické části nalezneme aplikaci úloh na reálný příklad z praxe, kdy hledáme nejkratší možné trasy pro řidiče společnosti PPL CZ s. r. o. za různých předpokladů. Řešení je získáváno pomocí řešitele Gurobi v rámci modelovacího systému MPL for Windows. V závěru práce jsou výsledky shrnuty a vzájemně porovnány jednotlivé modely.
|