Diskretna matematika

Nositelj

prof. dr. sc. Boris Čulina, dipl. ing. mat., pred. mr. sc. Damir Mikoč, dipl. ing. mat.

Naziv predmeta

DISKRETNA MATEMATIKA

Kod

VSITE202

Kratki naziv

DMAT

Vrsta

Izborni kolegij

Razina

Kolegij jezgre

Godina

Prva

Semestar

Zimski

ECTS
(uz odgovarajuće obrazloženje)

6 ECTS

( predavanja 45 sati – 1,5 ECTS / numeričke vježbe 30 sati  - 1 ECTS / kolokviji, konzultacije, samostalno  učenje, samostalno rješavanje numeričkih zadataka 105 sati ­- 3,5 ECTS)

Ciljevi predmeta

Osposobiti studenta za razumijevanje diskretnih modela.

Preduvjeti za upis

---

Kompetencije koje se stječu

Kolegij pruža proširena znanja diskretne matematike kao osnovu jezgre računarstva.

Ishodi učenja

Nakon uspješno položenog predmeta studenti će moći:

1. objasniti principe matematičkog modeliranja,  principe propozicijske logike i principe funkcijskog programiranja
2. primijeniti elemente matematičkog jezika, funkcije, relacije i skupove, indukciju i rekurziju, operacije nad skupovima i
3. razlikovati algebarske strukture i procijeniti složenost algoritama.

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. Asimptotska 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.

Preporučena literatura

1. Žubrinić, D.: Diskretna matematika, Element Zagreb, 1997.

Dopunska literatura

Osiguranje literature

Svi nastavni materijali su dostupni studentu u elektroničkom obliku.

Student dobiva u trajno vlasništvo tiskani primjerak udžbenika ili skripte (izdanje VSITE).

Oblici provođenja nastave

Predavanja, numeričke vježbe, konzultacije

Način provjere znanja i polaganja ispita

-       Kontinuirana provjera tijekom nastave (kolokviji po cjelinama)

-       Završni ispit (pismeni/usmeni)

Jezik poduke i mogućnosti praćenja na drugim jezicima

hrvatski, engleski

Način praćenja kvalitete i uspješnosti izvedbe svakog predmeta i /ili modula

-       Anketa o kvaliteti izvođenja nastave i nastavnih materijala

-       Pohađanje nastave i aktivnost u nastavi (povremena provjera od strane voditelja studija)

-       Vrednovanje rezultata ispita (godišnje)