Název: Pseudonáhodné procházky a chip-firing games
Překlad názvu: Pseudorandom walks and chip firing games
Autoři: Mittal, Parth ; Koucký, Michal (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Typ dokumentu: Diplomové práce
Rok: 2021
Jazyk: eng
Abstrakt: [eng] [cze]
We study two deterministic analogues of random walks. The first is the chip-firing game, a single player game played by moving chips around a directed graph, popularised by Björner and Lovász. We find an efficient simulation of boolean circuits and Turing machines using instances of the chip-firing game - after assigning a fixed strategy to the player. The second is the Propp machine, or the rotor router model, a quasirandom model intro- duced by Priezzhev. We improve results of Kijima et al. and show a bound of O(m) on the discrepancy of this process from a random walk on d-regular graphs with m edges. 1 Studujeme dva deterministické procesy analogické náhodným procházkám na grafech. První je hra s vystřelováním žetonů, chip-firing game, zavedená Björnerem a Lovászem. Jedná se o hru jednoho hráče hranou pohybem žetonů po orientovaném grafu. Našli jsme efektivní simulaci booleovských obvodů a Turingových strojů pomocí této hry. Druhým procesem je Prop- pův stroj, neboli rotor-router model, pseudonáhodný proces zavedený Priez- zhevem. Zlepšujeme výsledky Kijima a spol. a ukazujeme novou horní mez O(m) na diskrepanci tohoto procesu na grafech stupně d s m hranami. 1
Klíčová slova: Propp machine|pseudorandom walks|chip firing games; Propp machine|pseudorandom walks|chip firing games

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/127441

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-448348


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce