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

Abstract

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.

Keywords

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

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [J. Pustoslemšek]
UDC: 004:51(043.2)
COBISS: 120747523 Link will open in a new window
Views: 23
Downloads: 14
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Vertex cover with dancing links
Secondary abstract: 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.
Secondary keywords: 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;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000407
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 54 str.
ID: 16372684