Seminarska naloga - 1.del

Navodila

Pri tem delu seminarske naloge iz podatkovnih struktur in algoritmov pri DIRI 2005/6 boste spoznali podatkovne strukture ali algoritme, ki jih na predavanjih ne bomo obravnavali.  Na osnovi navedenih referenc (in tiste literature, ki jo boste poiskali sami) boste predstavili podatkovno strukturo/algoritem. Knjige so vse na voljo bodisi v Matematični knjižnici, bodisi pri Matiji Lokarju, kjer si lahko ustrezne strani skopirate. Sama predstavitev zajema razlago same teme in ilustracije uporabe te podatkovne strukture oziroma algoritma. Končni izdelek mora biti v obliki HTML strani, katere predlogo dobite tukaj. (kompletno v ZIP) - tam si preberite tudi natančnejši opis, kaj je potrebno narediti.

Osnovna ideja seminarske naloge je, da temo razložite tako, da bo bralec razumel zakaj gre in vsaj v principu znal potem algoritem oziroma podatkovno strukturo uporabiti! Pri tem predpostavite, da ima približno tako poznavanja podatkovnih struktur in algoritmov kot vi - torej kot slušatelj DIRI. Ne pišite preveč zapleteno - vse, kar napišete, morate zagotovo dobro razumeti! Če iz referenc enostavno prevajate in stvari ne premislite dobro, bodo težave. Namreč pogosto pozabimo, da je določen pojem, prijem, bil v originalnem besedilu razložen že prej, ali pa je ciljna publika druga, predznanje drugo, ... Skratka zadevo obdelajte pedagoško korektno!

Iz danega seznama si izberite ustrezno temo. Če izbrana tema ni označena kot zasedena (ni napisana rdeče), pošljete rezervacijo (na Matija.Lokar). Če bo sprejeta, boste obveščeni. Če imate posebno željo, da bi opisali kakšen algoritem/strukturo, ki ni na voljo, pošljite pošto in se bomo dogovorili. Temo lahko naknadno tudi zamenjate, če pošljete ustrezni predlog, kjer poveste kaj NE boste in kaj BI delali.

Če vam nobena od spodaj naštetih nalog ni všeč, si lahko izberete tudi tiste, ki so navedene tukaj in so označene kot neizbrane! V tem primeru jo rezervirate s pripombo, da je vzeta iz  R2!

Pri seminarski nalogi je nujen, važen in oh in sploh pomemben del PRIKAZ (lepa razlaga, čimbolj ilustrativna) delovanja algoritma na enem (ali še bolje več) konkretnem zgledu - npr. če bi pisali sem. nalogo iz odstranjevanja največjega elementa kopice bi na primer za kopico   123 56 48 56 12 40 36  10 5 6 pokazali, kaj se dogaja ob izločanju 123.

Primeri dobro narejenih nalog: 

Programov (npr. v Javi) ni potrebno pisati (le predstaviti ideje!) - razen pri 10 in 11 , seveda pa to ni prepovedano!

Seznam tem za seminarsko nalogo

Številka

Naslov

