velikost textu

Zobecněný Moranův proces

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Zobecněný Moranův proces
Typ:
Diplomová práce
Autor:
Bc. Jakub Svoboda
Vedoucí:
Mgr. Robert Šámal, Ph.D.
Oponent:
Mgr. Martin Balko
Id práce:
213526
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Informatický ústav Univerzity Karlovy (32-IUUK)
Program studia:
Informatika (N1801)
Obor studia:
Teoretická informatika (ITI)
Přidělovaný titul:
Mgr.
Datum obhajoby:
10. 6. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
stochastické procesy, Moranův proces, evoluční dynamika, graf
Klíčová slova v angličtině:
stochastic process, Moran process, evolutionary dynamics, graph
Abstrakt:
Moránův proces je model používaný k simulaci evolučních dynamik. Ve struk- turované populaci se objeví lépe přizpůsobený jedinec, mutant. Evoluce je simu- lována v krocích. V jednom kroku, jedinec je vybrán proporcionálně ke své fitness a rozšíří se na místo svého souseda. V této práci, vysvětlujeme Moránův proces, prezentujeme základní výsledky a definujeme vlastní variantu. Pracujeme v prostředí, kde každý jedinec má fitness v závislosti na svém typu a vrcholu, který obývá. V modifikovaném modelu dokážeme dvě věty o počtu kroků, který proces udělá než se dostane do stabilního stavu. Ukážeme, že na úplném grafu proces udělá polynomiálně mnoho kroků. Najdeme také graf, kde proces udělá expo- nenciálně mnoho kroků ale v normálním modelu jich udělá stejně jako v úplném grafu. 1
Abstract v angličtině:
The Moran process is a model for simulating evolutionary dynamics. In that model, one mutant with higher fitness is introduced to a structured population. Evolution is simulated in rounds. In one round, individual is selected proportio- nally to its fitness and spreads to the place of a random neighbour. In this thesis, we motivate the Moran process, present basic results, and define our variant. We work in a vertex dependent model; every individual has fitness according to its type and occupied vertex. In the vertex dependent model we prove two theorems about the number of steps the process has to make to get to the stable state. We show that on the complete graph, the process takes only polynomially many steps and we find a graph where the process take exponentially many steps, but in the normal settings the number of steps is the same as on the complete graph. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Jakub Svoboda 2.6 MB
Stáhnout Abstrakt v českém jazyce Bc. Jakub Svoboda 39 kB
Stáhnout Abstrakt anglicky Bc. Jakub Svoboda 37 kB
Stáhnout Posudek vedoucího Mgr. Robert Šámal, Ph.D. 114 kB
Stáhnout Posudek oponenta Mgr. Martin Balko 1.03 MB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Iveta Mrázová, CSc. 152 kB