Bakalářská práce

Detekce dynamických cyklů

Incremental Cycle Detection

Bc. Dominik Rumian
Anotace

Bakalářská práce představuje efektivní algoritmy pro detekci dynamických cyklů formou studijního materiálu. První částí práce je studijní text, ve kterém jsou algoritmy popsány slovně, pomocí pseudokódů a ilustrativních příkladů doplněných obrázky. Druhou částí práce je vzorová implementace představených algoritmů v programovacím jazyce Python. Poslední částí je pak vizualizační nástroj, který má formu …více

Abstract

This bachelor thesis introduces effective algorithms for dynamic cycle detection in a form of study material. The first part of the thesis is a study text consisting of text description, pseudocode and illustrative examples with pictures. The second part is implementation of the algorithms using Python programming language. The last part of the bachelor thesis is a visualization tool which allows to visualize individual steps of the algorithm during the computation.

Klíčová slova
orientovaný graf detekce cyklů algoritmy vizualizace studijní materiál Python JavaScript
Zadání práce
Problém detekce dynamických cyklů je formulován pro graf, do kterého postupně přidáváme orientované hrany. Cílem je určit první hranu, po jejímž přidání vznikne v grafu (orientovaný) cyklus. Problém je triviálně řešitelný např. pomocí opakovaného průzkumu grafu do hloubky. Cílem bakalářské práce je představit algoritmus pro detekci cyklů v rostoucích grafech založený na topologickém uspořádání vrcholů, publikovaný v článku "A New Approach to Incremental Cycle Detection and Related Problems" přehledným a srozumitelným způsobem. Výsledkem práce má být studijní materiál vhodný pro studenty. Bakalářská práce má tři části: (1) textovou část, která představí algoritmus formou textu, pseudokódů, ilustrativních příkladů a obrázků, (2) implementace algoritmu, a (3) vizualizace operací nad grafem s funkcionalitou srovnatelnou s nástrojem https://visualgo.net
Administrativní informace
Práce zkontrolována:
26. 5. 2021 08:08, prof. RNDr. Ivana Černá, CSc., učo 1419
Plný text práce
1,2 MB / soubor PDF
Přílohy (3)
Jazyk práce
čeština čeština
Termín obhajoby
30. 6. 2021
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Oponent

RNDr. Jaromír Plhák, Ph.D., učo 60773
KSUZD FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.