AI.{13.20}.IAM002.Diskretne i kombinatorne metode za ra─Źunarsku grafiku


SEMESTAR 3
ESPB 4
FOND ─îASOVA 2+2

Sadr┼żaj

1 Analiza algoritama

1.1 Algoritmi za pretra┼żivanje
1.2 Asimptotske oznake
1.3 Slo┼żenost algoritama
1.4 Rekurzija
1.5 Algoritmi za sortiranje
1.5.1 Bubble sort
1.5.2 Insertion sort
1.5.3 Selection sort
1.5.4 Merge sort
1.5.5 Quick sort

2 Apstraktni tipovi podataka (ADT)

2.1 Matrice
2.2 Polinomi
2.3 Stack
2.4 Queue
2.5 Primene

3 Grafovi kao ADT

3.1 Osnovne definicije
3.2 Strukture podataka za grafove
3.3 Pretra┼żivanje u ┼íirinu (BFS) i primene
3.4 Pretra┼żivanje u dubinu (DFS) i primene
3.5 Minimalno pokrivaju─çe drvo (MST)
3.6 Binarna drva
4 Primene
3.7 Problem anga┼żovanja
3.8 Problem trgova─Źkog putnika

Pitanja:

1. Bubble sort
2. Insertion sort
3. Selection sort
4. Merge sort
5. Quick sort
6. Slo┼żenost algoritama i asimptotske oznake
7. Rekurzija
8. Pregled algoritama za sortiranje
9. Matrice
10. Povezane liste
11. Stack pomo─çu povezanih listi
12. Queue pomo─çu povezanih listi
13. Stack pomo─çu nizova
14. Queue pomo─çu nizova
15. Grafovi, osnovne definicije i teoreme
16. Strukture podataka za grafove
17. Breadth first search (BFS)
18. Algoritmi nad grafovima (stepen, diametar, path, …)
19. Depth first search (DFS)
20. DFS forest, tipovi grana
21. DFS forest, topološko sortiranje
22. DFS forest, jako povezane komponente
23. Minimalno pokrivaju─çe drvo, Kruskal
24. Minimalno pokrivaju─çe drvo, Prim
25. Binarna drva, LC-RC reprezentacija
26. Binary search tree sort
27. Problem anga┼żovanja, ma─Ĺarska metoda
28. Problem trgova─Źkog putnika

Na─Źin polaganja

Predmet se sastoji iz zadataka koji se pola┼żu pismeno i teorije koja se pola┼że na usmenom delu.

Pismeni delovi se pola┼żu u toku slu┼íanja nastave preko kolokvijuma i u svakom ispitnom roku u terminu za koji je prijavljen ispit.

Va┼żenje pismenog dela polo┼żenog preko kolokvijuma je do kraja kalendarske godine u kojoj je odslu┼ían predmet ili do poni┼ítavanja izlaskom na pismeni ispit i re┼íavanjem zadataka iz odgovaraju─çeg dela.

Va┼żenje pismenog dela polo┼żenog u ispitnom roku je do usmenog ispita u tom roku, najdu┼że 7 dana.

Postoji minimalan broj bodova koji se mora osvojiti da bi se neki deo pismenog ispita ra─Źunao kao polo┼żen.

Usmeni ispit se odr┼żava par dana posle pismenog ispita, u terminu dogovorenom na pismenom ispitu. Na usmeni ispit su pozvani studenti koji su prijavili ispit u tom roku i imaju polo┼żene pismene delove.

Ocene se formiraju na osnovu osvojenih bodova, u skladu sa Statutom FTN-a: 51+ -> 6, 61+ -> 7, …

  Deo 1 Deo 2 Usmeni suma
MAX 40 40 20 100
MIN 18 18 0 51
Datum kolokvijuma

3. XII 2023.