Klasifikacija vjerojatnosnih algoritama

master's thesis

• Author: Ana Peterfaj
• Mentor: Mladen Vuković (mentor)
• Committee member: Mladen Vuković (predsjednik povjerenstva)
• Committee member: Zvonko Iljazović (član povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Slaven Kožić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-09-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu bavili smo se vjerojatnosnim algoritmima. Vjerojatnosni algoritmi su vrsta algoritama koji u barem jednom dijelu svog izvršavanja donose slučajnu odluku o daljnjem tijeku izvršavanja. Prvo smo definirali dva teorijska modela. Algoritmi iz prvog modela na slučajan način biraju deterministički algoritam koji zatim koriste na danom ulazu, dok algoritmi koji pripadaju drugom modelu tijekom izvršavanja donose više slučajnih odluka. Primjer algoritma građenog po prvom modelu je Protokol \(R_k\), a primjer algoritma građenog po drugom modelu je vjerojatnosni Quicksort. Zatim smo se bavili podjelom vjerojatnosnih algoritama s obzirom na vjerojatnost greške. Las Vegas algoritmi su vjerojatnosni algoritmi koji ne dopuštaju grešku. Za njih smo naveli dvije podvrste: oni koji dopuštaju odgovor "?" i oni koji ga ne dopuštaju. Dokazali smo da je podvrste ovih algoritama moguće svesti jedne na druge te smo analizirali Random - select algoritam kao primjer Las Vegas algoritma koji ne dopušta odgovor "?", te Protokol LV\(_{10}\) koji ga dopušta. Algoritmi s jednostranom greškom dopuštaju grešku, ali samo ako je vjerojatnost greške manja od \(\frac{1}{2}\) i to samo na ulazima koji bi trebali biti prihvaćeni. Naveli smo primjere algoritama s jednostranom greškom: vjerojatnosni protokol za jednakost te Pojednostavljeni Solovay - Strassen algoritam. Algoritmi s ograničenom greškom zahtijevaju da je vjerojatnost greške za svaki ulaz manja od \(\frac{1}{2} - \epsilon\), gdje je \(\epsilon\) fiksni broj iz \( \left(0, \frac{1}{2}\right]\). Analizirali smo brzinu smanjenja vjerojatnosti greške nekog algoritma s ograničenom greškom \(A\) s obzirom na broj nezavisnih ponavljanja s istim ulazom. Došli smo do zaključka da vjerojatnost greške na algoritmima s ograničenom greškom možemo spustiti proizvoljno nisko, uz konstantan broj nezavisnih ponavljanja. Algoritmi s neograničenom greškom zahtijevaju samo da je vjerojatnost greške manja od \(\frac{1}{2}\). Primjer jednog takvog algoritma je Protokol UMC za koji smo dokazali da zadovoljava definiciju algoritma s neograničenom greškom.

Abstract (english)

In this master’s thesis we have dealt with randomized algorithms. Randomized algorithms are a type of algorithms that in at least one part of their execution make a random decision about the further course of execution. We first define two theoretical models. The algorithms from the first model randomly select a deterministic algorithm, which they then use at a given input, while the algorithms belonging to the second model make more random decisions during execution. An example of an algorithm built on the first model is the \(R_k\) protocol, and an example of an algorithm built on the second model is the randomized Quicksort. We then dealt with the classification of randomized algorithms with respect to the probability of error. Las Vegas algorithms are randomized algorithms that guarantee that every compute answer is correct. We have listed two subtypes for them: those that allow the answer "?" and those that do not allow it. We have proven that the subtypes of these algorithms can be transformed to one another, and we have analyzed the Random - select algorithm as an example of a Las Vegas algorithm that does not allow the "?" answer, and the LV\(_{10}\) protocol that allows it. One-sided error algorithms allow errors, but only if the probability of an error is less than \(\frac{1}{2}\) and only at the inputs that should be accepted. We have provided examples of one-sided error algorithms: Randomized Equality Protocol and Simplified Solovay - Strassen Algorithm. Bounded-error algorithms require that the error probability for each input is less than \(\frac{1}{2} - \epsilon\), where \(\epsilon\) is a fixed number from \( \left(0, \frac{1}{2}\right]\). We have analyzed the rate of error reduction of a bounded-error algorithm A with respect to the number of independent repetitions with the same input. We have come to the conclusion that the probability of error on bounded-error algorithms can be lowered arbitrarily, with a constant number of independent repetitions. Unbounded-error algorithms only require that the error probability is less than \(\frac{1}{2}\). An example of such an algorithm is the UMC protocol, which we have proven to satisfy the definition of an unbounded-error algorithm.

• Keywords: vjerojatnosni algoritmi; Las Vegas algoritmi; algoritmi s jednostranom greškom; algoritmi s ograničenom greškom; algoritmi s neograničenom greškom; Protokol UMC
• Keywords (english): randomized algorithms; Las Vegas algorithm; one-sided error algorithms; bounded-error algorithms; unbounded-error algorithms; UMC protocol
• Language: croatian
• URN:NBN: urn:nbn:hr:217:056417
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-02-17 13:24:10