Primjene vjerojatnosne metode na determinističke igre

master's thesis

• Author: Ana Milošević
• Mentor: Vjekoslav Kovač (mentor)
• Committee member: Vjekoslav Kovač (predsjednik povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Committee member: Boris Muha (član povjerenstva)
• Committee member: Boris Guljaš (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-02-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu je obrađena takozvana vjerojatnosna metoda, s naglaskom na njezine primjene u analizi determinističkih igara. Obzirom da je sama metoda nekonstruktivna, izložen je i proces derandomizacije, koji producira učinkovite algoritme. U radu su opisane dvije najčešće korištene metode u procesu derandomizacije - metoda uvjetnih vjerojatnosti i metoda pesimističnih procjenitelja. Potom su na primjerima triju determinističkih igara za dva igrača provedeni postupci randomizacije, derandomizacije i antirandomizacije, s ciljem pronalaska savršenih pobjedničkih strategija za igrače, uz odgovarajuće vrijednosti danih parametara. Na kraju rada izloženi su konkretni primjeri strategija za igru lažova u svrhu približavanja i ilustracije prethodno dobivenih općenitih rezultata.

Abstract (english)

This thesis deals with the so-called probabilistic method, with emphasis on applications to the analysis of deterministic games. Since the method itself is nonconstructive, the process of derandomization which produces efficient algorithms is also presented. This thesis describes the two most commonly used methods in the process of derandomization – the method of conditional probabilities and the method of pessimistic estimators. Furthermore, the procedures of randomization, derandomization, and antirandomization were carried out on the examples of three deterministic games for two players, aimed at finding the perfect winning strategies for the players, depending on the corresponding values of the given parameters. At the end of the thesis concrete examples of strategies for the Liar game are given

• Keywords: vjerojatnosna metoda; determinističke igre; metoda uvjetnih vjerojatnosti; metoda pesimističnih procjenitelja
• Keywords (english): probabilistic method; deterministic games; method of conditional probabilities; method of pessimistic estimators
• Language: croatian
• URN:NBN: urn:nbn:hr:217:902215
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-24 16:40:36