Abstract: V magistrskem delu predstavimo tri algoritme za reševanje problema $k$ razlik, in sicer rešitev z dinamičnim programiranjem, vključno z Ukkonenovo izboljšavo pričakovane časovne zahtevnosti, algoritem Galila in Parkova ter algoritem Tarhia in Ukkonena. Predstavljene algoritme implementiramo v programskem jeziku Python in izvedemo meritve časov izvajanja pri različnih testnih primerih, tako na angleškem kot slovenskem besedilu. Na koncu predstavimo rezultate meritev in na podlagi le-teh primerjamo algoritme.Keywords: nizi, urejevalna razdalja, nenatančno iskanje vzorcev v nizih, problem $k$ razlik, algoritmi, analiza algoritmovPublished in DKUM: 28.10.2022; Views: 654; Downloads: 56 Full text (723,33 KB)
Abstract: S pomočjo priponskih dreves lahko zelo preprosto in hitro izvajamo različne operacije nad nizi. Za gradnjo priponskih dreves obstajajo različni algoritmi. V diplomskem delu opi-šemo in implementiramo Ukkonenov algoritem, ki priponsko drevo zgradi v linearnem času. Najprej preučimo delovanje algoritma in tvorimo ustrezne podatkovne strukture. Sledi implementacija in preizkušanje. Z eksperimenti pokažemo karakteristike algoritma ob različnem številu znakov ter preverimo njegovo časovno in prostorsko zahtevnost.Keywords: algoritmi, podatkovne strukture, analiza algoritmov, časovna in prostorska zahtevnostPublished in DKUM: 03.11.2020; Views: 1291; Downloads: 154 Full text (1,21 MB)