| Algoritmi i strukture podataka (izborni kurs na IV godini R smera)
Dizajn i analiza algoritama (nov naziv, obavezan predmet po novom statutu)
Asistent:
Andrija Urosevic
Termin:
predavanja - sreda od 12h
Obavestenja:
- [02.10.2023.] Nastava ce poceti nakon upisa u drugoj nedelji oktobra, 11.10.2023.
- Pismeni ispit u januarskom roku vazi i u februarskom za izlazak na usmeni.
- Link za pristup online konsultacijama: https://matf.webex.com/meet/sana
Gradivo predjeno na kursu:
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:
|