UVOD U ALGORITME I STRUKTURE PODATAKA

R smer

Kurs Uvod u algoritme i strukture podataka je kurs na trećoj godini R smera. Cilj ovog predmeta je sticanje osnovnih znanja o osnovnim strukturama podataka, njihovom korišćenju i implementaciji, kao i o osnovnim strategijama konstrukcije algoritama, analizi njihove složenosti i korektnosti. U okviru kursa se proučavaju sledeće teme:

  • analiza korektnosti i složenosti algoritama
  • sortiranje, binarna pretraga i tehnika dva pokazivača
  • induktivno-rekurzivna konstrukcija
  • osnovne strukture podataka: korišćenje i implementacija
  • različite strategije konstrukcije algoritama: gruba sila, dekompozicija, bektreking, dinamičko programiranje, pohlepni 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 7 poena na teorijskom testu

Predavanja po časovima

1. čas
Uvod. Korektnost algoritma i veza sa induktivno-rekurzivnom konstrukcijom. Dokaz korektnosti rekurzivnih i iterativnih funkcija. Složenost algoritama. Merenje vremena izvršavanja. Asimptotska analiza složenosti.
2. čas
Složenost nekih čestih oblika petlji. Sumiranja. Rekurentne jednačine. Tehnike za poboljšanje složenosti: zamena iteracije formulom, odsecanje.
3. čas
Tehnike za poboljšanje složenosti: odsecanje, inkrementalnost, prefiksne sume, razlike susednih elemenata, sortiranje.
4. čas
Binarna pretraga: traženje elementa za zadatom vrednošću, traženje prelomne tačke, binarna pretraga po rešenju. Tehnika dva pokazivača.
5. čas
Induktivno-rekurzivna konstrukcija: zvezda, apsolutni pobednik, broj rastućih segmenata. Ojačavanje induktivne hipoteze.
6. čas
Klasifikacija struktura podataka. Strukture podataka - korišćenje: skup, mapa, stek.
7. čas
Strukture podataka - korišćenje: red, red sa dva kraja, red sa prioritetom.
8. čas
Strukture podataka - implementacija: dinamički niz, lista, stek, red, dek, hip, heš tabele.
9. čas
Dekompozicija: Quick Sort, Merge Sort, k-ti najveći element, zbir k najvećih elemenata, maksimalni zbir segmenta, Karacubin algoritam za množenje polinoma, najbliži par tačaka.
10. čas
Generisanje kombinatornih objekata: sledeći podskup, svi podskupovi leksikografski, svi podskupovi, sledeća varijacija, sve varijacije. Bektreking: raspoređivanje n dama na šahovskoj tabli, broj podnizova datog zbira.
11. čas
Bektreking: merenje sa n tegova, bojenje grafa sa 3 boje, bojenje grafa minimalnim brojem boja. Dinamičko programiranje: n-ti Fibonačijev broj, ranac 0-1.
12. čas
Dinamičko programiranje: broj pojavljivanja podniske, edit rastojanje niski. Gramzivi algoritmi: reč u reč precrtavanjem slova, žaba na kamenju, razlomljeni problem ranca, raspored aktivnosti, Hafmanovo kodiranje.

Literatura

Rokovi

Primer praktičnog dela ispita za studente koji studiraju po novoj akreditaciji
Primer praktičnog dela ispita za studente koji studiraju po staroj akreditaciji
Primer praktičnog dela ispita za studente sa L smera

Zadaci po časovima

2. čas
2. čas
3. čas
3. čas
4. čas
4. čas
5. čas
5. čas
6. čas
6. čas
7. čas
7. čas
8. čas
8. čas

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

Drugi teorijski test

Drugi teorijski test neće biti održan u najavljenom terminu, zbog najavljene obustave nastave u narednoj nedelji. Novi termin testa biće naknadno poznat.

7. 12. 2024.

Drugi teorijski test

Drugi teorijski test biće održan u utorak 10.12. u terminu drugog časa predavanja.

29. 11. 2024.

Rezultati prvog kolokvijuma

Rezultati prvog kolokvijuma se mogu pronaći ovde. Uvid u radove je moguć putem mejla ili u pauzama između časova vežbi.

23. 11. 2024.

Prvi kolokvijum

Prvi kolokvijum će se održati u subotu 23.11.2024. od 12h na Studentskom Trgu. Trajanje kolokvijuma je 1h.

21. 11. 2024.

Odlaganje vežbi

U petak 22.11.2024. neće biti vežbi od 13h. Časovi vežbi se pomeraju za 15h, dok se nadoknada izgubljenog časa odlaže za petak 29.11.2024. od 15h u učionici N202.

21. 11. 2024.

Prijava za kolokvijum

Ukoliko želite da radite kolokvijum iz Uvoda u algoritme i strukture podataka u subotu 23.11.2024. molimo Vas da popunite
sledeću formu

18. 11. 2024.

Rezultati testa

Rezultati prvog teorijskog testa mogu se naći ovde

Uvid u radove je moguć u pauzama časova predavanja u utorak 19.11.

16. 11. 2024.

Odlaganje vežbi

U sredu 13.11.2024. i petak 15.11.2024. neće biti vežbi. Nadoknada će se održati u petak 22.11.2024. od 15h u N salama,
u učionici N202.

10. 11. 2024.

Primer testa

Primer prvog teorijskog testa može se naći ovde

6. 11. 2024.

Prvi teorijski test

Prvi teorijski test biće održan u utorak 12.11. u terminu drugog časa predavanja.

31. 10. 2024.

Matematički fakultet, Univerzitet u Beogradu
školska 2024/25. godina