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

master's thesis

• Title (english): Constructions of Steiner triple systems by means of heuristic hill climbing algorithm
• Author: Damir Bučar
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Domagoj Kovačević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2014-07-02, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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).

Abstract (english)

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).

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