| | 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 - 7 / 7
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
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: 1322; Prenosov: 86
.pdf Celotno besedilo (2,68 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: 735; Prenosov: 82
.pdf Celotno besedilo (1,71 MB)

3.
Algoritmi minimalnega vpetega drevesa v vsakdanjem življenju
Marija Gajić, 2016, delo diplomskega projekta/projektno delo

Opis: V zaključni projketni nalogi je opisano minimalno vpeto drevo in načini iskanja minimalnega vpetega drevesa v grafu. Predstavljeni in analizirani so trije algoritmi in sicer Primov, Kruskalov in Boruvkin algoritem. Podrobneje so predstavljene tudi programske implementacije teh treh algoritmov. V nadaljevanju je predstavljena praktična uporaba minimalnega vpetega drevesa v vsakdanjem življenju ter opis enega konkretnega primera – postavljanja vodovodnega omrežja. Za izbiro optimalnega algoritma so java programske implementacije algoritmov testirane na 408 testnih datotekah z grafi. Analizirana je odvisnost časovne zahtevnosti algoritma od števila povezav v grafu. Hkrati je predstavljena še primerjava časovne učinkovitosti vseh treh analiziranih algoritmov.
Ključne besede: minimalno vpeto drevo, uporaba v vsakdanjem življenju, primerjava algoritmov, časovna zahtevnost
Objavljeno: 22.03.2017; Ogledov: 1851; Prenosov: 127
.pdf Celotno besedilo (1,34 MB)

4.
Pohitritev transformacije domnevnih razdalj
Danijel Žlaus, 2016, magistrsko delo/naloga

Opis: V magistrskem delu opisujemo pohitritev transformacije domnevnih razdalj, ki je izpeljanka tradicionalnih algoritmov transformacij razdalj. Transformacije razdalj običajno delujejo nad dvodimenzionalnimi binarnimi slikami, kjer vsakemu elementu ospredja določijo oddaljenost do najbližjega elementa ozadja. Kadar slika ni binarna, je nad njo potrebno izvesti dodano predprocesiranje, ki vključuje korak binarizacije. Nasprotno pa lahko transformacijo domnevnih razdalj uporabimo neposredno nad sivinskimi, barvnimi in multispektralnimi slikami in se tako izognemo pogoste neželenemu predprocesiranju. Slabost tega pristopa pa je časovna zahtevnost, ki je v naivni implementaciji kar O(N^2.5). V magistrskem delu predstavimo pohitren algoritem transformacije domnevnih razdalj ter teoretično analizo njegove časovne zahtevnosti. Nad implementiranim algoritmom izvedemo tudi meritve, s čimer potrdimo teoretične časovne zahtevnosti pohitrenega pristopa, ki je enaka O(N^1.5) v pričakovanem ter O(N^2) v najslabšem primeru.
Ključne besede: matematična morfologija, transformacija domnevnih razdalj, transformacija razdalj, časovna zahtevnost, optimizacijske metode
Objavljeno: 06.09.2016; Ogledov: 635; Prenosov: 82
.pdf Celotno besedilo (6,77 MB)

5.
Szeged indeks povezav, pi indeks in wienerjev indeks povezav benzenoidnih sistemov
Doroteja Štunf, 2017, magistrsko delo

Opis: Magistrska naloga obravnava benzenoidne sisteme. Predstavljena je uporaba teorije grafov v kemiji in s tem uporabna povezava med kemijo in matematiko. V uvodnih poglavjih so zato predstavljeni osnovni pojmi teorije grafov in kemijski pojmi, ki so potrebni za razumevanje nadaljnje snovi. Benzenoidni sistemi so zanimivi za raziskovanje, saj predstavljajo skupino kemijskih spojin imenovano benzenoidni ogljikovodiki. V nadaljevanju naloge so podane osnovne lastnosti in definicije benzenoidnih sistemov. V uvodu osrednjega dela so navedene definicije Wienerjevega, Szeged in PI indeksa za poljubne in nato še za utežene grafe. Sledi vpeljava vseh treh indeksov povezav s predstavitvijo algoritmov za njihov izračun v linearni časovni zahtevnosti, ki je v nalogi tudi dokazana. Za lažje razumevanje so dodani primeri izračuna na izbranem primeru benzenoidnega sistema.
Ključne besede: benzenoidni sistem, topološki indeks, Wienerjev indeks povezav, Szeged indeks povezav, PI indeks, uteženi graf, elementarni razrez, kvocientno drevo, linearna časovna zahtevnost
Objavljeno: 09.01.2018; Ogledov: 570; Prenosov: 47
.pdf Celotno besedilo (1,09 MB)

6.
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: 15; Prenosov: 7
.pdf Celotno besedilo (1,21 MB)

7.
Diskretne strukture
Iztok Peterin, 2020

Opis: V učbeniku so predstavljene nekatere veje diskretne matematike, ki so še posebej uporabne v računalništvu. Tako se sprehodimo skozi logiko, s posebnim poudarkom na dokazu. Sledijo teorije, pri katerih igra poglavitno vlogo matematična indukcija oziroma bolj splošno induktivna posplošitev. Spoznamo osnove kombinatorike in teorije števil. Predstavljene so rekurzivne relacije, s katerimi lahko opišemo ponavljajoče se procese. To nam omogoča tudi vrednotenje algoritmov glede na čas potreben za njegovo izvedbo. Relacije, ki so podmnožice kartezičnega produkta poljubnih množic, predstavljajo širok vir presenetljivih rezultatov. Eden izmed njih rezultira v mrežah in njihovih posebnih predstavnikih Booleovih algebrah. Končamo z grafi, ki predstavljajo neverjetno uporaben matematični model za simuliranje procesov iz realnega življenja.
Ključne besede: izjavni račun, indukcija, kombinatorika, rekurzivna relacija, časovna zahtevnost, teorija števil, relacija, mreža, Booleova algebra, graf
Objavljeno: 27.10.2020; Ogledov: 35; Prenosov: 29
.pdf Celotno besedilo (5,40 MB)

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