Cilj PA predmeta je da naučimo osnovne principe projektovanja algoritama i struktura podataka. Prilikom implementacije digitalnih sistema, alati pokreću veliki broj složenih algoritama kako bi izvršili korake sinteze, prevođenja, mapiranja, implementacije i generisanja datoteke za konfiguraciju ciljanog FPGA integrisanog kola. Zbog toga će ovaj predmet, treći u nizu predmeta sa temom projektovanja digitalnih i računarskih sistema biti potpuno softverski orijentisan, sa ciljem savladavanja osnovnih koncepata analize i projektovanja algoritama. Na kraju predmeta, student će biti upoznat sa osnovnom teorijom i primenom algoritama i biti spreman za rešavanje problema koji su algoritamske prirode, bilo sa ciljem hardverskog ili softverskog rešenja problema.
U prvom delu predmeta naučićemo matematičke osnove analize algoritama – asimptotske notacije, rast funkcija, rekurencije. Ove metode će nam biti važne tokom čitavog predmeta jer kvalitet našeg algoritamskog rešenja nekog problema moramo nekako izmeriti i imati način poređenja dva algoritma. Analiza algoritama se vrši prostorno i vremenski, a mi ćemo dominantno raditi vremensku analizu kvaliteta algoritma. Nakon što savladamo matematičke osnove, prvi algoritmi koje ćemo učiti su algoritmi pretraživanja i sortiranja. Sortiranje je klasična tema kod učenja algoritama koja se prva izučava, zbog velikog broja rešenja koji se razlikuju u svom kvalitetu i preko kojih se mogu skoro potpuno savladati osnovni koncepti analize algoritama. Nije nam cilj da znamo napamet pet ili šest algoritama sortiranja, ali ćemo kroz njihovu raznolikost naučiti kako svoje algoritamsko rešenje analizirati i unaprediti.
U drugom delu predmeta razumećemo da strukture podataka mogu direktno da utiču na kvalitet nekog algoritamskog rešenja. Zbog toga će ovaj deo predmeta biti obojan učenjem raznih struktura podataka – stack, red, heap (kojeg ćemo prvi put upoznati dok učimo sortiranje), stabla, hash tabele, grafovi. Učićemo osnovne funkcije rada sa svakom od navedenih struktura podataka, a najviše ćemo se fokusirati na teoriju i implementaciju grafova. Naučićemo kako ih predstaviti, kako ih pretražiti, kako proveriti povezanost grafa i kako rešiti neke probleme pomoću grafova. U ovom delu predmeta pozabavićemo se i nekim numeričkim algoritmima iz teorije brojeva i numeričke matematike.
U trećem delu predmeta nastavićemo sa izučavanjem grafova kroz algoritme traženja najkraće putanje u grafu, što je jedna od najčešćih realno-potrebnih operacija u nekom grafu, koju koristimo svaki dan u našem navigacionom sistemu na telefonu. Nakon toga naučićemo princip dinamičkog programiranja koji nam omogućuje da problem rešimo iterativno, od jednostavnijih instanci problema ka složenijim. Dinamičko programiranje je tesno vezano sa pojmom rekurzije, a uporedo sa dinamičkim programiranjem upoznaćemo i koncept pohlepnih algoritama. Na kraju predmeta ćemo se površno upoznati sa nekim naprednim temama iz teorije algoritama – slučajnim, paralelnim i aproksimativnim algoritmima, pojmom NP-kompletnosti, čuvenim problemom trgovačkog putnika i sličnim temama.
Učenje algoritama ne zahteva poseban programski jezik zbog čega će svi primeri na predavanjima biti dati u pseudokodu. Za implementaciju algoritama naučićemo programski jezik Python koji je veoma dobar za učenje algoritama jer omogućava studentu da se skoncentriše na algoritam koji projektuje zbog veoma malih zahteva sa stanovišta ostalog dela koda koji je potrebno napisati da bi se neki algoritamski postupak izvršio (nema tipove podataka, sa listama se radi veoma jednostavno, itd.). Vežbe će proći kroz implementaciju svih naučenih algoritama, a zadaci dati mogućnost da primenimo naučeni algoritam u rešavanju nekog realnog problema koji nije nužno iz računarske struke.
L00. Uvod
L01. Uloga algoritama i prvi koraci
L02. Matematičke osnove
L03. Heap
L04. Quicksort. Linearno sortiranje
L05. Binarno stablo pretrage
L06. Heš tabele
L07. Otvoreno adresiranje. RSA kriptosistem
L08. Grafovi - uvod i pretraga
L09. Problem najkraće putanje
L10. Algoritmi nad grafovima
L11. Dinamičko programiranje
Organizacija laboratorijskih vežbi
LAB01. Python tutorial
dict_test.txt
LAB02. Sortiranje (kvadratna složenost)
LAB03. Sortiranje (logaritamska složenost)
Priprema za prvi test
LAB04. Sortiranje (linearna složenost) - G1
LAB04. Sortiranje (linearna složenost) - G2
LAB05. Strukture podataka (heap)
LAB05. Strukture podataka (heap) - rešenje
LAB06. Strukture podataka (BST)
LAB06. Strukture podataka (BST) - rešenje
LAB07. Strukture podataka (AVL)
LAB07. Strukture podataka (AVL) - rešenje
LAB08. BST primena - G1
LAB08. BST primena - G2
LAB09. Grafovi (BFS, DFS)
LAB10. Grafovi (Topološko sortiranje, Dijkstrin algoritam)
LAB11. Grafovi (Bellman-Ford) - priprema za ispit
LAB12. Grafovi (primena) - G1
LAB12. Grafovi (primena) - G2
LAB13. Dinamičko programiranje
Test 3 - rešenje
L01. Uloga algoritama i prvi koraci (1)
L01. Uloga algoritama i prvi koraci (2)
L02. Matematičke osnove (1)
L02. Matematičke osnove (2)
L02. Matematičke osnove (3)
P01. Problemi za vežbu - Python zagrevanje i sortiranje
L03. Heap (1)
L03. Heap (2)
L04. Quicksort
L04. Linearno sortiranje
L05. Binarno stablo pretrage (BST)
L05. Binarno stablo pretrage - AVL
P02. Problemi za vežbu - Heap. BST
L06. Heš tabele
Primer testa
L07. RSA kriptosistem
L08. Grafovi - uvod i pretraga
L09. Problem najkraće putanje
L10. Algoritmi nad grafovima
L11. Dinamičko programiranje
Primer ispita 1
Primer ispita 2
Pon | Uto | Sre | Čet | Pet |
---|---|---|---|---|
09:00 - 09:45 i 14:00 - 14:45 | ||||
Konsultacije se održavaju u kancelariji NTP 514. U sredu 23.11. konsultacije će biti održane samo u jutarnjem terminu, od 8:30 do 9:30. |
Pon | Uto | Sre | Čet | Pet |
---|---|---|---|---|
Konsultacije se održavaju po dogovoru, u prostorijama Odseka za računarsku tehniku i računarske komunikacije, NTP, kancelarija 516 ili na platformi MSTeams. |
Preporučeno predznanje
Kako bi uspešno pratili predmet, preporučuje se predznanje iz algebre, diskretne matematike i programiranja u bilo kom programskom jeziku. Predznanje iz programskog jezika Python nije neophodno, ali je veoma korisno.
Fond časova i opterećenje
Predmet se izvodi sa fondom časova 3+3. Nastava se izvodi kroz:
Predviđeno opterećenje studenta kroz sve oblike aktivnosti (nastava, domaći zadaci, učenje, ispiti) je ukupno 180 sati, što odgovara 6 ECTS poena. Semestar traje 14 radnih nedelja.
Literatura
Gradivne celine
Akademska etika
Poštovanje akademske etike i intelektualnih prava je jedan od osnovnih postulata modernog društva. Od svakog studenta se očekuje poštenje prilikom izrade domaćih zadataka, laboratorijskog rada i prilikom polaganja kolokvijuma i ispita. Sav predati rad mora da bude delo studenta koji je na njemu potpisan. Zabranjeno je korišćenje rezultata tuđeg rada bez adekvatne napomene u vidu citata ili koautorstva.
Grupni rad i kolaboracija su dozvoljeni tokom izrade domaćih zadataka i laboratorijskih vežbi.
Korišćenje tuđe intelektualne svojine bez adekvatne napomene biće sankcionisano oduzimanjem svih poena predviđenih za datu predmetnu obavezu, uz moguće dodatne sankcije prema pravilima FTN-a i Univerziteta u Novom Sadu.
Grupni rad i kolaboracija nisu dozvoljeni tokom polaganja kolokvijuma i ispita.