FOI Nastava - Diskretne strukture s teorijom grafova

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Diskretne strukture s teorijom grafova

Discrete Structures and Graph Theory
2020/2021

6 ECTSa

Informatika u obrazovanju 1.3 (IUO)
Informacijsko i programsko inženjerstvo 1.3 (IPI)
Organizacija poslovnih sustava 1.3 (OPS)
Baze podataka i baze znanja 1.3 (BPBZ)

Katedra za kvantitativne metode

1. semestar

Osnovne informacijemdi-information-variant

Izvođači nastavemdi-account-group

Nastavni plan i programmdi-clipboard-text-outline

Model praćenjamdi-human-male-board

Ispitni rokovimdi-clipboard-check-outline

Rasporedmdi-calendar-clock

Konzultacijemdi-account-voice

Izvođenje kolegija

Studij	Semestar	Obavezan
Informatika u obrazovanju 1.3 (IUO)	1	izborni
Informacijsko i programsko inženjerstvo 1.3 (IPI)	1	obavezan
Organizacija poslovnih sustava 1.3 (OPS)	1	obavezan
Baze podataka i baze znanja 1.3 (BPBZ)	1	izborni

Cilj kolegija

Upoznavanje i produbljivanje znanja studenata o jezgri matematičkih znanja, nužnih za razvoj informacijskih znanosti. Ta se jezgra većim dijelom podudara s poljem diskretne matematike i teorijom grafova. Jedan od ciljeva ovog kolegija jest da se kod studenata razvije mehanizam rigoroznog matematičkog razmišljanja, što je nužno za svakog tko želi pratiti zahtjeve vrlo dinamičke informatičke discipline. Cilj je također da student razvije osjećaj za različite stupnjeve matematičke strogosti i formalizma i nauči ih upotrebljavati primjereno problemskoj situaciji. Poglavlja odabrana za ovaj kolegij namijenjena su svima onima koji se žele baviti razvojem algoritama, primjenom postojećih algoritama vezanih uz teoriju brojeva i grafove, ali i naprednijom primjenom i istraživanjima u informatici.

Preduvjeti

Kolegij nema definirane preduvjete

Norma kolegija

Predavanja

30 sati

Seminar

30 sati

Nastavnik	Uloga na kolegiju	Oblik nastave	Tjedana	Sati	Grupa
Divjak Blaženka	Nositelj	Predavanja	10	3	1
Maretić Marcel	Nositelj	Seminar	10	3	2
Horvat Damir	Suradnik	Seminar	10	3	2

Sadržaj predavanja

Matematički modeli i metode dokazivanja tvrdnji u matematici
Matematički modeli. Klasična propozicijska i predikatna logika. Logička struktura matematičke tvrdnje. Vrste matematičkih dokaza: Direktni dokaz. Dokaz po slučajevima. Dokaz kontrapozicijom. Dokazivanje (niza) ekvivalentnih tvrdnji. Dokaz kontradikcijom. Obaranje tvrdnje protuprimjerom. Dokazivanje matematičkom indukcijom na prebrojivim strukturama.
Skupovi i relacije
Prebrojivi i neprebrojivi skupovi. Paradoksi teorije skupova. Relacije, binarne relacije. Istaknuta svojstva binarnih relacija. Matrica incidencije. Funkcije (domena, rang, injekcija, surjekcija, bijekcija. Kompozicija relacija i inverzi relacija.
Uređajne relacije i relacija ekvivalencije
Parcijalni uređaj. Usporedivost elemenata u parcijalno-uređenom skupu. Pojam minimalnog i maksimalnog elementa, te najveće gornje i donje međe u parcijalno uređenom skupu. Hasseovi dijagrami i njihova primjena. Linearni ili totalno uređeni skup. Leksikografski uređaj. Dobro uređeni skup. Mreže (engl. Lattice). Relacija ekvivalencije. Kvocijentni skup relacije ekvivalencije. Particija skupa inducirana relacijom ekvivalencije.
Elementarna teorija brojeva i primjene u kriptografiji
Djeljivost. Prosti brojevi. Kongruencije modulo n. Modularna aritmetika. Prošireni Euklidov algoritam. Rješavanje linearnih kongruencija. Kineski teorem o ostacima. Primjena kongruencija u kodiranju (ISBN, UPC kodovi). Eulerova funkcija (totient). Modularno potenciranje. Primjene modularne aritmetike u modernoj kriptografiji (RSA kriptosustav). Digitalni potpis.
Matematički grafovi
Definicija grafa. Osnovni pojmovi. Stupanj vrha, višestruki bridovi, pseudograf (multigraf). Specijalni grafovi: potpuni graf, bipartitni, potpuni bipartitni graf, regularni, planarni graf. Eulerova propozicija (suma stupnjeva svih vrhova jednaka je dvostrukom broju bridova). Matrica incidencije i matrica susjedstva. Svojstva matrice susjedstva. Različiti oblici prikazivanja grafa u računalu. Izomorfizam grafova. Veza izomorfnih grafova preko matrice permutacija. Invarijante (izomorfizma) grafova. Šetnja, zatvorena šetnja, staza, put i ciklus. Karakterizacija bipartitnosti. Eulerova tura. Povezani graf. Karakterizacija Eulerovog grafa. Hamiltonov graf. Otvoreni problem nužnog i dovoljnog uvjeta za Hamiltonovosti grafa. Petersenov graf. Traženje Eulerove staze ili ture. Brojanje šetnji.
Težinski grafovi
Težinski graf i njegove primjene. Problem najkraćeg puta. Dijkstrin algoritam. Problem trgovačkog putnika. Udaljenost u težinskom grafu Floyd-Warshallov algoritam. Problem kineskog poštara. “Eulerizacija grafa”. Kwanov algoritam.
Stabla
Definicija stabla. Nekoliko karakterizacija. Šuma. Korjensko stablo. Binarno stablo. Binarno stablo pretraživanja. Algoritam sortiranja. Binarno stablo u prikazu algebarskih izraza. Minimalno razapinjuće stablo. Pojam podgrafa. Razapinjući podgraf. Težina stabla. Problem nalaženja minimalnog razapinjućeg stabla. Kruskalov algoritam. Primov algoritam. Usporedba i složenost Kruskalovog i Primovog algoritma. Pretraživanje stabla. Algoritmi traženja u grafu (DFS, BFS).
Usmjereni grafovi
Usmjereni graf. Usmjerena šetnja, usmjereni put. Turnir: definicija i svojstva. Postojanje usmjerenog Hamiltonovog puta u svakom turniru. Mreže i kritični putevi. Problem rasporeda. Metoda kritičnog puta - CPM, PERT. Primjene u vođenju i planiranju projekata. Usmjereni aciklički graf (DAG) i topološko sortiranje. Bellman-Fordov algoritam za traženje najkraćeg puta u usmjerenom grafu. Primjena. Transportna mreža. Protok i rez. Teorem o maksimalnom protoku i minimalnom rezu u transportnoj mreži. Ford-Fulkersonov algoritam za određivanje maksimalnog protoka u transportnoj mreži.
Bojanje grafova i sparivanja
Planarnost grafa. Problem četiri boje. Povijesni osvrt i Appel-Hakenovo rješenje. Bojenje vrhova grafa. Kromatski broj grafa. Primjena kromatskog broja grafa na slaganje rasporeda. Kromatski brojevi nekih poznatih grafova. Bridno bojanje grafa. Teoremi o kromatskom broju (Brooks, Vizing, Gupta i dr.). Sparivanje u grafovima. Maksimalno sparivanje u grafu. Sparivanje u bipartitnim grafovima. Hallov teorem.
Matematička teorija grafova s primjenama: Grafovi
Definicija grafa i osnovna svojstva grafova. Stupanj vrha, višestruki bridovi, pseudograf. Podgraf. Specijalni grafovi: potpuni graf, bipartitni graf, potpuni bipartitni graf. Regularni grafovi. Eulerova propozicija (suma stupnjeva svih vrhova jednaka je dvostrukom broju bridova). Broj vrhova neparnog stupnja je paran. Izomorfizam grafova. Veza izomorfnih grafova preko matrice permutacija. Invarijante izomorfnih grafova. Šetnja, zatvorena šetnja, staza u grafu.
Putevi i ciklusi
Eulerova tura kao zatvorena Eulerova staza i Eulerov graf. Povezani grafovi. Graf je Eulerov ako i samo ako je povezan i svaki mu je vrh parnog stupnja. Rješenje problema Koeningsberških mostova. Hamiltonov ciklus. Hamiltonov graf. Petersonov graf kao protuprimjer Hamiltonovog grafa. Otvoreni problem nužnog i dovoljnog uvjeta za Hamiltonov graf. Matrica incidencije i matrica susjedstva. Svojstva matrice susjedstva. Algoritam za nalaženje Eulerove staze i ciklusa. Problem deadlockova.
Težinski grafovi. Algoritmi najkraćeg puta.
Težinski graf. Najkraći put između dva vrha u težinskom grafu. Primjene težinskih grafova. Problem trgovačkog putnika. Traženje Hamiltonovog ciklusa najmanje težine. Dijkstrin algoritam i poboljšani Dijkstrin algoritam. Floyd- Warshallov algoritam. Usporedba ta dva algoritma, njihova složenost i mogućnosti primjene. Problem kineskog D-278 poštara u Eulerovom grafu i grafu koji nije Eulerov. “Eulerizacija grafa”. Primjeri rada algoritama.
Stabla
Stablo kao povezani graf koji ne sadrži niti jedan ciklus. Svojstva stabla. Šuma. Stablo s korijenom (korjensko stablo). Binarno stablo. Binarno stablo pretraživanja. Algoritam sortiranja. Binarno stablo u prikazu algebarskih izraza. Minimalno razapinjuće stablo. Pojam podgrafa. Razapinjući podgraf. Težina stabla. Problem nalaženja minimalnog razapinjućeg stabla. Algoritmi za minimalno razapinjuće stablo. Kruskalov algoritam. Primov algoritam. Usporedba i složenost Kruskalovog i Primovog algoritma. Pretraživanje stabla. Prolasci grafom i stablom.
Usmjereni grafovi
Usmjereni graf (digraph). Usmjerena šetnja, usmjereni put. Turnir: definicija i svojstva. Postojanje usmjerenog Hamiltonovog puta u svakom turniru. Mreže i kritični putevi. Problem rasporeda. Metoda kritičnog puta - CPM, PERT. Primjene u vođenju i planiranju projekata. Protoci i rezovi. Transportna mreža. Vrijednost protoka. Pojam frastućeg puta. Max flow – min cut teorem. Dokaz teorema. Primjeri primjene teorema. Algoritam za maksimalni protok transportne mreže.
Bojanje grafova
Problem četiri boje. Povijesni osvrt i Appel-Hakenovo rješenje. Bojenje vrhova grafa. Kromatski broj grafa. Primjena kromatskog broja grafa na slaganje rasporeda. Kromatski broj, ekvivalencija na grafovima, klase boje. Klike i broj klike. Kromatski brojevi nekih poznatih grafova. Teoremi o kromatskom broju. Bojanje bridova grafa. Kromatski broj grafa i primjeri. Teorem (Vizig, Gupta).
Sparivanje u grafovima
Sparivanje u grafovima. Maksimalno sparivanje u grafu. Sparivanje u bipartitnim grafovima. Hallov teorem.

Sadržaj seminara/vježbi

Seminari prate predavanja
Sadržajno seminari prate predavanja, ali se na razini ishoda fokusiraju na vježbu i primjenu. Na seminarima se rješavaju zadaci vezani uz teoriju obrađenu na predavanjima. Naglasak je, gdje god je to moguće, na praktičnim zadacima koji su vezani za realne probleme, posebno informatičke. Također se pokazuje na koji način je neki zadatak moguće riješiti u nekom programskom alatu ili jeziku kao što su npr. Python, SAGE, Octave, Maxima. Studenti također rade u timu na zahtjevnijem praktičnom zadatku iz područja diskretne matematike i/ili teorije grafova koji osim teoretske obrade uključuju i izradu ili napredno korištenje programskog rješenja, te analizu rješenja realnog problema.
Studenti također rješavaju dva praktična zadatka u Pythonu (ili SAGE-u, ili Maximi)
Jedan zadatak se odnosi na diskretnu matematiku i vezan je uglavnom za neku primjenu u teoriji brojeva i kombinatorici, a drugi zadatak je vezan uz teoriju grafova

Ishodi učenja kolegija

Definirati i klasificirati binarne relacije na diskretnim skupovima te ih koristiti u karakterističnim zadacima.
Definirati osnovne pojmove i koncepte iz teorije grafova i povezati ih s istaknutim problema iz teorije grafova.
Efikasno raditi u timu na modeliranju i rješavanju problema konceptima i algoritmima iz područja diskretne matematike i/ili teorije grafova.
Identificirati strukturu i tipove dokaza u matematici te koristiti matematički način provjere valjanosti algoritama.
Koristiti matematičku literaturu, umjetnu inteligenciju i mješovito e-učenje, te barem jedan alat i programski jezik za rješavanje problema koji zahtijevaju primjenu teorije grafova i/ili diskretne matematike.
Primijeniti algoritme koji se temelje na teoriji brojeva na probleme iz prakse, s naglaskom na kriptografiju.
Primijeniti teoreme i algoritme iz teorije grafova na rješavanje standardnih zadataka manulano i uz pomoć prikladnih alata.

Ishodi učenja programa

Primijeniti etička načela, zakonsku regulativu i norme koje se koriste u struci
Procijeniti uvjete za primjenu suvremenih informacijskih i komunikacijskih tehnologija (IKT), savjetovati druge u primjeni IKT-a te u zadanom kontekstu odrediti utjecaj na pojedinca, organizaciju i društvo.
Modelirati probleme iz područja informacijskih i poslovnih sustava korištenjem matematičkih metoda, metoda razvoja informacijskih sustava i koncepata planiranja, upravljanja i poslovanja
Analizirati uvjete, donositi odluke, savjetovati druge te primijeniti odluke u zadanom kontekstu rješavanja problema iz područja informacijskih i poslovnih sustava
Vrednovati učinkovitost uvođenja i korištenja programskih rješenja i pripadajuće infrastrukture za konkretne problemske domene
Voditi interdisciplinarni tim i raditi u takvom timu te razviti planove upravljanja karijerom za sebe i članove tima uključujući elemente cjeloživotnog učenja i razvoj kompetencija poduzetnosti
Svrsishodno komunicirati na hrvatskom i stranom jeziku, unaprijediti komunikaciju sa svim dionicima (klijentima, korisnicima i kolegama) uz primjenu odgovarajuće terminologije uključujući popularizaciju suvremenih informatičkih trendova i tema
Primijeniti odgovarajuće metode i tehnike projektiranja, planiranja, razvoja i uvođenja složenog informacijskog sustava u suvremenim razvojnim okolinama
Optimizirati procese poslovnog sustava organizacije u suradnji sa stručnjacima odabirom metoda i koncepata planiranja, upravljanja organizacijom i analize poslovanja
Oblikovati softversku arhitekturu složenog informacijskog sustava, odabrati i postaviti njegovu odgovarajuću tehnološku platformu i sigurnosne mehanizme te programirati dijelove složenog sustava
Utvrditi uvjete za primjenu ključnih informacijskih tehnologija, procijeniti njihov učinak i u zadanom kontekstu donositi odluke i davati savjete vezano uz upravljanje IT uslugama i resursima
Analizirati uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke vezane uz metodološke pristupe razvoju organizacijskih i informacijskih sustava
Osmsliti projekt učinkovitog unapređenja poslovnog sustava u osnovnim vertikalnim područjima uz korištenje suvremenih IKT, realizirati takav projekt vlastitim razvojem ili izborom odgovarajućeg standardnog softvera
Analizirati objekte poslovnog sustava te postaviti formalni model objektnog sustava kao temelj izgradnje informacijskog sustava.
Dizajnirati i izgraditi sustav temeljen na distribuiranim bazama podataka i velikim izvorima znanja korištenjem tehnika izgradnje velikih i distribuiranih podatkovnih sustava i razrješavanja konflikata između kompetitivnih izvora znanja.
Izgraditi računalni sustav za pohranu podataka i znanja uključujući digitalne arhive.
Predložiti poboljšanja poslovnog sustava temeljem optimiziranog modela poslovnih procesa i poslovnih pravila.
Modelirati i izgraditi analitički podatkovni sustav skladišta podataka i višedimenzionalnih kocaka temeljen na postojećem transakcijskom sustavu.
Izgraditi i optimizirati model procesa, klasa podataka i poslovnih pravila poslovnog sustava te predložiti poboljšanja poslovnog sustava.
Modelirati i izgraditi sustave temeljene na znanju i sustave za podršku u odlučivanju.
Identificirati potrebe za strategijskim i upravljačkim promjenama u organizacijama
Primijeniti metode upravljanja životnim ciklusom informacijskog sustava organizacije te osmisliti i primijeniti suvremene strategije nastupa na tržištu informatičkih proizvoda i usluga
Definirati elemente strategijskog kontinuuma i primijeniti metode strategijskog upravljanja uz potporu informacijsko komunikacijske tehnologije.
Razviti i validirati sustav mjerenja organizacijske učinkovitosti uz primjenu IKT
Analizirati tržište primjenom informacijsko-komunikacijskih tehnologija
Analizirati poslovne procese te preporučiti i primijeniti odgovarajuće informacijske i komunikacijske tehnologije za unapređenje poslovnih procesa
Prezentirati razvoj i organizaciju odgojno-obrazovnih sustava, povijest informatike i računarstva, ustroj odgojno-obrazovnog procesa, društvenu uvjetovanost odgojno-obrazovne prakse i primijeniti suvremene odgojno-obrazovne koncepcije
Organizirati nastavni proces uključujući i poučavanje upotrebom tehnologije i u kriznim uvjetima te osmisliti postupke za upravljanje procesom učenja i poučavanja uz primjenu odrednica djelovanja i ponašanja ljudske jedinke i dinamike grupe
Artikulirati nastavni sat primjenjujući primjerene nastavne metode i oblike rada, didaktičke principe i nastavna sredstva
Voditi pedagošku dokumentaciju, ispitivanje, ocjenjivanje i vrednovanje u skladu sa zakonskom regulativom i kriterijima osobne i profesionalne etičnosti
Poučavati učenike primjeni različitih oblika učenja, samovrednovanju i samoreguliranom učenju
Upravljati razrednim odjeljenjem, i surađivati s roditeljima i drugim strukturama unutar i izvan odgojno-obrazovne institucije
Primijeniti i sukreirati suvremene računalne sustave u dizajnu obrazovnog informacijskog sustava u nastavi u skladu s pedagoškim i metodičkim principima te ih popularizirati sukladno trendovima i potrebama
Primijeniti principe proceduralnog programiranja, interneta, weba, stolnih aplikacija u kontekstu rješavanja problema iz realnog svijeta
Formulirati problem iz realnog svijeta u smislu problemskog zadatka u informatici te ga znati riješiti i rješenje evaluirati
Izvoditi proces poučavanja u multikulturalnim i multietničkim sredinama i drugim posebnim uvjetima (treća dob, centri izvrsnosti …)
Strukturirati i procjenjivati osobna i profesionalna iskustva (razvijati refleksivnu praksu) uključujući cjeloživotno učenje

Osnovna literatura

Divjak B., Lovrenčić A. Diskretna matematika s teorijom grafova. TIVA-FOI, Varaždin, 2005.
Goodaire E. G., Parmenter M. M. Discrete mathematics with graph theory. Prentice Hall, New York, 2005.
Cormen T. H., Leiserson, C.E., Rivest, R.L., Stein C. Introduction To Algorithms, MIT press, 2009

Dopunska literatura

Garnier R., Taylor J. Discrete mathematics for new technology. Institute of Physics Publishing, Bristol & Philadelphia, 1999.
Veljan D. Kombinatorna i diskretna matematika. Algoritam, Zagreb, 2001.
Tucker, A. Applied combinatorics. John Wiley & Sons, Hoboken, 2007.
Dujella A., Maretić M. Kriptografija. Element, Zagreb, 2007.

Slični kolegiji

Redoviti studenti

Izvanredni studenti

izvanredni rok

Datum: 15.04.2025.

Vrijeme: 16:00

Opis: Na Fakultetu

U kalendaru ispod se nalaze konzultacije predmetnih nastavnika, no za detalje o konzultacijama možete provjeriti na profilu pojedinog predmetnog nastavnika.