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 19/20
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
NastavniciNositelji: dr. sc. Boris Čulina, prof. v. š., Aleksandar Hatzivelkos, v. pred.
PreduvjetiNema
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)
  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
auditorne vježbe (A)
  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
kolokvij - teorija (KP)
  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.
ispit - teorija (IU)
  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
samostalno učenje (SU)
  1. kolokviji, konzultacije, samostalno učenje, samostalno rješavanje numeričkih zadataka