Vzporedni algoritmi za problem Levenshteinove razdalje in najdaljše skupno podzaporedjeBajić, Luka (Avtor) Mihelič, Jurij (Mentor) vzporedni algoritmivečnitnostLevenshteinova razdaljanajdaljše skupno podzaporedjedinamično programiranjeAlgoritmi za iskanje podobnosti med nizi so pomemben gradnik raznovrstnih aplikacij, ki so dandanes v vsakodnevni uporabi, od črkovalnikov do orodij za vodenje izvedb izvorne kode (npr. Git). Diplomsko delo opiše različne pristope optimizacije dveh tovrstnih algoritmov: Levenshteinove razdalje in najdaljšega skupnega podzaporedja, z uporabo koncepta večnitnosti in dveh temeljnih pristopov vzporejanja -- diagonalni in naprej-nazaj. Glavni cilj je časovna pohitritev algoritmov, ki jo ustrezno izmerimo in primerjamo nove implementacije z obstoječimi. Tako za diagonalni pristop kot za pristop naprej-nazaj razvijemo tudi prostorsko optimizirano metodo, ki je smiselna za uporabo pri velikih količinah vhodnih podatkov.20242024-08-29 10:45:08Diplomsko delo/naloga160507sl