1 Topološko sortiranje
2 Verjetnostni algoritem za preverjanje praštevilskosti
3 B-drevesa
4 Rdeče-črna drevesa
5 Optimalno dvojiško iskalno drevo
6 Vrsta s prednostjo
7 Generiki v jeziku Java
8 Hamiltonov cikel
9 Najkrajše poti v grafu
10 Minimalno vpeto drevo v grafu (Kruskalov algoritem)
11 Minimalno vpeto drevo v grafu (Primov algoritem)
12 Najkrajše poti v uteženem grafu (Bellman-Ford)
13 Najkrajše poti v uteženem grafu (Dijkstra)
14 Najkrajše poti v uteženem grafu (Floyd-Warshall)
15 Iskanje podnizov v besedilu - Rabin-Karp
16 Iskanje podnizov v besedilu - Knuth-Moris-Prath
17 Iskanje sekajočih daljic
18 Konveksna ogrinjača - Grahamov pregled
19 Konveksna ogrinjača - Jarvisov obhod
20 Iskanje najbližjega para točk
21 Polifazno sortiranje
22 Naključna števila
23 Lomljena drevesa
24 Dvojna vrsta
25 Iskanje podnizov v besedilu - Boyer-Moore
26 Huffmanovo kodiranje
27 Shell sort
28 AVL drevesa
29 Tranzitivno zaprtje usmerjenega grafa
30 Močno povezane komponente v usmerjenem grafu (Kasarayu)
31 Močno povezane komponente v usmerjenem grafu (Tarjan)
32 Minimalno vpeto drevo v grafu (Boruvkov algoritem)
33 Skoraj optimalno dvojiško iskalno drevo z Walker-Gotliebovo metodo
34 Močno povezane komponente v usmerjenem grafu (Tarjan)
35 Razpršene tabele z odprtim naslavljanjem (linearno poskušanje)
36 Razpršene tabele z odprtim naslavljanjem (dvojna razpršitev)
37 Razpršene tabele z odprtim naslavljanjem (kvadratno poskušanje)
38 Razpršene tabele z linearnimi seznami
39 Urejanje po delih
40 Urejanje s stresanjem

Topološko sortiranje

Vhodni podatek algortmu je usmerjen acikličen graf. Naloga algoritma je, da uredi vozlišča v grafu v tak vrstni red, da se izvor vsake povezave pojavi pred ponorom. Za reference glej:

Verjetnostni algoritem za preverjanje praštevilskosti

Iskanje praštevil je zelo zapleten postopek. Še do nedavnega ni obstajal polinomski algoritem za preverjanje, ali je število praštevilo ali ne. Zato so se velikokrat uporabljali t.i. verjetnostni algoritmi, ki so z veliko verjetnostjo zelo hitro povedali, ali je število praštevilo ali ne (včasih pa se zmotijo in sestavljeno število označijo za praštevilo). Naloga bo pregledati enega izmed teh algoritmov, in sicer Rabin-Millerjev algoritem. Reference:

B-drevesa

B-drevesa so taka drevesa, v katerih ima koren lahko več kot dva sinova. Opišite, ilustrirajte in razložite osnovne operacije nad to podatkovno strukturo. Opisati bo potrebno ustrezen razred, ki je implementacija B-drevesa in sestaviti nekaj algoritmov, s katerimi boš ilustriral uporabo teh dreves. Reference:

Rdeče-črna drevesa

Rdeče-črna drevesa so dvojiška iskalna drevesa, kjer s pomočjo določenih operacij dosežemo, da se drevo ne izrodi preveč. Sicer se lahko izrodi bolj kot AVL drevo, a je rdeče-črna drevesa zato veliko lažje implementirati. Opišite, ilustrirajte in razložite osnovne operacije nad to podatkovno strukturo. Opisati  bo potrebno ustrezen razred, ki je implementacija tega drevesa in sestaviti nekaj algoritmnov, s katerimi boš ilustriral uporabo teh dreves. Reference:

Optimalno dvojiško iskalno drevo

Optimalno iskalno dvojiško iskalno drevo zgradimo takrat, kadar iščemo elemente in vemo, kako pogosto bomo iskali določen element. Seveda si želimo, da bi bili pogosteje iskani elementi hitreje dostopni kot tisti, ki se bodo iskali redko, saj bomo tako prihranili kar nekaj časa. To nam naredi algoritem za gradnjo optimalnega iskalnega dvojiškega drevesa. Referenca:

Vrsta s prednostjo

Vrsta s prednostjo je vrsta, kjer operaciji vrh() in odstrani() vrneta/odstranita največji element v vrsti. Ena izmed učinkovitih implementacij vrste s prednostjo je s kopico. Opišite, ilustrirajte in razložite osnovne operacije nad to podatkovno strukturo. Opisati bo potrebno ustrezen razred, ki je implementacija te strukture in sestaviti nekaj algoritmov, s katerimi boš ilustriral uporabo teh dreves. Reference:

Generiki v jeziku Java

