Sadržaj se učitava...
mdi-home Početna mdi-account-multiple Djelatnici mdi-script Studiji mdi-layers Katedre mdi-calendar-clock Raspored sati FOI Nastava search apps mdi-login
Diskretne strukture s teorijom grafova
Discrete Structures and Graph Theory
2017/2018
6 ECTSa
Organizacija poslovnih sustava 1.2 (OPS)
Informatika u obrazovanju 1.2 (IUO)
Informacijsko i programsko inženjerstvo 1.2 (IPI)
Baze podataka i baze znanja 1.2 (BPBZ)
Katedra za kvantitativne metode
TO
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 Studijski program Semestar Obavezan
Organizacija poslovnih sustava 1.2 (OPS) 1 obavezan
Informatika u obrazovanju 1.2 (IUO) 3 izborni
Informatika u obrazovanju 1.2 (IUO) 1 izborni
Informacijsko i programsko inženjerstvo 1.2 (IPI) 1 obavezan
Baze podataka i baze znanja 1.2 (BPBZ) 3 izborni
Baze podataka i baze znanja 1.2 (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. 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 predmet namijenjena su svima onima koji se žele baviti istraživanjem u informatici, ali i naprednijom primjenom informatike.
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 5 3 1
Horvat Damir Suradnik Seminar 10 3 2
Maretić Marcel Suradnik Predavanja
Seminar 		5
10 		3
3 		1
1
Žugec Bojan Suradnik
Sadržaj predavanja
  • Modeli i struktura matematike
    Matematički modeli. Karakteristike matematičkih modela. Struktura matematike. Aksiomi i njihova uloga u gradnji teorije. Osnovni i izvedeni pojmovi, veze među pojmovima. Teoremi. Primjeri poznatih matematičkih teorija i njihova evolucija.
  • Metode dokazivanja tvrdnji u matematici
    Propozicijska i predikatna logika. Sudovi i operacije sa sudovima. Složene izjave povezane s i, ili. Implikacija i njezina svojstva. Struktura tvrdnje. Tehnike dokazivanja. Direkni dokaz. Dokaz po slučajevima. Dokaz kontrapozicijom. Ekvivalentne tvrdnje. Niz ekvivalentnih tvrdnji i način dokazivanja njihove ekvivalencije. Protuprimjeri za obaranje tvrdnji. Kvantifikator egzistencije i univerzalni kvantifikator. Matematička indukcija kao instrument dokazivanja na prirodnim (cijelim) brojevima. Peanovi aksiomi.
  • Diskretna matematika: Skupovi i relacije
    Ponavljanje: Skup kao osnovni matematički pojam. Problematika zadavanja skupova. Paradoksi teorije skupova. Cantorov i Zermelov doprinos teoriji skupova. Relacije na skupovima (podskup, pravi podskup, jednakost skupova). Partitivni skup. Operacije na skupovima (unija, presjek, razlika, komplement) i njihova svojstva. Vennovi dijagrami. Dokazivanje tvrdnji o skupovima. Tablica pripadnosti. Problemi kod diskretnih i kontinuiranih skupova i njihove različitosti. Kartezijevi produkti n skupova (diskretni i kontinuirani slučaj). Skupovi brojeva. Kompleksni brojevi. Relacije, binarne relacije, svojstva binarnih relacija. Matrica incidencije. Funkcije (domena, rang, bijekcija, prebrojivost skupova). Inverzi i kompozicije.
  • Kongruencija i njezine primjene
    Relacija ekvivalencije. Kvocjentni skup kod relacije ekvivalencije. Particija skupa inducirana relacijom ekvivalencije. Kongruencije. Operacije s kongruencijama (zbrajanje, oduzimanje, množenje). Rješavanje jednadžbi s kongruencijama. Primjena kongruencije na International Standard Book Number, Universal Product Code. Kineski teorem s ostatkom. Određivanje brojeva preko postotaka. Primjena kongruencija u kriptografiji.
  • Dobro uređeni skupovi i mreže
    Parcijalni uređaj na skupu, definicija i osnovni primjeri. Leksikografski uređaj. Usporedivost elemenata u parcijalno D-277 uređenom skupu. Hasseovi dijagrami i njihova primjena. Linearni ili totalno uređeni skup. Pojam minimalnog i maksimalnog, te najveće gornje i donje međe u parcijalno uređenom skupu. Dobro uređeni skup.
  • Dobro uređeni skupovi i mreže
    Mreža (lattice); definicija i primjeri. Djeljivost cijelih brojeva kao relacija parcijalnog uređaja. Najveći zajednički djelitelj i Euklidov algoritam. Najmanji zajednički višekratnik. Mreža djelitelja prirodnih brojeva. Princip dobrog uređaja (svaki neprazni skup prirodnih brojeva ima najmanji element). Ekvivalentnost principa matematičke indukcije i principa dobrog uređaja na skupu. Prosti brojevi i njihova svojstva. Eratostenovo sito. Osnovni teorem aritmetike (svaki se cijeli broj, veći od 2, može zapisati kao produkt potencija prostih brojeva). Goldbachova hipoteza.
  • Rekurzije
    Rekurzivno zadani nizovi. Početni uvjeti kod rekurzivnog zadavanja. Rješenje rekurzivne relacije. Neki specijalni nizovi. Fibonccijev niz. Postupak rješavanja rekurzivno zadanih relacija. Homogene rekurzivne relacije. Karakteristični polinom. Nalaženje n-tog člana Fibonaccijevog niza. Pojam partikularnog rješenja i rješenje nehomogenih rekurzivnih relacija s konstantnim koeficijentima – rješavanje pomoću tablice partikularnih rješenja i pomoću homogenizacije. Rješavanje rekurzivnih relacija preko funkcija izvodnica.
  • Algoritmi (ponavljanje)
    Principi prebrojavanja skupova. Binomni teorem. Ponavljanje metoda izgradnje algoritama. Euklidov algoritam. Hornerova shema. Složenost algoritma. Asimptotske ocjene složenosti. Svojstva asimptotskih ocjena složenosti. Pretraživanje i sortiranje. Slijedno i binarno pretraživanje. Sortiranje umetanjem. Mjehuričasto sortiranje. Sortiranje spajanjem. Quicksort.
  • Algebarske strukture
    Grupa; definicija i primjeri. Komutativna (Abelova) grupa. Ispitivanje svojstava grupe i ekvivalentih iskaza. Izomorfizam grupa. Prsteni i polja. Polje relalnih brojeva. Algebarski zatvorena polja. Primjer polja kompleksnih brojeva. Vektorski prostor kao apstrakna struktura. Polinomi kao primjer vektorskog prostora. Vektorski prostor matrica. Primjena grupa u teoriji kodiranja. Otkrivanje i ispravljanje grešaka u prijenosu podataka. Matrica kodiranja i kontrolna matrica.
  • 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
    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 mogu biti vezani za neki realni problem. Također se pokazuje na koji način je neki zadatak moguće riješiti u nekom programskom alatu ili jeziku kao što su Python, SAGE i Maxima.
  • 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 skupovima poznajući njihova svojstva i karakteristične primjere
  • definirati i znati povezati osnovne pojmove i probleme iz teorije grafova
  • efikasno raditi u timu na osmišljavanju, formuliranju, odabiru strategije i rješavanju problema iz područja diskretne matematike i teorije grafova
  • identificirati strukturu i tipove dokaza u matematici
  • koristiti matematičku literaturu različitih izvora uključujući i sustav za e-učenje, te barem jedan alat za obradu problema koji zahtijevaju primjenu teorije grafova
  • primijeniti algoritme koji se temelje na prostim brojevima na probleme iz prakse
  • primijeniti teoreme i algoritme iz teorije grafova na rješavanje zadataka srednje težine
 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.
 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
U kalendaru ispod se nalaze konzultacije predmetnih nastavnika, no za detalje o konzultacijama možete provjeriti na profilu pojedinog predmetnog nastavnika.
 2024 © Fakultet organizacije i informatike, Centar za razvoj programskih proizvoda