Tato diplomová práce porovnává algoritmy pro hledání optimální cesty na dopravní a počítačové síti. Algoritmy jsou podrobně vysvětleny a jsou uvedeny jejich různé modifikace, vhodné pro specifické druhy problémů. Dále jsou součástí teoretické části práce základní pojmy z oblasti teorie grafů, operačního výzkumu a počítačových sítí. V praktické části jsou implementovány všechny základní algoritmy a porovnány jejich asymptotické a reálné časové složitosti. Práce může sloužit jako ucelený přehled v problematice hledání nejkratší cesty, která se na Dopravní fakultě Jana Pernera vyskytuje poměrně často.
Anotace v angličtině
This graduation theses compares the algorithms for searching optimal path inside of transport and computer network. The algorithms are explained in detail and listed their various modifications, suitable for specific kinds of problems. The theoretical part also includes the basic concepts of graph theory, operations research and computer networks. The practical part are implemented all the basic algorithms and compared their asymptotic complexity and real time. This thesis can serve as a comprehensive overview of the issue of searching the shortest path, which is quite often occurring at the Transport Faculty Jan Perner.
Klíčová slova
Teorie grafů, graf, dopravní síť, počítačová síť, hledaní optimální cesty, hledání nejkratší cesty, Dijkstrův algoritmus, Floyd-Warshallův algoritmus, Bellman-Fordův algoritmus
Klíčová slova v angličtině
Graph theory, graph, transport network, computer network, searching optimal path, searching the shortest path, Dijkstra's algorithm, Floyd-Warshall algorithm, Bellman-Ford algorithm
Rozsah průvodní práce
60 s.
Jazyk
CZ
Anotace
Tato diplomová práce porovnává algoritmy pro hledání optimální cesty na dopravní a počítačové síti. Algoritmy jsou podrobně vysvětleny a jsou uvedeny jejich různé modifikace, vhodné pro specifické druhy problémů. Dále jsou součástí teoretické části práce základní pojmy z oblasti teorie grafů, operačního výzkumu a počítačových sítí. V praktické části jsou implementovány všechny základní algoritmy a porovnány jejich asymptotické a reálné časové složitosti. Práce může sloužit jako ucelený přehled v problematice hledání nejkratší cesty, která se na Dopravní fakultě Jana Pernera vyskytuje poměrně často.
Anotace v angličtině
This graduation theses compares the algorithms for searching optimal path inside of transport and computer network. The algorithms are explained in detail and listed their various modifications, suitable for specific kinds of problems. The theoretical part also includes the basic concepts of graph theory, operations research and computer networks. The practical part are implemented all the basic algorithms and compared their asymptotic complexity and real time. This thesis can serve as a comprehensive overview of the issue of searching the shortest path, which is quite often occurring at the Transport Faculty Jan Perner.
Klíčová slova
Teorie grafů, graf, dopravní síť, počítačová síť, hledaní optimální cesty, hledání nejkratší cesty, Dijkstrův algoritmus, Floyd-Warshallův algoritmus, Bellman-Fordův algoritmus
Klíčová slova v angličtině
Graph theory, graph, transport network, computer network, searching optimal path, searching the shortest path, Dijkstra's algorithm, Floyd-Warshall algorithm, Bellman-Ford algorithm
Zásady pro vypracování
Cílem DP bude porovnání implementace algoritmu hledání optimální cesty na dopravní síti a počítačové síti. Práce bude obsahovat teoretický popis fungování algoritmu hledání optimální cesty včetně symbolického popisu a definování pojmů. V praktické části bude výstupem program demonstrující hledání optimální cesty a rozbor rozdílů mezi reálnou dopravní sítí a směrovanou počítačovou sítí.
Zásady pro vypracování
Cílem DP bude porovnání implementace algoritmu hledání optimální cesty na dopravní síti a počítačové síti. Práce bude obsahovat teoretický popis fungování algoritmu hledání optimální cesty včetně symbolického popisu a definování pojmů. V praktické části bude výstupem program demonstrující hledání optimální cesty a rozbor rozdílů mezi reálnou dopravní sítí a směrovanou počítačovou sítí.
Seznam doporučené literatury
SPORTACK, Mark. Směrování v IP sítích. první. Brno : Computer Press, 2004. 351 s. ISBN 80-251-0127-4.
VOLEK, J. Operační výzkum I. Pardubice, 2002. ISBN 80-7194-410-6.
DEMEL, J. Grafy a jejich aplikace. Academia, 2002.
NEČAS, J. Grafy a jejich použití. Polytechnická knižnice, SNTL, 1978.
SEDLÁČEK, J. Kombinatorika v teorii a praxi. Nakladatelství ČSAV, 1964.
Seznam doporučené literatury
SPORTACK, Mark. Směrování v IP sítích. první. Brno : Computer Press, 2004. 351 s. ISBN 80-251-0127-4.
VOLEK, J. Operační výzkum I. Pardubice, 2002. ISBN 80-7194-410-6.
DEMEL, J. Grafy a jejich aplikace. Academia, 2002.
NEČAS, J. Grafy a jejich použití. Polytechnická knižnice, SNTL, 1978.
SEDLÁČEK, J. Kombinatorika v teorii a praxi. Nakladatelství ČSAV, 1964.
Přílohy volně vložené
1 CD
Přílohy vázané v práci
-
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Student reagoval na připomínky uvedené v posudcích vedoucího a oponenta diplomové práce, zodpověděl dotazy členů komise.