Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo

diplomski rad

• Naslov (engleski): Constructions of Steiner triple systems by means of heuristic hill climbing algorithm
• Autor: Damir Bučar
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Domagoj Kovačević (č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: 2014-07-02, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu bavimo se konstrukcijom Steinerovih sustava trojki, jednog od proučavanijih kombinatoričkih blokovnih dizajna. Nakon konciznog pregleda matematičke podloge, nastavljamo s usporedbom egzaktnog backtracking algoritma s heurističkim algoritmom penjanja uzbrdo na klasičnom NP-teškom 0–1 problemu naprtnjače, kako bismo pokazali prednosti (i poneke nedostatke) metoda heurističke pretrage.
Slijedi opis Stinsonovog algoritma, temeljenog na heurističkom algoritmu penjanja
uzbrdo, te dviju varijanti korištenih struktura podataka. Pokazujemo da je istim
moguće konstruirati Steinerove sustave trojki viših redova (v > 5000) u razumnom
vremenskom rasponu (oko 1 minute), s eksperimentalno utvrđenom vremenskom složenošću O(v^2 ln v^2).

Sažetak (engleski)

This thesis concerns with the construction of Steiner triple systems, one of the
more studied combinatorial block designs. After a concise theoretical overview, we
compare the exact backtracking algorithm with the heuristic hill-climbing algorithm
on a classic NP-hard 0–1 knapsack problem, to show the advantages (and some of the
disadvantages) of heuristic search.
Further on, we describe the Stinson’s algorithm, based on the heuristic hill-climbing algorithm, which we implement using two different data structure sets. We show it is possible to employ the algorithm in construction of higher order Steiner triple systems (v > 5000), within reasonable time (around 1 min) and with experimentally determined time complexity of O(v2 ln v2).

• Ključne riječi: Steinerov sustav trojki; 0--1 problem naprtnjače; backtracking; heuristička pretraga; algoritam penjanja uzbrdo; Stinsonov algoritam
• Ključne riječi (engleski): Steiner triple systems; 0--1 knapsack problem; backtracking; heuristic search; hill-climbing algorithm; Stinson's algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:123846
• 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: 2018-02-06 08:04:37