Studenti će se upznati s definicijom grafa kao strukture podataka, njegovim efikasnim prikazom u računalu, te različitim posebnim vrstama grafova. Kroz poznatije probleme s grafovima i algoritme za njihovo rješavanje studenti će se upoznati na idejnoj razini, ali isto tako i praktično implementirati neke od algoritama i tako naučiti koristiti strukturu podataka graf za modeliranje stvarnih fizikalnih problema.

Uvjeti za upis predmeta

Ostvareni uvjeti za upis druge godine studija.

Sadržaj

Uvod i osnovni pojmovi. Matematička definicija grafa i primjeri. Vrste grafova. Efikasni načini pohrane grafova u računalu. Rijetko popunjeni grafovi. Problem obilaska grafa. BFS i DFS agoritmi. Problem povezanosti čvorova kod grafa. Algoritam pronalaženja čvrsto povezanih komponenti grafa. Problem Eulerovog ciklusa. Problem najmanjeg razapinjućeg stabla. Problem najkraćih puteva. Bellman-Fordov i Dijkstrin algoritam. NP-složeni problemi s grafom. Problem bojanja grafa. Problem trgovačkog putnika. Definicija mreže. Problem maksimalnog protoka kroz mrežu.

Obveze studenata

Definirano Okvirima kriterija ocjenjivanja studenata FERIT-a i stavkom 1.9

Praćenje rada studenata

Definirano Okvirima kriterija ocjenjivanja studenata FERIT-a i stavkom 1.9

Osnovna literatura

1. 1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introduction to Algorithms (3rd ed.) MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (2009) [1990]

Pretraži literaturu na:

1. 1 R. Sedgewick Algorithms in C++ Part 5: Graph Algorithms (3rd Edition) Addison-Wesley Professional, 2002.

2. 2 Shimon Even Graph Algorithms Cambridge University Press, 2011, ISBN: 1139504150, 9781139504157

Provođenje sveučilišnih anketa o nastavnicima (pristup prema studentima, transparentnost kriterija, motivacija na izvršavanje aktivnosti, jasnoća izlaganja, i sl.). Provođenje fakultetskih anketa o predmetima (nakon položenog predmeta samoevaluacija studenata o usvojenim ishodima učenja, te o opterećenosti u usporedbi s ECTS-ima aktivnosti i predmeta u cjelini).

Pregled ishoda učenja, nastavnih metoda i procjena ishoda učenja

1. opisati strukturu podataka graf te poznatije probleme i algoritme s grafovima

2. prepoznati strukturu grafa kod modeliranja mnogih već poznatih problema, te ju koristiti za rješavanje tih problema

3. provesti analizu složenosti za poznatije algoritme s grafovima

4. ugraditi i rabiti različite algoritme za probleme poput najkraćeg puta, Eulerovog ciklusa i drugih

5. primijeniti stečena znanja u oblikovanju programske podrške gdje je neizbježno korištenje grafova

Aktivnosti studenta: Vidi tablicu aktivnosti