Full metadata record
DC poleHodnotaJazyk
dc.contributor.advisorKaiser, Tomáš
dc.contributor.authorHanzlík, Michal
dc.contributor.refereeKrál, Daniel
dc.date.accepted2012-06-18
dc.date.accessioned2013-06-19T06:55:15Z
dc.date.available2011-10-01cs
dc.date.available2013-06-19T06:55:15Z
dc.date.issued2012
dc.date.submitted2012-05-23
dc.identifier48806
dc.identifier.urihttp://hdl.handle.net/11025/3682
dc.description.abstractDiplomová 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.cs
dc.format38 s.cs
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherZápadočeská univerzita v Plznics
dc.rightsPlný text práce je přístupný bez omezení.cs
dc.subjectteorie výpočetní složitostics
dc.subjectprostorová složitostcs
dc.subjectlogaritmický prostorcs
dc.subjectlog-spacecs
dc.subjectjednoznačný log-spacecs
dc.subjectmřížkové grafycs
dc.subjectmin-unique grafycs
dc.subjectproblém souvislosti orientovaného grafucs
dc.titleProstorová složitost grafových a matroidových problémůcs
dc.title.alternativeSpatial complexity of graph problemsen
dc.typediplomová prácecs
dc.thesis.degree-nameMgr.cs
dc.thesis.degree-levelNavazujícícs
dc.thesis.degree-grantorZápadočeská univerzita v Plzni. Fakulta aplikovaných vědcs
dc.description.departmentKatedra matematikycs
dc.thesis.degree-programMatematikacs
dc.description.resultObhájenocs
dc.rights.accessopenAccessen
dc.description.abstract-translatedDiploma 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.en
dc.subject.translatedcomputational complexity theoryen
dc.subject.translatedspace complexityen
dc.subject.translatedlogarithmic spaceen
dc.subject.translatedlog-spaceen
dc.subject.translatedunambiguous log-spaceen
dc.subject.translatedgrid graphsen
dc.subject.translatedmin-unique graphsen
dc.subject.translateddirected connectivity problemen
Vyskytuje se v kolekcích:Diplomové práce / Theses (KMA)

Soubory připojené k záznamu:
Soubor Popis VelikostFormát 
Hanzlik-DP-2012.pdfPlný text práce567,4 kBAdobe PDFZobrazit/otevřít
PV-Hanzlik.pdfPosudek vedoucího práce106,56 kBAdobe PDFZobrazit/otevřít
PO-Hanzlik.pdfPosudek oponenta práce184,14 kBAdobe PDFZobrazit/otevřít
P-Hanzlik.pdfPrůběh obhajoby práce37,75 kBAdobe PDFZobrazit/otevřít
Zobrazit minimální záznam Zobrazit statistiky


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/3682

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Vysokoškolské kvalifikační práce / Theses
  3. Fakulta aplikovaných věd / Faculty of Applied Sciences
  4. Katedra matematiky / Department of Mathematics
  5. Diplomové práce / Theses (KMA)