FOI nastava
FOI logo

Lista kolegija iz:

ak.god:
2015/2016
semestar:
1. semestar

2015/2016

6ECTSa

Diplomski

Diplomski studij informatike v1.2

Program Obavezan
Baze podataka i baze znanja BPBZ Ne
Informatika u obrazovanju IO Ne
Informacijsko i programsko inženjerstvo IPI Da
Organizacija poslovnih sustava OPS Da
1. semestar
1. nastavna godina

Diskretne strukture s teorijom grafova npp:93106

Engleski naziv

Discrete Structures and Graph Theory

Katedra

Katedra za kvantitativne metode

Kategorija ("boja")

TO

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.

Nastava

Predavanje
30sati
Seminar
30sati

Ishodi učenja predmeta

  • 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

  • Analizirati, preporučiti, implementirati i koristiti sustave za e-učenje u skladu s metodičkim i pedagoškim principima Analizirati, preporučiti, implementirati i koristiti sustave za e-učenje u skladu s metodičkim i pedagoškim principima
  • Formulirati problem iz realnog svijeta u smislu problemskog zadatka u informatici te ga znati riješiti i rješenje evaluiratiFormulirati problem iz realnog svijeta u smislu problemskog zadatka u informatici te ga znati riješiti i rješenje evaluirati
  • Modeliranje problema iz područja informacijskih i poslovnih sustava korištenjem matematičkih metoda, metoda razvoja informacijskih sustava i koncepata planiranja, upravljanja i poslovanja Modeliranje problema iz područja informacijskih i poslovnih sustava korištenjem matematičkih metoda, metoda razvoja informacijskih sustava i koncepata planiranja, upravljanja i poslovanja
  • Unaprijediti i primijeniti metode stručnog rada pronalaženjem i vrednovanjem suvremenih izvora znanja Unaprijediti i primijeniti metode stručnog rada pronalaženjem i vrednovanjem suvremenih izvora znanja
  • Voditi interdisciplinarni tim i raditi u takvom timuVoditi interdisciplinarni tim i raditi u takvom timu

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

Alati koji se koriste na predmetu

  • Sage
    Open source matematički program napisan u pythonu koji nudi vlastite funkcije, ali koristi isto tako unutar sebe i ostale ponajbolje open source matematičke programe poput Maxima, Axiom, GAP i slično. Prirodno sučelje mu je linux operacijski sustav, ali može se koristiti i preko weba.
  • Maxima
    open source
  • Mathematica
    Ukoliko postoji licenca, u obzir dolazi kao alternativa
  • Python
    Besplatni programski jezik velikih mogućnosti. Kod teorije grafova posebno je moćan njegov modul networkx.

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 predmeti

Nastavnik Oblik nastave Tjedana Sati tjedno Grupa
Divjak Blaženka Predavanje 10 3 1
Horvat Damir Seminar 10 3 1
Maretić Marcel Seminar 10 3 2
Nema definiranih ispitnih rokova

Diskretne strukture s teorijom grafova - Redovni studenti

Studij: Diplomski studij informatike
Akademska godina: 2015/2016

Praćenje rada studenata

Elementi praćenjaBodova
Aktivnost na nastavi6
Problemski zadatak - timski rad30
Zadaci u e-učenju (Moodle)4
Kolokviji60
ZBROJ100


Bodovna skala ocjena

OdDoOcjena
0 49 nedovoljan (1)
50 60 dovoljan (2)
61 75 dobar (3)
76 90 vrlo dobar (4)
91 100 odličan (5)


Nužan uvjet za pozitivnu ocjenu je postizanje barem 25 bodova putem kolokvija pri čemu na svakom kolokviju treba imati barem 3 boda.

Uvjet za potpis je prikupljenih 20 bodova, ne više od 3 izostanka s nastave i na svakom kolokviju treba imati barem 1 bod.


Kolokviji

Naziv / Tjedan 1234567891011121314151617 1. razdoblje
udio (%)
2. razdoblje
udio (%)
3. razdoblje
udio (%)
Trajanje Pismeni Usmeni
1. kolokvij + 100.0 50.0 75 +
2. kolokvij + 50.0 100.0 75 +
Prezentacija i obrana projekta + +


Opis elemenata praćenja

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Prisustvovanje i aktivnost na nastavi 6 Na predavanjima će se nenajavljeno provesti kratki testovi (između 5 i 10 minuta) ili neka druga vrsta provjere aktivnosti studenata, gdje će studenti rješavati zadani problem vezan uz gradivo koje je prethodno već obrađeno ili se trenutno obrađuje na tom satu ili će vrednovati rad drugih studenata. Preko Moodle-a treba riješiti dvije provjere, svaku s 50% točnosti, bez kojih se ne može dalje napredovati kroz predmet. Nadoknada se ne predviđa.
Problemski zadatak – timski rad 30 Inačica 1.
Studenti će u timovima od troje ljudi morati smisliti neki realni problem koji je vezan uz gradivo koje se obrađuje na kolegiju. Problem treba biti jasno i precizno opisan i mora biti takav da njegovo rješavanje zahtijeva korištenje računala (programiranje, korištenje programskih paketa poput SAGE-a i slično). Svaki tim rješava problem kojeg je zadao neki drugi tim u prvoj fazi kod zadavanja problema. Raspodjelu zadanih problema po timovima obavlja nastavnik, s time da niti jedan tim neće rješavati svoj problem kojeg je zadao, nego rješava problem od nekog drugog tima. Inzistira se na korištenju računala tokom rješavanja problema. Korištenje tuđeg rješenja (plagijat) je zabranjeno te povlači disciplinsku odgovornost.

