Metoda rješavanja problema egzaktnog pokrivanja

završni rad

• Naslov (engleski): Method for solving exact cover problem
• Autor: Antonio Lakoš
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Lenka Mihoković (član povjerenstva)
• Član povjerenstva: Marina Furkes (č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: 2021-07-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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

Sažetak (engleski)

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.

• Ključne riječi: problem egzaktnog prekrivanja; egzaktno prekrivanje; pokrivač; dancing links; algoritam X; dizajn; DLX; Steinerov dizajn
• Ključne riječi (engleski): exact cover problem; exact cover; cover; dancing links; algorithm x; design; DLX; Steiner system
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:582260
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 20:57:05