IT - Strukture podataka i algoritmi

Strategije programiranja. Rekurzija. Osnove složenosti algoritama. Pretraživanje: sekvencijalno, binarno, stabla. Sortiranje: bubble, selection, insertion, shell, quick, heap. Strukture podataka: niz, vezana lista, stablo, hash tablica. Uređeni i neuređeni kontejneri: stog, red, lista skup, mapa, prioritetni red, graf. Dinamički algoritmi: Fibonnacijev niz, optimalno binarno stablo, množenje niza matrica. Grafovi: minimalno stablo, Dijkstrov algoritam. Rješavanje težih problema: "Problem trgovačkog putnika", "Problem kineskog poštara".

Kolegij pruža temeljna znanja o uporabi i svojstvima često korištenih struktura podataka, o izvedbi poznatijih algoritama, analizi vremena izvedbe i efikasnosti algoritama, te implementaciji zadanih algoritama.

1. Razumijeti i znati opisati značenje složenosti algoritama. Pronaći složenost jednostavnijih algoritama.
2. Razumijeti koncept apstraktnog tipa podataka i njegovu primjenu u razvoju softvera. Razumijeti osnovne strukture podataka. Razumjeti metode implementacije apstraktnih tipova podataka pomoću struktura podataka.
3. Poznavati osnovne ATP-ove i razlike u njihovom ponašanju, načinu primjene i performansama u raznim scenarijima.
4. Razumijeti algoritme obrađene u kolegiju, znati opisati algoritme, ali i tijek izvršavanja tih algoritama na konkretnim podacima.
5. Znati samostalno odabrati i koristiti algoritme, strukture podataka i apstraktne tipove podataka u danim uvjetima i obzirom na praktične zahtjeve na softver koji se razvija.

Kolegij pruža specijalistička znanja s područja programiranja kao nadogradnju jezgre računarstva, te obučava polaznika za efikasnu uporabu složenih struktura podataka i algoritama obrade

1. Cormen, Thomas H: "Introduction to Algorithms", 2nd edition, McGraw-Hill, New York 2001.
2. Knuth, Donald E: "The Art of Computer Programming, Vol. 1, 3" Addison-Wesley, 1997

1. Aho, Alfred V; Hopcroft, John E: "Data structures and algorithms", Addison-Wesley, Massachusetts 1983.
2. Manber, Udi: Introduction To Algorithms - A Creative Approach, Addison-Wesley, 1989.

1. 1. Uvod i motivacija za kolegij 2. Rekurzija 3. Standardne funkcije za pretraživanje i sortiranje (bsearch, qsort)
2. 1. Definicija algoritma, zahtjevi za algoritam, analiza algoritma 2. O-notacija, gornja i donja ograda 3. Mjerenje složenosti (zadaća, ulaz)
3. 1. Sortiranje (uvod) 2. Sortiranje izmjenjivanjem (Bubble) 3. Sortiranje odabiranjem (Selection) 4. Sortiranje ubacivanjem (Insertion i Shell) 5. Sortiranje izmjenjivanjem (Quick) 6. Usporedba algoritama sortiranja i zaključak
4. 1. Dugi integeri (definicija, zbrajanje, oduzimanje, množenje) 2. Divide and conquer princip 3. Divide and conquer primjeri 3.1. min/max 3.2. k-ti element 3.3. Karatsubino množenje 4. Divide and conquer (složenost, zaključak) 5. Dinamičko programiranje (definicija, top/down, bottom/up) 5.1. 0-1 Knapsack 5.2. Chain multiplication 6. Backtracking
5. 1. Struktura vezane liste 2. Apstraktni tip podataka 3. Sučelje 4. ATP u C-u 5. ATP Stog 5.1. Sučelje 5.2. Implementacije (niz, vezana lista) 6. ATP Red 6.1. Sučelje 6.2. Implementacije (niz, vezana lista)
6. 1. Iteratori 2. ATP Lista 2.1. Sučelje 2.2. Implementacije (niz, vezana lista)
7. 1. ATP Set 1.1. Sučelje 1.2. Implementacije (niz, sortirana vezana lista, bit-vektor, hash tablica)
8. PRVI KOLOKVIJ
9. 1. Stabla 1.1. Definicije 1.2. Reprezentacija 1.3. Obilasci 2. Binarna stabla pretraživanja 2.1. Algoritmi 2.2. Složenost
10. 1. Hash tablica 1.1. Vrste 1.2. Obrade sudara 1.3. Re-hashing 2. ATP Map 2.1. Sučelje 2.2. Implementacije (stablo, hash tablica)
11. 1. Struktura hrpe (heap) 2. ATP Prioritetni red 2.1. Sučelje 2.2. Implementacije (hrpa)
12. 1. Grafovi 1.1. Definicije 1.2. Primjene 1.3. Nastanak teorije grafova 1.4. Reprezentacija
13. 1. ATP Graph 2. Grafovi (nastavak) 2.1. Obilasci 2.1.1. DFS 2.1.2. BFS 2.2. Minimalna razapinjuća stabla (MST) 2.2.1. Kruskalov algoritam 2.2.2. Primov algoritam 2.2.3. Složenost
14. 1. Grafovi (nastavak) 1.1. Najkraći put (Dijkstrin algoritam) 1.2. Kratki pregled nekih problema u teoriji grafova
15. DRUGI KOLOKVIJ

