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
2014/2015
6 ECTSa
Baze podataka i baze znanja 1.2 (BPBZ)
Informatika u obrazovanju 1.2 (IUO)
Organizacija poslovnih sustava 1.2 (OPS)
Informacijsko i programsko inženjerstvo 1.2 (IPI)
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
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 15 2 1
Horvat Damir Suradnik Seminar 15 2 1
Maretić Marcel Suradnik Seminar 15 2 2
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
  • Analizirati i procijeniti uvjete za primjenu suvremenih informacijskih i komunikacijskih tehnologija (ICT), savjetovati druge u primjeni iste te u zadanom kontekstu odrediti utjecaj primjene na pojedinca, organizaciju i društvo.
  • Modeliranje problema iz područja informacijskih i poslovnih sustava korištenjem matematičkih metoda, metoda razvoja informacijskih sustava i koncepata planiranja, upravljanja i poslovanja
  • Primijeniti, utvrditi uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke vezane uz rješavanje problema iz područja informacijskih i poslovnih sustava
  • Analizirati i ocijeniti učinkovitost uvođenja i korištenja ICT (programskog rješenja i pripadajuće opreme) za konkretne problemske domene informacijskih i poslovnih sustava
  • Procijeniti i preporučiti programska rješenja za konkretne problemske domene informacijskih i poslovnih sustava
  • Voditi interdisciplinarni tim i raditi u takvom timu
  • Predstaviti i popularizirati suvremena trendove u informatici u stručnim i laičkim krugovima
  • Unaprijediti metode komuniciranja i komunikaciju s klijentima, korisnicima i kolegama na verbalan i pisani način uz primjenu odgovarajuće terminologije uključujući i sposobnost komunikacije o struci na stranom jeziku
  • Unaprijediti i primijeniti metode stručnog rada pronalaženjem i vrednovanjem suvremenih izvora znanja
  • Valorizirati stručnu literaturu na hrvatskom i stranom jeziku
  • Razviti vlastite planove i planove drugih članova tima u upravljenju karijerom u struci i vlastitih poduzetničkih poduhvata s obzirom na potrebe poslovnog okruženja
  • Planirati proces cjeloživotnog osobnog i profesionalnog razvoja i definirati optimalne individualne strategije učenja
  • Projektirati, planirati, izraditi i uvesti svaki poslovni složeni informacijski sustav i/ili voditi projektni tim u slučaju kada na tim poslovima mora biti uključen veći broj stručnjaka
  • Razumjeti poslovni sustav organizacije i u suradnji s poslovnim stručnjacima optimalizirati njezine poslovne procese te izraditi strateški plan primjene ICT-a
  • Oblikovati softversku arhitekturu složenog informacijskog sustava, odabrati i postaviti odgovarajuću tehnološku platformu i programirati najsloženije dijelove složenog sustava
  • Primijeniti metode planiranja i upravljanja poslovanjem uz pomoć ICT u osnovnim vertikalnim područjima primjene ICT
  • Utvrditi uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke vezane uz ključne aspekte primjene i razvoja informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja)
  • Utvrditi uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke vezane uz suvremene tehničke koncepte i prakse u informacijskim tehnologijama (arhitektura računala, operacijski sustavi, mreže računala)
  • Utvrditi uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke vezane uz metode i koncepte planiranja, upravljanja organizacijom i obračuna poslovanja
  • Analizirati uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke vezane uz metodološke pristupe razvoju organizacijskih i informacijskih sustava
  • Analizirati uvjete za primjenu, savjetovati i u zadanom kontekstu donositi odluke za primjenu koncepata elektroničkog poslovanja podržanih odgovarajućim arhitekturama informacijskih sustava (klasične ili distribuirane)
  • Osmisliti projekt učinkovitog unapređenja poslovne tehnologije poslovnog sustava uz korištenje suvremenih ICT te realizirati takav projekt vlastitim razvojem ili izborom prikladnog standardnog softvera
  • Odabrati i primijeniti odgovarajuće sigurnosne mehanizme pri projektiranju i izgradnji informacijskog sustava
  • Odabrati i primijeniti metode i tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama
  • Utvrditi uvjete za primjenu, savjetovati, procijeniti učinak i donositi odluke vezane uz procese, metode i tehnologije upravljanja IT uslugama i resursima te podrške i pružanja različitih vrsta usluga vezanih uz ICT
  • Objasniti stručnoj i općoj publici informatička rješenja za unapređenje poslovne tehnologije
  • Analizirati i valorizirati atribucije (atribute) objekata poslovnog sustava te postaviti formalni model objektnog sustava kao temelj izgradnje informacijskog sustava
  • Izgraditi informacijski sustav temeljen distribuiranim komponentama kao i na autonomnim i međusobno kompetitivnim izvorima znanja i razriješiti konflikte koji se javljaju među izvorima znanja
  • Primijeniti metode i tehnike izgradnje digitalnih arhiva i dugotrajnog pohranjivanja podataka
  • Primijeniti metode i tehnike pretraživanja i klasifikacije informacija
  • Prepoznati kritične procese i klase podataka poslovnog sustava, izgraditi formalni model procesa i klasa te ga optimizirati i ponuditi prijedloge poboljšanja poslovnog sustava
  • Modelirati poslovna pravila, poslovne podatke kao i pravila za izvođenje transakcijskih podataka koji nisu eksplicitno zadani
  • Modelirati i izgraditi sustav izvođenja analitičkih podataka iz transakcijskih metodama rudarenja i drugim metodama, te izgradnje skladišta podataka u koja se ti podaci pohranjuju
  • Modelirati i izgraditi sustave poslovne inteligencije temeljene na skladištima podataka, kao i njihovo pretraživanje korištenjem metoda višedimenzionalnih kocaka podataka (OLAP)
  • Izgraditi računalni sustav za pohranu podataka i znanja korištenjem suvremenih alata za izradu baza podataka, baza znanja i semantici podataka
  • Izgraditi i optimizirati bazu podataka i bazu znanja primjenom odgovarajućih strategija organizacije podataka i sigurnosti informacijskog sustava
  • Modelirati raspodjelu podataka prema mjestu korištenja podataka, izgraditi sustav replikacije baze podataka i izgraditi distribuiranu bazu podataka
  • Modelirati i izgraditi sustave temeljene na znanju, kao što su višeagentni sustavi, deduktivni sustavi (uključujući i ekspertne sustave), semantički Web sustavi, neuralne mreže itd.
  • Procijeniti potrebe za strategijskim i upravljačkim promjenama u organizacijama
  • Primijeniti metode upravljanja životnim ciklusom informacijskog sustava organizacije
  • Primijeniti metode korporacijskog upravljanja i strategijskog menadžmenta uz potporu informacijske tehnologije
  • Razviti i validirati sustav mjerenja organizacijske učinkovitosti uz primjenu odgovarajućih programskih alata
  • Analizirati tržište primjenom informacijsko-komunikacijskih tehnologija
  • Analizirati poslovne procese i preporučiti primjenu odgovarajuće informacijske i komunikacijske tehnologije za unapređenje poslovnih procesa
  • Organizirati sustav vođenja u javnoj upravi uz primjenu informacijske tehnologije
  • Razviti elemente kontinuuma strategijskog upravljanja: misiju, organizacijske vrijednosti, viziju, strateške ciljeve
  • Analizirati potrebu za e-poslovanjem i primijeniti koncepte e-poslovanja
  • Procijeniti spremnost organizacije za uvođenje suvremenih ERP sustava i definirati projekt uvođenja istih
  • Razumjeti povijesni aspekt edukacijskih sustava, društvenu uvjetovanost odgojno-obrazovne prakse i diferenciranost suvremenih odgojno-obrazovnih koncepcija
  • Poznavati organizaciju sustava odgoja i obrazovanja te ustroj odgojno-obrazovnog procesa na svim razinama
  • Razumjeti odrednice djelovanja i ponašanja ljudske jedinke i grupnu dinamiku (razrednog odjeljenja, timova, kolektiva …)
  • Organizirati nastavni proces
  • 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 s 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
  • Analizirati građu računala, suvremene računalne arhitekture te primijeniti ta znanja u dizajnu obrazovnog informacijskog sustava, kao i u nastavi
  • Primijeniti principe proceduralnog programiranja, izgradnje struktura podataka i algoritama
  • Interpretirati povijest informatike i računarstva
  • Analizirati i usporediti računalne Web i desktop alate za prezentaciju informacija i primijeniti ih u nastavi
  • Formulirati problem iz realnog svijeta u smislu problemskog zadatka u informatici te ga znati riješiti i rješenje evaluirati
  • Analizirati, preporučiti, implementirati i koristiti sustave za e-učenje u skladu s metodičkim i pedagoškim principima
  • Izvoditi proces poučavanja u multikulturalnim i multietničkim sredinama i drugim posebnim uvjetima (treća dob, centri izvrsnosti …)
  • Osmisliti postupke za upravljanje procesom učenja i poučavanja u rizičnim situacijama
  • Predstavljati informatička znanja i vještine kao učinkovite instrumente za podupiranje integracijskih procesa
  • Predstavljati nastavnicima mogućnosti korištenja informatike u odgojno-obrazovnom procesu
  • Preispitivati, strukturirati i restrukturirati svoja osobna i profesionalna iskustva (razvijati refleksivnu praksu)
  • Koristiti stečena znanja o vizualnom oblikovanju i sadržajima u ostvarivanju kreativnih vizualnih projekata pri radu s računalom.
  • Modelirati postojeće vizualne sadržaje za potrebe konkretnih osobnih (ili učeničkih) računalnih radova (web dizajn, grafički dizajn, dizajn multimedija,…).
  • Koristiti vještine učenja potrebne za cjeloživotno učenje i nastavak obrazovanja na diplomskom studiju.
  • Upoznati Nacionalni okvirni kurikulum. Upoznati metodologiju izradbe školskog i nastavnog kurikuluma. Upoznati primjenu nastavnog kurikuluma u praksi.
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
izvanredni rok
Datum: 16.04.2024.
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.
2024 © Fakultet organizacije i informatike, Centar za razvoj programskih proizvoda