| Naziv predmeta | Diskretna matematika |
| Detalji | Kod
VSITE005 Skr.
DMAT ECTS
6 Godina
4 Semester
Zimski semestar Vrsta
obvezatni Razina HKO 6
Preddiplomski studij E-Learning
0% |
| Aktivnosti | IT zg - Ljet 23/24
ECTS
Jedinice
Sati
Svega P
1.5
15
3
45
A
1
15
2
30
L
0
0
0
0
S
0
0
0
0
KA
0
0
0
0
KP
0
2
1
0
PR
0
0
0
0
IP
0
0
0
0
IU
0
1
2
0
SU
4
1
105
105
|
| Nastavnici | Nositelji: dr. sc. Aleksandar Hatzivelkos, v. pred.
Asistenti: dr. sc. Boris Čulina, prof. v. š. |
| Preduvjeti | Nema |
| Sadržaj | 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.
|
| Ciljevi učenja | 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.
|
| Ishodi učenja | 1. Dublje razumijeti osnovne elemente matematičkog jezika.
2. Razumjeti logičke jezike i osnovne logičke pojmove.
3. Modelirati probleme u logičkom jeziku.
4. Znati prevoditi između prirodnog i logičkog jezika.
5. Znati osnovni matematički vokabular skupova, relacija, funkcija i struktura, te njihova osnovna svojstva.
6. Znati pojmove vezane uz izračunljivost i složenost algoritama.
7. Razumjeti indukciju i rekurziju i znati je primjenjivati u modeliranju i rješavanju problema.
8. Znati osnove kombinatorike i znati je primijeniti na analizu složenosti algoritma.
9. Znati osnovne pojmove o grafovima i rješavati neke probleme: problem dostiživosti, problem najkraćeg puta, problem minimalnog stabla i problem sortiranja, umetanja i pretraživanja na stablu.
|
| Sposobnosti | Kolegij pruža proširena znanja diskretne matematike kao osnovu tehničkog studija.
|
| Preporučena literatura | 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
|
| Dodatna literatura | 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
|
| predavanja (P) | - 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
- 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 asimetrična kriptografija. Strukture podataka.
- Izračunljivost. Pojam algoritma i izračunljivosti. Složenost algoritama. Asimetrična kriptografija.
- Ponavljanje i priprema za prvi kolokvij
- Indukcija i rekurzija: Indukcija i rekurzija nad skupom prirodnih brojeva. Totalna indukcija i rekurzija.
- Indukcija i rekurzija: Rekurzivno modeliranje i programiranje. Eksplicitne formule.
- Indukcija i rekurzija: Indukcija i rekurzija nad drugim oblastima.
- Kombinatorika: Osnovni principi prebrajanja. Osnovne formule.
- Kombinatorika: 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.
- Ponavljanje i priprema za drugi kolokvij
|
| auditorne vježbe (A) | - Vježbanje elemenata matematičkog jezika
- vježbanje elemenata logičkog jezika veznika
- vježbanje elemenata logičkog jezika predikata
- vježbanje jezika teorije skupova - operacije sa skupovima
- vježbanje jezika teorije skupova - relacije i funkcije
- algebra modulo n i simetrična kriptografija
usporedba složenosti algoritama
- prvi kolokvij
- indukcija i rekurzija nad skupom prirodnih brojeva
- totalna indukcija i rekurzija nad skupom prirodnih brojeva
- Eksplicitne formule
- indukcija i rekurzija nad drugim oblastima - liste i stabla
- problemi prebrajanja
- ispitivanje složenosti algoritama
- algoritmi nad grafovima
- 2. kolokvij
|
| kolokvij - teorija (KP) | - 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.
- 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.
|
| ispit - teorija (IU) | - 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
|
| samostalno učenje (SU) | - kolokviji, konzultacije, samostalno učenje, samostalno rješavanje numeričkih zadataka
|
