Stručni studij

Nazad   Raspored   Engleski

Algoritmi s grafovima SIR401-17

ECTS 5 | P 30 | A 15 | L 15 | K 0 | ISVU 175204 | Akademska godina: 2019./2020.

Grupe studenata

Prikaži sve grupe na predmetu

Nastavnici na predmetu

BAUMGARTNER ALFONZO, nositelj

Ciljevi predmeta

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:

Dopunska literatura

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

Način praćenja kvalitete i uspješnosti izvedbe kolegija

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

Ishodi 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