You are here

Osnovne informacije

Naziv: 
PA - Projektovanje Algoritama
Studijski program: 
Računarstvo i automatika – E2
Semestar: 
VI
Asistent: 
Nedeljni fond časova: 
3+3

Opis

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.

Konsultacije: Prof. dr Ivan Kaštelan
Pon Uto Sre Čet Pet
    15:15 - 16:45    

Konsultacije se održavaju u kancelariji NTP-514.

Konsultacije: MSc Milica Matić
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:

  • Predavanja: 1 put nedeljno, 3 časa.
  • Računarske vežbe: 1 put nedeljno, 3 časa.

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

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: „Introduction to Algorithms“, Third Edition, MIT Press, 2009.
  • Materijali sa predavanja i vežbi.

Gradivne celine

  • Asimptotska notacija, rast funkcija
  • Rekurencije i metode analize njihovih složenosti
  • Algoritmi pretraživanja
  • Algoritmi sortiranja
  • Strukture podataka – heap, stablo, hash tabele
  • Hash funkcije
  • Numerički algoritmi
  • Grafovi i najkraće putanje
  • Dinamičko programiranje
  • Napredne teme

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.

  • Svaki student treba da preda svoje rešenje papirnog dela domaćeg zadatka, a ukoliko je radio/la u timu/grupi ili bio/la pomognut/a od strane drugog studenta, neophodno je da na radu bude naznačeno sa kojim studentima je radio/la.
  • Isto važi i za računarski deo zadatka, s tim da svaki pojedinačni član tima treba da pokaže zadovoljavajuće znanje i vladanje materijom da bi dobila/o maksimalan broj poena predviđen za zadatak koji je uradila/o.

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.