Algoritmi i strukture podataka (izborni kurs na IV godini R smera)


Asistent: Vladan Kovacevic

Termin: utorkom od 13h

 

Obavestenja:

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: