| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 3 / 3
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Ukkonenov algoritem konstrukcije priponskega drevesa
Štefan Horvat, 2020, diplomsko delo

Opis: 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.
Ključne besede: algoritmi, podatkovne strukture, analiza algoritmov, časovna in prostorska zahtevnost
Objavljeno: 03.11.2020; Ogledov: 110; Prenosov: 26
.pdf Celotno besedilo (1,21 MB)

2.
ALGORITEM BURROWS-WHEELERJEVE TRANSFORMACIJE
Andrej Žuran, 2016, diplomsko delo

Opis: 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.
Ključne besede: algoritmi, predponsko drevo, časovna zahtevnost, prostorska zahtevnost
Objavljeno: 13.04.2016; Ogledov: 829; Prenosov: 93
.pdf Celotno besedilo (1,71 MB)

3.
Iskanje niza v besedilu
Sergej Pukšič, 2012, diplomsko delo

Opis: 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.
Ključne besede: niz, besedilo, iskanje, ujemanje, algoritem, naivni, Rabin-Karp, končni avtomat, časovna zahtevnost, prostorska zahtevnost
Objavljeno: 23.05.2012; Ogledov: 1428; Prenosov: 91
.pdf Celotno besedilo (2,68 MB)

Iskanje izvedeno v 0.1 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici