prikaz prve stranice dokumenta Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo
No public access
master's thesis
Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2014. urn:nbn:hr:168:123846
Bučar, Damir
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Bučar, D. (2014). Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo (Master's thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:123846

Bučar, Damir. "Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2014. https://urn.nsk.hr/urn:nbn:hr:168:123846

Bučar, Damir. "Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2014. https://urn.nsk.hr/urn:nbn:hr:168:123846

Bučar, D. (2014). 'Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo', Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 16 July 2024, https://urn.nsk.hr/urn:nbn:hr:168:123846

Bučar D. Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo [Master's thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2014 [cited 2024 July 16] Available at: https://urn.nsk.hr/urn:nbn:hr:168:123846

D. Bučar, "Konstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo", Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2014. Available at: https://urn.nsk.hr/urn:nbn:hr:168:123846

Metadata
TitleKonstrukcije Steinerovih sustava trojki pomoću heurističkog algoritma penjanja uzbrdo
Title (english)Constructions of Steiner triple systems by means of heuristic hill climbing algorithm
AuthorDamir Bučar
MentorMario Osvin Pavčević (mentor)
Committee memberMario Osvin Pavčević (predsjednik povjerenstva)
Committee memberMario Krnić (član povjerenstva)
Committee memberDomagoj Kovačević (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2014-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:123846
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2018-02-06 08:04:37