KONSTRUKCIJA I ANALIZA ALGORITAMA

I smer

Kurs Konstrukcija i analiza algoritama je kurs na drugoj godini I smera. Cilj ovog predmeta je produbljivanje znanja o strukturama podataka i strategijama konstrukcije algoritama i upoznavanje sa fundamentalnim algoritmima u različitim domenima. U okviru kursa se proučavaju sledeće algoritamske oblasti:

  • napredne strukture podataka
  • grafovski algoritmi
  • algebarski algoritmi
  • algoritmi za obradu teksta
  • geometrijski 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
  • dodatnih 10 poena na teorijskim testovima
Praktični deo ispita je moguće položiti i preko tri kolokvijuma.
Prvi kolokvijum biće održan u nedelju 26.4, drugi kolokvijum u subotu 30.5, a treći u ponedeljak 22.6.

Pragovi:

  • bar 25 poena na praktičnom delu ispita
  • bar 20 poena na usmenom delu ispita

Predavanja po časovima

1. čas
Prefiksno drvo. Strukture podataka za predstavljanje disjunktnih skupova.
Pitanja za obnavljanje gradiva sa 1. časa
2. čas
Statički upiti raspona. Dinamički upiti raspona. Segmentno drvo. Lenjo segmentno drvo.
Pitanja za obnavljanje gradiva sa 2. časa
3. čas
Grafovi: osnovni pojmovi, predstavljanje grafa. Pretraga neusmerenog grafa u dubinu.
4. čas
Pretraga usmerenog grafa u dubinu. Pretraga grafa u širinu. Topološko sortiranje grafa.
Pitanja za obnavljanje gradiva sa 3. i 4. časa
5. čas
Komponente jake povezanosti u usmerenom grafu. Kosaradžuov algoritam. Ojlerovi i Hamiltonovi putevi i ciklusi u grafu. Hirholcerov algoritam za određivanje Ojlerovih ciklusa.
Pitanja za obnavljanje gradiva sa 5. časa
6. čas
Težinski grafovi. Najkraći putevi iz zadatog čvora: aciklički grafovi, grafovi sa nenegativnim granama: Dajkstrin algoritam, grafovi koji mogu imati negativne grane: opšti algoritam zasnovan na relaksaciji grana, Belman-Fordov algoritam.
7. čas
Konstrukcija minimalnog povezujućeg drveta: Primov, Kraskelov algoritam. Svi najkraći putevi: indukcija po broju grana i po broju čvorova, Flojd-Varšalov algoritam. Tranzitivno zatvorenje grafa.
8. čas
Mostovi i artikulacione tačke u neusmerenom grafu. Prošireni Euklidov algoritam (prestavljanje NZD preko uzastopnih ostataka, predstavljanje ostataka preko a i b). Rešavanje linearnih Diofantovih jednačina.
9. čas
Faktorizacija broja (faktorizacija isprobavanjem delilaca, faktorizacija više brojeva pomoću Eratostenovog sita). Multiplikativne funkcije. Ojlerova funkcija (direktan algoritam, svođenje na faktorizaciju, računanje Ojlerove funkcije svih brojeva do n). Modularna aritmetika: modularne grupe, Ojlerova i mala Fermaova teorema.
10. čas
Modularni multiplikativni inverz (svođenjem na prošireni Euklidov algoritam i korišćenjem Ojlerove i male Fermaove teoreme). Kineska teorema o ostacima. RSA kriptografija. Brza Furijeova transformacija: direktna Furijeova transformacija.
11. čas
Brza Furijeova transformacija: inverzna Furijeova transformacija. Heširanje niski (polinomska heš funkcija sleva udesno i zdesna nalevo, računanje heš vrednosti segmenata niza, Rabin-Karpov algoritam). z-niz i z-algoritam.
12. čas
Rabin-Karpov algoritam. Algoritam KMP. Osnovni geometrijski algoritmi: skalarni, vektorski proizvod, računanje površine trougla i primene, orijentacija trojke tačaka i primene.
13. čas
Konstrukcija prostog mnogougla. Ispitivanje pripadnosti tačke unutrašnjosti prostog i konveksnog mnogougla. Algoritmi za konstrukciju konveksnog omotača: direktni induktivni algoritam, Grejemov algoritam.

