Naslov
Metoda rješavanja problema egzaktnog pokrivanja
(Method for solving exact cover problem)

Autori
Lakoš ; Antonio

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
28.06

Godina
2021

Stranica
21

Mentor
Anamari Nakić

Ključne riječi
problem egzaktnog prekrivanja ; egzaktno prekrivanje ; pokrivač ; dancing links ; algoritam X ; dizajn ; DLX ; Steinerov dizajn
(exact cover problem ; exact cover ; cover ; dancing links ; algorithm x ; design ; DLX ; Steiner system)

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

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA