Diskretna matematika

Naziv predmeta

DISKRETNA MATEMATIKA

Kod

VSITE005

Vrsta

Obvezatni kolegij

Razina

Kolegij napredne razine

Godina

Treća

Semestar/trimestar

Proljetni / 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)

Nastavnik

dr. sc. Boris Čulina, viši pred.

Kompetencije koje se stječu

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

Preduvjeti za upis

Položeno VSITE001,002 i 003

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.

Preporučena literatura

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

Dopunska literatura

 

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)