Diskretne strukture 3 (I-smer)

Literatura: (moze se naci na Matematickom fakultetu ili u skriptarnici na 4. spratu)

-   Djordje Dugošija i Aleksandar Savić, Operaciona istraživanja, Beograd, 2017.

-   Djordje Dugošija, Linearno programiranje, Beograd, 2011.

-   Aleksandar Jović, Skripta (vežbe)

Raspodela bodova

Ispit nosi ukupno 100 bodova. Bodovanje se vrši po sledećem principu:
1. varaijanta: Bez domaćih zadataka
Pismeni ispit50p
Usmeni ispit50p
2. varaijanta:
Domaći zadaci40x1.5=60p (maksimlano skalirano)
Pismeni ispit20p (maksimalno)
Usmeni ispit40p

Sadržaj kursa:
  • Uvod u linearno programiranje, osnovni modeli
  • Sistemi linearnih nejednačina, Furije-Mozkinova metoda eliminacije
  • Slaba i jaka dualnost u linearnom programiranju, uslovi komplementarnosti
  • Simpleks metod
  • Revidiran simpleks metod
  • Revidiran simpleks metod sa eta matricama
  • Dual simpleks metod
  • Dvofazni simpleks metod
  • Transportni problem
  • Svodjenje problema linearnog programiranja na transportni problem
  • Assignment problem
  • Matricne igre
  • Problem ranca
  • Gomorijeva metoda odsecanja
  • Metod grananja i ograničavanja
  • Metod implicitnog prebrojavanja
  • Ojlerov put i cikl, Fleury-ev algoritam
  • Pretrage u dubinu i širinu
  • Pretrage u dubinu i širinu za orijentisane grafove, problem jednosmernih ulica
  • Minimalna razapinjuća stabla, Kruskalov i Prajmov algoritam, modifikovan Kruskalov algoritam
  • Minimalna razapinjuća stabla u orijentisanom grafu, Edmonsov algoritam
  • Problem trgovackog putnika, metod grananja ogranicavanja, 3-opt

DOMAĆI ZADACI


4. domaći zadatak : Transportni(otvoren i zatvoren) i Assignment_problem
5. domaći zadatak : Matricne igre
6. domaći zadatak : Ranac (Unazad, Unapred i 3. rekurentna formula)
7. domaći zadatak : Gomorijev metod
8. domaći zadatak : Grananje i ogranicavanje ILI Impicitno prebrojavanje
OBVESTENJA:
Seminarski zadatak iz DS3 treba da sadrzi kratak opis algoritma (koraci ili pseudokod) za metodu koju ste dobili i najmanje jedan uradjen primer.



Vežbe u ovom semestru bice organizovane online preko webex platforme po vazecem rasporedu. Link za pristup casu matf.webex.com/meet/ajovic.
Materijali za vežbe bice dostupni na ovoj stranici, ali cu vam iste slati i na mail. Po potrebi, mailom cemo se dogovoriti za sve druge vidove konsultacija. Stojim vam na raspolaganju za sva pitanja. Ne ustručavajte se da zatražite pomoć za bilo šta.


OBAVESTENJA:

Pismeni ispit iz Diskretnih struktura 3 (28.06.) je na Studentskom trgu od 17h. Sacekajte me kod skriptarnice.