Optimizacioni algoritmi (ETF RII OA 3645)

Opšte informacije

Naziv kursa

Optimizacioni algoritmi

Oznaka (šifra) predmeta

ETF RII OA 3645

Studij

ETF-B

Odsjek

Računarstvo i informatika

Godina

3

Semestar

6

Tip

Izborni

ECTS

4.5

Ukupno sati nastave

45

Sati predavanja

30

Sati vježbi

0

Sati tutorijala

15

Cilj kursa - Znanje i vještine koje treba postići student
  Kurs ima za cilj studentima produbiti stečena znanja iz problematike optimizacije, naglašavajući osnovne metodologije i matematičku podlogu, te posebno se osvrćući na primjenu tehnika matematičkog modeliranja kompleksnih optimizacionih problema i razvoj i implementaciju efikasnih i egzaktnih algoritama za rješavanje različitih klasa optimizacionih problema. Naročita pažnja je posvećena eksperimentalnoj realizaciji modela i razmatranih algoritama.

Program
  1.Uvodna razmatranja: Klasifikacija problema optimizacije, Matematički modeli problema optimizacije, tehnike matematičkog modeliranja problema optimizacije;

2.Teorija i algoritmi linearnog programiranja: Osnove simpleksne tehnike i linearnog programiranja, Modifikacije simpleksnog algoritma za probleme velike dimenzionalnosti, Metode dekompozicije, Metode na bazi rijetkih matrica, Metode na bazi pretraživanja unutrašnjosti skupa, Korištenje softverskih alata za rješavanje problema kontinualnog linearnog programiranja;

3.Teorija i algoritmi cjelobrojnog programiranja: Formulacija, Geometrijska predstava, Algoritmi cjelobrojnog programiranja, Gomory-jev algoritam, Branch-And-Bound algoritam, Aproksimativne i heurističke metode pretraživanja, Korištenje softverskih alata za rješavanje problema cjelobrojnog i mješovitog linearnog programiranja;

4.Teorija i algoritmi nelinearnog programiranja: Modeli i algoritmi za polinomijalne probleme, Optimizacija bez ograničenja i sa ograničenjima, Lagrange-ova i konusna teorija dualnosti, Geometrijska interpretacija, Jednodimenzionalne metode pretraživanja, Newton-Raphson, Kvadratično i Kubično pretraživanje, Fibonačijev metod, Metod zlatnog sječenja, Nesekvencijalne metode pretraživanja, Slučajno pretraživanje, Faktorijelno pretraživanje, Univarijantno i relaksaciono pretraživanje, Algoritmi na bazi gradijenta, Algoritmi na bazi ubrzanja, Metoda konjugovanih gradijenata, Ostale tehnike traženja;

5.Osnovni modeli i tehnike rješavanja problema sekvencijalnog donošenja odluka u uslovima neodređenosti: Egzaktni algoritmi za NP-hard probleme, Dinamičko programiranje, Redukcija broja stanja, Ograničenja, Branch-and-bound algoritmi, Branch-and-cut algoritmi, Branch-and-price algoritmi, primjena algoritama na Knapsack i Travelling Salesman problemima;

6.Eksperimentalna analiza performansi obrađenih algoritama.

Literatura
Obavezna1.Bilješke i slajdovi s predavanja (moći će se preuzeti na WEB siteu Fakulteta);

2.Donald A. Pierre, Optimization Theory with Application, Dover Publications, Inc.

3.Charles S. Beightler, Don T. Phillips, Douglass J. Wile, Foundations of Optimization, Prentice-Hall

4.P. TOTH, Discreet D. VIGO (edited by) ' The Vehicle Routing Problem', SIAM Monographs on Mathematics and Applications 2002.

5.S. HAMMER, P. TOTH ' Knapsack Problems: Algorithms and Computer Implementations', J. Wiley 1990.

6.R.K. AHUJA, T.L. MAGNANTI, J.B. ORLIN ' Network Flows: Theory, Algorithms and Applications', Prentice Hall 1993.

