| Title: | Prostorová složitost grafových a matroidových problémů |
| Other Titles: | Spatial complexity of graph problems |
| Authors: | Hanzlík, Michal |
| Advisor: | Kaiser, Tomáš |
| Referee: | Král, Daniel |
| Issue Date: | 2012 |
| Publisher: | Západočeská univerzita v Plzni |
| Document type: | diplomová práce |
| URI: | http://hdl.handle.net/11025/3682 |
| Keywords: | 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 |
| Keywords in different language: | computational complexity theory;space complexity;logarithmic space;log-space;unambiguous log-space;grid graphs;min-unique graphs;directed connectivity problem |
| Abstract: | 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. |
| Abstract in different language: | 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. |
| Rights: | Plný text práce je přístupný bez omezení. |
| Appears in Collections: | Diplomové práce / Theses (KMA) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Hanzlik-DP-2012.pdf | Plný text práce | 567,4 kB | Adobe PDF | View/Open |
| PV-Hanzlik.pdf | Posudek vedoucího práce | 106,56 kB | Adobe PDF | View/Open |
| PO-Hanzlik.pdf | Posudek oponenta práce | 184,14 kB | Adobe PDF | View/Open |
| P-Hanzlik.pdf | Průběh obhajoby práce | 37,75 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/3682Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.