Inačica 2.
Problemski zadatak je unaprijed pripremljen od strane nastavnika, a studenti ga rješavaju u timovima od troje ljudi. Inzistira se na korištenju računala tokom rješavanja problema.
Korištenje tuđeg rješenja (plagijat) je zabranjeno te povlači disciplinsku odgovornost.

Inačica 3.
Studenti pohađaju i polažu neki od MOOC-ova na Courseri u dogovoru s nastavnikom te o tome pišu osvrt/dnevnik na Moodle-u te izrađuju kratku prezentaciju.
Nadoknada se ne predviđa.
Zadaci u e-učenju (Moodle) 4 Ukupno će biti dvije provjere na Moodleu i svaka će nositi 2 boda. Prva provjera će se odnositi na diskretnu matematiku, a druga na teoriju grafova. Nadoknada se ne predviđa.
1. kolokvij 30 Kolokvij se sastoji od zadataka koji su koncipirani tako da traže odgovore teoretske naravi i rješavanje zadataka uz dodatak teoretskih pitanja otvorenog tipa i pitanja koja ispituju razumijevanje. Nije dozvoljena upotreba mobitela niti kalkulatora. Nadoknada se ne predviđa.
2. kolokvij 30 Kolokvij se sastoji zadataka koji su koncipirani tako da traže odgovore teoretske naravi i rješavanje zadataka uz dodatak teoretskih pitanja otvorenog tipa i pitanja koja ispituju razumijevanje. Nije dozvoljena upotreba mobitela niti kalkulatora (osim ako nastavnik dozvoli upotrebu kalkulatora na kolokviju). Nadoknada se ne predviđa.
ZBROJ 100 20 Studenti za prolaznu ocjenu trebaju izaći na sve kolokvije i na svakom ostvariti minimalno 3 boda i ukupno barem 50.
Za ovjeravanje indeksa potpisom potrebno je izaći na sve kolokvije i ostvariti bodove na kolokvijima te ukupno imati barem 20 bodova. Ukupno su dozvoljena 3 izostanka (seminari i predavanja).


Za potpis je potrebno skupiti minimalno 20 bodova i ne imati više od 3 izostanka s nastave i na svakom kolokviju treba imati barem 1 bod.

Napomena: Prepisivanje na kolokvijima, korištenje tuđih rješenja u zadaćama, provjerama i praktičnim zadacima je strogo zabranjeno i povlači stegovnu odgovornost studenata.

Diskretne strukture s teorijom grafova - Izvanredni studenti

Studij: Diplomski studij informatike
Akademska godina: 2015/2016

Prisustvovanje predavanjima i seminarima nije obavezno, ali student treba sudjelovati u e-učenju. Student se treba tijekom prva dva tjedna nastave prijaviti u sustav za e-učenje Moodle i pratiti nastavu i zadatke posredstvom sustava. Na moodlu treba riješiti dvije kratke provjere, svaku s 50% točnosti, bez kojih se ne može dalje napredovati kroz predmet.


Praćenje rada studenata

Elementi praćenjaBodova
Zadaci u e-učenju (Moodle)4
MOOC30
Kolokviji60
ZBROJ94


Bodovna skala ocjena

OdDoOcjena
0 46 nedovoljan (1)
47 57 dovoljan (2)
58 70 dobar (3)
71 82 vrlo dobar (4)
83 94 odličan (5)


Nužan uvjet za pozitivnu ocjenu je postizanje barem 25 bodova putem kolokvija pri čemu na svakom kolokviju treba imati barem 3 boda.


Kolokviji

Naziv / Tjedan 1234567891011121314151617 1. razdoblje
udio (%)
2. razdoblje
udio (%)
3. razdoblje
udio (%)
Trajanje Pismeni Usmeni
1. kolokvij + 100.0 50.0 75 +
2. kolokvij + 50.0 100.0 75 +


Opis elemenata praćenja

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
MOOC 30 Studenti pohađaju i polažu neki od MOOC-ova na Courseri u dogovoru s nastavnikom te o tome pišu osvrt/dnevnik na Moodle-u te izrađuju kratku prezentaciju. Nadoknada se ne predviđa.
Zadaci u e-učenju (Moodle) 4 Ukupno će biti dvije provjere na Moodleu i svaka će nositi 2 boda. Prva provjera će se odnositi na diskretnu matematiku, a druga na teoriju grafova. Nadoknada se ne predviđa.
1. kolokvij 30 Kolokvij se sastoji od zadataka koji su koncipirani tako da traže odgovore teoretske naravi i rješavanje zadataka uz dodatak teoretskih pitanja otvorenog tipa i pitanja koja ispituju razumijevanje. Nadoknada se ne predviđa.
2. kolokvij 30 Kolokvij se sastoji od zadataka koji su koncipirani tako da traže odgovore teoretske naravi i rješavanje zadataka uz dodatak teoretskih pitanja otvorenog tipa i pitanja koja ispituju razumijevanje. Nadoknada se ne predviđa.
ZBROJ 94 20


Napomena: Prepisivanje na kolokvijima, korištenje tuđih rješenja u zadaćama, provjerama i praktičnim zadacima je strogo zabranjeno i povlači stegovnu odgovornost studenata.

Predavanje Seminar Auditorne vježbe Laboratorijske vježbe Vježbe (jezici, tzk) Ispit Kolokviji Nadoknade Demonstrature
Copyright © 2015 FOI Varaždin. All Rights Reserved. Sva prava pridržana.
Povratak na vrh