Metoda rješavanja problema egzaktnog pokrivanja

undergraduate thesis

• Title (english): Method for solving exact cover problem
• Author: Antonio Lakoš
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Lenka Mihoković (član povjerenstva)
• Committee member: Marina Furkes (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem potpunog prekrivanja razmatramo u kontekstu računalne konstrukcije (v, k, 1)-dizajna. Potrebno je pronaći k-člane blokove dizajna koji ujedno tvore egzaktno pokrivanje nad skupom parova svih točaka. Za traženje pokrivača koristimo algoritam X, algoritam kojeg je osmislio Donald Knuth. Knuthova implementacija oslanja se na metodu "dancing links".

Abstract (english)

Program implementation of Donald Knuth's algorithm X is used to solve an exact cover problem for (v, k, 1)-designs. Algorithm finds k-sized subsets called blocks which cover a set of point pairs. Algorithm X is implemented using "dancing links" method.

• Keywords: problem egzaktnog prekrivanja; egzaktno prekrivanje; pokrivač; dancing links; algoritam X; dizajn; DLX; Steinerov dizajn
• Keywords (english): exact cover problem; exact cover; cover; dancing links; algorithm x; design; DLX; Steiner system
• Language: croatian
• URN:NBN: urn:nbn:hr:168:582260
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 20:57:05