Hladový algoritmus v NP úplných problémech

Pokorný, Ondřej

Publikace:
Hladový algoritmus v NP úplných problémech

Diplomová práceopen access

dc.contributor.advisor	Rak, Josef
dc.contributor.author	Pokorný, Ondřej
dc.contributor.referee	Merta, Jan
dc.date.accepted	2025-06-11
dc.date.accessioned	2025-07-07T07:31:34Z
dc.date.issued	2025
dc.date.submitted	2025-05-23
dc.description.abstract	V optimalizačních problémech je hodně úloh, které jsou NP-úplné. To znamená, že nelze nalézt algoritmus jiné než exponenciální složitosti, který problém řeší. Příkladem může být například úloha plnění batohu, problém barvení grafu, či problém obchodního cestujícího. Hladový algoritmus je heuristika, která spočívá v lokálně optimální volbě v každé fázi. V mnoho situacích tato strategie nepřináší optimální řešení. Může ale přinést řešení, které se v rozumném čase blíží optimálnímu. Cílem práce je aplikování hladového algoritmu na různé NP úplné problémy, jeho modifikace a studium jeho chování.	cze
dc.description.abstract-translated	There are many optimization problems that are NP-complete. That is, one cannot find an algo-rithm of non-exponential complexity that solves the problem. Examples include the backpack filling problem, the graph coloring problem, or the travelling salesman problem. Greedy algo-rithm is a heuristic that consists of a locally optimal choice at each stage. In many situations this strategy does not provide an optimal solution. However, it may provide a solution that is close to optimal in reasonable time. The aim of this paper is to apply the greedy algorithm to various NP-complete problems, modify it and study its behavior.	eng
dc.description.defence	Prezentovaná diplomová práce se zabývá problémem využití hladového algoritmu v NP-úplných úlohách. V práci autor uplatňuje poznatky z matematiky jakou jsou teorie grafů, celočíselné programování, optimalizace, teorie složitosti algoritmů, heuristické algoritmy, Po přednesení posudku vedoucího a oponenta práce, student zodpověděl dotazy a reagoval na připomínky členů komise pro státní závěrečné zkoušky.	cze
dc.description.department	Fakulta elektrotechniky a informatiky	cze
dc.description.grade	Dokončená práce s úspěšnou obhajobou	cze
dc.format	88 s.
dc.identifier.stag	49764
dc.identifier.uri	https://hdl.handle.net/10195/84978
dc.language.iso	cze
dc.publisher	Univerzita Pardubice	cze
dc.rights	Bez omezení
dc.subject	graf	cze
dc.subject	časová složitost	cze
dc.subject	NP-úplný problém	cze
dc.subject	hladový algoritmus	cze
dc.subject	barvení grafu	cze
dc.subject	chromatické číslo	cze
dc.subject	problém batohu	cze
dc.subject	problém obchodního cestujícího	cze
dc.subject	graph	eng
dc.subject	time complexity	eng
dc.subject	NP-complete problem	eng
dc.subject	greedy algorithm	eng
dc.subject	graph coloring	eng
dc.subject	chromatic number	eng
dc.subject	knapsack problem	eng
dc.subject	travelling salesman problem	eng
dc.thesis.degree-discipline	Informační technologie	cze
dc.thesis.degree-grantor	Univerzita Pardubice. Fakulta elektrotechniky a informatiky	cze
dc.thesis.degree-name	Ing.
dc.thesis.degree-program	Informační technologie	cze
dc.title	Hladový algoritmus v NP úplných problémech	cze
dc.title.alternative	Greedy algorithm in NP complete problems	eng
dc.type	diplomová práce	cze
dspace.entity.type	Publication