IT - Discrete Mathematics

MATEMATIČKO MODELIRANJE. Matematičke strukture. Jezik i formalne procedure. Diskretno i neprekidno. MATEMATIČKI JEZIK. Simbolizacija i upotreba varijabli. Elementi matematičkog jezika. Definiranje i dokazivanje. LOGIKA. Propozicijska logika. Uvod u logika predikata. Uvod u logičko programiranje i Prolog. Problem korektnosti programa. SKUPOVI. Algebra skupova. Partitivni skup i particija skupa. Uređeni par i Kartezijev produkt. RELACIJE. Relacije uređaja. Topološko sortiranje. Relacije ekvivalencije. Primjena na relacijske baze podataka. FUNKCIJE. Uvod u funkcijsko programiranje i Lisp. STRUKTURE. Strukture, izomorfnost, specifikacija i realizacija. Algebra modulo n i simetrična kriptografija. Strukture podataka. INDUKCIJA I REKURZIJA. Struktura prirodnih brojeva. Princip dokazivanja indukcijom. Princip definiranja rekurzijom. Sume. Rekurzivno modeliranje. KOMBINATORIKA. Adicijski princip i princip uključenja-isključenja. Multiplikativni princip i stabla izbora. Permutacije i selekcije. SLOŽENOST ALGORITAMA. Usporedba asimptotskog ponašanja. Asimpotska ocjena složenosti. Složenost rekurzivnih algoritama. Praktična neizračunljivost i kriptografija javnog ključa. P, NP i NP potpuni problemi. GRAFOVI. Problem kineskog poštara. Problem trgovačkog putnika. Problem povezanosti. Problem najkraćeg puta. Problem minimalnog stabla. Problem toka. FORMALNI JEZICI I AUTOMATI. Jezici, automati i gramatike. Regularni jezici i konačni automati. Kontekstno slobodni jezici i potisni automati. Turingovi strojevi i izračunljivost.

Opća. Poznavanje osnovnih logičkih i matematičkih pojmova, kao i određena elokventnost u matematičkim i logičkim jezicima, koji su potrebni za praćenje tehničke literature i za precizno modeliranje i izražavanje zamisli. Umijeće rekurzivnog modeliranja i induktivnog dokazivanja. Analiza složenosti algoritama. Modeliranje pomoću grafova.
Posebna. Poznavanje elemenata matematičkih i logičkijh jezika. Poznavanje osnovnog matematičkog vokabulara. Poznavanje osnovnih pojmova teorije izračunljivosti. Umijeće induktivnog dokazivanja i rekurzivnog opisivanja. Utvrđivanje složenosti algoritama. Poznavanje navedenih algoritama na grafovima.

1. Understand the basic elements of mathematical language on a deeper level.
2. Understand the language of logic and basic concepts in logic.
3. Model problems in the language of logic.
4. Translate between natural language and the language of logic.
5. Know the basic mathematical vocabulary of sets, relations, functions and structures as well as their basic properties.
6. Know the terms related to computability and complexity of algorithms.
7. Understand the induction and recursion and to know how to use it in modeling and problem solving.
8. Know the basics of combinatorics and to know how to apply it to the analysis of the complexity of algorithms.
9. Know the basic concepts about graphs and to solve some sort of problems: the accessibility problem, the shortest path problem, the problem of minimal spanning tree, and sorting, inserting new elements and searching tree.

Kolegij pruža proširena znanja diskretne matematike kao osnovu tehničkog studija.

Boris Čulina: Diskretna matematika, nastavni materija za prvi kolokvij, ITN produkt, Zagreb,2013
Boris Čulina: Diskretna matematika, nastavni materija za drugi kolokvij, ITN produkt, Zagreb, 2013

1. Alfred V. Aho, Jeffrey D. Ullman: Foundations of Computer Science: C Edition, W. H. Freeman, 1994
2. Thomas Koshy: Discrete Mathematics with Applications, Academic Press 2003

