diplomsko delo
Jure Pustoslemšek (Avtor), Uroš Čibej (Mentor)

Povzetek

V diplomskem delu smo implementirali Knuthove algoritme X, C in C$^\$$. S temi algoritmi smo reševali problem $n$ kraljic in iskanja minimalnega vozliščnega pokritja grafa. Definirali smo pojma posplošenega in pobarvanega razbitja. Problem $n$ kraljic smo prevedli na iskanje posplošenega razbitja, iskanje minimalnega vozliščnega pokritja pa na iskanje najcenejšega pobarvanega razbitja. Primerjali smo učinkovitost algoritmov X in C$^\$$ v primerjavi z običajnimi algoritmi za reševanje teh problemov. Videli smo, da je algoritem X učinkovit pri reševanju problema $n$ kraljic, za iskanje minimalnega vozliščnega pokritja pa so bolj primerni namenski algoritmi, vendar pa je algoritem C$^\$$ kljub temu uporaben pri reševanju tega problema na manjših in gostih grafih.

Ključne besede

plešoči kazalci;vozliščno pokritje;razbitje;kraljice;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [J. Pustoslemšek]
UDK: 004:51(043.2)
COBISS: 120747523 Povezava se bo odprla v novem oknu
Št. ogledov: 23
Št. prenosov: 14
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Vertex cover with dancing links
Sekundarni povzetek: In this thesis we have implemented Knuth's algorithms X, C and C$^\$$. With these algorithms, we solved the $n$ queens problem and the minimum vertex cover problem. We defined generalized and colored exact covers. We reduced the $n$ queens problem to the generalized exact cover problem, and the minimum vertex cover problem to the optimal colored exact cover problem. We compared the efficiency of algorithms X and C$^\$$ to the efficiency of regular algorithms for solving those problems. We say that algorithm X is efficient for solving the $n$ queens problem, however, purpose-specific algorithms are better for the minimum vertex cover problem, but algorithm C$^\$$ is still effective for solving this problem on small and dense graph.
Sekundarne ključne besede: dancing links;vertex cover;exact cover;queens;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000407
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 54 str.
ID: 16372684