| Dizajn i analiza algoritama (nov naziv, obavezan predmet po novom statutu)
- stari statut - Algoritmi i strukture podataka (izborni kurs na IV godini R smera)
Asistent:
Milan Mitreski
Termin:
predavanja - ponedeljak 15h - N sale
Obavestenja:
Gradivo predjeno na kursu 2026/2027:
- 0. cas: [predjeno na vezbama] 1.1. Prefiksno drvo (do strane 21)
- 1. cas: 1.3. Union-find; 1.4. Upiti raspona; 1.4.2.1. Segmentno drvo (do strane 76)
- 2. cas: 1.4.3.3. Lenjo segmentno drvo; 2. Grafovi; 2.1. osnovni pojmovi; 2.2. predstavljanje grafa; 2.3. Pretraga neusmerenog grafa u dubinu (do strane 124, poglavlje 2.3.1.)
Materijali za kurs:
Podela poena i organizacija polaganja:
- Dva dela teorijskog ispita 2 x 20 poena
- Dva dela prakticnog ispita 2 x 20 poena
- Seminarski rad - 20 poena
- Polaganje i teorije i zadataka bice podeljeno na dva dela i bice organizovano u kolokvijumskim nedeljama (detaljne informacije bice na sajtu asistenta)
- Prag - 40% za pojedinacnu obavezu (8 od 20);
prag - 50% u sumi na predispitnim obavezama (30 od 60); za oba kolokvijuma sa zadacima i seminarskim radom
Gradivo predjeno na kursu 2024/2025:
SVI MATERIJALI SU PREUZETI SA SAJTA PROFESORKE VESNE MARINKOVIC
- Materijal za 1. i 2. cas: Prefiksno drvo, disjunktni podskupovi, segmentno drvo
Dopuna: Mape u jeziku C++ (Sana Stojanovic Djurdjevic, AiSP - I smer)
- Materijal za 3. cas: Fenvikovo drvo, lenjo segmentno drvo
Dopuna: Oznaceni zapisi celih brojeva (Jovana Kovacevic, UOR1), Operacije u binarnom brojnom sistemu
- Materijal za 4. cas: Algebarski algoritmi
Dopuna: Racunanje modula u C/C++-u
- Materijal za 5. cas: Multiplikativni inverz, kineska teorema o ostacima, brza Furijeova transformacija
Dopuna: Razlicite primene brze Furijeove transformacije
- Materijal za 6. cas: Hesiranje niski, Z-algoritam
- Materijal za 7. cas: KMP algoritam, periodicnost niske, Manacerov algoritam
- Materijal za 8. cas: Osnovni geometrijski algoritmi
- Materijal za 8. i 9. cas: Napredni geometrijski algoritmi
Dopuna: Michiel Smid, Computing intersections
- Materijal za 9. cas:
Podsecanje sa osnovnog kursa (posebno obratiti paznju na DFS algoritam): Reprezentacija grafova, DFS i BFS pretraga
- Materijal za 10. cas:
Topolosko sortiranje grafa (podsecanje sa osnovnog kursa); Artikulacione tacke i mostovi; Komponente jake povezanosti grafa;
- Materijal za 11. cas: Najkraci putevi; Tranzitivno zatvorenje; Putevi i ciklusi u grafovima;
Sadrzaj kursa:
-
Osnovna zamisao ovog kursa jeste da dopuni znanje studenata na R smeru u
skladu sa algoritamskim predmetima koji se drze na I smeru. Za pocetak to
znaci da ce biti predjeno svo gradivo sa kursa AiSP (II godina I smera)
koje nije obradjeno u kursu KiAA (III godina R smera).
- Osnovno gradivo:
- elementarne tehnike za poboljsanje slozenosti (tema 3)
- tehnika pokazivaca (tema 4)
- induktivno-rekurzivna konstrukcija (tema 5)
- podeli pa vladaj (tema 8)
- pretraga: gruba sila, bektreking (tema 9)
- dinamicko programiranje (tema 10)
- gramzivi algoritmi (tema 11)
- Dodatno, bice obradjene neke teme sa kursa KiAA (sa I smera).
- Napredno gradivo (bice predjene neke od narednih tema, ne sve):
- Prefiksno drvo, disjunktni podskupovi, segmentno drvo (tema 1)
- Fenvikovo drvo, lenjo segmentno drvo (tema 2)
- Topolosko sortiranje grafa. Arikulacione tacki i mostovi.
Komponente jake povezanosti grafa (tema 4)
- Modularna aritmetika. Faktorizacija. Ojlerova funkcija. Broj i
zbir delilaca. Prosireni Euklidov algoritam (tema 7)
- Modularni multiplikativni inverz. Kineska teorema o ostacima. FFT. (tema 8)
- Osnovni geometrijski algoritmi. Tacka u prostom mnogouglu.
Konstrukcija prostog mnogougla (tema 11)
- Konveksni omotac. Preseci horizontalnih i vertikalnih duzi (tema 12)
Literatura i reference:
|