izpis_h1_title_alt

Algoritmi za problem izomorfizma dreves
MAGDEVSKI, PETAR (Author), Mihelič, Jurij (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (1,06 MB)

Abstract
V diplomskem delu so predstavljeni algoritmi za preverjanje enakovrednosti, oz. izomorfnosti dreves. Definirana so drevesa, opisani so osnovni koncepti drevesnih obhodov, podane so podrobnosti algoritmov za drevesni izomorfizem, med katerimi sta bolj podrobno predstavljena algoritma za izomorfizem neurejenih dreves po Valiente ter po Aho, Hopcroft in Ullman. Algoritmi so tudi implementirani ter eksperimentalno primerjani. Primerjava je bila narejena na podlagi časa, ki ga je vsak od algoritmov porabil pri določanju izomorfizma naključno generiranih dreves. Drevesa so bila razvrščena v skupine, odvisno od števila vozlišč in nad vsako skupino dreves sta bila izvedena oba algoritma.

Language:Slovenian
Keywords:drevo, izomorfizem, algoritem.
Work type:Bachelor thesis/paper (mb11)
Organization:FRI - Faculty of computer and information science
Year:2016
Views:668
Downloads:322
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:English
Title:Algorithms for the tree isomorphism problem
Abstract:
In this thesis algorithms for checking isomorphism between trees are elaborated. Tree definition is provided, basic concepts of tree traversals are described, details of tree isomorphism algorithms are given, putting special attention and focus on unordered tree isomorphism, algorithm by Valiente as well as algorithm by Aho, Hopcroft and Ullman. Algorithms have been implemented and compared. Comparison was done upon the times needed for each of the algorithms to determine the isomorphism between randomly generated trees. Trees were classified in groups depending on the number of vertices and both algorithms were executed over each group of vertices.

Keywords:tree, isomorphism, algorithm.

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back