Algoritmi za podudaranje znakovnih nizova

Souček, Amalia

prikaz prve stranice dokumenta Algoritmi za podudaranje znakovnih nizova

Pristup korisnicima matične ustanove

diplomski rad

Algoritmi za podudaranje znakovnih nizova

Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2016. urn:nbn:hr:217:622889

Souček, Amalia

Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Zatraži primjerak
dokumenta

Citirajte ovaj rad

APA 6th Edition

Souček, A. (2016). Algoritmi za 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:622889

MLA 8th Edition

Souček, Amalia. "Algoritmi za podudaranje znakovnih nizova." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2016. https://urn.nsk.hr/urn:nbn:hr:217:622889

Chicago 17th Edition

Souček, Amalia. "Algoritmi za podudaranje znakovnih nizova." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2016. https://urn.nsk.hr/urn:nbn:hr:217:622889

Harvard

Souček, A. (2016). 'Algoritmi za podudaranje znakovnih nizova', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 19.04.2024., https://urn.nsk.hr/urn:nbn:hr:217:622889

Vancouver

Souček A. Algoritmi za podudaranje znakovnih nizova [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2016 [pristupljeno 19.04.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:622889

IEEE

A. Souček, "Algoritmi za podudaranje znakovnih nizova", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2016. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:622889

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:622889

Prijavite se u repozitorij kako biste mogli spremiti objekt u svoju listu.

Podaci o radu

Naslov	Algoritmi za podudaranje znakovnih nizova
Autor	Amalia Souček
Mentor	Goranka Nogo (mentor)
Član povjerenstva	Goranka Nogo (predsjednik povjerenstva)
Član povjerenstva	Mladen Vuković (član povjerenstva)
Član povjerenstva	Filip Najman (član povjerenstva)
Član povjerenstva	Vjekoslav Kovač (č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 obrane	2016-04-27, Hrvatska
Znanstveno / umjetničko područje, polje i grana	PRIRODNE ZNANOSTI Matematika
Sažetak	U ovom radu opisali smo četiri važna algoritma koji rješavaju problem podudaranja znakovnih nizova: Knuth-Morris-Prattov, Boyer-Mooreov, Two ways i Shift or. Objasnili smo ideju svakog algoritma te računali njegovu složenost. Zaključili smo da Boyer-Mooreov algoritam ima sublinearnu složenost u prosječnom slučaju dok ostali imaju linearnu složenost u najgorem slučaju. Dobivene rezultate za zadnja tri opisana algoritma smo provjerili na testnim primjerima. Kao sto smo i očekivali, dobili smo da je Boyer-Mooreov brži od Two ways i Shift or. Takoder uočili smo kako je Shift or zapravo vrlo efikasan, usprkos jednostavnoj implementaciji, ali ograničen na dozvoljenoj dužini obrasca.
Sažetak (engleski)	In this work we presented four important string matching algorithms: Knuth-Morris-Pratt, Boyer-Moore, Two ways and Shift or. We explained the idea behind each one and computed their time complexity. We concluded that the time complexity of Boyer-Moore is sublinear in the average case while the time complexity of the remaining algorithms is linear in the worst case. We tested our results for the last three algorithms on test data. As expected, Boyer-Moore was quicker than Two ways and Shift or. Besides, we noticed that Shift or is actually very efficient, even though its implementation is very simple. However, this algorithm is limited by the length of the pattern.
Ključne riječi
Ključne riječi (engleski)
Jezik	hrvatski
URN:NBN	urn:nbn:hr:217:622889
Studijski program	Naziv: 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 resursa	Tekst
Način izrade datoteke	Izvorno digitalna
Prava pristupa	Pristup korisnicima matične ustanove
Uvjeti korištenja
Repozitorij	Repozitorij Prirodoslovno-matematičkog fakulteta
Datum i vrijeme pohrane	2019-02-07 12:04:57

Nacionalna i sveučilišna knjižnica u Zagrebu

Dabar