Dalyko sando kodas

IRAL7124

Dalyko sando pavadinimas

Randomizuoti algoritmai

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

Prof. habil. dr. Mindaugas Bloznelis

Katedra, centras

Matematinės 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ų

pratybų 32

laboratorinių darbų

kontrolinių darbų skaičius - 2

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 pagrindinius šios srities rezultatus

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

Dalyko sando turinys

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

2.    Žaidimų teorijos metodų taikymas randomizuotiems algoritmams tirti.

3.   Etikečių kolekcijos tikimybinis modelis. Taikymai stabilių vedybų tikimybiniam algoritmui ir Hamiltono ciklo paieškai.

4.  Markovo grandinių Monte-Karlo metodas. Atsitiktinis klaidžiojimas grafe.  SAT-k uždavinio tikimybinis algoritmas, kai k=2,3.

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. Uždavinių sprendimo metodai

analizuojami pratybų metu. Taip pat pratybų metu pristatomi projektai diskusijai. Projektus rengia studentai individualiai ar keliu studentų grupės.

Lankomumo reikalavimai

Būtina lankyti ne mažiau nei 70% pratybų.

Atsiskaitymo reikalavimai

Egzaminas. Atsakymai į klausimus raštu (egzamino metu). Būtina už darbą semestro metu surinkti ne mažiau nei 3 balus (iš 7 = maksimalus balų skaičius už darbą semestro metu). Projektinį darbą būtina atsiskaityti laiku (laikantis tvarkaraščio).

Vertinimo būdas

70% galutinio pažymio sudaro darbas semestro metu: (projektas max 4 balai) + (kontrolinis max 3 balai).

30%  pažymio sudaro rašto darbas – egzaminas (max 3 balai). 

Aprobuota katedros

2009 02 07

Patvirtinta Studijų programos komiteto

2009 02 10