Dalyko sando aprašas

 

Dalyko sando kodas

(Course unit code)

MDIS2114

Dalyko sando pavadinimas

(Course unit title)

Diskrečioji matematika

Dėstytojo (-jų) pedagoginis vardas, mokslo laipsnis, vardas ir pavardė

(Name and title of lecturer)

Dr. Valdas Dičiūnas

Katedra, centras

Informatikos katedra

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

(Level of course)

Pirmosios pakopos

Semestras

(Semester)

Rudens (1)

ECTS kreditai

(ECTS credits)

6

VU kreditai

(VU credits)

4

Auditorinės valandos

Viso dalyko  80

 

Paskaitų  48

 

Seminarų

 

Pratybų  32

 

Laboratorinių darbų

 

Konsultacijų

Reikalavimai

(Prerequisites)

Mokyklinės matematikos žinojimas

 

Dėstomoji kalba

(Language of instruction)

Lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

(Objectives and learning outcomes)

Susipažinti su diskrečiojoje matematikoje nagrinėjamais objektais ir jų savybėmis: aibėmis, sąryšiais, grafais, Būlio funkcijomis ir schemomis, loginiais samprotavimais, algo-ritmais bei kodais. Įsisavinti ir mokėti taikyti diskrečiosios matematikos, matematinės logikos ir algoritmų teorijos metodus. Mokėti įvertinti algoritmų sudėtingumą ir identifikuoti algoritmiškai neišsprendžiamas problemas.

Dalyko sando turinys

(Course unit content)

Baigtinės, skaičiosios ir kontinuumo galios aibės. Aibių operacijos. Sąryšiai ir funkcijos. Hesės diagramos.

Būlio funkcijos ir formulės. Formulių taikymas aibių teorijoje. Disjunktyvioji ir konjunktyvioji normaliosios formos. Pilnos Būlio funkcijų sistemos. Pagrindinės grafų sąvokos. Būlio schemos. Būlio schemų bei funkcijų sudė-tingumas.

Teiginių logika. Predikatų logika. Loginių samprotavimų teisingumas. Formaliosios teorijos ir teoremų įrodymo metodai.

Algoritmai ir jų savybės. Determinuotos ir nedetermi-nuotos Turingo mašinos.  Algoritmų sudėtingumas. Užda-vinių sudėtingumo klasės.

Abėcėliniai kodai ir jų savybės. Geometrinis kodo iššifruo-jamumo kriterijus. Optimalūs Hafmano kodai.

Pagrindinės literatūros sąrašas (Reading list)

1.    V. Dičiūnas, Diskrečiosios Matematikos Paskaitos, www.mif.vu.lt/valdas/diskrmat.

2.    K.H. Rosen, Discrete Mathematics and Its Applica-tions,   McGraw-Hill, Boston, 2003.

3.    S. Norgėla, Matematinė Logika, Leidykla TEV, Vilnius, 2004.

4.    S.V. Jablonskij, Vvedenije v Diskretnuju Matematiku, 2-as leid., Nauka, Maskva, 1986 (rusų k.).

5.    V. Stakėnas, Informacijos Kodavimas, VU leidykla, Vilnius, 1996.

Papildomos literatūros sąrašas

1.    O.P. Kuznecov, G.M. Adel'son-Vel'skij, Diskretnaja Matematika dlia Inženera, Energoatomizdat, Maskva, 1988 (rusų k.).

2.    G.P. Gavrilov, A.A. Sapoženko, Sbornik Zadač po Diskretnoj Matematike, Nauka, Maskva, 1977 (rusų k.).

Mokymo metodai

(Teaching methods)

Paskaitos, pratybos, konsultacijos ir kontrolinis darbas.

 

Lankomumo reikalavimai (Attendance requirements)

Ne mažiau 80%  paskaitų ir pratybų. 

Atsiskaitymo reikalavimai (Assessment requirements)

Egzaminas raštu. Į egzamino bilietą įeina viena teorema su įrodymu, apibrėžimai, teoremų formuluotės, uždaviniai, pavyzdžių ir kotrapavyzdžių konstravimas.

Vertinimo būdas

(Assessment methods)

Iki 3 balų už kontrolinį darbą ir iki 8 balų už egzaminą, po to sumuojama.

Aprobuota katedros

2009-08-31

Patvirtinta Studijų programos komiteto

2010-02-10