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:

• dr Vesna Marinković
• dr Filip Marić

Asistenti:

• Strahinja Stanojević
• Andrija Urošević
• Matija Lojović

Obavezan predmet

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

Ispitne obaveze (100 poena):

• praktični ispit: 50 poena
• teorijski test: 10 poena
• usmeni ispit: 40 poena

Pragovi:

• bar 25 poena na praktičnom delu ispita
• bar 7 poena na teorijskom testu

Predavanja po časovima

1. čas

Prefiksno drvo. Strukture podataka za predstavljanje disjunktnih skupova (poglavlja 1.1 i 1.3 udžbenika).
Pitanja za obnavljanje gradiva sa 1. časa

2. čas

Statički upiti raspona. Dinamički upiti raspona. Segmentno drvo (poglavlja 1.4.1 i 1.4.2.1).
Grafovi: osnovni pojmovi, predstavljanje grafa (poglavlja 2.1 i 2.2).
Pitanja za obnavljanje gradiva sa 2. časa

3. čas

Pretraga grafa u dubinu. Pretraga grafa u širinu (poglavlje 2.3).
Pitanja za obnavljanje gradiva sa 3. časa

4. čas

Topološko sortiranje grafa. Mostovi i artikulacione tačke u neusmerenom grafu (poglavlja 2.4 i 2.5).
Pitanja za obnavljanje gradiva sa 4. časa

5. čas

Komponente jake povezanosti (poglavlja 2.6.1 i 2.6.2 ili 2.6.3). Ojlerovi i Hamiltonovi putevi i ciklusi (poglavlje 2.7.1 i 2.7.2). Hirholcerov algoritam za određivanje Ojlerovih ciklusa (poglavlje 2.7.1.1).
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: Belman-Fordov algoritam (poglavlja 2.8 i 2.9). Konstrukcija minimalnog povezujućeg drveta: Primov, Kraskelov algoritam (poglavlje 2.10).

7. čas

Svi najkraći putevi: Flojd-Varšalov algoritam. Tranzitivno zatvorenje grafa (poglavlje 2.11). Osnovni i prošireni Euklidov algoritam. Rešavanje linearnih Diofantovih jednačina (poglavlje 3.1). Faktorizacija broja (poglavlje 3.2.1 i 3.2.3).

8. čas

Multiplikativne funkcije: Ojlerova funkcija, funkcije delilaca (poglavlje 3.3.1 i 3.3.2). Modularna aritmetika, Ojlerova i mala Fermaova teorema. Modularni multiplikativni inverz. Kineska teorema o ostacima (poglavlje 3.4). RSA kriptografija (poglavlje 3.5).

9. čas

Brza Furijeova transformacija (poglavlja 3.6.1, 3.6.2, 3.6.3). Heširanje niski (poglavlje 4.1).

10. čas

z-niz (poglavlje 4.2). Algoritam KMP. Ispitivanje periodičnosti niske (poglavlje 4.3).

11. čas

Osnovni geometrijski algoritmi (poglavlje 5.1). Preseci horizontalnih i vertikalnih duži (poglavlje 5.2). Konstrukcija prostog mnogougla (poglavlje 5.3).

12. čas

Pripadnost tačke unutrašnjosti mnogougla (poglavlje 5.4). Algoritmi za konstrukciju konveksnog omotača: direktni algoritam, uvijanje poklona, Grejemov algoritam, brzi algoritam (poglavlje 5.5).

Literatura

• Konstrukcija i analiza algoritama, skripta u html formatu
• Konstrukcija i analiza algoritama, skripta u pdf formatu
• Primer pitanja za teorijski test
• Spisak ispitnih pitanja u 2024/25.
• Video materijali sa predavanja održanih u školskoj 2020/21. godini

Zadaci po časovima

1. čas

Uvod u napredne strukture podataka. Opisi problema.

• Naivni autocomplete
• Naivna suma raspona
• Suma raspona preko prefiksnih suma
• Disjunktni skupovi preko povezane liste

2. čas

Prefiksna drveta. Disjunktni skupovi.

• Najduži zajednički prefiks
• Složene reči
• Par koji daje najveći XOR
• Autocomplete
• Osvoji region
• Odnosi

3. čas

Segmentna drveta. Fenvikova drveta

• Berza
• Funkcije
• Broj inverzija
• Maksimalan proizvod
• Karte
• Temperatura

4. čas

Reprezentacije grafa. Pretraga u dubinu. Pretraga u širinu.

• Korensko drvo
• Zmije i lestve
• Dijametar drveta
• Čudna mreža
• Kružni autobusi

5. čas

Mostovi. Artikulacione tačke. Pretraga.

• Usmeravanje puteva
• Uklanjanje čvorova
• Kose crte
• Bipartitan graf

6. čas

Topološko sortiranje. Komponente jake povezanosti.

• Usmeri grane
• Dodaj grane
• Broj puteva
• Raskrsnice
• Svetiljke
• Polupovezanost

7. čas

Najkraći putevi od zadatog čvora.

• Aerodromi
• Ugnježdene kutije
• Arbitraža dobiti
• Autoputevi

8. čas

Ojlerovi ciklusi. Najkraći putevi između svaka dva čvora. Minimalno povezujuće drvo.

• Lavirint
• Nadogradnja mreže
• Igra uklanjanja čvorova
• Turistički vodič
• Bitke
• Tačke u ravni

9. čas

Prosti brojevi. Faktorizacija. Ojlerova funkcija. Euklidov algoritam.

• Prost trougao
• Zbir prostih prost
• Dopuna do potpunog kvadrata
• Proizvodi potpuni kvadrati
• Ojlerova funkcija
• Bilijar iz ćoška

10. čas

Euklidov algoritam. Prošireni Euklidov algoritam. RSA kriptosistem.

• Modularni inverz
• Torta
• Učenici na istim sedištima
• RSA

11. čas

Kineska teorema o ostacima. Niske. Rabin-Karpov algoritam.

• Kineska teorema
• Svi različiti
• ASCII umetnost

12. čas

Algoritmi za obradu teksta. KMP algoritam. Z algoritam. Manačerov algoritam.

• Nula xor
• Broj palindroma
• Dopuna do palindroma
• Cirkularna niska

13. čas

Geometrijski algoritmi. Pripadnost tačke mnogouglu. Konstrukcija konveksnog omotača.

• Ribice
• Obim omotača
• Galsko selo

Primer ispita

• 1. zadatak
• 2. zadatak
• 3. zadatak

Literatura za predavanja

• Konstrukcija i analiza algoritama, skripta u html formatu
• Konstrukcija i analiza algoritama, skripta u pdf formatu

Dodatno

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