Računalna konstrukcija ortogonalnih latinskih kvadrata i primjena na problem izrade rasporeda

master's thesis

• Title (english): Computational construction of orthogonal Latin squares and application to the problem of scheduling
• Author: Mihaela Bakšić
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Committee member: Mate Puljiz (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-10, Croatia

Abstract

Turniri igraju ključnu ulogu u raznim područjima poput izrade rasporeda sportskih događanja, analize društvenih mreža i eksperimentalnog dizajna. Ovaj rad istražuje konstrukciju turnira koristeći latinske kvadrate i Međusobno Ortogonalne Latinske Kvadrate (MOLS). Implementirani su postojeći algoritmi za konstrukciju balansiranih i bipartitnih turnira. Fokus ovog istraživanja je procjena vremenske i prostorne složenosti implementiranih algoritama. Obavlja se sveobuhvatna analiza za različite vrijednosti parametra veličine koja mjeri vrijeme izvođenja, korištenje memorije i skalabilnost algoritama.

Rezultati pokazuju da implementirani algoritmi učinkovito konstruiraju turnire koristeći latinske kvadrate i MOLS. Analiza vremenske i prostorne složenosti otkriva skalabilnost algoritama, čineći ih pogodnima za primjenu za velike turnire. Mjerenja performansi pokazuju da dizajni koji su stvoreni posjeduju željene karakteristike i zadovoljavaju zahtjeve stvarnih scenarija.

Abstract (english)

Tournament designs play a crucial role in various fields, such as sports scheduling, social network analysis, and experimental design. This thesis explores the construction of tournament designs using Latin squares and Mutually Orthogonal Latin Squares (MOLS). The existing algorithms for constructing Balanced tournament designs and Bipartite tournament designs were implemented. The focus of this study is to assess the time and space complexity of the algorithms. A comprehensive analysis is performed on various size parameter values measuring the execution time, memory usage, and scalability of the algorithms.

The results demonstrate that the implemented algorithms efficiently construct tournament designs using Latin squares and MOLS. The time and space complexity analysis reveals the scalability of the algorithms, making them suitable for large-scale applications. The performance measurements indicate that the designs produced possess desirable properties and meet the requirements of real-world scenarios.

• Keywords: problem raspoređivanja; latinski kvadrati; međusobno ortogonalni latinski kvadrati; turniri; balansirani turniri; bipartitni turniri; kombinatorni dizajn; Moore-MacNeish teorem; Eulerov problem 36 službenika
• Keywords (english): Scheduling problems; Latin squares; Mutually Orthogonal Latin squares; Tournament designs; Balanced tournament designs; Bipartite tournament designs; Combinatorial design; Moore-MacNeish theorem; Euler’s 36 officers problem
• Language: english
• URN:NBN: urn:nbn:hr:168:069929
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-10-11 08:20:29