Literatura

Zadaci po časovima

1. čas
Uvod u napredne strukture podataka. Opisi problema.
2. čas
Prefiksna drveta. Dodatno za vežbu:
3. čas
Strukture za predstavljanje disjunktnih skupova (union-find)
4. čas
Segmentna stabla. Lenja segmentna stabla. Dodatno za vežbu:
5. čas
Grafovi. Pretraga. Topološko sortiranje. Dodatno za vežbu:
6. čas
Komponente jake povezanosti. Ojlerovi putevi i ciklusi. Dodatno za vežbu:
7. čas
Najkraći putevi u grafu. Dodatno za vežbu:
8. čas
Minimalna razapinjuća stabla.
9. čas
Mostovi i artikulacione tačke. Vežbanje za kolokvijum.
10. čas
Euklidov algoritam. Prošireni Euklidov algoritam. Prosti brojevi. Eratostenovo sito. Faktorizacija. Ojlerova funkcija.
11. čas
Modularni inverz. Kineska teorema o ostacima. Heširanje niski. RSA algoritam. Dodatno za vežbu:
12. čas
Algoritmi za obradu teksta. Z algoritam. Manačerov algoritam.
13. čas
Geometrijski algoritmi. Konstrukcija prostog mnogougla. Pripadnost tačke mnogouglu. Konstrukcija konveksnog omotača

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

Termin usmenog dela ispita u junskom predroku

U narednoj tabeli nalaze se termini za usmeni deo ispita. Studenti koji žele da izađu na usmeni deo ispita u predroku treba da se upišu za datum 25.6. u tabelu

21. 6. 2026.

Rezultati treceg teorijskog testa

Rezultati treceg teorijskog testa se nalaze na sledećem linku. Uvid je moguć u ponedeljak 22.6. pre/posle kolokvijuma.

21. 06. 2026.

Raspored za polaganje 3. kolokvijuma

Raspored po grupama za treći kolokvijum se nalazi na sledećem linku. Prva grupa će početi sa radom u 10h, a druga u 12h. Svi studenti će kolokvijum polagati na Trgu. Mole se studenti da dođu 15 minuta ranije radi lakšeg raspoređivanja.

21. 06. 2026.

Prijava za polaganje 3. kolokvijuma

Drugi kolokvijum će biti održan 22.6. sa početkom u 10h. U slučaju velikog broja prijava, studenti će biti podeljeni u 2 grupe, a obaveštenje o tome će biti okačeno na sajt predmeta.
Formular za prijavu kolokvijuma se može naći na sledećem linku. Prijava će biti otvorena do nedelje u podne. Prijava je obavezna. Ukoliko ste se prijavili, a odlučite da ne izađete na kolokvijum, obavezno se javite nekom od asistenata.

18. 06. 2026.

Termin trećeg testa

Treći teorijski test biće održan u utorak 16.6. u 18:15 u terminu časova predavanja i u petak 19.6. u 17:15 u terminu časova predavavanja.

15. 06. 2026.

Rezultati 2. kolokvijuma

Rezultati drugog kolokvijuma se nalaze na sledećem linku. Pored broja poena, u tabeli se nalaze komentari koji ukazuju na propuste u implementaciji. Za uvid u rad se javiti Matiji mejlom najkasnije do srede.

31. 05. 2026.

Raspored za polaganje 2. kolokvijuma

Raspored po grupama za drugi kolokvijum se nalazi na sledećem linku. Prva grupa će početi sa radom u 10h, a druga u 12h. Svi studenti će kolokvijum polagati na Trgu. Mole se studenti da dođu 15 minuta ranije radi lakšeg raspoređivanja.

