Dalyko sando kodas

ALAN2114

Dalyko sando pavadinimas

Algoritmų analizė

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

pirmosios pakopos

Semestras

pavasario (6) 

ECTS kreditai

4,5

VU kreditai

3

Auditorinės valandos

viso dalyko 64

Paskaitų 32

seminarų

pratybų

laboratorinių darbų 32

konsultacijų

Reikalavimai

INFO2214, MDIS2114, TTMS1114, ALGE1114, KGTE2214

Dėstomoji kalba

lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

Susipažinti su pagrindiniais algoritmų konstravimo metodais ir kombinatoriniais algoritmais. Išmokti įvertinti algoritmų bei uždavinių sudėtingumą ir pasirinkti optimalesnį algoritmą. Mokėti atskirti praktiškai tinkamus algoritmus nuo praktiškai netinkamų eksponentinio sudėtingumo algoritmų. Mokėti taikyti apytikslius algoritmus.

Dalyko sando turinys

Kombinatoriniai algoritmai ir jų analizė. Algoritmų ir uždavinių sudėtingumas. Viršutinis ir apatinis rūšiavimo uždavinio sudėtingumo įverčiai.

Kombinatoriniai objektai: sveikieji skaičiai, sekos, aibės, medžiai, grafai. Kombinatorinių objektų vaizdavimas kompiuterio atmintyje. 

Algoritmų konstravimo metodai. Metodas „skaldyk ir valdyk“. Dinaminis programavimas. Paieška su atkirtimu. Šakų ir rėžių metodas. Euristiniai algoritmai. Algoritmai grafuose. Paieška gilyn ir platyn. Dvigubai jungios grafo komponentės. Oilerio ciklai. Hamiltono ciklai. Grafų izomorfizmas. Trumpiausi keliai grafuose. Maksimalus srautas tinkle.

Kalbų sudėtingumas. Klasės P ir NP. Sudėtingumo klasių hierarchija. NP-pilni uždaviniai, jų pavyzdžiai. Apytiksliai algoritmai.

Pagrindinės literatūros sąrašas

1. V. Dičiūnas, Algoritmų Analizės Pagrindai, elektroninė mokymo priemonė (VU, Vilnius, 2005), http://www.mif.vu.lt/katedros/cs/Asmen/algoritmu_analize.pdf

2.  T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms (The MIT Press/McGraw-Hill, Cambridge, MA/New York, 1990).
3. R. Čiegis, Duomenų Struktūros, Algoritmai ir jų Analizė (Technika, Vilnius, 2007).

4.  E.M. Reingold, J.Nievergelt and N.Deo, Combinatorial Algorithms (Prentice-Hall, Englewood Cliffs, NJ, 1977).

Papildomos literatūros sąrašas

Mokymo metodai

Paskaitos, konsultacijos, individualūs namų darbai ir 1 laboratorinis darbas. Namų darbus bei laboratorinį darbą galima atlikti namuose arba pratybų metu.

Lankomumo reikalavimai

Paskaitų lankomumui specialių reikalavimų nėra, bet galutinį egzaminą leidžiama laikyti tik semestro metu už namų darbus ir laboratorinį darbą surinkus ne mažiau kaip 2 balus ir atlikus ne mažiau kaip 40% namų darbų.

Atsiskaitymo reikalavimai

Namų darbai atliekami raštu ir apginami per pratybas iki nustatytos datos. Laboratorinis darbas pateikiamas kartu su 4-5 psl. ilgio darbo aprašymu ir apginamas per pratybas iki nustatytos datos. Egzaminas raštu.

Vertinimo būdas

20-30% namų darbai, 30% laboratorinis darbas, 40-50% egzaminas.

Aprobuota katedros

2009 02 02

Patvirtinta Studijų programos komiteto

2009 02 03