20.500.12556/RUL-81047 Algoritmi za problem izomorfizma dreves Algorithms for the tree isomorphism problem 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. 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. drevo izomorfizem algoritem. tree isomorphism algorithm. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2016-03-25 16:35:21 2016-03-25 16:35:21 2022-08-01 21:12:11 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 16121 Magdevski_Petar_-_Algoritmi_za_problem_izomorfizma_dreves.pdf Magdevski_Petar_-_Algoritmi_za_problem_izomorfizma_dreves.pdf 1 7F8747621F5B6CB8B68B86AC8DE58919 9130008e1f002cb7eb67eee28288bc7ff25d1d6b9c4a2e7f187031e298761e1a 468e8c12-a1a9-11eb-a523-00155dcfd717 20.500.12556/rul/6a0fd8ad-219b-4dfc-8d4c-37b7ee64d746 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=81266 Fakulteta za računalništvo in informatiko 0 0 0