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 za usmeni

1. Kompjuteri i programski jezici – istorija i principi
2. Bubble sort
3. Insertion sort
4. Selection sort
5. Merge sort
6. Quick sort
7. Složenost algoritama i asimptotske oznake
8. Rekurzija
9. Pregled algoritama za sortiranje
10. Protraživanje
11. Matrice
12. Povezane liste
13. Stack pomoću povezanih listi
14. Queue pomoću povezanih listi
15. Stack pomoću nizova
16. Queue pomoću nizova
17. Grafovi, osnovne definicije i teoreme
18. Strukture podataka za grafove
19. Breadth first search (BFS)
20. Algoritmi nad grafovima (stepen, diametar, path, …)
21. Depth first search (DFS)
22. DFS forest, tipovi grana
23. DFS forest, topološko sortiranje
24. DFS forest, jako povezane komponente
25. Minimalno pokrivajuće drvo, Kruskal
26. Minimalno pokrivajuće drvo, Prim
27. Binarna drva, LC-RC reprezentacija
28. Binary search tree sort
29. Problem angažovanja, mađarska metoda
30. 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 23. XI 2024. 17:00 A1, A2      

 

Literatura

  1. Početak knjige
  2. Folije
  3. Ostalo
  4. Introduction to Algorithms, fourth edition