Search the digital library catalog

Query:	search in
	search in
	search in
	search in
Work type:	* old and bologna study programme
Language:
Search in:
Options:	Show only hits with full text
	Reset

1 - 3 / 3

Ukkonenov algoritem konstrukcije priponskega drevesa : diplomsko delo
Štefan Horvat, 2020, undergraduate thesis

Abstract: S pomočjo priponskih dreves lahko zelo preprosto in hitro izvajamo različne operacije nad nizi. Za gradnjo priponskih dreves obstajajo različni algoritmi. V diplomskem delu opi-šemo in implementiramo Ukkonenov algoritem, ki priponsko drevo zgradi v linearnem času. Najprej preučimo delovanje algoritma in tvorimo ustrezne podatkovne strukture. Sledi implementacija in preizkušanje. Z eksperimenti pokažemo karakteristike algoritma ob različnem številu znakov ter preverimo njegovo časovno in prostorsko zahtevnost.
Keywords: algoritmi, podatkovne strukture, analiza algoritmov, časovna in prostorska zahtevnost
Published in DKUM: 03.11.2020; Views: 1291; Downloads: 153
Full text (1,21 MB)

ALGORITEM BURROWS-WHEELERJEVE TRANSFORMACIJE
Andrej Žuran, 2016, undergraduate thesis

Abstract: V diplomski nalogi smo obravnavali algoritem Burrows-Wheelerjeve transformacije. Spoznali smo idejo transformacije in njen zgodovinski razvoj. Opisali smo najpogosteje uporabljene algoritme in inverz transformacije. Implementirali smo dva izbrana algoritma BWT. Prvi, tako imenovani izboljšan osnovni algoritem transformacije BWT nadgradi osnovno idejo BWT z izboljšanjem prostorske zahtevnosti. Drugi, algoritem, temelječ na predponskem drevesu, si pri gradnji transformacije pomaga s predponskim drevesom, ki smo ga zgradili z Ukkonenovim algoritmom. Implementirana algoritma smo nato primerjali glede na porabo časa CPU in porabo pomnilniškega prostora.
Keywords: algoritmi, predponsko drevo, časovna zahtevnost, prostorska zahtevnost
Published in DKUM: 13.04.2016; Views: 1545; Downloads: 148
Full text (1,71 MB)

Iskanje niza v besedilu
Sergej Pukšič, 2012, undergraduate thesis

Abstract: Besedilo B in niz S sta zaporedji znakov iz abecede ∑. Pri problemu iskanja niza v besedilu želimo poiskati vse ponovitve niza S v besedilu B. V ta namen so v prvem poglavju diplomskega dela predstavljene teoretične osnove. Opisan je princip snovanja in ob tem predstavljen postopek ocenjevanja časovne in prostorske zahtevnosti algoritmov. Drugo poglavje je namenjeno teoretičnim osnovam, ki se pojavljajo pri problemu iskanja niza v besedilu. Predstavljena je definicija, nato so opisane lastnosti in zakonitosti, ki se pojavljajo tekom iskanja nizov v besedilu. Naslednja poglavja so namenjena predstavitvi treh algoritmov, ki se uporabljajo pri nalogah iskanja niza v besedilu. Opisane so njihove lastnosti, njihovo delovanje pa je predstavljeno z različnimi grafičnimi prikazi ter psevdokodo. Za vsakega izmed njih je prav tako predstavljena ocena časovne zahtevnosti.
Keywords: niz, besedilo, iskanje, ujemanje, algoritem, naivni, Rabin-Karp, končni avtomat, časovna zahtevnost, prostorska zahtevnost
Published in DKUM: 23.05.2012; Views: 2100; Downloads: 127
Full text (2,68 MB)

Search done in 0.09 sec.