7.G. GUTIN, To PUNNEN (edited by) ' The Traveling Salesman Problem and its Variations', Kluwer 2002.
Preporučena1.John Tsitiklis, Dimitris P. Bertsekas, Introduction to Linear Optimization, Athena Scientific

2.Dimitris P. Bertsekas, Nonlinear Programming, Athena Scientific

Didaktičke metode
  Kurs se provodi kroz teorijska predavanja na kojima se prezentiraju osnovni koncepti. Predavanja su podržana nizom praktičnih i empirijskih primjera od strane nastavnika. Kroz tutorijal se, pod vođenjem i pratnjom tutora, rješavaju i drugi zadaci, uključujući i zadatke s prethodnih ispitnih rokova; ove aktivnosti organizirane su tako da se već tokom izvođenja nastavnog programa kroz domaće zadaće i parcijalne ispite, kontinuirano provjerava stupanj pripremljenosti studenata da ovlada znanjima i vještinama koje treba postići u okviru ovog kursa.

Način provjere znanja
  Tokom trajanja kursa student prikuplja bodove prema slijedećem sistemu:

prisustvo satima predavanja, vježbi i tutorijala: 10 bodova, student koji više od tri puta izostane s predavanja,vježbi i/ili tutorijala ne može ostvariti bodove po ovoj osnovi;

izrada domaćih zadaća: maksimalno 10 bodova; predviđena je izrada od 5 do 10 domaćih zadaća ravnomjerno raspoređenih tokom semestra;

parcijalni ispiti: dva pismena parcijalna ispita, pri čemu svaki pozitivno ocijenjen parcijalni ispit donosi 20 bodova;

Student koji je tokom trajanja semestra ostvario manje od 20 bodova ponovno upisuje ovaj kurs.

Student koji je tokom trajanja semestra ostvario 40 i više bodova pristupa usmenom završnom ispitu; ovaj ispit sastoji se iz diskusije zadataka s parcijalnih ispita, domaćih zadaća i odgovora na jednostavna pitanja koja se odnose na teme kursa. Usmeni završni ispit donosi maksimalno 40 bodova. Da bi postigao pozitivnu završnu ocjenu, student na ovom ispitu mora ostvariti minimalno 20 bodova. Student koji ne ostvari ovaj minimum pristupa usmenom dijelu popravnog ispita.Student koji je tokom trajanja semestra ostvario 20 i više bodova, a manje od 40 bodova, pristupa popravnom ispitu. Popravni ispit struktuiran je na slijedeći način:

pismeni dio koji je struktuiran na isti način kao i pismeni parcijalni ispit; u okviru ovog ispita student polaže zadatke iz tema za koje nije postigao prolaznu ocjenu (10 i više bodova) polažući parcijalne pismene ispite,

usmeni dio koji je struktuiran na isti način kao usmeni dio završnog ispita.

Usmenom dijelu popravnog ispita može pristupiti student koji je nakon polaganja posmenog dijela popravnog ispita uspio stvariti ukupan skor od 40 i više bodova; ovaj skor sastoji se od bodova ostvarenih kroz: prisustvo nastavi, izradu domaćih zadaća, polaganje parcijalnih sipita i polaganje pismenog dijela popravnog ispita.

Usmeni popravni ispit donosi maksimalno 40 bodova. Da bi postigao pozitivnu završnu ocjenu student na ovom ispitu mora ostvariti minimalno 20 bodova. Student koji ne ostvari ovaj minimum ponovno upisuje ovaj kurs.

Napomene
  Prilikom polaganja pismenog ispita, student može koristiti od strane nastavnika pripremljenu listu formula koje mogu biti od koristi prilikom rješavanja zadataka. Nije dozvoljeno korištenje drugih bilješki, knjiga, mobilnih telefona niti drugih elektronskih pomagala, osim džepnog elektronskog kalkulatora.

Zadaci koje student treba riješiti na ispitu su istog tipa kao oni rješavani tokom izvođenja predavanja i tutorijala.