Konstrukcija i primjena kombinatornih dizajna

master's thesis

• Title (english): Construction and application of combinatorial designs
• Author: Antonio Lakoš
• 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-06-27, Croatia

Abstract

Kažemo da je uređeni par (X, B) kombinatorni dizajn s parametrima (v, k, l) ako se skup X sastoji od v točaka, skup B od k-članih podskupova skupa X (blokova), te su svake dvije točke sadržane u točno l blokova. Pronalazak skupa blokova B je težak kombinatorni zadatak koji se svodi na rješavanje problema egzaktnog pokrivanja. U slučaju da je parametar l > 1, rješavamo višestruki problem egzaktnog pokrivanja. Taj se problem rješava algoritmom hi, modifikacijom algoritma X, koji je predstavljen u radu. U radu je izložena i Kramer-Mesnerova metoda za konstrukciju kombinatornih dizajna sa zadanom grupom automorfizama radi ubrzanja računalne konstrukcije. Izložena su i područja primjene kombinatornih dizajna.

Abstract (english)

Ordered pair (X, B) is a combinatorial design with parameters (v, k, l) if set X contains v points, set B contains k-sized subsets of X (blocks) and every two points are contained in exactly l blocks. Construction of set B is a hard combinatorial problem which can be reduced to an exact cover problem which is solved with algorithm chi, a modification of algorithm X. Algorithm chi as well as Kramer-Mesner method for construction of combinatorial designs with determined automorphism group are described. An overview of real-world applications of design theory are given.

• Keywords: dizajn eksperimenata; algoritam x; kramer-mesnerova metoda; problem egzaktnog pokrivanja; kombinatorni dizajn
• Keywords (english): design of experiments; algorithm x; kramer-mesner method; exact cover problem; combinatorial design
• Language: croatian
• URN:NBN: urn:nbn:hr:168:097894
• 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-07-13 10:16:17