1. Matematički jezik: Simbolizacija i varijable. Elementi matematičkog jezika. Definiranje i dokazivanje Jezik veznika: Sintaksa i semantika. Logički pojmovi. Prevođenje i argumentiranje
2. Jezik predikata: Sintaksa i semantika. Logički pojmovi. Prevođenje. Granice formalizma. Uvod u logičko programiranje. Problem korektnosti programa.
3. Skupovi: Pojam skupa. Operacije sa skupovima. Partitivni skup. Kartezijev produkt. Relacije: Pojam relacije. Svojstva relacija. Relacije ekvivalencije. Relacije uređaja. Primjena na relacijske baze podataka
4. Funkcije: Pojam funkcije. Svojstva funkcija. Algebra funkcija. Ekvipotentnost. Uvod u funkcijsko programiranje.
5. Strukture. Pojam strukture. Izomorfizam struktura. Specifikacija i realizacija struktura. Algebra modulo n i asimetrična kriptografija. Strukture podataka.
6. Izračunljivost. Pojam algoritma i izračunljivosti. Složenost algoritama. Asimetrična kriptografija.
7. Ponavljanje i priprema za prvi kolokvij
8. Indukcija i rekurzija: Indukcija i rekurzija nad skupom prirodnih brojeva. Totalna indukcija i rekurzija.
9. Indukcija i rekurzija: Rekurzivno modeliranje i programiranje. Eksplicitne formule.
10. Indukcija i rekurzija: Indukcija i rekurzija nad drugim oblastima.
11. Kombinatorika: Osnovni principi prebrajanja. Osnovne formule.
12. Kombinatorika: Primjena na složenost algoritama
13. Grafovi. Pojam usmjerenog i neusmjerenog grafa. Eulerov problem i problem kineskog poštara. Hamiltonov problem i problem trgovačkog putnika. Problem dostiživosti. Problem najkraćeg puta: Dijkstrin algoritam . Problem minimalnog razapinjućeg stabla: Primov algoritam.
14. Stabla: sortiranje, umetanje i pretraživanje.
15. Ponavljanje i priprema za drugi kolokvij

1. Vježbanje elemenata matematičkog jezika
2. vježbanje elemenata logičkog jezika veznika
3. vježbanje elemenata logičkog jezika predikata
4. vježbanje jezika teorije skupova - operacije sa skupovima
5. vježbanje jezika teorije skupova - relacije i funkcije
6. algebra modulo n i simetrična kriptografija usporedba složenosti algoritama
7. prvi kolokvij
8. indukcija i rekurzija nad skupom prirodnih brojeva
9. totalna indukcija i rekurzija nad skupom prirodnih brojeva
10. Eksplicitne formule
11. indukcija i rekurzija nad drugim oblastima - liste i stabla
12. problemi prebrajanja
13. ispitivanje složenosti algoritama
14. algoritmi nad grafovima
15. 2. kolokvij

1. Matematički jezik. Simbolizacia i varijable. Elementi matematičkog jezika. Definiranje i dokazivanje. Jezik veznika. Sintaksa i semantika. Logički pojmovi. Prevođenje i argumentiranje. Jezik predikata. Sintaksa i semantika. Logički pojmovi. Prevođenje. Granice formalizma. Uvod u logičko programiranje. Problem korektnosti programa. Skupovi. Pojam skupa. Operacije sa skupovima. Partitivni skup. Kartezijev produkt. Relacije. Pojam relacije. Svojstva relacija. Relacije ekvivalencije. Relacije uređaja. Primjena na relacijske baze podataka. Funkcije. Pojam funkcije. Svojstva funkcija. Algebra funkcija. Ekvipotentnost. Uvod u funkcijsko programiranje. Strukture. Pojam strukture. Izomorfizam struktura. Specifikacija i realizacija struktura. Algebra modulo n i simetrična kriptografija. Strukture podataka. Izračunljivost. Pojam algoritma i izračunljivosti. Složenost algoritama. Asimetrična kriptografija.
2. Indukcija i rekurzija. Indukcija i rekurzija nad skupom prirodnih brojeva. Totalna indukcija i rekurzija. Rekurzivno modeliranje i programiranje. Eksplicitne formule. Indukcija i rekurzija nad drugim oblastima. Kombinatorika. Osnovni principi prebrajanja. Osnovne formule. Primjena na složenost algoritama. Grafovi. Pojam usmjerenog i neusmjerenog grafa. Eulerov problem i problem kineskog poštara. Hamiltonov problem i problem trgovačkog putnika. Problem dostiživosti. Problem najkraćeg puta: Dijkstrin algoritam . Problem minimalnog razapinjućeg stabla: Primov algoritam. Stabla: sortiranje, umetanje i pretraživanje.

1. Način provjere znanja: prisutnost i aktivnost na nastavi (maksimalno 5 bodova), dva kolokvija (maksimalno 40 bodova), završni usmeni ispit (maksimalno 15 bodova). Studenti koji iz kolokvija i pohađanja nastave osvoje manje od 12 bodova moraju ponovo upisati kolegij Studenti koji osvoje više od 11 a manje od 23 boda, pri čemu iz svakog kolokvija barem 7 bodova, moraju na završnom ispitu prvo popravljati jedan od kolokvija da bi mogli pristupiti završnom usmenom ispitu Studenti koji imaju više od 22 boda izlaze na završni usmeni ispit. Kriterij za formiranje ocjene prije završnog ispita: 23 – 28 bodova → 2, 39 do 33 boda → 3, 34 do 39 bodova →4, 40 do 45 → 5 Kriterij za formiranje konačne ocjene nakon završnog ispita: 30 – 38 bodova → 2, 39 do 44 boda → 3, 45 do 50 bodova →4, 51 bod i više → 5

1. kolokviji, konzultacije, samostalno učenje, samostalno rješavanje numeričkih zadataka