prikaz prve stranice dokumenta Algoritmi za djelomično podudaranje znakovnih nizova
  Preuzmi
PDF 325.95 KB
diplomski rad
Algoritmi za djelomično podudaranje znakovnih nizova
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2015. urn:nbn:hr:217:400399
Ružić, Sanjin
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Ružić, S. (2015). Algoritmi za djelomično podudaranje znakovnih nizova (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić, Sanjin. "Algoritmi za djelomično podudaranje znakovnih nizova." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2015. https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić, Sanjin. "Algoritmi za djelomično podudaranje znakovnih nizova." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2015. https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić, S. (2015). 'Algoritmi za djelomično podudaranje znakovnih nizova', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 03.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić S. Algoritmi za djelomično podudaranje znakovnih nizova [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2015 [pristupljeno 03.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:400399

S. Ružić, "Algoritmi za djelomično podudaranje znakovnih nizova", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2015. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:400399

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:400399
Podaci o radu
NaslovAlgoritmi za djelomično podudaranje znakovnih nizova
AutorSanjin Ružić
MentorGoranka Nogo (mentor)
Član povjerenstvaGoranka Nogo (predsjednik povjerenstva)
Član povjerenstvaMiljenko Marušić (član povjerenstva)
Član povjerenstvaGoran Igaly (član povjerenstva)
Član povjerenstvaMarko Vrdoljak (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2015-09-25, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom radu obradili smo algoritme koji rješavaju problem podudaranja znakovnih nizova. Promatrali smo tri različita problema: problem egzaktnog podudaranja, problem aproksimativnog podudaranja te problem podudaranja sa zamjenskim znakovima. Pritom smo se vise usredotočili na posljednje dvije klase problema. Za svaku od klasa naveli smo jedan ili vise najznačajnijih algoritama koji rješava dotični problem. Tako smo za problem egzaktnog podudaranja znakovnih nizova, uz naivni algoritam, analizirali i klasične algoritme kao sto su Rabin-Karpov, Knuth-Morris-Prattov te Boyer-Mooreov. Za svaki od njih objasnili smo osnovnu ideju te pokazali vremensku složenost. Za problem aproksimativnog podudaranja znakovnih nizova odabrali smo Wagner-Fischerov algoritam temeljen na ideji dinamičkog programiranja koji računa edit-udaljenost između dvaju stringova. Detaljno smo dokazali njegovu korektnost te vremensku složenost. Iako on sam ne rješava problem aproksimativnog podudaranja znakovnih nizova kako smo ga mi u radu definirali, vidjeli smo da se njegovom sitnom modifikacijom koju je uveo Sellers moze rješiti i naš problem. Na kraju, za problem podudaranja stringova sa zamjenskim znakovima predstavili smo tri rješenja. Prvo rješenje se zasniva na regularnim izrazima koji su zapravo puno ekspresivniji nego je nama potrebno pa imaju relativno veliku vremensku složenost. Drugo rješenje je dobiveno rekurzivnim algoritmom koji smo optimizirali koristeći dinamičko programiranje. Posljednje rješenje se zasniva na ideji backtrackinga, a u usporedbi s preostala dva ima najmanju prosječnu vremensku složenost. Sve spomenute algoritme smo implementirali u programskom jeziku Java uz zaključak da se dobiveni eksperimentalni rezultati podudaraju s teoretskim.
Sažetak (engleski)
In this thesis we studied string matching algorithms. We analyzed three different problems: exact, approximate and wildcard string matching. We focused on last two classes of algorithms. We mentioned one or more most significant representatives of each class. For exact string matching, beside naive algorithm, we also analyzed classic algorithms such as Rabin-Karp, Knuth-Morris-Pratt and Boyer-Moore. For each of them we described main idea and determined complexity. For approximate string matching, we chose Wagner-Fischer algorithm which is based on dynamic programming. It computes edit distance between two strings. While it does not solve problem of approximate string matching as we defined it, we saw that it can be modified in order to solve our problem, too. This modification was introduced by Sellers. Finally, for wildcard string matching we presented three solutions. First one was based on regular expressions which are in fact more expressive than we need so they have relative high complexity. Second solution was recursive algorithm which is further optimized by dynamic programming. Last solution is based on idea of backtracking, and in comparison with another two solutions had lowest average time complexity. We implemented all mentioned algorithms in programming language Java. Conclusions were that all experimental results coincide with theoretical results.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:400399
Studijski programNaziv: Računarstvo i matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2019-02-05 15:54:22