Bakalářská práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Complexity of Consumption Games

David Klaška, učo 374303
Anotace

Práce se zabývá tzv. consumption games, hrami dvou hráčů, které modelují interaktivní systémy s několika typy zdrojů, jež jsou průběžně spotřebovávány a doplňovány nezávisle na sobě. Konkrétně řešíme problémy prázdnosti, příslušnosti a minimálních vektorů. U každého z těchto tří problémů klasifikujeme podtřídy consumption games, pro něž jsou řešitelné v polynomiálním čase. Dále ukazujeme, že vně těchto tříd jsou řešené problémy výpočetně těžké.

Abstract

We study consumption games, a model for interactive systems with several resource types which are consumed and reloaded independently. Several naturally arising problems about consumption games have been studied, namely the emptiness problem, the membership problem, and the minimal-resource problem. For each of these problems, we classify subclasses of consumption games for which it is solvable in …více

Klíčová slova
consumption games binary encoding polynomially solvable emptiness problem membership problem minimal-resource problem one-player games one-dimensional consumption games decreasing consumption games single-reloading consumption games
Zadání práce
The goal is to investigate computational complexity of solving so called consumption games, a special form of two-player, turn-based games with counters. First, the thesis should briefly survey existing results. Second, the thesis should identify subclasses of consumption games that can be efficiently solved.
Administrativní informace
Práce zkontrolována:
20. 1. 2014 09:25, doc. RNDr. Tomáš Brázdil, Ph.D., MBA, učo 4074
Plný text práce
285,5 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
7. 2. 2014
Práce byla úspěšně obhájena

Vedoucí

doc. RNDr. Tomáš Brázdil, Ph.D., MBA, učo 4074
ITI FI MU

Oponent

prof. RNDr. Mojmír Křetínský, CSc., učo 631
KTP FI MU

Literatura

  • BRÁZDIL, Tomáš; Krishnendu CHATTERJEE; Antonín KUČERA a Petr NOVOTNÝ. Efficient Controller Synthesis for Consumption Games with Multiple Resource Types. In Computer Aided Verification - 24th International Conference, CAV 2012. Berlin: Springer, 2012, s. 23-38. ISBN 978-3-642-31423-0. Dostupné z: https://doi.org/10.1007/978-3-642-31424-7_8.
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.

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