| Název: | Prostorová složitost grafových a matroidových problémů |
| Další názvy: | Spatial complexity of graph problems |
| Autoři: | Hanzlík, Michal |
| Vedoucí práce/školitel: | Kaiser, Tomáš |
| Oponent: | Král, Daniel |
| Datum vydání: | 2012 |
| Nakladatel: | Západočeská univerzita v Plzni |
| Typ dokumentu: | diplomová práce |
| URI: | http://hdl.handle.net/11025/3682 |
| Klíčová slova: | teorie výpočetní složitosti;prostorová složitost;logaritmický prostor;log-space;jednoznačný log-space;mřížkové grafy;min-unique grafy;problém souvislosti orientovaného grafu |
| Klíčová slova v dalším jazyce: | computational complexity theory;space complexity;logarithmic space;log-space;unambiguous log-space;grid graphs;min-unique graphs;directed connectivity problem |
| Abstrakt: | Diplomová práce je rozdělena do tří částí. V první části připomeneme několik základních faktů z teorie výpočetní složitosti, zavedeme standardní výpočetní model zvaný Turingův stroj a pomocí něho definujeme několik složitostních tříd. V další části se budeme podrobněji zabývat problémy s logaritmickou prostorovou složitostí a obzvlášt třídami NL a UL. Panuje obecné přesvědčení o tom, že se tyto třídy sobě rovnají, ale problém zůstává otevřeným. Na konci této části připomeneme některé techniky, které se využívají při práci s třídami problémů řešitelných v logaritmickém prostoru. V poslední části dokážeme hlavní výsledek této práce: tvrzení, že problém souvislosti orientovaného grafu na podmnožině třídy mřížkových grafů patří do UL. |
| Abstrakt v dalším jazyce: | Diploma thesis is divided into three parts. In the first part we review some basic facts of the computational complexity theory, present a standard model of computation called Turing machine and use it to define some complexity classes. In the next part we take a closer look at the logarithmic space complexity classes and especially the classes NL and UL. It is believed that these classes are equal but the problem remains open. At the end of this part we recall some techniques for working with classes using logarithmic space. In the last part we prove the main result of this thesis: the directed connectivity problem on a restricted subclass of grid graphs belongs to UL. |
| Práva: | Plný text práce je přístupný bez omezení. |
| Vyskytuje se v kolekcích: | Diplomové práce / Theses (KMA) |
Soubory připojené k záznamu:
| Soubor | Popis | Velikost | Formát | |
|---|---|---|---|---|
| Hanzlik-DP-2012.pdf | Plný text práce | 567,4 kB | Adobe PDF | Zobrazit/otevřít |
| PV-Hanzlik.pdf | Posudek vedoucího práce | 106,56 kB | Adobe PDF | Zobrazit/otevřít |
| PO-Hanzlik.pdf | Posudek oponenta práce | 184,14 kB | Adobe PDF | Zobrazit/otevřít |
| P-Hanzlik.pdf | Průběh obhajoby práce | 37,75 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/3682Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.