Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Algoritmi i strukture podataka > usmeni > Flashcards

usmeni Flashcards

1
Q

Što je algoritam? Primjer.

A

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,…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Koja je razlika između algoritma i programa?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Znakovni tip podataka. Kako se prikazuje u memoriji, a kako na ekranu?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Cjelobrojni tip podataka. Vrste i raspon vrijednosti.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Cjelobrojni tip podataka. Kako se prikazuje u memoriji?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Opisati dvostruki (binarni) komplement.

A

Dvostruki (binarni) komplement je broj kojemu je promijenjen predznak.
Komplementiranje se vrši invertiranjem svih bitova u broju i aritmetičkim dodavanjem bita
„1“

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Realni tip podataka. Kako se prikazuje u memoriji?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Realni tip podataka. Greške pomičnog zareza, zbog čega? Primjer.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Nizovi (jednodimenzionalna polja) kao struktura podataka. Svojstva?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Algoritam SEKVENCIJALNO PRETRAŽIVANJE niza. Složenost?

A

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.

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Algoritam BINARNO PRETRAŽIVANJE niza. Složenost?

A

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).

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Usporedba algoritama sekvencijalnog i binarnog pretraživanja niza.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Algoritam SELEKT-SORT. Složenost?

A

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).

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Matrice (dvodimenzionalna polja) kao struktura podataka. Svojstva?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Primjer algoritma s matricom. Složenost?

A

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

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Algoritam MNOŽENJE KVADRATNIH MATRICA. Složenost?

A

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)

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Statičko i dinamičko alociranje memorije. Objasniti na primjeru niza.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Memorijska adresa kao tip podataka.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Povezani popis kao struktura podataka.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Algoritam KREIRANJE POVEZANOG POPISA

A

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.

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Algoritam OBILAZAK POVEZANOG POPISA.

A

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.

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Usporedba niza i povezanog popisa. Prednosti i mane.

A

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.

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Algoritam INSERT SORT. Složenost?

A

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).

  1. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Stog. Definicija, princip rada.

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
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).
26
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. 11. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
27
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) 12. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
28
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. 13. 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. 14. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
29
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.
30
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). 15. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
31
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* 16. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
32
Red. Primjer algoritma.
Algoritam Putne torbe se također može koristiti i s redom. Još jedan primjer je Quick Sort.
33
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
34
Primjer jednostavne rekurzivne funkcije.
Funkcija za računanje faktorijela. 17. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
35
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.
36
Algoritam POVRH koristeći rekurziju. b=0, a=1
18. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
37
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). 19. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
38
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). 20. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
39
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;
40
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
41
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.
42
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). 21. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
43
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
44
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). 22. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
45
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). 23. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
46
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).
47
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. 24. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
48
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.
49
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.
50
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.
51
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. 25. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
52
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
53
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. 26. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
54
Hrpa. Algoritam NAPRAVI HRPU. Složenost.
27. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
55
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 )
56
Hrpa. Dodavanje čvorova u hrpu
Hrpa sa NH čvorova prikazana nizom V od N čvorova 28. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
57
Hrpa. Brisanje čvorova iz hrpe
29. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
58
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
59
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. 32. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
60
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 33. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
61
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)* 34. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
62
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 35. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
63
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!
64
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. 36. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
65
Bellman-Fordov algoritam.
37. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
66
Interpretacija rezultata dobivenih Bellman-Fordovim algoritmom.
Vremenska složenost ovisi o broju grana i čvorova, N i M Složenost algoritma je O(N3)
67
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). 38. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
68
Warshalov algoritam najkraćih puteva. Složenost.
39. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
69
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. 40. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe
70
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.
71
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) 41. slika: https://drive.google.com/drive/folders/1TfhzcY68ZFxln6kgz1bQ7-2HcqBiebDe

Algoritmi i strukture podataka (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions