Diskretne strukture i algoritmi

Osnovni cilj kolegija je upoznati studente s diskretnim matematičkim strukturama koje su neophodne za shvaćanje i recepciju kvantitativnih aspekata znanja u informacijskim znanostima. Cilj kolegija je kod studenata razviti sposobnost izražavanja matematičkim jezikom kao i razviti apstraktno mišljenje i logičko rasuđivanje. Studenti će se pripremiti na algoritamski način razmišljanja kako bi mogli pratiti brzi razvoj i prodornost informacijsko-komunikacijske tehnologije te će im se pružiti znanje na temelju kojega će moći samostalno ili timski rješavati cjelovite probleme vezane uz primjenu algoritama u informacijskim znanostima.

Po završetku nastave iz navedenog kolegija student će moći:

• upoznati osnovne ideje i metode teorije grafova na nizu ilustracija
• razlikovati jednostavne i složene vrste algoritama i njihove primjene
• objasniti utjecaj strukture podataka na izvedbu i brzinu algoritama
• rješavati raznorodne probleme vezane uz primjenu pojedinih algoritama

Studenti će se upoznati sa diskretnim strukturama – apstraktnim matematičkim konačnim strukturama i mogućnostima njihove primjene u informacijskim znanostima. Na predavanjima će se obraditi odabrana poglavlja teorije grafova te će se predstaviti najpoznatiji algoritmi i njihove primjene.

Tijekom kolegija obradit će se sljedeće teme: Relacije na skupovima (podskup, pravi podskup, jednakost skupova); Partitivni skup; Operacije na skupovima (unija, presjek, razlika, komplement); Vennovi dijagrami; Skupovi brojeva; Kompleksni brojevi; Relacije, binarne relacije; Matrica incidencije; Funkcije; Relacija ekvivalencije; Kongruencije; Operacije s kongruencijama; Primjena kongruencije na International Standard Book Number; Primjena kongruencija u kriptografiji; Rekurzivno zadani nizovi; Fibonaccijev niz; Homogene rekurzivne relacije; Karakteristični polinom; Binomni teorem; Euklidov algoritam; Hornerova shema; Složenost algoritma; Pretraživanje i sortiranje; Slijedno i binarno pretraživanje; Sortiranje umetanjem; Mjehuričasto sortiranje; Sortiranje spajanjem; Quicksort; Grupa; Komutativna (Abelova) grupa; Izomorfizam grupa; Prsteni i polja; Polje realnih brojeva; Vektorski prostor matrica; Primjena grupa u teoriji kodiranja; Definicija grafa i osnovna svojstva grafova; Stupanj vrha, višestruki bridovi, pseudograf; Podgraf; Specijalni grafovi: potpuni graf, bipartitni graf, potpuni bipartitni graf; Regularni grafovi; Izomorfizam grafova; Šetnja, zatvorena šetnja, staza u grafu; Eulerova tura kao zatvorena Eulerova staza i Eulerov graf; Povezani grafovi; Problem  Koeningsberških mostova; Hamiltonov ciklus; Hamiltonov graf; Matrica incidencije i matrica susjedstva; Algoritam za nalaženje Eulerove staze i ciklusa; Problem deadlockova; Težinski graf; Najkraći put između dva vrha u težinskom grafu; Primjene težinskih grafova; Problem trgovačkog putnika; Dijkstrin algoritam; Floyd-Warshallov algoritam; Problem kineskog poštara; Eulerizacija grafa; Stablo; Svojstva stabla; Binarno stablo; Algoritam sortiranja; Minimalno razapinjuće stablo; Razapinjući podgraf; Težina stabla; Kruskalov algoritam; Primov algoritam; Pretraživanje stabla; Prolasci grafom i stablom; Usmjereni graf; Usmjerena šetnja, usmjereni put; Metoda kritičnog puta - CPM, PERT; Problem četiri boje; Bojenje vrhova i bridova grafa; Kromatski broj grafa; Klike i broj klike.

predavanja, seminari i radionice, vježbe

NASTAVNA METODA	AKTIVNOST STUDENTA	ISHOD UČENJA	METODA PROCJENE
predavanja	slušanje predavanja i sudjelovanje u raspravama	upoznati osnovne ideje i metode teorije grafova na nizu ilustracija	pismeni ispit
seminarsko izlaganje i radionice	sustavno opažanje, slušanje izlaganja, analiza literature	razlikovati jednostavne i složene vrste algoritama i njihove primjene	seminarski rad
praktični rad na vježbama	rješavanje problemskih zadataka	objasniti utjecaj strukture podataka na izvedbu i brzinu algoritama	pohađanje nastave i aktivnost studenata u nastavi
praktični rad na vježbama	rješavanje problemskih zadataka	rješavati raznorodne probleme vezane uz primjenu pojedinih algoritama	pohađanje nastave i aktivnost studenata u nastavi

Pismeni ispit, Pohađanje nastave, Seminarski rad, Usmeno izlaganje

usmeno i pismeno

Element	Opterećenje u ECTS	Udio u ocjeni
Pismeni ispit	2	60%
Pohađanje nastave	1,5	0%
Seminarski rad	1,3	30%
Usmeno izlaganje	0,2	10%

Iz svih elemenata praćenja i provjeravanja student može ostvariti maksimalno 100 ocjenskih bodova, što čini 100% ocjene. Za prolaznu ocjenu student treba ostvariti minimalno 60 ocjenskih bodova ili 60% ocjene.

Skala je ocjenjivanja sljedeća: 60% - 69,9%  = dovoljan (2), 70% - 79,9%  = dobar (3), 80% - 89,9%   = vrlo dobar (4), 90% - 100% = izvrstan (5).

Studenti su obvezni pohađati 70 % održanih nastavnih sati. Ako student ima 5 ili više izostanaka (jedan izostanak iznosi 2 nastavna sata), neće dobiti potpis, kao ni ukoliko ukupno ostvari manje od 40% ocjene.

1. Divjak, B.; Lovrenčić, A. Diskretne strukture s teorijom grafova. Varaždin: TIVA-FOI, 2005.
2. Goodaire, E. G.; Parmenter, M. M. Discrete Mathematics with Graph Theory. New York: Prentice Hall, 2002.

1. Discrete Discoveries. URL: http://mathforum.org/workshops/sum96/discrete/toc.html
   2. Graph Theory Resources. URL: http://www.graphtheory.com/
2. Math Archives: Discrete Mathematics. URL: http://archives.math.utk.edu/topics/discreteMath.html

• Provedba jedinstvene sveučilišne ankete među studentima za ocjenjivanje nastavnika koju utvrđuje Senat Sveučilišta
• Praćenje i analiza kvalitete izvedbe nastave u skladu s Pravilnikom o studiranju i Pravilnikom o unaprjeđivanju i osiguranju kvalitete obrazovanja Sveučilišta.