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

diplomski rad

• Naslov (engleski): Computational construction of orthogonal Latin squares and application to the problem of scheduling
• Autor: Mihaela Bakšić
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Član povjerenstva: Mate Puljiz (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-07-10, Hrvatska

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: 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
• Ključne riječi (engleski): 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
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:069929
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 08:20:29