1.
Primerjava algoritmov nenatančnega iskanja vzorcev v nizih : magistrsko deloKarmen Potočan, 2022, magistrsko delo
Opis: 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.
Ključne besede: nizi, urejevalna razdalja, nenatančno iskanje vzorcev v nizih, problem $k$ razlik, algoritmi, analiza algoritmov
Objavljeno v DKUM: 28.10.2022; Ogledov: 654; Prenosov: 58
Celotno besedilo (723,33 KB)
