Dalyko sando kodas

RMSK7114

Dalyko sando pavadinimas

RINKTINIAI MATEMATIKOS SKYRIAI

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

Prof. habil. dr. Mindaugas Bloznelis

Katedra, centras

Matematinės informatikos

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

antrosios pakopos

Semestras

rudens (1)

ECTS kreditai

3

VU kreditai

2

Auditorinės valandos

viso dalyko  32

paskaitų  32

seminarų

pratybų  

laboratorinių darbų,

konsultacijų

kontrolinių darbų skaičius-1

Reikalavimai

Klausytojai turi būti susipažine su duomenų struktūromis ir algoritmais, diskrečiaja matematika ir tikimybių teorija

Dėstomoji kalba

lietuvių, anglų

Dalyko sando tikslai ir numatomi gebėjimai

Tikslas yra pateikti tikimybinius algoritmų konstravimo ir analizės metodus, bei pagridcinius šios srities rezultatus.

Išklausęs kursą ir sėkmingai išlaikęs egzaminą (įskaitą) studentas geba analizuoti ir taikyti tikimybinius algoritmus, konstruoti nsudėtingas randomizuotas duomenų struktūras.

Dalyko sando turinys

Las Vegas ir Monte-Karlo algoritmų pavyzdžiai ir jų analizė: grafo pjūvio radimo algoritmas, greito rūšiavimo algoritmas, Find algoritmas.

Žaidimų teorijos metodų taikymas randomizuotiems algoritmams tirti.

Etikečių kolekcija ir stabilių vedybų tikimybinis algoritmas.

Markovo grandinių Monte-Karlo metodas: atsitiktinis klaidžiojimas grafe, SAT-2 uždavinio tikimybinis algoritmas.

Dinaminių duomenų struktūrų tikimybiniai konstravimo metodai.

Pagrindinės literatūros sąrašas

1.   Rajeev Motwani. Prabhakar Raghavan. Randomized Algoritms, Cambridge Univ. Pres, 2000, 475 p.

2.   Habib M., McDiarmid C.J., Ramirez-Alfonsin J., Reed B. (Eds) Probabilistic Methods for Aslgorithms Discrete Mathematics, Springer, 1998, 323 p.

3.   Cormen T.H., Leiserson C.E., Rivest R.L. Introduction to Algorithms, The MIT Press Cambridge, McGraw-Hill, 1996.

4.   Olle Hagggstrom, Finite Markov Chains and Algorithms Applications, London  Mathematical Society Student Texts 52, Cambridge University press, 2003.

Papildomos literatūros sąrašas

Mokymo metodai

Teorinės žinios pateikiamos paskaitose. Čia taip pat formuluojamos problemos ir analizuojami sprendimo metodai. Individualaus darbo metu studentų grupės (5-6 asmenys) ruošia projektus..

Lankomumo reikalavimai

70%

Atsiskaitymo reikalavimai

Įskaita. atsakymai į klausimus raštu, testas

Vertinimo būdas

50% pažymio sudaro darbas semestro metu

50%  pažymio sudaro įskaitos rezultatas. Tokiu būdu galima surinkti 10 balų. Įskaita pasirašoma už 6 balus.

Aprobuota katedros

2004 10 19

Patvirtinta Studijų programos komiteto

2004 11 09