Využití dynamického programování v grafových algoritmech

Název anglicky

Dynamic Programming in Graph Algorithms

Jazyk práce

český

Abstrakt

Tato práce se zabývá grafovými algoritmy, jejich využitím a přínosem optimalizační metody dynamického programování. Tento přínos je předveden uživateli pomocí aplikace. Grafové algoritmy najdou využití v mnoha odvětvích lidské činnosti i dnes. Používají se ve směrování paketů nebo například v navigaci.V práci jsou zpracovány tři metody, které patří mezi grafové algoritmy. Tyto problémy řeším klasickým i dynamickým způsobem a následně zjištěná data jsou porovnána.

Klíčová slova

Dynamické programování, C++, gtkmm, optimalizace, graf, nejkratší cesta, obchodní cestující, skrytý markovův model, Viterbiho algoritmus

Ústav

Ústav informačních systémů FIT VUT v Brně

Studijní program

Informační technologie

Soubory

Stav

obhájeno, hodnocení D

Obhajoba

10. června 2019

Oponent

Křivka Zbyněk, Ing., Ph.D.

Průběh obhajoby

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm D.

Otázky u obhajoby

V textu zmiňujete, že by bylo lepší porovnat časovou složitost dle průměrného stupně grafu, což ale není funkce. Pro graf se 100 hranami a 10 vrcholy nebude přece časová složitost odpovídat grafu s 1000 hranami a 100 vrcholy, kde je stejný průměrný stupeň. Jak by takové porovnání vypadalo?
Vůči kterým algoritmům by bylo zajímavější experimentálně porovnávat časové složitosti dynamických variant?

Komise

Kolář Dušan, doc. Dr. Ing. (UIFS FIT VUT), předseda
Burgetová Ivana, Ing., Ph.D. (UIFS FIT VUT), člen
Černocký Jan, prof. Dr. Ing. (UPGM FIT VUT), člen
Peringer Petr, Dr. Ing. (UITS FIT VUT), člen
Vašíček Zdeněk, doc. Ing., Ph.D. (UPSY FIT VUT), člen

Citace

BILOŠ, Martin. Využití dynamického programování v grafových algoritmech. Brno, 2019. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2019-06-10. Vedoucí práce Burgetová Ivana. Dostupné z: https://www.fit.vut.cz/study/thesis/22053/

BibTeX

@bachelorsthesis{FITBT22053,
    author = "Martin Bilo\v{s}",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Vyu\v{z}it\'{i} dynamick\'{e}ho programov\'{a}n\'{i} v grafov\'{y}ch algoritmech",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2019,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/22053/"
}