V jeziku Java smo že uporabili sklad nizov, celih števil... Da ne bi za vsak tip posebej pisali svojega sklada, nam Java 1.5 prinaša nov koncept - generike (generics). Preberi si dokumentacijo o generikih. Prikaži kako generike uporabljamo, navedi veliko ilustrativnih zgledov  in z uporabo generikov predstavi strukturo Dvojiško Drevo, v katerem lahko hranimo katerekoli podatkovne tipe. Dodaj tudi nekaj primerov uporabe. Reference:

Hamiltonov cikel

Hamiltonov cikel v grafu je obhod grafa. Začne se v izbrani točki in obišče vsako vozlišče grafa natanko enkrat, konča pa se v začetnem vozlišču. Referenca:

Najkrajše poti v grafu

Razišči algoritem, ki z uporabo pregleda v širino poišče vse najkrajše poti v neuteženem grafu, ki se začnejo v dani točki. Reference:

Minimalno vpeto drevo v grafu (Kruskalov algoritem)

Naj bo G povezan neusmerjen graf z uteženimi povezavami. Radi bi našli tako vpeto drevo, da bo vsota cen povezav v tem vpetem drevesu minimalna. Eden izmed algoritmov za reševanje tega problema je Kruskalov algoritem. Ker smo o algoritmu govorili že na predavanjih, bo poudarek na implementaciji algoritma. Nič ne bo narobe, če bo izdelan applet kot npr. na internetni referenci, ki bo prikazal delovanje algoritma. Reference:

Minimalno vpeto drevo v grafu (Primov algoritem)

Naj bo G povezan neusmerjen graf z uteženimi povezavami. Radi bi našli tako vpeto drevo, da bo vsota cen povezav v tem vpetem drevesu minimalna. Eden izmed algoritmov za reševanje tega problema je Primov algoritem. Ker smo o algoritmu govorili že na predavanjih, naj bo poudarek na implementaciji algoritma. Nič ne bo narobe, če bo izdelan applet kot npr. na internetni referenci, ki bo prikazal delovanje algoritma. Reference:

Najkrajše poti v uteženem grafu (Bellman-Ford)

Kadar imamo zemljevid in potujemo iz kraja v kraj se velikokrat vprašamo, kakšna je najkrajša pot med dvema točkama. Če zemljevid predstavimo kot graf, v katerem kraji predstavljajo vozlišča in so uteži na povezavah enake razdaljam med kraji, potem iščemo najkrajšo pot v usmerjenem uteženem grafu. Eden izmed algoritmov, ki poišče vse najkrajše poti z začetkom v dani točki, je Bellman-Fordov algoritem. Referenca:

Najkrajše poti v uteženem grafu (Dijkstra)

Kadar imamo zemljevid in potujemo iz kraja v kraj, se velikokrat vprašamo, kakšna je najkrajša pot med dvema točkama. Če zemljevid predstavimo kot graf, v katerem kraji predstavljajo vozlišča in so uteži na povezavah enake razdaljam med kraji, potem iščemo najkrajšo pot v usmerjenem uteženem grafu. Eden izmed algoritmov, ki poišče vse najkrajše poti z začetkom v dani točki, je Dijkstrin algoritem. Referenca:

Najkrajše poti v uteženem grafu (Floyd-Warshall)

Kadar imamo zemljevid in potujemo iz kraja v kraj, se velikokrat vprašamo, kakšna je najkrajša pot med dvema točkama. Če zemljevid predstavimo kot graf, v katerem kraji predstavljajo vozlišča in so uteži na povezavah enake razdaljam med kraji, potem iščemo najkrajšo pot v usmerjenem uteženem grafu. Eden izmed algoritmov, ki poišče vse najkrajše poti med vsemi točkami v grafu, je Floyd-Warshallov algoritem. Referenca:

Iskanje podnizov v besedilu - Rabin-Karp

Zelo pogosta operacija pri urejevalnikih besedila je iskanje podniza v danem besedilu. Če je besedilo dolgo, lahko veliko prihranimo na času iskanja, če uporabimo dober algoritem za iskanje vzorcev. Referenca:

Iskanje podnizov v besedilu - Knuth-Moris-Prath

Zelo pogosta operacija pri urejevalnikih besedila je iskanje podniza v danem besedilu. Če je besedilo dolgo, lahko veliko prihranimo na času iskanja, če uporabimo dober algoritem za iskanje vzorcev. Referenca:

Iskanje sekajočih daljic

Podano imamo množico daljiv. Povedati moramo, ali se kateri dve daljici sekata. Seveda je potrebno to storiti na pameten način, ki ima časovno zahtevnost manjšo ali enako O(n logn), kjer je n število daljic. Referenca:

Konveksna ovojnica - Grahamov pregled

Iskanje konveksne ovojnice množice točk je eden izmed pogosteje uporabljanih algoritmov v računalniški geometriji. Referenca:

Konveksna ovojnica - Jarvisov obhod

Iskanje konveksne ovojnice množice točk je eden izmed pogosteje uporabljanih algoritmov v računalniški geometriji. Referenca:

Iskanje najbližjega para točk

Na vajah smo že nekajkrat iskali najbližji točki iz množice točk, a nikoli nismo naredili algortma, ki bi tekel hitreje kot s kvadratno časovno zahtevnostjo. S pomočjo tehnike deli in vladaj pa se da doseči časovno zahtevnost reda O(n logn). Referenca:

Polifazno sortiranje

Včasih se zgodi, da imamo samo sekvenčen dostop do podatkov (recimo na tračnih enotah). Kako v takem primeru sortirati podatke, če imamo na voljo več tračnih enot, tako, da bo za to potrebno čim manj časa?

Naključna števila

Ko kličemo ukaz Math.random() velikokrat niti ne pomislimo, kako nam računalnik izračuna naključno število. Ker je računalnik determinističen stroj, seveda to število ne more biti zares naključno, ampak se mora nekako izračunati. Ena izmed metod za generiranje naključnih števil je linearna kongruentna metoda. Referenca:

Lomljena drevesa

Lomljena drevesa so binarna iskalna drevesa (BST), ki se lomijo ob vsaki operaciji nad drevesom. S tem se prepreči pomankljivost navadnih dvojiških iskalnih dreves, za katere obstaja neugodni vrstni red operacij, s katerim se drevo izrodi. Opišite, ilustrirajte in razložite osnovne operacije nad to podatkovno strukturo.

Dvojna vrsta

Dvojna vrsta je struktura, ki podpira poleg običajnega vstavljanja in brisanja na začetku vrste tudi vstavljanje in brisanje elementov na koncu vrste. Opišite, ilustrirajte in razložite osnovne operacije nad to podatkovno strukturo. Opiši način implementacije take strukturo in navedi nekaj zgledov uporabe. Referenca:

Iskanje podnizov v besedilu (Boyer-Moore)

Zelo pogosta operacija pri urejevalnikih besedila je iskanje podniza v danem besedilu. Če je besedilo dolgo, lahko veliko prihranimo na času iskanja, če uporabimo dober algoritem za iskanje vzorcev. Referenca:

Huffmanovo kodiranje

Tekstovne datoteke lahko stisnemo tako, da zamenjamo pogosto ponavljajoče se besede s krajšimi simboli. Eden izmed načinov takega kodiranja je Huffmanovo kodiranje.

Pregled v širino

V grafih moramo pogosto pregledati vse točke oz. povezave. Eden izmed možnih pregledov je t.i. pregled v širino.

Pregled v globino

V grafih moramo pogosto pregledati vse točke oz. povezave. Eden izmed možnih pregledov je t.i. pregled v globino.

Tranzitivno zaprtje usmerjenega grafa

Tranzitivno zaprtje usmerjenega grafa je usmerjen graf, ki ima povezave iz dane točke v vse tiste točke, ki jih iz te točke lahko dosežemo s sprehodom po usmerjenih povezavah v originalnem grafu.

Močno povezane komponente v usmerjenem grafu (Kasarayu)

V povezanem grafu lahko definiramo močno povezane komponente. To so množice vozlišč, za katere velja, da iz poljubne začetne točke lahko pridemo do poljubne končne točke s sprehodom po usmerjenih povezavah.

