Dalyko sando kodas

IRDS7114

Dalyko sando pavadinimas

Rinktiniai diskrečių struktūrų skyriai

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

Dr. Valdas Dičiūnas

Katedra, centras

Informatikos katedra

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

antrosios pakopos

Semestras

pavasario (2)

ECTS kreditai

6

VU kreditai

4

Auditorinės valandos

viso dalyko 64

Paskaitų 32

seminarų 16

pratybų 16

laboratorinių darbų

konsultacijų

Reikalavimai

Diskrečioji matematika, Algoritmų teorija, Algoritmų analizė, Kombinatorika ir grafų teorija

Dėstomoji kalba

lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

Įvaldyti pagrindinius skaičiavimo modelius, suprasti jų galimybes ir ryšius tarp skirtingų skaičiavimo modelių. Išmokti taikyti baigtinius automatus bei reguliarias ir bekontekstes gramatikas sintaksinėje analizėje, paieškos mechanizmų kūrime ir transliavimo metoduose.  Įsisavinti uždavinių sudėtingumo hierarchiją ir mokėti įvertinti uždavinių sudėtingumą.

Dalyko sando turinys

Skaičiavimo modeliai: baigtiniai automatai, reguliarios kalbos, įvairių tipų Turingo mašinos, mašinos su neribotais registrais, Būlio schemos. Jų galimybės ir tarpusavio ryšiai.

Reguliarios kalbos. Determinuoti ir nedeterminuoti baigtiniai automatai. Reguliarių reiškinių ir baigtinių automatų ryšys. Bekontekstės gramatikos, stekiniai  auto-matai, jų panaudojimas sintaksinei analizei.

Kalbų ir uždavinių sudėtingumas.  Laiko ir erdvės sudėtingumas. Polinominė uždavinių redukcija. Uždavinių sudėtingumo klasės P, NP, NPC, PSPACE ir jų hierarchija.

Pagrindinės literatūros sąrašas

1.      J.L. Hein, Discrete Structures, Logic, and Computability, 2nd Edition,Jones and Bartlett, 2002.

2.      J.E. Hopcroft, R. Motwani and J.D. Ulman, Introduction to Automata Theory, Languages and Computation, 2nd Edition, Addison-Wesley, Reading, MA, 2001.

3.  M. Sipser, Introduction to the Theory of Computation, 2nd edition, Course Technology, 2005

Papildomos literatūros sąrašas

1.      J. Hromkovic, Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.

2.      B.M. Moret, The Theory of Computation, Addison-Wesley, Reading, MA,1998.

3.  M.J. Atallah (Ed.), Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton, FL, 1999.

Mokymo metodai

Paskaitos, pratybos, seminarai, konsultacijos, kontro-linis darbas. Seminaruose studentai daro pranešimus iš papildomų temų.

Lankomumo reikalavimai

Laikyti egzaminą galima dalyvavus 50% seminarų bei pratybų bei padarius pranešimą seminare.

Atsiskaitymo reikalavimai

Pasisakymas ir aktyvumas seminaruose bei pratybose, kontrolinis darbas iš pratybų medžiagos, egzaminas raštu.

Vertinimo būdas

Kaupiamasis pažymys: 20% pasisakymas ir aktyvumas seminaruose, 20% kontrolinis darbas, 60% egzaminas raštu.

Aprobuota katedros

2008 10 20

Patvirtinta Studijų programos komiteto

2005 11 24