UVOD U ALGORITME I STRUKTURE PODATAKA

R smer

Kurs Uvod u algoritme i strukture podataka je kurs na trećoj godini R smera. Cilj ovog predmeta je sticanje osnovnih znanja o osnovnim strukturama podataka, njihovom korišćenju i implementaciji, kao i o osnovnim strategijama konstrukcije algoritama, analizi njihove složenosti i korektnosti. U okviru kursa se proučavaju sledeće teme:

  • analiza korektnosti i složenosti algoritama
  • sortiranje, binarna pretraga i tehnika dva pokazivača
  • induktivno-rekurzivna konstrukcija
  • osnovne strukture podataka: korišćenje i implementacija
  • različite strategije konstrukcije algoritama: gruba sila, dekompozicija, bektreking, dinamičko programiranje, pohlepni algoritmi

Predmetni nastavnici:

Asistenti:

Obavezan predmet

  • 6 ESPB bodova
  • 3 časa predavanja
  • 2 časa vežbi

Ispitne obaveze (100 poena):

  • praktični ispit: 50 poena
  • usmeni ispit: 50 poena
Moguće je ceo ispit (ili neki njegov deo) položiti preko kolokvijuma tokom semestra

Pragovi:

  • bar 25 poena na praktičnom delu ispita
  • bar 51 poen u zbiru na praktičnom i usmenom delu ispita

Predavanja po časovima

1. čas
Uvod. Korektnost algoritma i veza sa induktivno-rekurzivnom konstrukcijom. Dokaz korektnosti rekurzivnih i iterativnih funkcija. Složenost algoritama. Merenje vremena izvršavanja. Asimptotska analiza složenosti.
2. čas
Složenost nekih čestih oblika petlji. Sumiranja. Rekurentne jednačine. Amortizovana analiza složenosti. Tehnike za poboljšanje složenosti: zamena iteracije formulom.
3. čas
Tehnike za poboljšanje složenosti: odsecanje, inkrementalnost, prefiksne sume, razlike susednih elemenata, sortiranje.
4. čas
Binarna pretraga: traženje elementa za zadatom vrednošću, traženje prelomne tačke, binarna pretraga po rešenju. Tehnika dva pokazivača.
5. čas
Induktivno-rekurzivna konstrukcija: zvezda, apsolutni pobednik, broj rastućih segmenata. Ojačavanje induktivne hipoteze.
6. čas
Klasifikacija struktura podataka. Strukture podataka - korišćenje: skup, mapa, stek.
7. čas
Strukture podataka - korišćenje: red, red sa dva kraja, red sa prioritetom. Strukture podataka - implementacija: dinamički niz, lista, stek, red, dek, uređeno binarno drvo.
8. čas
Strukture podataka - implementacija: hip, heš tabele. Dekompozicija: Quick Sort, Merge Sort, k-ti najveći element, zbir k najvećih elemenata, Karacubin algoritam za množenje polinoma.
9. čas
Dekompozicija: maksimalni zbir segmenta, najbliži par tačaka. Generisanje kombinatornih objekata: sledeći podskup, svi podskupovi leksikografski, svi podskupovi. Bektreking: raspoređivanje n dama na šahovskoj tabli, broj podnizova datog zbira.
10. čas
Bektreking: merenje sa n tegova, bojenje grafa sa 3 boje, bojenje grafa minimalnim brojem boja. Dinamičko programiranje: n-ti Fibonačijev broj, broj pojavljivanja podniske.
11. čas
Dinamičko programiranje: ranac 0-1, edit rastojanje niski.
12. čas
Dinamičko programiranje: optimalno množenje matrica. Gramzivi algoritmi: reč u reč precrtavanjem slova, žaba na kamenju, razlomljeni problem ranca, raspored aktivnosti, Hafmanovo kodiranje.

Literatura

Rokovi

Primer praktičnog dela ispita za studente koji studiraju po novoj akreditaciji
Primer praktičnog dela ispita za studente koji studiraju po staroj akreditaciji
Primer praktičnog dela ispita za studente sa L smera

Zadaci po časovima

1. čas
1. čas
2. čas
2. čas
3. čas
3. čas
4. čas
4. čas
5. čas
5. čas
6. čas
6. čas
7. čas
7. čas
8. čas
8. čas
9. čas
9. čas
10. čas
10. čas
11. čas
11. čas
12. čas
12. čas

Literatura za predavanja

Literatura za vežbe

Dodatno

  • Miodrag Živković: Algoritmi
  • Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein: Introduction to Algorithms

Rezultati treceg kolokvijuma i testa

Rezultati treceg kolokvijuma i treceg teorijskog testa mogu se naći ovde

Javiti se profesoru ili asistentu za uvid u radove. Studenti koji ne zele da upisu ocenu osvojenu u predroku treba da se jave predmetnom profesoru.

12. 2. 2026.

Prijava za treći kolokvijum

Ukoliko planirate da polažete treći kolokvijum iz UASP-a, molimo Vas da popunite sledeću formu.

5. 2. 2026.

Treći kolokvijum

Treći praktični kolokvijum će se održati u utorak 10.2.2026. u 8:30h na Studentskom trgu u učionici 718.

5. 2. 2026.

Treći kolokvijum

Treći teorijski kolokvijum će se održati u sredu 11.2.2026. u 11h na Studentskom trgu u učionici 706.

4. 2. 2026.

Rezultati testa

Rezultati drugog teorijskog testa mogu se naći ovde

Javiti se profesoru ili asistentu za uvid u radove.

2. 2. 2026.

Drugi kolokvijum

Drugi teorijski kolokvijum će se održati u subotu 24.1.2026. na Studentskom trgu u učionici 830 od 15:15h do 16h.

20. 1. 2026.

Prijava za drugi kolokvijum

Ukoliko planirate da polažete drugi kolokvijum iz UASP-a, molimo Vas da popunite sledeću formu. Teorijski deo će se održati u subotu 24.1.2026. u terminu časa. Praktični deo će se održati u utorak od 8:30h na Studentskom trgu.

19. 1. 2026.

Rezultati testa

Rezultati prvog teorijskog testa mogu se naći ovde

Javiti se profesoru ili asistentu za uvid u radove.

24. 12. 2025.

Prvi kolokvijum

Prvi kolokvijum će se održati u utorak 16.12.2025. na Studentskom trgu u učionicama 704 i BIM. Oba dela počinju u 8:30h i ukupno vreme za rad je 1 sat i 45 minuta.

Prijava za prvi kolokvijum

Ukoliko planirate da polažete prvi kolokvijum iz UASP-a, molimo Vas da popunite sledeću formu.

Početak semestra

Nastava na kursu kreće u sredu 12.11. Srećno!

Matematički fakultet, Univerzitet u Beogradu
školska 2024/25. godina