Algoritmi generiranja slučajnih permutacija

master's thesis

• Author: Tihana Kovče
• Mentor: Saša Singer (mentor)
• Committee member: Saša Singer (predsjednik povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Permutacija je uređeni niz svih elemenata danog skupa. Slučajne permutacije nalaze široku primjenu u brojnim granama matematike i računalnih znanosti, npr. u kombinatorici i umjetnoj inteligenciji, ali i u svakodnevnom životu; npr. za miješanje špilova karata i popisa pjesama. Cilj ovog diplomskog rada bio je navesti i analizirati algoritme generiranja slučajnih permutacija, tzv. shuffling algoritme. Prvi se dio rada fokusirao na definiranje algoritama generiranja slučajnih permutacija i opisivanje kasnije korištenih metoda mjerenja i usporedbe njihovih složenosti. Također, naveli smo primjere pristranih i neoptimalnih algoritama, s ciljem prezentiranja loše prakse prilikom generiranja slučajnih permutacija. U drugom su dijelu nabrojani shuffling algoritmi, opisane njihove instrukcije, procijenjene složenosti i u koracima prikazana njihova izvođenja na testnim skupovima. Među opisanim algoritmima je i Fisher--Yatesov algoritam generiranja slučajnih permutacija, jedan od najpoznatijih algoritama u računalnoj znanosti. Dodatno, osvrnuli smo se na česte uzroke pristranosti pri generiranju slučajnih permutacija te istovremeno komentirali kako ih uspješno izbjeći. Konačno, algoritme smo implementirali u programskom jeziku C# te ocijenili njihovo izvođenje na kvantitativno značajnim podacima. Rezultati su prezentirani i uspoređeni, uz zaključak da je moderna verzija Fisher--Yatesovog algoritma istovremeno primjenjiva na dovoljno velikom skupovima, kao i zadovoljavajuće brza.

Abstract (english)

Permutation is a way of arranging all the elements of a given set into a sequence or an order. Random permutations are commonly used in different areas of mathematics and computer science, such as combinatorics and artificial intelligence, as well as in the everyday life; for arranging decks of cards, music play-lists, etc. The aim of this master’s thesis was to describe and analyze algorithms for generating random permutations, also known as shuffling algorithms. The first part of the thesis focused on defining shuffling algorithms and describing techniques later utilized for comparing their complexities. We also presented examples of how-not-to-shuffle, showing algorithms that are either biased or nonoptimal thus should not be used in data shuffling. The second part enumerated shuffling algorithms by identifying their steps, calculating complexities and displaying their step-by-step execution on a given example set. Among others, we mentioned the Fisher–Yates shuffle, one of the most widely recognized algorithms in computer science. Furthermore, we addressed frequent causes of bias in shuffling algorithms, simultaneously providing their solutions. Finally, the thesis validates given algorithms by implementing them in the programming language C# and executing the code with substantial input data. The outcomes are presented and compared, resulting in a conclusion that the modern, in-place version of the Fisher–Yates shuffle is both fast and applicable on arbitrarily large data sets.

• Keywords: permutacija; slučajne permutacije; shuffling algoritmi; Fisher--Yatesov algoritam; uzroci pristranosti
• Keywords (english): permutation; random permutations; shuffling algorithms; Fisher–Yates shuffle; causes of bias
• Language: croatian
• URN:NBN: urn:nbn:hr:217:501803
• 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: 2019-05-24 14:41:14