usmeni Flashcards
Što je algoritam? Primjer.
Algoritam je opis postupka koji, nakon konačnog broja radnji, daje suvisli rezultat.
Algoritam je i dio posla u procesu koji od uočenog problema dovodi do rezultata.
Slijed posla:
FIZIKALNA STVARNOST -> MATEMATICKI MODEL -> ALGORITAM -> STRUKT. PODATAKA ->
RACUNALNI PROGRAM
Svojstva:
1. Točnost
2. Konačnost
3. Učinkovitost
Primjer: Bubble Sort, Quick Sort, Algoritam komplementiranja binarnog broja,…
Koja je razlika između algoritma i programa?
Algoritam je niz uputa koje pomažu pri rješavanju problema i ne sadrži programske naredbe,
dok je program realizacija / implementacija algoritma u nekom programskom jeziku.
Znakovni tip podataka. Kako se prikazuje u memoriji, a kako na ekranu?
Znakovni tip podataka (char) se u memoriji prikazuje kao niz bitova.
Kombinacija od 8 bitova sadrži 256 znakova.
Za prikaz na ekranu niz bitova iz memorije se dekodira prema 7 bitnom ASCII (0-127) kodu,
za dijakritičke znakove koristi se code page.
Na 8 bitova se prikazuje prošireni ASCII s kodnom stranicom pojedinih država.
UNICODE je 16-bitni znakovni tip.
Cjelobrojni tip podataka. Vrste i raspon vrijednosti.
Cjelobrojni tip podataka (int) dijelimo po broju bita kojim ih prikazujemo u memoriji (8, 16,
32 ,64) i s obzirom na predznak (s predznakom i bez predznaka).
Rasponi:
1. slika
https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Pozicioni brojni sustav
Definirano: Baza B i znamenke di s vrijednostima [0,B-1]. Broj N zapisan u dek ima vrijednost:
N = SUMA(1 do n-1)(di*B(na i))
Negativni brojevi prikazuju se preko dualnog komplementa.
Cjelobrojni tip podataka. Kako se prikazuje u memoriji?
Prikazuje se nizom od: 8 (short int), 16 (int), 32 (long int) ili 64 (long long int) bitova.
Ako je broj s predznakom, predznak zauzima prvi bit.
Opisati dvostruki (binarni) komplement.
Dvostruki (binarni) komplement je broj kojemu je promijenjen predznak.
Komplementiranje se vrši invertiranjem svih bitova u broju i aritmetičkim dodavanjem bita
„1“
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Realni tip podataka. Kako se prikazuje u memoriji?
Realni tip podataka se u memoriji prikazuje nizom od 32, 64 ili 80 bita.
Zapis se sastoji od predznaka, karakteristike (eksponenta) i mantise.
P(1) + K(7) + M(24) - 32-bitni broj
Realni tip podataka. Greške pomičnog zareza, zbog čega? Primjer.
Do greške pomičnog zareza dolazi ukoliko broj nije prikaziv, odnosno nije ga moguće
pohraniti u određeni broj bita (32,64, 80) pa se ga je potrebno zaokružiti.
Na primjer: Računanje vrijednosti broja π Ludolfovom metodom.
Primjer: zbrajanje velikih i malih brojeva
AKo je razlika brojeva dovoljno velika, zbrajanje će uvijek dati rezultat jednak većem broju, zbog zaokruživanja.
Množenje velikih i malih brojeva funkcionira bez problema.
Nizovi (jednodimenzionalna polja) kao struktura podataka. Svojstva?
Niz je linearna struktura koja se sastoji od 2 ili više podataka istog tipa.
Zahtjeva neprekinuti niz memorije.
Prvi element niza ima indeks „0“ , a zadnji „n-1“ (n-veličina niza).
Podaci unutar niza mogu biti bilo kojeg tipa, uključujući i još jedan niz.
Alociraju se statički i dinamički. Moguć izravan pristup svakom elementu.
Konačan broj el. N. Direktan pristup svakome (O(1)), el. slijede jedan iza drugoga.
Algoritam SEKVENCIJALNO PRETRAŽIVANJE niza. Složenost?
Sekvencijalno pretraživanje je najsporiji način pretraživanja.
Niz se pretražuje element po element.
Složenost O(n) - linearna.
Predani niz ne mora biti prethodno sortiran.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam BINARNO PRETRAŽIVANJE niza. Složenost?
Binarno se pretraživati može samo već prethodno sortirani niz.
Pretraživanje se vrši dijeljenjem niza na pola. Ukoliko je traženi broj veći od broja u sredini,
zanemaruju se svi brojevi manji od srednjeg (obrnuto ukoliko je traženi broj manji) i
„novonastali“ niz se ponovno dijeli na pola sve dok se ne pronađe traženi broj.
Složenost je O(log n).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Usporedba algoritama sekvencijalnog i binarnog pretraživanja niza.
Algoritam binarnog pretraživanja je efikasniji jer ima manju složenost, ali niz koji se
pretražuje mora biti prethodno sortiran što nije slučaj za sekvencijalno pretraživanje
Algoritam SELEKT-SORT. Složenost?
Algoritam selekt-sort pretražuje cijeli niz tražeći najmanji element i zatim ga prebacuje na
prvo mjesto u nizu.
Nakon toga ponovno pretražuje cijeli niz i traži drugi najmanji broj i prebacuje ga na drugo
mjesto i tako sve dok niz nije sortiran.
Složenost O(n2).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Matrice (dvodimenzionalna polja) kao struktura podataka. Svojstva?
Matrice su linearne strukture podataka raspoređenih po stupcima i redcima.
Pravokutna shema podataka; svi el. istog tipa; direktan pristup svakom.
To su zapravo polja čiji elementi su druga polja.
Indeksi mjesta se zapisuju u obliku [n][m], gdje je n- indeks retka, a m-indeks stupca.
Indeksi kao i kod niza kreću od 0.
Primjer algoritma s matricom. Složenost?
Algoritam množenja matrica. Složenost O(mnk). m-broj redaka prve matrice, n- broj stupaca
prve matrice i broj redaka druge, k-broj stupaca druge matrice.
Problem magičnog kvadrata – O(m^2) – formiranje kvadratnu matricu m x m (m je neparan)
takva da su sume svih redaka, stupaca, dijagonala jednake
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam MNOŽENJE KVADRATNIH MATRICA. Složenost?
Množenje matrica se vrši tako da se elementi prvog retka prve matrice množe sa elementima
prvog stupca druge matrice. Rezultati množenja se zbroje i dobije se element u prvom retku,
prvom stupcu. Za element u prvom retku, drugom stupcu treba množiti elemente prvog
retka sa elementima drugog stupca itd.. Složenost algoritma je O(mnk) jer sve matrice imaju jednak broj redaka i stupaca.(n and n)
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Statičko i dinamičko alociranje memorije. Objasniti na primjeru niza.
Niz se može alocirati statički i dinamički. Pri statičkom alociranju maksimalna veličina niza
mora biti poznata kako bi se pronašlo prikladno mjesto u memoriji.
Niz se sprema na stog (Stack).
Mjesto u memoriji će ostati zauzeto sve dok ne izađe iz dosega.
Pri dinamičkoj alokaciji nije potrebno znati maksimalnu veličinu niza. Za razliku od statičke
alokacije, niz se sprema u hrpu (Heap). Dinamička alokacija također nudi mogućnost
oslobađanja memorije tokom izvođenja programa.
Dinamički se alocira naredbama malloc i new.
Memorijska adresa kao tip podataka.
Memorijska adresa je pokazivač koji može imati vrijednost od prve adrese (0) do najveće
vrijednosti zadnje lokacije u memoriji.
To je nenegativni cijeli broj bez predznaka zapisan u heksadekadskom sustavu.
Pokazivačima pridjeljujemo memorijsku adresu varijable.
Povezani popis kao struktura podataka.
Povezani popis je linearna dinamička struktura podataka
Elementi popisa se stavljaju u slobodan dio memorije i međusobno su povezani pokazivačima
koji pokazuju na adresu sljedećeg elementa.
Sastoji se od 2 osnovna dijela, podatkovnog i pokazivačkog.
Točkicom ili ‘->’ se pristupa elementima odnosno pojedinim članovima čvora.
Varijabla ‘prvi’, ‘root’ predstavlja početak povezane liste te prvi=NULL znači da je povezana
lista prazna.
Algoritam KREIRANJE POVEZANOG POPISA
Prilikom kreiranja povezanog popisa potrebno je definirati strukturu koja sadrži vrijednost
elementa i pokazivač na sljedeći element. Možemo dodavati svaki novi podatak na kraj
popisa, a možemo novog dodavati i na početak povezanog popisa.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam OBILAZAK POVEZANOG POPISA.
Za primjer ovog algoritma potrebno je ispisati sve elemente povezanog popisa. Za ovaj
algoritam koristi se pomoćni pokazivač trenutni koji pokazuje na adresu trenutnog elementa.
Na početku algoritma trenutni se postavlja na prvi član povezanog popisa. Nakon toga se
ispisuje vrijednost elementa povezanog popisa koji se nalazi na lokaciji na koju pokazuje
trenutni. Trenutnom se zatim pridružuje memorijska adresa sljedećeg elementa. Taj proces
se ponavlja sve dok trenutni nije jednak NULL, odnosno nema sljedećeg elementa.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Usporedba niza i povezanog popisa. Prednosti i mane.
Niz se može alocirati statički i dinamički, dok se povezani popis može alocirati samo
dinamički. Prednosti povezanog popisa su: trenutno dodavanje i brisanje elemenata u
povezani popis i mogućnost potpunog iskorištenja memorije. Pristup elementima popisa nije
trenutan kao kod niza, već se mora pristupati element po element. To je jedina mana
povezanog popisa u usporedbi s nizom.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam INSERT SORT. Složenost?
Algoritmom insert sort se već pri dodavanju elemenata sortirani popis. Koristimo pokazivače
na osnovni element N, P i T.
N – koristimo za novi osnovni element koji kreiramo na dinamički način;
P – koristimo kao adresu prethodnog zapisa kada pretražujemo povezani popis;
T – koristimo kao trenutačnu adresu prilikom istog pretraživanja. Složenost O(n2).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Stog. Definicija, princip rada.
Stog je linearna struktura kojoj je princip rada LIFO (Last in first out).
Određen je s četiri funkcije: POP, PUSH(x), IS_EMPTY i CLEAR. Sve su atomske O(1)
Stog. Pomoću kojih struktura ga ostvarujemo?
Može se izvesti pomoću niza (niz V od N elemenata i dodatni podatak Sp (Stack pointer) -
cijeli broj koji pokazuje na zadnji element u stogu; prazan ako Sp=0, pun ako Sp=N) ili
povezanog popisa (dovoljan je jedan povezani popis, ali vrh stoga mora biti na početku
povezanog popisa radi efikasnost).
Stog. Izvedba push i pop procedura kada je stog ostvaren pomoću niza.
Prvi korak procedure PUSH je provjera je li stog pun. Ukoliko je stog pun, treba prekinuti
proceduru uz poruku :“ Stack overflow…“ . Ako ima mjesta u stogu pomičemo se iza zadnjeg
elementa i prirodajemo novi.
Prilikom izvođenja procedure POP potrebno je provjeriti je li stog prazan. Ukoliko je
prekinuti proceduru uz poruku: „Illegal POP…“ . Ako stog nije prazan, ispisujemo trenutni
element i pomičemo se jedno mjesto ispred. Kretanje po stogu i provjere se obavljaju
pomoću indeksa niza i pri proceduri POP elementi se ne brišu već se zanemaruju i izmjenjuju.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Stog. Izvedba push i pop procedura kada je stog ostvaren pomoću povezanog popisa.
Dovoljna je 1 lista. Vrh stoga mora biti na pocetku povezane liste ako se zeli biti efikasan. Sve funkcije su atomske osim Clear, koja moze biti O(n)
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Stog. Primjer algoritma.
Problem putne torbe. Naći bilo koji podskup Torba skupa Tezine tako da zbroj elemenata u
Torba bude jednak T. Ako takvog podskupa nema, ispisati odgovarajuću poruku.
Eksponencijalna složenost.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Problem QuickSort – uzeti neki element(pivot) u nizu i naći mu konačno mjesto; tako da svi
lijevo od njega budu manji a desno veći (ili jednaki). O(N) je ta procedura (Nadji_s može imati
gg-dg ponavljanja). Algoritam ide od N*logN (slucaj polovljenja) do N^2.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Red. Definicija, princip rada.
Red je linearna struktura kojoj je princip rada FIFO (First In First Out).
Određen je s četiri funkcije: POP/DEQUEUE, PUSH/ENQUEUE, IS_EMPTY, CLEAR.
Red. Pomoću kojih ga struktura možemo ostvariti?
Red možemo ostvariti pomoću niza(niz V od N elemenata te su potrebna i dva dodatna
podatka Ulaz i Izlaz -to su dva cijela broja koji pokazuju na početak i kraj reda) ili povezanog
popisa (mora imati pokazivač na prvi i zadnji).
Red preko niza može biti konačan i ciklički. Kod cikličkog je potrebna i varijabla Zadnji_push
kojom se prati je li red prazan ili pun.
Ulaz=Izlaz-1 i Zadnji_push znaci da je red pun.
Ulaz=Izlaz-1 i Zadnj_push=FALSE znaci da je red prazan (odnosno zadnji je bio pop).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Red. Izvedba push i pop procedura.
Za red izveden pomoću niza nije samo dovoljan niz od N elemenata nego i dva dodatna
podatka ULAZ i IZLAZ. To su dva cijela broja koja pokazuju na početak i kraj reda. Procedura
Push (Enqueue) prvo provjerava je li red pun. Ukoliko je ulaz = izlaz i logička varijabla
zadnji_push = true, onda je red pun te se izvođenje prekida. Zadnji_push-provjerava je li
zadnja promjena bila POP ili PUSH. Ukoliko red nije pun zadnji push se postavlja na true,
indeks niza se povećava za mod(ulaz+1,N) kako bi se postigao ciklički niz i zatim se na taj
indeks sprema novi element.
Procedura POP prvo provjerava je li red prazan, procedurom Is_Empty. Ukoliko nije
zadnji_push se postavlja na false. Ispisuje se element na trenutnom indeksu niza i zatim se
indeks smanjuje za mod(izlaz+1,N). potrebne su izmjene dolje zbog Ulaz=Izlaz
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Red. Primjer algoritma.
Algoritam Putne torbe se također može koristiti i s redom. Još jedan primjer je Quick Sort.
Rekurzivne funkcije. Definicije.
Rekurzivna funkcija ili procedura – ona koja poziva samu sebe unutar svojih naredbi barem
jednom (može i više puta).
Općenito rekurzivna procedura ima oblik:
Ako je rješenje trivijalno vratiti to rješenje
U suprotnom obaviti rekurzivni poziv
Primjer jednostavne rekurzivne funkcije.
Funkcija za računanje faktorijela.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Veza između rekurzivnih funkcija i stoga.
Svaki algoritam koji je moguće napisati kao rekurzivnu funkciju ili proceduru, moguće ga je
napisati bez korištenja rekurzije, ali upotrebom stoga.
Algoritam POVRH koristeći rekurziju. b=0, a=1
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam QUICK SORT
Prvo odabiremo element iz niza koji će nam biti pivot (vodeći) i on se nalazi u sredini. Svi
elementi manji od njega se prebacuju s njegove lijeve strane, a svi veći s desne. Nakon toga
se postupak ponavlja za lijevi i desni niz i tako sve dok se ne dođe do niza veličine 1. Može se
izvesti kao rekurzija, a i ne mora. Složenost O( n*log n).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam MERGE SORT
Niz koji sortiramo se dijeli na pola i nastaju dva nova niza. Zatim se ta dva nova niza dijele na
pola i od svakog nastaju nova dva i tako sve dok više nije moguće dijeliti niz na pola, odnosno
kada svaki element čini 1 niz. Nakon toga se uspoređuju prvi i drugi niz, treći i četvrti itd. i
spajaju. Proces se ponavlja sve dok se svi nizovi ne spoje nazad u jedan. Složenost O(n*log n).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Stablo kao struktura podataka. Definicija.
Stablo je nelinearna (hijerarhijska) struktura koja se sastoji od čvorova i grana. Svi čvorovi
imaju svoj podređeni i nadređeni. Jedino korijenski čvor nema svoj nadređeni čvor. Stablo
može biti OPĆE – proizvoljan broj podređenih čvorova. Opća stabla mogu biti uređena i
neuređena (redoslijed podređenih čvorova bitan/nebitan). Osim općeg stablo može biti i
binarno.
struct cvor{
int x;
struct cvor *left;
struct cvor *right;
};
struct cvor *korijen = NULL;
Binarno stablo kao struktura podataka. Definicija.
Binarno stablo je stablo kod kojeg svaki čvor može imati najviše dva nasljednika, lijevi i desni.
Svaka razina ima ograničeni, maksimalni broj čvorova, tako i-ta razina može imati najviše 2^i
čvorova
Ukupno može biti 2^n-1 čvorova ako je n ukupan broj razina (uključujući i 0-tu).
Svaki čvor ima 1 nadređeni, osim korijenskog koji nema nadređenih čvorova
Binarno stablo. Prikaz u računalu.
Binarno stablo se u računalu može prikazati pomoću matrice s 3 stupca ili na dinamički način
uz pomoć pokazivača. Nijedan način ne nudi izravan pristup elementu.
Kod matrice u prvi red se stavlja korijenski čvor. Drugi stupac nalazi se broj retka gdje je lijevi
nasljednik, a treći stupac broj retka gdje je desni nasljednik.
Binarno stablo. Algoritmi obilaska. Primjer jednog od njih.
Algoritmi obilaska su: Preorder (NLD), Inorder(LND) i Postorder( LDN).
To je sve po dubini.
Po širini ide s redom. Obilazak se može vršiti pomoću stoga ili rekurzivne funkcije.
Funkcije su linearne, tj. ovise o broju čvorova - složenost je O(n).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Poredano binarno stablo, definicija
Poredano binarno stablo je stablo kojemu su čvorovi označeni usporedivim oznaka i to tako
da su tako da su svi lijevi nasljednici čvorovi s manjom vrijednosti, a s desne strane s većom.
L<N<D : lijevo podstablo, nadređeni čvor, desno podstablo
Ovakvo stablo omogućuje efikasno pretraživanje, dodavanje i brisanje čvorova
Poredano binarno stablo, algoritam DODAJ P
Algoritam DODAJ P dodaje novi čvor ukoliko taj čvor već ne postoji u stablu. Prvo se poziva
funkcija NADJI P koja pretražuje stablo. Ukoliko čvor nije pronađen, funkcija NADJI P će nam
vratiti pokazivač na zadnji element u stablu te je samo potrebno provjeriti je li vrijednost
čvora manja ili veća od vrijednosti zadnjeg elementa. Dodavanje se obavlja trenutno O(1), ali
se unutar procedure poziva i procedura NADJI P čija složenost ovisi o izbalansiranosti stabla.
Njena složenost u najgorem slučaju može biti O(n). Složenost ide od O(logN) do O(N).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Poredano binarno stablo, algoritam NADJI P
Varijabli cvor pridružujemo vrijednost korijenskog čvora, varijabla nadjen=0 i varijabla
nadredjeni = NULL. Ukoliko je vrijednost čvora spremljenog u varijablu cvor jednaka
vrijednosti koju tražimo postavljamo nadjen=1 i prekidamo izvođenje. Ukoliko nije u varijablu
nadredjeni spremamo trenutni čvor i provjeravamo je li tražena vrijednost manja ili veća od
vrijednosti trenutnog čvora. Ukoliko je manja, u varijablu cvor spremamo čvor koji se nalazi
lijevo od trenutnog, ukoliko on postoji, ukoliko ne postoji varijabla nadjen= -1 i procedura se
prekida. Ako je tražena vrijednost veća u varijablu cvor spremamo čvor desno od trenutnog,
ukoliko postoji. Ako ne postoji nadjen = -1 i procedura se prekida. Nakon toga se procedura
ponavlja sve dok varijabla nadjen ne poprimi vrijednost 1 ili -1. Složenost ovisi o
izbalansiranosti stabla, u najgorem slučaju O(n).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Poredano binarno stablo, algoritmi i njihova složenost
Algoritmi vezani uz poredano binarno stablo su: NADJI P- Složenost O(n), Dodaj P- Složenost
same procedure je O(1), ali budući da se poziva procedura NADJI P, O(n), BRIŠI P- Složenost
također poziva proceduru NADJI P pa je složenost O(n). U praktičnoj primjeni stablo treba biti
izbalansirano pa složenost sva 3 algoritma možemo gledati kao O(log n).
Prošireno binarno stablo, definicija i primjer
Prošireno binarno stablo je stablo u kojem svaki čvor ima dva ili nijedan podređeni čvor.
Čvorovi bez nasljednika se nazivaju vanjski, a čvorovi s nasljednicima, unutarnji.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Prošireno binarno stablo, težinski put za cijelo stablo
Dužina puta li do vanjskog čvora i definirana je brojem grana koje
treba proći od korjena do vanjskog čvora. Težinski put do čvora i tj. wi definiran je umnoškom:
li * wi.
//wi-vrijednost čvora, li-redni broj grane.
Huffmanovo stablo i algoritam generiranja takvog stabla
Huffmanovo stablo je prošireno binarno stablo s najmanjim mogućim težinskim putem.
Huffmanovo stablo se generira Huffmanovim Algoritmom.
Huffmanovo kodiranje
Huffmanov kod dobiva se tako, da se grane koje idu k lijevim nasljednicima označe s 0, a
grane prema desnim nasljednicima s 1. Koristi se pri kodiranju poruka. Huffmanovo kodiranje
spada u statičke metode sažimanja podataka, gdje se informacije kodiraju nizovima bitova
različitih duljina u skladu s frekvencijom odnosno vjerojatnošću njihova pojavljivanja.
Potpuno binarno stablo, definicija i primjer
Potpuno binarno stablo je ono stablo u kojem su sve razine popunjene, jedino zadnja razina
ne mora biti popunjena. Razine se popunjavaju s lijeva na desno.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Potpuno binarno stablo, efikasni prikaz u računalu
PBS se jednostavno prikazuje nizom V od N elemenata. Niz se popunjava kao kad bi PBS
obilazili po razinama.
Za svaki redni broj i čvorova u poredanom stablu vrijede ova svojstva:
1. Lijevi nasljednik ima parni i, a desni ima neparni i
2. Korijenski čvor ima i = 1
3. Nadređeni i-tom čvoru ima redni broj |i / 2|
4. Lijevi nasljednik i-tog čvora ima redni broj 2 · i
5. Desni nasljednik i-tog čvora ima redni broj 2 · i +1
Hrpa. Definicija, primjer.
Hrpa je potpuno binarno stablo za koje dodatno vrijedi da je vrijednost svakog čvora manja ili
jednaka vrijednosti njemu nadređenog čvora (vrijedi za sve osim za korijen). Još se naziva i
Max-Hrpa. Postoji i Min-Hrpa za koju vrijedi obrnuto.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Hrpa. Algoritam NAPRAVI HRPU. Složenost.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Algoritam HEAP SORT. Složenost.
Pozovi algoritam NAPRAVI HRPU
zadnji = NH
Za svaki i = zadnji unazad do 2 činiti
Zamjeni( V1, Vi)
NH = NH -1
UHRPI( 1 )
Složenost: O( NH log NH )
Hrpa. Dodavanje čvorova u hrpu
Hrpa sa NH čvorova prikazana nizom V od N čvorova
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Hrpa. Brisanje čvorova iz hrpe
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Graf. Definicija, primjer.
Graf G( V, E ) se sastoji od:
* Skupa čvorova (ili vrhova; engl. Nodes, vertices) V(G)
* Skupa grana (bridova; engl; branches, edges) E(G)
Ako se skup E(G) sastoji od neuređenih parova e{u, v} (u i v su čvorovi iz V(G)) onda kažemo
da se radi o neusmjerenom grafu. Ako se radi o uređenim parovima e(u, v) onda govorimo o
usmjerenom grafu. Grana e s istim krajnjim tockama naziva se petlja. Stupanj deg(u) odreden
je brojem grana pridruzenih cvoru. Ako je deg(u)=0 govorimo o izoliranom cvoru.
Kod usmjerenih grafova postoje grane koje ulaze i izlaze: deg(u)=indeg(u)+outdeg(u)
Put duzine P(v0,v1,v2…vn) za koji vrijedi da su vi i vi+1 susjedi i ako je v0=vn takav put se
naziva ciklus. Ciklicki grafovi su oni koji imaju barem jedan ciklus.
Ako izmedu svaka dva cvora grafa G postoji put, takav graf naziva se POVEZANI.
Postoje i planarni i neplanarni grafovi. Planarni su takvi da se nijedan njegov brid ne sijece.
Primjer neusmjerenog grafa:
30. i 31. slika:
https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Prikaz grafa u računalu pomoću matrice, primjer.
Statički način, direktan pristup svakom čvoru i grani
Matrica susjedstva ima redaka i stupaca onoliko koliko graf ima čvorova. Ako je N = |V(G)|,
onda je SN×N matrica.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Prikaz grafa u računalu pomoću niza povezanih lista, primjer.
Za svaki čvor postoji povezani popis u kojem su elementi ostali čvorovi s kojima je on susjed.
Znači postoji N = |V(G)| povezanih popisa, za svaki čvor po jedan
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Graf. Algoritam OBILAZAK PO ŠIRINI
Zadano: Graf G(V, E) s N = |V(G)| čvorova i M = |E(G)| grana, pc – početni čvor iz kojeg
krećemo obilazak
OBA ALG IMAJU SLOZENOST O(M+N) osim ako se radi pomocu matrica tezina, onda je
O(N^2)
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Graf. Algoritam OBILAZAK PO DUBINI
Zadano: Graf G(V, E) s N = |V(G)| čvorova i M = |E(G)| grana, pc – početni čvor iz kojeg
krećemo obilazak
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Problem najkraćih puteva kod grafova. Definicija.
Iz jednog čvora ( SSSP – single source shortest paths)
Iz svih čvorova ( APSP – all-pairs shortest paths)
Postoji usmjereni graf i težinska funkcija w koja svakom bridu pridružuje realni broj koji
nazivamo težina. Tražimo najkraći put s obzirom na težine. Težina može biti negativna, ali
ciklus ne smije!
Graf koji ima težinsku funkciju pridijeljenu bridovima. Prikaz u računalu.
Težinska funkcija može se prikazati na računalu matricom težina W u kojoj je wi,j težina grane
od i-tog do j-tog čvora.
- slika:
https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Bellman-Fordov algoritam.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Interpretacija rezultata dobivenih Bellman-Fordovim algoritmom.
Vremenska složenost ovisi o broju grana i čvorova, N i M
Složenost algoritma je O(N3)
Ograničenja i složenost Dijkstrinog algoritma za problem najkraćih puteva.
Ograničenje jest da udaljenosti na granama moraju biti pozitivne. Vremenska složenost
algoritma je O( N 2).
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Warshalov algoritam najkraćih puteva. Složenost.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Mreža. Definicija i primjer.
Poseban oblik grafa kod kojeg postoje dva posebna vrha s i t, takav da je s je izvor (source)
te nema ulaznih bridova, samo izlazne, a t je ponor (sink) te nema izlaznih bridova, samo
ulazne. Skup bridova ima i dodijeljenu funkciju kapaciteta. Tok je realna fja koja mora
zadovoljavati 3 svojstva: svojstvo simetrije, svojstvo kapaciteta i svojstvo odrzanja.
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
Definicija problema maksimalnog protoka.
Najprije je potrebno naći put od s do t. Nakon toga uvećati tok duž tog puta za najviše što se
može, a to je ograničeno s najmanjim kapacitetom na tom putu.
Algoritmi koji postoje kao rješenje problema maksimalnog protoka.
Tri su algoritma, Ford-Fulkersonov, Edmond-Karpov algoritam i Goldberg-Tarjanov
algoritam(push-relabel). Ford-Fulkersonov algoritam nije strogo polinomijalan, već ovisi o
vrijednosti ukupnog maksimalnog toka. Preciznije, vremenska složenost je O( M · fmax ).
Edmond-Karpov algoritam je strogo polinomijalni algoritam za problem maksimalnog
protoka. Ovaj algoritam je izveden iz Ford-Fulkersonovog tako da se prilikom traženja puta
od s do t uvijek traži najkraći put s obzirom na broj bridova. Vremenska složenost tada iznosi
O(N ·M 2).
Najefikasniji algoritam za problem maksimalnog toka je tzv. PUSH-RELABEL
algoritam. Algoritam u svakom svom koraku ne zadovoljava svojstva simetrije i održanja toka,
ali pamti koliki su ‘preljevi’ toka u svakom čvoru i na kraju se ipak dobiva ostvarivo i točno
rješenje. Ovaj algoritam u svojoj osnovnoj izvedbi ima složenost O(N 2 ·M). Međutim, u svojoj
posebnoj izvedbi RELABEL-TO-FRONT postiže najbolju asimptotsko vrijeme za problem
maksimalnog toka koje iznosi O(N 3)
- slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
