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
  • teorijski test: 10 poena
  • usmeni ispit: 40 poena

Pragovi:

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

Predavanja po časovima

1. čas
Prefiksno drvo. Strukture podataka za predstavljanje disjunktnih skupova. Statički upiti raspona. Dinamički upiti raspona. Segmentno drvo.
2. čas
Fenvikovo drvo. Ažuriranje segmenata. Lenjo segmentno drvo.
3. čas
Pojam grafa i osnovna terminologija. Reprezentacije grafa. Pretraga u dubinu. Pretraga u širinu.
4. čas
Mostovi i artikulacione tačke u grafu. Komponente jake povezanosti u grafu: Tardžanov algoritam (raspored komponenti).
5. čas
Tardžanov algoritam (izdvajanje komponenti, određivanje baznih čvorova). Topološko sortiranje. Ojlerovi i Hamiltonovi ciklusi.
6. čas
Hirholcerov algoritam za određivanje Ojlerovih ciklusa. Težinski grafovi. Najkraći putevi iz zadatog čvora: aciklički grafovi, grafovi sa nenegativnim granama: Dajkstrin algoritam.
7. čas
Najkraći putevi iz zadatog čvora: Belman-Fordov algoritam. Konstrukcija minimalnog povezujućeg drveta: Primov, Kruskalov algoritam. Svi najkraći putevi: induktivni pristup, Flojd-Varšalov algoritam. Tranzitivno zatvorenje grafa.
8. čas
Prošireni Euklidov algoritam. Faktorizacija broja. Multiplikativne funkcije: Ojlerova funkcija.
9. čas
Multiplikativne funkcije: funkcije delilaca. Modularna aritmetika. Mala Fermaova i Ojlerova teorema. Modularni multiplikativni inverz. RSA kriptografija.
10. čas
Kineska teorema o ostacima. Direktna i inverzna Furijeova transformacija. Heširanje niski.

Literatura

Zadaci po časovima

1. čas
Uvod u napredne strukture podataka. Opisi problema.
2. čas
Prefiksna drveta. Disjunktni skupovi.
3. čas
Segmentna drveta. Fenvikova drveta
4. čas
Reprezentacije grafa. Pretraga u dubinu. Pretraga u širinu.
5. čas
Mostovi. Artikulacione tačke. Pretraga.
6. čas
Topološko sortiranje. Komponente jake povezanosti.
7. čas
Najkraći putevi od zadatog čvora.
8. čas
Ojlerovi ciklusi. Najkraći putevi između svaka dva čvora. Minimalno povezujuće drvo.
9. čas
Prosti brojevi. Faktorizacija. Ojlerova funkcija. Euklidov algoritam.
10. čas
Euklidov algoritam. Prošireni Euklidov algoritam. RSA kriptosistem.

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 nadoknade za vežbe kod Matije

Nadoknada otkazanih vežbi za obe grupe biće u sredu 15.05.2024. u učionici N202, sa početkom u 10:00.

09. 05. 2024.

Otkazivanje vežbi kod Matije za sredu 24.04.2024.

Vežbe za obe grupe kod Matije u sredu 24.04.2024. se otkazuju zbog bolesti asistenta. Termin nadoknade biće određen u dogovoru sa studentima (najverovatije posle praznika).

23. 04. 2024.

Promena termina vežbi kod Matije

Vežbe koje su se održavale sredom od 14:00 do 16:00 u N202, održavaće se od 15:00 do 17:00 u istoj učionici.

10. 03. 2024.

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