Močno povezane komponente v usmerjenem grafu (Tarjan)

V povezanem grafu lahko definiramo močno povezane komponente. To so množice vozlišč, za katere velja, da iz poljubne začetne točke lahko pridemo do poljubne končne točke s sprehodom po usmerjenih povezavah.

Minimalno vpeto drevo v grafu (Boruvkov algoritem)

Naj bo G povezan neusmerjen graf z uteženimi povezavami. Radi bi našli tako vpeto drevo, da bo vsota cen povezav v tem vpetem drevesu minimalna. Eden izmed algoritmov za reševanje tega problema je Boruvkov algoritem. Reference:

Skoraj optimalno dvojiško iskalno drevo

Optimalno iskalno dvojiško iskalno drevo zgradimo takrat, kadar iščemo elemente in vemo, kako pogosto bomo iskali določen element. Seveda si želimo, da bi bili pogosteje iskani elementi hitreje dostopni kot tisti, ki se bodo iskali redko, saj bomo tako prihranili kar nekaj časa. To nam naredi algoritem za gradnjo optimalnega iskalnega dvojiškega drevesa. Praktično uporaben je algoritem za tvorbo približno optimalnega drevesa (Walker - Gotlieb, 1972). Referenca:

Močno povezane komponente v usmerjenem grafu (Gabow)

V povezanem grafu lahko definiramo močno povezane komponente. To so množice vozlišč, za katere velja, da iz poljubne začetne točke lahko pridemo do poljubne končne točke s sprehodom po usmerjenih povezavah.

Razpršene tabele I

Razpršene tabele so podatkovna struktura, ki omogoča zelo hitro vstavljanje in iskanje. Obstaja več različnih implementacij. Predstaviti bo potrebno tisto, ki probleme ključev z enakimi kodami rešuje z linearnim poskušanjem.

Razpršene tabele II

Razpršene tabele so podatkovna struktura, ki omogoča zelo hitro vstavljanje in iskanje. Obstaja več različnih implementacij. Predstaviti bo potrebno tisto, ki probleme ključev z enakimi kodami rešuje z dvojnim razprševanjem.

Razpršene tabele III

Razpršene tabele so podatkovna struktura, ki omogoča zelo hitro vstavljanje in iskanje. Obstaja več različnih implementacij. Predstaviti bo potrebno tisto, ki probleme ključev z enakimi kodami rešuje s kvadratnim razprševanjem.

Razpršene tabele IV

Razpršene tabele so podatkovna struktura, ki omogoča zelo hitro vstavljanje in iskanje. Obstaja več različnih implementacij. Predstaviti bo potrebno tisto, ki probleme ključev z enakimi kodami rešuje z uporabo linearnih seznamov.

Urejanje s stresanjem

Urejanje s stresanjem (shake sort) je različica urejanja z mehurčki. Podrobno predstavi algoritem.

Shell sort

Sortiranje z vstavljanjem s padajočim prirastkom – Shellsort (avtor D. Shell 1957) je izboljšana različica urejanja z vstavljanjem. Podrobno predstavi algoritem.

Urejanje po delih

Urejanje po delih (radix sort) uporabljamo za urejanje takih podatkov, kjer so ključi lahko zelo zapleteni. Obstaja več različic takega urejanja. Predstaviti je potrebno osnovno idejo in podrobneje eno od različic.

AVL drevesa

AVL drevesa so dvojiška iskalna drevesa. Imajo to lastnost, da se višina levega in desnega poddrevesa v vsakem vozlišču razlikuje kvečjemu za ena, tako da za iskanje elementa v tem drevesu vedno porabimo log n časa, cena za to pa je zahtevnejše vstavljanje in brisanje elementov. Opišite, ilustrirajte in razložite osnovne operacije nad to podatkovno strukturo. Opisati bo potrebno ustrezen razred, ki je implementacija tega drevesa in sestaviti nekaj algoritmov, s katerimi boš ilustriral uporabo teh dreves. Reference:

Valid XHTML 1.0! Valid CSS!