Diplomová práce

Prohledávání grafů pomocí náhodné procházky

Graph traversal by random walk

Bc. Pavel Stupka
Anotace

Práce se zabývá porovnáním efektivity náhodné procházky na různých typech grafů, kterými jsou např. stromy, bezškálové sítě a náhodné grafy. Dále práce zavádní modifikace algoritmu náhodné procházky, pomocí kterých se snaží posílit efektivitu při prohledávání. Součástí je i úvod do teorie grafů a sítí a teoretický popis náhodné procházky.

Abstract

This thesis deals with the problem of the random walk algorithm on different kinds of graphs. These are for example trees, scale-free networks or random graphs. Thesis also introduces new modifications of the random walk algorithm to enhance the cover time. Second part of the work is an introduction to a graph theory and a theoretical description of the random walk.

Klíčová slova
orientovaný graf neorientovaný graf síť bezškálová síť náhodný graf prohledávání grafu náhodná procházka
Zadání práce
Cílem práce je porovnat chování a efektivitu náhodné procházky na různých typech grafů (např. stromy, bezškálové sítě a náhodné grafy). Náhodná procházka je metoda, při níž graf procházíme tak, že putujeme náhodně z jednoho vrcholu do druhého. Konkrétní cíle práce jsou:
  • Shromáždit grafy z různých aplikačních oblastí a různých typů a převést je do jednotného vstupního formátu.
  • Naimplementovat náhodnou procházku a metody pro monitorování jejího chování.
  • Provést experimentální porovnání a vyhodnocení.
Součástí práce dále bude navržení modifikace náhodné procházky, která by měla posílit její efektivitu na různých typech testovaných grafů. Práce bude také obsahovat stručný úvod do teorie grafů a popis náhodné procházky.
Administrativní informace
Práce zkontrolována:
11. 10. 2008 13:02, (IS automaticky)
Plný text práce
10,8 MB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
3. 7. 2008
Práce byla úspěšně obhájena

Vedoucí

doc. Mgr. Radek Pelánek, Ph.D., učo 4297
KSUZD FI MU

Oponent

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

Literatura

  • PELÁNEK, Radek; Tomáš HANŽL; Ivana ČERNÁ a Luboš BRIM. Enhancing Random Walk State Space Exploration. In Formal Methods for Industrial Critical Systems. Lisbon: ACM SIGSOFT, 2005, s. 98-105. ISBN 1-59593-148-1.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

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

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

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Pavel Stupka FI N-AP AP y3x63/9
Stupka, P.
15. 5. 2008
Složky
Soubory
Anotace anglicky annotation_english.txt
Stupka, P.
15. 5. 2008
Anotace česky annotation.txt
Stupka, P.
15. 5. 2008
Klíčová slova keywords.txt
Stupka, P.
15. 5. 2008
Posudek oponenta posudek_oponenta.pdf
Černá, I.
9. 6. 2008
programy.tar.gz
Stupka, P.
15. 5. 2008
thesis-print.pdf
Stupka, P.
22. 5. 2008
vysledky.tar.gz
Stupka, P.
15. 5. 2008
zdroj.tar.gz
Stupka, P.
15. 5. 2008

  • 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.