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)
