| dc.contributor.advisor |
Hrabec, Dušan
|
|
| dc.contributor.author |
Šikudová, Lucie
|
|
| dc.date.accessioned |
2023-12-20T13:25:13Z |
|
| dc.date.available |
2023-12-20T13:25:13Z |
|
| dc.date.issued |
2022-12-02 |
|
| dc.identifier |
Elektronický archiv Knihovny UTB |
|
| dc.identifier.uri |
http://hdl.handle.net/10563/53932
|
|
| dc.description.abstract |
Mnoho situací kolem nás je možné si zjednodušit vhodným modelem. Vhodným prostředkem je právě graf, který dokáže modelovat vztahy mezi objekty. Oblasti, ve kterých se grafy používají, jsou různorodé - přes logistiku, počítačové sítě, dopravu, lingvistiku po biologii. Pro pochopení složitějších grafových algoritmů je nutné znát základní principy a přístupy, které se v praxi využívají. Představíme si základní algoritmy pro průchod grafem a řešení vybraných grafových problémů. Teorie grafů je také svázána s matematickou optimalizací. Práce seznamuje čtenáře s grafovými problémy také z pohledu optimalizace pomocí modelů celočíselného lineárního programování. Určité problémy se řadí do NP těžkých problémů a z toho důvodu je není možné efektivně v reálném čase vyřešit. Tento fakt ilustrujeme na ukázkách časové náročnosti naivních přístupů pro řešení takových problémů. Praktickou ukázkou jsou kódy v jazyce Python, které slouží jako názorná ukázka pro pochopení algoritmů. Práce také podrobně uvádí čtenáře do problematiky jednotlivých přístupů pomocí názorných obrázků a kroků jednotlivých algoritmů. |
|
| dc.format |
103 s. |
|
| dc.language.iso |
cs |
|
| dc.publisher |
Univerzita Tomáše Bati ve Zlíně |
|
| dc.rights |
Bez omezení |
|
| dc.subject |
teorie grafů
|
cs |
| dc.subject |
prohledávání grafu
|
cs |
| dc.subject |
BFS
|
cs |
| dc.subject |
DFS
|
cs |
| dc.subject |
hamiltonovská cesta
|
cs |
| dc.subject |
problém obchodního cestujícího
|
cs |
| dc.subject |
problém nejkratší cesty
|
cs |
| dc.subject |
Dijkstrův algoritmus
|
cs |
| dc.subject |
algoritmus Bellmana Forda
|
cs |
| dc.subject |
optimalizace
|
cs |
| dc.subject |
NP problémy
|
cs |
| dc.subject |
lineární programování
|
cs |
| dc.subject |
graph theory
|
en |
| dc.subject |
graph traversal
|
en |
| dc.subject |
BFS
|
en |
| dc.subject |
DFS
|
en |
| dc.subject |
Hamiltonian path
|
en |
| dc.subject |
travelling salesman problem
|
en |
| dc.subject |
shortest path problem
|
en |
| dc.subject |
Dijkstra's algorithm
|
en |
| dc.subject |
Bellman Ford algorithm
|
en |
| dc.subject |
optimization
|
en |
| dc.subject |
NP problems
|
en |
| dc.subject |
linear programming
|
en |
| dc.title |
Optimalizační a grafové problémy |
|
| dc.title.alternative |
Optimization and Graph Problems |
|
| dc.type |
bakalářská práce |
cs |
| dc.contributor.referee |
Cerman, Zbyněk |
|
| dc.date.accepted |
2023-06-12 |
|
| dc.description.abstract-translated |
Many situations that occur can be simplified by using an appropriate model. A suitable tool is a graph, which can model the relationships between objects. The fields in which graphs are used are diverse - from logistics, computer networks, transport, linguistics to biology. To understand more complex graph algorithms, it is necessary to know the basic principles and approaches that are used in practice. Basic algorithms for traversing the graph and solving selected graph problems will be introduced. Graph theory is also tied to mathematical optimization. The paper also makes the reader familiar with graph problems from the perspective of optimization using integer linear programming models. Certain problems are classified as NP-hard problems and, for this reason, cannot be solved efficiently in a real-time manner. As an illustration of this fact, examples of time-consuming naive approaches to solving such problems are presented. As a practical example, we use Python codes to illustrate the algorithms. The paper also guides the reader through the details of each approach with illustrative figures and steps of each algorithm. |
|
| dc.description.department |
Ústav informatiky a umělé inteligence |
|
| dc.thesis.degree-discipline |
Softwarové inženýrství |
cs |
| dc.thesis.degree-discipline |
Software Engineering |
en |
| dc.thesis.degree-grantor |
Univerzita Tomáše Bati ve Zlíně. Fakulta aplikované informatiky |
cs |
| dc.thesis.degree-grantor |
Tomas Bata University in Zlín. Faculty of Applied Informatics |
en |
| dc.thesis.degree-name |
Bc. |
|
| dc.thesis.degree-program |
Softwarové inženýrství |
cs |
| dc.thesis.degree-program |
Software Engineering |
en |
| dc.identifier.stag |
63529
|
|
| dc.date.submitted |
2023-05-24 |
|