1. 1. Ponavljanje: strukture, datoteke, predprocesor, stringovi, dinamička alokacija memorije.
2. 1. Određivanje vremenske i prostorne složenosti poznatih algoritama: izbacivanje člana iz niza, strlen, strcmp, strcat. 2. Rekurzivne implementacije poznatih algoritama: faktorijeli, strlen, Fibonaccievi brojevi.
3. 1. Demonstracija algoritama sortiranja: 1.1 Bubble 1.2 Selection 1.3 Insertion 1.4 Shell 1.5 Quick
4. 1. Knapscak. 2. Ponavljanje rekurzije i priprema za implementaciju rekurzivnog spusta na laboratorijskim vježbama.
5. 1. Operacije nad vezanom listom. 2. Implementacija ATP Stoga i ATP Reda nizom 3. Uvod u implementaciju ATP Stoga i ATP Reda vezanom listom (priprema za laboratorijske vježbe)
6. 1. Implementacija ATP Liste nizom. 2. Implementacija ATP Liste vezanom listom.
7. 1. Implementacija ATP Skupa nizom. 2. Implementacija ATP Skupa vezanom listom.
8. 1. Rješavanje zadataka sa prvog kolokvija.
9. 1. Operacije nad stablima: 1.1 Obilasci. 1.2 Dodavanje čvorova. 1.3 Brisanje čvorova.
10. 1. Rješavanje zadataka upotrebom ATP Mape.
11. 1. Rješavanje zadataka upotrebom ATP Prioritetnog reda.
12. 1. Najkraći put (Dijkstrin algoritam) 2. Detektiranje ciklusa u grafu.
13. 1. Minimalna razapinjuća stabla (MST)
14. 1. Kratki pregled nekih problema u teoriji grafova
15. 1. Rješavanje zadataka sa drugog kolokvija.

1. Priprema, korištenje Visual Studia za projekte sa više datoteka. Utvrđivanje elemenata C-jezika potrebnih za sljedeće vježbe (strukture, pokazivači).
2. Iterativne i rekurzivna implementacija binarne pretrage.
3. Mjerenje vremena izvršavanja pripremljenih algoritama sortiranja. Hibridno sortiranje.
4. Rekurzivni spust kroz matricu.
5. Rekurzivni spust kroz matricu (backtracking optimizacije, pamćenje puta).
6. Implementacije ATP Stoga i ATP Reda vezanom listom
7. Nije definirano
8. Nije definirano

1. Tijekom semestra održat će se dva međuispita (kolokvija) – kombinirano teorije i zadataka u 8. i 14. tjednu nastave. Na završnom ispitu studenti koji polože međuispite oslobođeni su polaganja ispita. Ukoliko student položi samo jedan od kolokvija, tijekom ljetnih ispitnih rokova umjesto završnog ispita omogućeno mu je polaganje gradiva međuispita koji nije položio. Kolokvij je zadan pismeno, u obliku 5 zadataka. Rješavanje kolokvija traje 90 minuta, nije dopušteno korištenje materijala ispita ni drugih pomagala. Sadržaj prvog kolokvija: Složenost algoritama, Algoritmi za sortiranje (opis i provedba na konkretnim podacima) Dinamičko programiranje ATP Stack, Queue, List Vezane liste (fragmenti koda)
2. Sadržaj drugog kolokvija: ATP Set, Dictionary, Map, Prioritetni red Hash tablica Stabla, Binarna stabla pretraživanja (opis i provedba na podacima) Hrpa (opis i provedba na podacima) Algoritmi na grafovima

1. Završni ispit zadaje se u obliku 7-10 pismenih zadataka iz teorije i izvedbe algoritama. Rješavanje ispita traje 90 minuta. Dopušteno je korištenje isključivo tablice ATP operacija dostupne na strnici predmeta. Po potrebi predavač može zatražiti usmeno odgovaranje. Uvjet za konačnu pozitivnu ocjenu je odrada svih laboratorijskih vježbi, prisustvo na barem 50% predavanja, pozitivna ocjena međuispita ili završnog ispita, uz eventualnu korekciju po usmenom odgovoru. Ocjena (%) = (K1 + K2) / 2 ili Ocjena (%) = ZI (u slučaju da student nije položio oba međuispita do kraja ljetnih ispitnih rokova tekuće nastavne godine) K1, K2 – bodovi iz kombiniranih međuispita. ZI – bodovi iz završnog ispita Konačna se ocjena utvrđuje na sljedeći način: [0, 40] 1 [40, 55) 2 [55, 70) 3 [70, 85) 4 [85, 100] 5 Sadržaj ispita: Složenost algoritama, Algoritmi za sortiranje (opis i provedba na konkretnim podacima), Dinamičko programiranje, Vezane liste, ATP Stog, Red, Lista, Skup, Stabla, Binarna stabla pretraživanja (opis i provedba na podacima) Hash tablica ATP Mapa, Prioritetni red Hrpa (opis i provedba na podacima) Grafovi

1. 1. Konzultacije 2. Analiza ponuđenih implementacija algoritama. 3. Samostalno rješavanje zadataka 4. Rad u laboratoriju