29. 05. 2026.

Promena lokacije vežbi za grupe 2i2b i 2i2v

Usled zdravstvenih problema, asistent Matija neće biti u mogućnosti da drži vežbe do daljnjeg.
Grupa 2i2b će četvrtkom slušati vežbe sa grupom 2i1b u učionici N153 od 14h ili sa grupom 2i2a u učionici N225 u istom terminu.
Grupa 2i2v će četvrtkom slušati vežbe sa grupom 2i1a u učionici N153 od 16h.

26. 05. 2026.

Prijava za polaganje 2. kolokvijuma

Drugi kolokvijum će biti održan 30.5. sa početkom u 10h. U slučaju velikog broja prijava, studenti će biti podeljeni u 2 grupe, a obaveštenje o tome će biti okačeno na sajt predmeta.
Formular za prijavu kolokvijuma se može naći na sledećem linku. Prijava će biti otvorena do petka u podne. Prijava je obavezna. Ukoliko ste se prijavili, a odlučite da ne izađete na kolokvijum, obavezno se javite nekom od asistenata.

26. 05. 2026.

Rezultati drugog teorijskog testa

Rezultati drugog teorijskog testa se nalaze na sledećem linku. Uvid je moguć u pauzama časova predavanja.

20. 05. 2026.

Promena lokacije vežbi

Grupa 2i2b će u četvrtak 21.05. slušati vežbe sa grupom 2i1b u učionici N153 od 14h.
Grupa 2i2v će u četvrtak 21.05. slušati vežbe sa grupom 2i1a u učionici N153 od 16h.

19. 05. 2026.

Termin drugog testa

Drugi teorijski test biće održan u utorak 12.5. u 18:15 u terminu časova predavanja i u petak 15.5. u 17:15 u terminu časova predavavanja.

08. 05. 2026.

Rezultati 1. kolokvijuma

Rezultati prvog kolokvijuma se nalaze na sledećem linku. Pored broja poena, u tabeli se nalaze komentari koji ukazuju na propuste u implementaciji. Uvid u radove će održati asistent Andrija, u pauzama i nakon časova u četvrtak, 07.05.

01. 05. 2026.

Raspored za polaganje 1. kolokvijuma

Raspored po grupama za prvi kolokvijum se nalazi na sledećem linku. Prva grupa će početi sa radom u 10h, a druga u 12h. Svi studenti će kolokvijum polagati na Trgu. Mole se studenti da dođu 15 minuta ranije radi lakšeg raspoređivanja.

25. 04. 2026.

Prijava za polaganje 1. kolokvijuma

Prvi kolokvijum će biti održan 26.4. sa početkom u 10h. U slučaju velikog broja prijava, studenti će biti podeljeni u 2 grupe, a obaveštenje o tome će biti okačeno na sajt predmeta.
Formular za prijavu kolokvijuma se može naći na sledećem linku. Prijava će biti otvorena do subote u podne. Prijava je obavezna. Ukoliko ste se prijavili, a odlučite da ne izađete na kolokvijum, obavezno se javite nekom od asistenata. Studenti koji su se prijavili, nisu izašli na kolokvijum, a pri tome nisu obavestili blagovremeno nekog od asistenata, gube pravo polaganja narednih kolokvijuma.

21. 04. 2026.

Rezultati prvog teorijskog testa

Rezultati prvog teorijskog testa se nalaze na sledećem linku. Uvid je moguć u pauzama časova predavanja.

21. 04. 2026.

Termini kolokvijuma

Prvi kolokvijum biće održan u nedelju 26.4, drugi kolokvijum u subotu 30.5, a treći u periodu od 20.6. do 25.6 (termin će biti naknadno određen).

30. 03. 2026.

Početak nastave

Svim studentima želimo srećan početak drugog semestra i puno uspeha na kursu!

22. 03. 2026.

Matematički fakultet, Univerzitet u Beogradu
školska 2023/24. godina