ASP Kolokvij 2 PDF

7. Stablo stablo korijen stabla Struktura podataka koja se sastoji od povezanih čvorova Čvor može biti roditelj (prethodnik) i/ili dijete (sljedbenik) nekog drugog čvora Jedan element zove se korijen jedan list stabla stabla (A) Čvorovi koji nisu roditelji zovu se listovi stabla (E, G, H, I, J, C, D) Stablo s 10 čvorova primjeri primjene stabla - DOM DOM (Document Object Model) (www.w3.org) primjeri primjene stabla - XML, JSON XML, JSON { "bookstore": { "books": [ { "category": "fiction", Harry Potter "title": "Harry Potter", J.K. Rowling "author": "J.K. Rowling", 19.99 "price": 19.99 }, { Into the Wild "category": "non-fiction", Jon Krakauer "title": "Into the Wild", 14.95 "author": "Jon Krakauer", "price": 14.95 } ] } } primjeri primjene stabla - XML, JSON Object { | "bookstore": { "bookstore" "books": [ | { └── Object "category": "fiction", | "title": "Harry Potter", ├── "books" "author": "J.K. Rowling", | "price": 19.99 └── Array }, | { ├── Object "category": "non-fiction", | ├── "category" "title": "Into the Wild", | ├── "title" "author": "Jon Krakauer", | ├── "author" "price": 14.95 | └── "price" } | ] └── Object } ├── "category" } ├── "title" ├── "author" └── "price" primjeri primjene stabla - sintaksna analiza Izraz kao 3+4*2-1 može se prikazati stablom primjeri primjene stabla - sintaksna analiza Naredba kao if (x > y) return 0; else return 1; može se prikazati stablom primjeri primjene stabla - pozivi funkcija Izvršavanje programa primjeri primjene stabla - programski jezici Jezici kao Clojure, Racket, Lisp Aritmetiki izraz: (* 3 (+ 1 2)) Naredba if: (if (> a b) (print a) (print b)) Definicija funkcije: (define abs n (if (< n 0) -n n)) primjeri primjene stabla - programski jezici struktura aritmetičkog izraza (* 3 (+ 1 2)) odgovara izrazu 3*(1+2) primjeri primjene stabla - programski jezici struktura izraza (if (> a b) (print a) (print b)) primjeri primjene stabla - strategijske igre na ploči Teorija igara Primjer stabla u igri križić-kružić stablo za binarno pretraživanje (engl. binary search tree) Pretraživanje Da bi došli do podatka koji tražimo moramo znati kako su podaci organizirani Cilj je podatke organizirati tako da ih se brzo može pronaći Brzo = bez pregledavanja svih podataka, t.j. da u postupku pretraživanja što više podataka “preskočimo”, ali tako da ne preskočimo i ono što tražimo Tehnički izraz je suziti ili smanjiti prostor pretraživanja (engl. search space) Binarno pretraživanje Vidjeli smo ga na početku gdje smo tražili vrijednost u sortiranom nizu p1 p3 p4 p2 Indeks elementa 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 3 7 8 12 14 15 16 20 27 28 31 33 36 44 51 58 60 61 66 70 a b Niz mora biti soritran a b a b a b stablo za binarno pretraživanje Podaci se mogu organizirati u stablo gdje se lijevo od svakog čvora nalaze elementi manji od onoga u čvoru, a desno veći Na primjer, klasa map u C++u koristi SBP stablo za binarno pretraživanje Ovakvo stablo zovemo stablo za binarno pretraživanje (SBP), binarno jer svaki čvor ima najviše dva sljedbenika Jedan skup podataka možemo prikazati kroz više različitih stabala za binarno pretraživanje. Na primjer, podatke {7, 4, 1, 9, 3} možemo prikazati na više načina: oblici i svojstva binarnog stabla i stabla za binarno pretraživanje visina stabla Visina čvora u stablu odgovara broju lukova najdužeg puta od tog čvora do nekog lista stabla Visina stabla ispod je 4 (korijen je na razini 0) balansirano binarno stablo Binarno stablo kod kojeg se visina lijevog i desnog podstabla svakog čvora ne razlikuje za više od 1 balansirano stablo nebalansirano balansirano potpuno binarno stablo Binarno stablo kod kojeg svaki list ima istu dubinu, a svaki unutrašnji čvor dva djeteta (Slika 4.24) Skoro potpuno binarno stablo (Slika 4.25) je ono kod kojeg posljednja razina ne mora biti do kraja popunjena, a svi listovi na toj razini poslagani su jedan do drugoga bez praznih mjesta, promatrajući ih s lijeva na desno. Potpuno binarno stablo visine h ima 2h − 1 unutrašnjih čvorova i 2h listova puno binarno stablo Binarno stablo kod kojeg svaki čvor ima dva djeteta ili je list stabla odnosno nema djece Broj čvorova punog binarnog stabla najmanje je 2h+1, a najviše 2h+1−1 operacije: najmanji i najveći element Najmanji element SBP je krajnji lijevi elementi koji nema lijevo dijete, a najveći krajnji desni koji nema desno dijete Vremenska složenost je O(h) u najgorem slučaju operacije: prethodni i idući element po veličini Prethodni element od 15 je 13 (najveći element lijevog podstabla), a idući 17 (najmanji element desnog podstabla) Vremenska složenost je O(h) u najgorem slučaju obilazak stabla za binarno pretraživanje obilazak stabla u dubinu Tri vrste obilaska SBP u dubinu * infiksno * prefiksno * postfiksno Ovo su varijante obilaska u dubinu (engl. Depth First Search ili DFS) inﬁksni obilazak Možemo zamisliti da stablo sadrži aritmetičke operatore, kao +, -, *, /, … Tada infiksni obilazak mora ispisati elemente u obliku školske notacije, na primjer, a+b*c, to jest tako da je operator između dva operanda [3,*,1,+,2] inﬁksni obilazak Infiksno: prođi lijevu stranu čvora X, ispiši X, prođi desnu stranu čvora X -> 2, 5, 5, 6, 7, 8 inﬁksni obilazak inﬁksni obilazak element stabla za binarno pretraživanje SBP je skup čvorova Svaki čvor povezan je s 0, 1 ili 2 sljedbenika (djeca) i jednim prethodnikom (roditeljem) inﬁksni obilazak preﬁksni obilazak Kod prefiksnog oblika operator dolazi prije operanada [*,3,+,1,2] preﬁksni obilazak Prefiksno: ispiši X, prođi lijevu stranu čvora X, prođi desnu stranu čvora X a) 6, 5, 2, 5, 7, 8 b) 2, 5, 7, 6, 5, 8 preﬁksni obilazak preﬁksni obilazak postﬁksni obilazak Kod posfiksnog oblika operator dolazi iza operanada [3,1,2,+,*] postﬁksni obilazak Postfiksno: prođi lijevu stranu čvora X, prođi desnu stranu čvora X, ispiši X a) 2, 5, 5, 8, 7, 6 b) 5, 6, 8, 7, 5, 2 postﬁksni obilazak postﬁksni obilazak inﬁksni obilazak i sortirani redoslijed elemenata Elemente SBP možemo lako dobiti u sortiranom redoslijedu infiksnim obilaskom stabla evaluacija aritmetičkih izraza Prefiksni i infiksni oblik izraza jednostavan je za evaluaciju jer nema zagrada Prvo moramo izraz konvertirati u stablo -> sintaksna analiza Izraz 3*(1+2) u prefiksnom obliku je *,3,+,1,2, a u postfiksnom 3,1,2,+,* Da bi izračunali izraz u postfiksnom obliku evaluiramo prvi operator (s lijeva) koji se nalazi na indeksu P koji ima dva operanda s lijeve strane na indeksima P-1 i P-2; taj postupak ponavljamo dok ne ostane jedna vrijednost (rezultat) (slično je s prefiksnim oblikom, samo se operandi nalaze desno od operatora) 3*(1+2) => stablo => 3,1,2,+,* -> 3,3,* -> 9 Prioritet operacija je implicitan 4+(2*8-1) => stablo => 4,2,8,*,1,-,+ -> 4,16,1,-,+ -> 4,15,+ -> 19 generiranje koda na osnovu preﬁsknog ili postﬁksnog obilaska stabla Umjesto ispisivanja podataka u čvorovima možemo generirati instrukcije za procesor ili VM Neka je izraz 4+(2*8-1) 1. PUSH 4 Sadržaj stoga 2. PUSH 2 1. 4,2,8-> (nakon instr. 3) 3. PUSH 8 2. 4,16-> (nakon MUL) 4. MUL 3. 4,16,1-> (nakon PUSH 1) 5. PUSH 1 4. 4,15-> (nakon SUB) 6. SUB 5. 19-> (nakon ADD) 7. ADD obilazak u dubinu iterativno Može se implementirati rekurzivno i iterativno Stog prije pop() Ispis Stog na kraju petlje 1. 7-> 7 9, 3-> 2. 9, 3-> 3 9, 4, 1-> 3. 9, 4, 1-> 1 9, 4 -> 4. 9, 4 -> 4 9-> 5. 9-> 9 - 6. - obilazak u širinu Postoji i obilazak u širinu (engl. Breadth-First Search ili BFS) BFS: 20, 14, 36, 5, 16, 31, 40, 1, 22, 35, 38, 44, 39 obilazak u širinu obilazak u širinu Implementira se kao i obilazak u dubinu, ali se umjesto stoga koristi red obilazak u širinu Implementira se iterativno Red prije DEQUEUE() Ispis Red na kraju petlje 1. 7-> 7 9, 3-> 2. 9, 3-> 3 4, 1, 9-> 3. 4, 1, 9-> 9 4, 1 -> 4. 4, 1 -> 1 4-> 5. 4-> 4 - 6. - operacije nad binarnim stablom Treba nam i neki objekt koji će predstavljati stablo najmanji i najveći element Za najmanji element slijedimo lijevi put do kraja, a za najveći, desni Vremenska složenost je O(h) prethodnik i sljedbenik čvora S P Najmanji element desnog podstabla Vremenska složenost je O(h) pretraživanje Krećemo se po stablu zavisno od toga je li traženi element veći ili manji od trenutnog elementa stabla dodavanje novog elementa Dodavanje elementa 13 Vremenska složenost je O(h) Možemo li 13 dodati odmah desno od 12? 10 13 11 dodavanje novog elementa brisanje elemenata Nekoliko slučajeva: 1. Ako z nema djece onda odgovarajući atribut njegovog roditelja postavimo na NIL. 2. Ako z ima jedno dijete onda z zamijenimo tim djetetom tako da postavimo odgovarajući atribut roditelja na to dijete. 3. Ako z ima oba djeteta onda ga zamijenimo njegovim sljedbenikom (jer taj nema lijevo dijete) koji će se nalaziti u desnom podstablu čvora z. brisanje elemenata ako je slučaj d) za slučaj c) i d) teorem Operacije dodavanja i brisanja elementa iz stabla za binarno pretraživanje mogu se implementirati u vremenu O(h) gdje je h visina stabla. vremenska složenost operacija nad sbp Ispis elemenata u sortiranom redoslijedu: Θ(n) Obilazak u dubinu: Θ(n) Pretraživanje: O(h), gdje je h visina stabla Pronalaženje minimuma ili maksimuma: O(h) Umetanje elementa: O(h) Brisanje elementa: O(h) 8. Tablica raspršivanja (engl. hash table) Niz kao osnova za složenije strukture podataka Indeksiranje niza odvija se u konstantnom vremenu Možemo li niz iskoristiti za neki “praktičniji” pristup elementima osim samo putem brojčanog indeksa? Možemo li na osnovu jednog podatka doći do drugih? Na primjer, ako nam indeks niza označava broj ECTS bodova, a element na tom indeksu je povezana lista JMBAGova, onda možemo eﬁkasno doći do svih studenata s određenim brojem ECTSa Indeks nam je u tom slučaju ključ za pretraživanje U ovom slučaju podatke ne moramo tražiti nego direktno dođemo do njih Niz kao osnova za složenije strukture podataka Niz tada možemo zamisliti kao tablicu s dva stupca: ključ i vrijednost Ključ nije potrebno smještati u memoriju Da bi došli do vrijednosti moramo naći redak u kojem se ona nalazi Redak pronalazimo putem ključa U primjeru s ECTS bodovima, ključ je broj ključ (ECTS) vrijednost bodova, a vrijednost lista studenata s tim 1 ana → ivo → marko brojem bodova 2 petar 3 luka → martina 4 goran → sara … Tablica s direktnim adresiranjem (TDA) Ovakva se tablica zove tablica s direktnim adresiranjem (engl. direct address table) Kod TDA elementima se pristupa putem cjelobrojnog ključa (≥ 0) Operacije pristupa, umetanja i brisanja imaju jednostavnu implementaciju: dohvati(T, k): return T[k] dodaj(T, k, e): T[k] = e O(1) obrisi(T, k): T[k] = NIL Nedostaci TDA Primjer: želimo doći do podatka o osobama na osnovu datuma rođenja bez godine, onda datum rođenja oblika ggggmmdd može biti ključ (na primjer, 19730528) Ključeva može biti jako puno i indeksi su jako veliki Ne želimo niz sa svim ovim indeksima držati u memoriji jer je prevelik i dobar dio indeksa ne bi bio iskorišten (ako, primjerice, nitko od ovih osoba nije rođen prije 1900.) Možemo u memoriji čuvati puno manji niz, s tim da ključeve transformiramo u neke manje brojeve Na primjer, možemo iz ključa ukloniti prve dvije znamenke Nedostaci TDA Druga opcija je korištenje mod operacije (ostatak dijeljenja) Na primjer, ako je niz veličine 1000 elemenata onda ključ možemo transformirati po formuli i = k mod 1000 Ovo nam daje više ﬂeksibilnosti za odabir veličine niza, ali i ključa Općenito, za niz veličine m i ključ k, indeks na kojem se nalazi traženi podatak je i = k mod m Na primjer, za m = 574 indeks ključa 19730528 je 426 Nedostaci TDA Ali šta ako je ključeva više od m? Tada dva ili više ključa, odnosno podaci koje oni predstavljaju, “dijele” isti indeks u nizu To se zove kolizija; na primjer, 19830404 mod 574 je također 426! Struktura podataka koja podržava veći broj ključeva od veličine niza i rad s kolizijama zove se tablica raspršivanja (engl. hash table) Tablica raspršivanja (TR) Tablica raspršivanja je generalizacija tablice s direktnim adresiranjem TDA radi samo s brojčanim ključevima (indeksima) Još jedan problem s TDA: ako je broj svih mogućih ključeva velik, TDA treba puno memorije Ako u tablicu smještamo samo mali broj mogućih ključeva onda je većina te memorije neiskorištena Ako je broj ključeva koji smještamo u tablicu puno manji od broja svih mogućih ključeva, tablica raspršivanja (engl. hash table) je bolja struktura podataka Tablica raspršivanja (TR) U praksi ima odlične performanse pretraživanja, blizu O(1) u prosjeku, ali postoje preduvjeti Zasniva se na principu funkcije raspršivanja (engl. hash function) Umjesto pristupa elementima direktno putem indeksa, indeks se izračuna na osnovu ključa i hash funkcije Kod TDA element s ključem k smješten je na poziciji k, dok je kod TR on smješten na poziciji h(k) Tablica raspršivanja (TR) Tablicu raspršivanja možemo proširit tako da elementima niza možemo pristupati putem nekog drugog tipa ključa kao što je string ili datum Mnogi programski jezici podržavaju ovakvu strukturu podataka Umjesto da pišemo x ← podaci // podaci je niz da možemo pisat x ← podaci[“zagreb”] // podaci je tablica, “zagreb” je ključ podaci[“zagreb”] znači “u tablici podaci nađi vrijednost s ključem zagreb” Sintaksa može biti i drugačija, kao podaci.find(“zagreb”) Tablica raspršivanja (TR) Takvu strukturu podataka zovemo rječnik (engl. dictionary) Zove se još i mapa ili asocijativan niz Za razliku od tablice s direktnim adresiranjem, ključ ne predstavlja indeks u nizu, ali se preko njega dolazi do indeksa Rječnik se često implementira pomoću TR (ali i stabla za binarno pretr.) Rječnik isto možemo zamisliti kao tablicu s dva stupca: ključ i vrijednost ključ vrijednost “zagreb” 29 “rijeka” 28 “pula” 30 Primjer: telefonski imenik Želimo implementirati imenik kontakta kod kojeg na osnovu imena i prezimena dobijemo broj telefona Ovo možemo zamisliti kao tablicu s dva stupca: # IME I PREZIME TEL. 0 Pero Perić 123-4567 1 Iva Ivić 987-6543 2 Mara Marić 456-1234 3 Marko Markić 654-3210 … … … “Naivna” implementacija Jedan jednostavan način na koji ovo možemo implementirati je pomoću dva niza: jedan za imena i drugi za brojeve telefona. Da bi našli broj telefona za neko ime jednostavno nađemo na kojem se indeksu nalazi to ime i s tog indeksa pročitamo broj telefona: for i ← 1.. veličina-niza(imena) do if imena[i] = trazeno_ime then return tel_brojevi[i] end if end for Ako je n broj imena, vremenska složenost ovakve funkcije je, očito, Θ(n) u najgorem slučaju (ako niz brojeva nije sortiran) Implementacija funkcijom raspršivanja Možemo li doći do traženog imena na brži način? Ako je niz imena sortiran onda do traženog imena možemo doći u Θ(lg n) vremenu u najgorem slučaju Međutim, često možemo dobiti i bolju vremensku složenost Ako bi za traženo ime mogli izračunati na kojem se indeksu nalazi, uopće ne bi morali tražiti (pod uvjetom da su ta imena na isti način i smještena u niz) Kako bi to mogli izračunati? Implementacija funkcijom raspršivanja Postoji više načina, zavisno o kakvoj vrsti podatka se radi U ovom primjeru radimo sa stringovima Jedan način je da na osnovu duljine imena + prezimena dobijemo indeks na kojem se takva imena nalaze Pero Perić - 10 znakova (s razmakom) Iva Ivić - 8 znakova Marta Marić - 11 znakova Marko Markić - 12 znakova Implementacija funkcijom raspršivanja Ovo ne možemo primijeniti na postojeću tablicu jer je ona popunjena na drugačiji način Tablicu moramo popuniti uzevši u obzir princip po kojem ćemo pronalaziti imena “Pero Perić” 10 znakova “Iva Ivić” 8 znakova “Marta Marić” 11 znakova “Marko Markić” 12 znakova Neka tablica sadrži prostor za maksimalno M=5 redaka Formula može biti ovo: duljina(ime) mod M Primjerice, 10 mod 5 = 0, 8 mod 5 = 3, 11 mod 5 = 1, 12 mod 5 = 2 Implementacija funkcijom raspršivanja Postupak traženja nekog imena sada izgleda ovako: 1. Izračunaj indeks po formuli i = # IME I PREZIME TEL. duljina-imena mod maks-redaka 2. Ako se na indeksu i nalazi 0 Pero Perić 123-4567 traženo ime vrati broj telefona 1 Marta Marić 852-3698 na indeksu i 3. U suprotnom, vrati NIL 2 Marko Markić 654-3210 3 Iva Ivić 987-6543 4 Implementacija funkcijom raspršivanja ključ vrijednost Ovim smo dobili jednostavnu tablicu raspršivanja # IME I PREZIME TEL. Ime i prezime je ključ (kao jedan string) 0 Pero Perić 123-4567 Imali smo 4 ključa (“Pero Perić”, “Marta 1 Marta Marić 852-3698 Marić”, …) Svakom ključu pridružena je jedna 2 Marko Markić 654-3210 vrijednost 3 Iva Ivić 987-6543 Formula po kojoj smo računali indekse zove 4 se funkcija raspršivanja (engl. hash function), odnosno h(k) = duljina(ime) mod M Vremenska složenost Možemo vidjeti da u ovom postupku nije bilo traženja - izračunali smo indeks i došli do ključa koji smo tražili Koja je vremenska složenost ovog postupka? Ovisi li on o broju podataka u tablici? 1. Izračunaj indeks po formuli h(k) = len(k) mod M 2. Ako se na indeksu i nalazi traženo ime vrati broj telefona na indeksu i 3. U suprotnom, vrati None Vidimo da nema traženja U nekim slučajevima, međutim, i TR malo “traži” Kolizije Kolizije Jedini problem s ovim postupkom je što ne kolizija uzima u obzir kolizije Kolizija nastaje kada za dva različita ključa # IME I PREZIME TEL. funkcija raspršivanja daje isti broj U našem primjeru, dva ključa (“Pero Perić” 0 Pero Perić 123-4567 i “Sara Sarić”) imaju isti broj znakova Sara Sarić 456-1234 Kako bi mogli izbjeći koliziju? 1 Marta Marić 852-3698 Treba nam bolja funkcija raspršivanja Jedna dobra takva funkcija za stringove je 2 Marko Markić 654-3210 h(s) = s*31(n-1) + s*31(n-2) +... + s[n-1] 3 Iva Ivić 987-6543 4 gdje je s string, a n njegova duljina Primjer u Pythonu def hash(k, M): Vidimo da i ovdje imamo koliziju r = 0 for i in range(len(k)): na indeksima 2 i 0 r += ord(k[i]) * pow(31, (len(k) - (i + 1))) To je zato što je tablica premala return r % M Primjerice, za veličinu 25 (umjesto 5) dobili bi 22, 0, 2, 16, velicina = 5 print( 5 hash('Marko Markic', velicina), hash('Iva Ivic', velicina), Implementacije tablica hash('Pero Peric', velicina), hash('Sara Saric', velicina), raspršivanja obično proširuju hash('Marta Maric', velicina)) tablicu kada popunjenost pređe # ispisuje 2 0 2 1 0 oko 75% Tehnike rješavanja kolizija: Ulančavanje Kolizija je slučaj kada funkcija raspršivanja daje istu vrijednost za dva ili više različitih ključeva Najjednostavniji način rješavanja kolizija je ulančavanje Vrijednosti ključeva koji su u koliziji smještaju se u povezanu listu Tehnike rješavanja kolizija: Ulančavanje Faktor opterećenosti (engl. load factor) deﬁnira se kao ⍺ = n / m, gdje je n broj elemenata u tablici, a m veličina tablice Ovo daje prosječan broj elemenata u ulančanom nizu Neuspješno pretraživanje tablice raspršivanja s ulančavanjem je u prosjeku Θ(1 + 𝛼), pod uvjetom da hash funkcija ravnomjerno raspoređuje elemente Tehnike rješavanja kolizija: Otvoreno adresiranje Svi elementi su u tablici, nema povezanih lista Umjesto povezanih lista računamo niz indeksa koje pretražujemo Da bi dodali novi ključ ispitujemo tablicu dok ne nađemo slobodan indeks, ali ne po redu nego pomoću funkcije raspršivanja oblika h(k, i) Funkcija raspršivanja ovdje prima dva parametra: ključ k i broj pokušaja i, gdje se i kreće u rasponu 0..m-1 Time računamo vrijednost funkcije raspršivanja redoslijedom h(k,0), h(k, 1), …, h(k, m-1) (dok ne dođemo do praznog mjesta u tablici) Otvoreno adresiranje Pseudokod umetanja i pretraživanja tablice raspršivanja kod otvorenog adresiranja: Otvoreno adresiranje Brisanje je malo složenije Ne možemo jednostavno postaviti NIL na mjesto koje brišemo (zašto?) Jedan način je da se mjesto s koje smo obrisali element označi nekom specijalnom vrijednošću (npr. OBRISANO) gdje bi procedura za dodavanje elementa tu vrijednost tretirala kao NIL (procedura za pretraživanje ne bi zahtijevala promjene) Ako se iz tablice raspršivanja često brišu podaci onda je bolje koristiti ulančavanje Otvoreno adresiranje Šta je h? Dvije često korištene tehnike računanja niza indeksa za ispitivanje 1. Dvostruko raspršivanje (engl. double hashing) 2. Linearno ispitivanje (engl. linear probing) Dvostruko raspršivanje Smatra se jednom od najboljih metoda otvorenog adresiranja h(k, i) = (h1(k) + i h2(k)) mod m h1 i h2 su pomoćne funkcije raspršivanja Inicijalno ispitivanje ide na T[h1(k) mod m], a ostala su pomaknuta za h2(k) mod m Niz ispitivanja, dakle, na dva načina ovisi o ključu k Ako je faktor opterećenja 𝛼 = n / m < 1, broj ispitivanja kod neuspjelog pretraživanja je najviše 1/(1-𝛼) (pod uvjetom ravnomjernog raspoređivanja elemenata) Na primjer, ako je n = 5900, m = 7919, onda je 𝛼 = 0.75, pa je broj ispitivanja najviše 1/(1-0.75) ≤ 4 Dvostruko raspršivanje Primjer: Dodavanje elemenata dvostrukim raspršivanjem h(k, i) = (h1(k) + i h2(k)) mod m m = 13 h1(k) = k mod 13 h2(k) = 1 + (k mod 11) Neka je redoslijed dodavanja ključeva sljedeći: h(79, 0) = 1 h(69, 0) = 4 h(72, 0) = 7 h(98, 0) = 7; h(98, 1) = 5 h(14, 0) = 1; h(14, 1) = 5; h(14, 2) = 9 h(50, 0) = 11 Na isti način bi tražili ključ, npr. 14 Primjer dvostrukog raspršivanja Crvenom bojom označene su kolizije m = 13, n = 12 Ključevi: [482, 31, 62, 326, 399, 201, 434, 270, 376, 159, 456, 154] 482: i=0, h=1 376: i=0, h=12 31: i=0, h=5 159: i=0, h=3 62: i=0, h=10 456: i=0, h=1 326: i=0, h=1 456: i=1, h=7 326: i=1, h=9 154: i=0, h=11 399: i=0, h=9 154: i=1, h=12 399: i=1, h=0 154: i=2, h=0 154: i=3, h=1 201: i=0, h=6 154: i=4, h=2 434: i=0, h=5 Rezultat: [399, 482, 154, 159, 270, 31, 201, 456, 434: i=1, h=11 None, 326, 62, 434, 376] 270: i=0, h=10 270: i=1, h=4 Linearno ispitivanje h(k, i) = (h’(k) + i) mod m i = 0, 1, …, m-1 Za tablicu T dobili bi ispitivanja T[h’(k)], T[h’(k)+1], T[h’(k)+2], …, T, T, …, T[h’(k)-1] Problem linearnog ispitivanja je stvaranje klastera ili grupiranja elemenata, što utječe na vrijeme rješavanja kolizija h’(k) = k mod 11 Šta je dobra funkcija raspršivanja? Funkcija raspršivanja je ključna komponenta tablice raspršivanja jer o njoj ovise performanse TR Osnovna karakteristika dobre funkcije raspršivanja je koliko “ravnomjerno” raspoređuje ključeve u tablici Nezavisno ravnomjerno raspoređivanje: svaki ključ ima jednaku vjerojatnost da se smjesti na bilo koji od m indeksa, neovisno o tome gdje su smješteni drugi ključevi To u praksi ne možemo provjeriti Statičko i randomizirano raspršivanje Dva načina rješavanja kolizija: ulančavanje i otvoreno adresiranje (linearno ispitivanje i dvostruko raspršivanje) Dva načina izrade funkcije raspršivanja: statičko i randomizirano raspršivanje Statičko raspršivanje: koristimo ﬁksnu funkciju raspršivanja Dvije metode: metoda dijeljenja i metoda množenja Pretpostavljamo da je ključ kratki cijeli nenegativni broj Može se koristiti i kod linearnog ispitivanja i kod dvostrukog raspršivanja Statičko raspršivanje: Metoda dijeljenja Metoda dijeljenja: h(k) = k mod m Na primjer, ako je k = 84, a m = 17 onda je h(k) = 16 Ova metoda radi dobro kada je m prost broj koji nije previše blizu nekog broja s potencijom 2 Statičko raspršivanje: Metoda množenja Metoda množenja: h(k) = ⌊m (kA mod 1)⌋ Izdvojimo decimalni dio od kA, pomnožimo s m i izdvojimo decimalni dio i uzmemo pod rezultata Konstanta A je u rasponu 0 < A < 1 Ova metoda najbolje radi kada je m = 2t za neki cijeli broj t gdje je t ≤ w i w je broj bitova u jednoj riječi procesora (obično 32 ili 64 bita) Primjer metode množenja k=12345 m=16 A=0.6180339887 (preporučena vrijednost) k⋅A=12345⋅0.6180339887=7630.72656 Izdvoji decimalni dio: 0.72656 Pomnoži s veličinom tablice: 0.72656⋅16=11.625 Uzmi pod: h(k)=⌊11.625⌋=11 Ključ 12345 mapira se na indeks 11 Randomizirano raspršivanje U teoriji, netko tko zna kakva se funkcija raspršivanja koristi može to iskoristiti za maliciozne svrhe (odabrati takve ključeve da dobije što više kolizija) Ideja randomiziranog raspršivanja je da se funkcija raspršivanja odabere nasumično, iz nekog skupa takvih funkcija Dakle, na početku programa odaberemo jednu funkciju raspršivanja To osigurava da se kod svakog izvršavanja programa neće nužno koristiti ista funkcija, pa ni ključevi neće biti distribuirani na isti način Može se koristiti i kod linearnog ispitivanja i kod dvostrukog raspršivanja Tablica raspršivanja i stablo za bin. pretraživanje Jedna i druga struktura podataka podržavaju operacije pretraživanja, dodavanja i brisanja Tablica raspršivanja treba dobru funkciju raspršivanja (koja ima malo kolizija) da bi bila brza Brzina pristupa elementima tablice raspršivanja ovisio o funkciji raspršivanja i o popunjenosti tablice (funkcija raspršivanja može imati kolizije kada je tablica 75% popunjena, ali ne mora imati kolizije kada je tablica manje od 50% popunjena) S dobrom funkcijom raspršivanja i adekvatnom popunjenošću tablice pretraživanje tablica raspršivanja je blizu O(1) u prosjeku Elementi SBP moraju podržavati operacije < i =, a stablo treba biti balansirano SBP je O(lg n) u prosjeku ako je stablo balansirano, ali može biti i O(n) ako nije Implementacije u programskim jezicima Neki progrmamski jezici imaju u TR i SBP (kao dio jezika ili standardne biblioteke) C++ u standardnoj biblioteci ima map i unordered_map Implementacije u programskim jezicima 9. Grafovi Struktura podataka graf Koristi se u mnogim STEM granama kao računalne mreže, društvene mreže, kombinatorna optimizacija, operacijska istraživanja, teorijsko računarstvo, … - uglavnom svuda gdje su važni odnosi među podacima Također se koristi kao model podataka u graf-bazama podataka Ima veliku primjenu u računarstvu Ako neki problem postavimo kao graf onda pomoću graf-algoritama možemo doći do rješenja ili nekih novih spoznaja o tom problemu Graf Struktura podataka koja se sastoji od čvorova i lukova koji povezuju čvorove Čvorovi mogu biti i samostalni A B C D Primjer 1: najkraći put u grafu Primjer 2: poredak predmeta s uvjetima Ispišite sve predmete u redoslijedu (takvih redoslijeda može biti i više) po kojem studenti mogu upisati sve te predmete, ali tako da je za svaki predmet zadovoljen njegov preduvjet. Za predmet 1 nema preduvjeta. Predmet 1 preduvjet je za predmete 2, 3 i 4. Predmet 2 preduvjet je za predmete 4 i 5. Predmet 5 preduvjet je za predmete 4 i 7. Predmet 4 preduvjet je za predmete 3, 6 i 7. Predmeti 3 i 7 preduvjeti su za predmet 6. Primjer 3: povezani sudionici Neka u nekoj društvenoj mreži postoji povezana grupa sudionika. Zanima nas koliko od tih sudionika su povezani direktno ili indirektno tako da svaki sudionik može stupiti u kontakt sa svakim drugim sudionikom ili direktno ili indirektno preko jednog ili više međusudionika. Primjer 4: Graf baze podataka Teme 1. Pretraživanje grafa u širinu 2. Pretraživanje grafa u dubinu 3. Topologijsko sortiranje 4. Čvrsto povezane komponente Graf G = (V, E) V - skup čvorova (engl. vertices) E - skup lukova (engl. edges) Lûk je par (v, w) gdje su v, w Є V (ako je par uređen graf je usmjeren) ili {v, w} ako nije Neke vrste grafova su usmjereni/neusmjereni, ciklički/aciklički, težinski i dr. Prikaz neusmjerenog grafa Prikaz usmjerenog grafa Primjer grafa u Pythonu Upotreba rječnika graf = { 'b': ['e', 'c'], 'c': ['f', 'd'], 'd': ['a'], 'e': ['c'], 'f': ['g', 'd'], 'g': ['f'], 'h': ['g'], } Primjer traženja ciklus u grafu (Python) def ciklus(graf, polazni_cvor, trenutni_cvor, put): if polazni_cvor in put: return put else: if trenutni_cvor in graf: for cvor in graf[trenutni_cvor]: if cvor not in put: r = ciklus(graf, polazni_cvor, cvor, put + [cvor]) if r: return r return [] Algoritam za obilazak u širinu (BFS, Breadth-First Search) Osnova mnogih drugih algoritama kao što su minimum spanning tree (povezivanje svih čvorova tako da je “težina“ lukova minimalna), i Dijkstrin algoritam za najkraći put u grafu Ovaj algoritam polazi od jednog polaznog čvora i ispituje sve čvorove na udaljenosti 1 koji su s njim povezani… To onda ponavlja i za svaki taj čvor Ovaj algoritam radi na sličan način kao i obilazak stabla u širinu … ali on ujedno i bilježi najkraći put od polaznog čvora do svakog drugog čvora do kojeg može doći Generira i stablo pretraživanja u širinu koje sadrži sve dohvaćene čvorove Algoritam za obilazak u širinu Algoritam za obilazak u širinu BFS(G, S) za svaki čvor U u skupu čvorova V - {S} U.boja ← BIJELO U.udaljenost ← +BESKONACNO U.prethodnik ← NIL S.boja ← SIVO S.udaljenost ← 0 S.prethodnik ← NIL R ← prazan red # red kao struktura podataka dodaj(R, S) dok R nije prazan U ← izvadi(R) # prvi element u redu za svaki čvor V koji je susjed čvora U if V.boja = BIJELO V.boja ← SIVO V.udaljenost ← V.udaljenost + 1 V.prethodnik ← U dodaj(R, V) U.boja ← CRNO Algoritam za obilazak u dubinu (DFS, Depth-First Search) Slično kao obilazak stabla u dubinu Za svakog sljedbenika prvo ispitamo sve njegove sljedbenike Pretraživanje u dubinu generira jedno ili više stabala (DFS stablo) koja prikazuju redoslijed obilaska čvorova Ovaj algoritam može dati informacije o strukturi grafa, na primjer postoje li ciklusi To radi tako da klasiﬁcira lukove u sljedeće kategorije: * Lȗk stabla (engl. tree edge, T): Lȗk kojim se otkriva novi čvor * Povratni lȗk (engl. back edge, B): Lȗk koji neki čvor povezuje s njegovim prethodnikom u stablu pretraživanja u dubinu * Preskočni lȗk (engl. forward edge, F): Lȗk koji neki čvor povezuje s njegovim sljedbenikom u stablu pretraživanja u dubinu * Poprečni lȗk (engl. cross edge, C): Lȗk koji povezuje neki čvor s čvorom koji mu nije niti sljedbenik niti prethodnik Algoritam za obilazak u dubinu lȗk B: v je prethodnik od x lȗk C: y nije niti sljedbenik niti prethodnik od w u lȗk F: x nije otkriven DFS stablu iz u (zato nije T) p/z = početno vrijeme / završno vrijeme Algoritam za obilazak u dubinu DFS(G) za svaki čvor U grafa G U.boja ← BIJELO U.prethodnik ← NIL vrijeme ← 0 za svaki čvor U grafa G if U.boja = BIJELO DFS-PROLAZ(G, U) DFS-PROLAZ(G, U) vrijeme ← vrijeme + 1 U.d ← vrijeme // vrijeme otkrivanja U.boja ← SIVO za svaki susjedni čvor V čvora U if V.boja = BIJELO V.prethodnik ← U DFS-PROLAZ(G, V) U.boja ← CRNO vrijeme ← vrijeme + 1 U.f ← vrijeme // završno vrijeme Algoritam za obilazak u dubinu Stablo obilaska u dubinu 5 Vremenska složenost obilaska grafa Kao što je vremenska složenost pretraživanja niza ili stabla ovisila o broju elemenata, kod grafova ovisi o broju čvorova i lukova Ne mora svaki čvor imati isti broj ulaznih i izlaznih lukova Obilazak u širinu i dubinu ima vremensku složenost Θ(V+E) Topologijsko sortiranje Uređuje čvorove grafa tako da ako postoji lȗk (u, v) onda se u nalazi prije v u topologijski sortiranom poretku Deﬁnirano je samo za usmjerene acikličke grafove Često se upotrebljava kada skup aktivnosti treba urediti tako da prvo idu one o kojima ovise druge Rješava se upotrebom obilaženja u dubinu, ali ima i drugih načina Topologijsko sortiranje Algoritam: 11/14 12/13 1. pozovi DFS da se dobiju završna vremena za svaki čvor 2. nakon što je čvor završen dodaj ga na vrh povezane liste 7/8 6/9 3. vrati povezanu listu 1/10 v1 → v2 → v5 → v4 → v3 → v7 → v6 Vremenska složenost je Θ(V+E) 2/5 3/4 Topologijsko sortiranje - drugi način U svakom koraku uklonimo čvor koji nema ulazne lukove i taj čvor dodamo u rezultirajući niz {v1, v2, v3, v4, v5, v6, v7} - {v2, v3, v4, v5, v6, v7} = {v1} {v2, v3, v4, v5, v6, v7} - {v3, v4, v5, v6, v7} = {v2} {v3, v4, v5, v6, v7} - {v3, v4, v6, v7} = {v5} {v3, v4, v6, v7} - {v3, v6, v7} = {v4} {v3, v6, v7} - {v6} = {v3, v7} {v6} - {} = {v6} Rezultat: v1, v2, v5, v4, v3/v7, v6 Čvrsto povezane komponente grafa to je najveći skup čvorova C ⊆ V takav da je za svaki par čvorova u, v ∈ C, postoji put od čvora u do čvora v odnosi se na usmjerene grafove Čvrsto povezane komponente grafa Šta treba znati? Načini prikaza grafa Obilazak grafa (u dubinu i širinu, bez klasiﬁkacije lukova, ali s razumijevanjem početnog i završnog vremena) Topologijsko sortiranje Što su čvrsto povezane komponente (samo konceptualno, bez algoritma)

ASP Kolokvij 2 PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue