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,

Grafų teorija

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 objektai, jų vaizdavimas kompiuterio atmintyje. Grafai ir jų vaizdavimo būdai. Kombinatoriniai algoritmai ir jų analizė. Algoritmų ir uždavinių sudėtingumas. Viršutinis ir apatinis rūšiavimo uždavinio sudėtingumo įverčiai.

Algoritmizavimo metodai. Metodas ‘skaldyk ir valdyk”. Dinaminis programavimas. Paieška su atkirtimu. Šakų ir rėžių metodas. Rėčio metodas. Euristiniai algoritmai.

Algoritmai grafuose. Paieška gylyn ir platyn. Dvigubai jungios komponentės. Oilerio ciklai. Hamiltono ciklai. Grafų izomorfizmas. Trumpiausi keliai grafuose. Maksimalus srautas tinkle.

Kalbų sudėtingumas. Determinuotos ir nedeterminuotos Tiuringo mašinos. Sudėtingumo hierarchija. Klasės P ir NP. 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, paskaitų konspektai (2005), http://www.mif.vu.lt/~valdas/ ALGORITMAI/KONSPEKTAI/

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.   E.M. Reingold, J.Nievergelt and N.Deo, Combinatorial Algorithms (Prentice-Hall, Englewood Cliffs, NJ, 1977).

4.   A.V. Aho, J.E. Hopcroft and J.D. Ulman, The Design and Analysis of Computer Algorithms (Adison-Wesley, Reading, MA, 1976).

5.   N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, New York, 1975).

Papildomos literatūros sąrašas

M.R. Garey and D.S. Johnson, Computers and intractability (Freeman, New York, 1979).

Mokymo metodai

Per paskaitas pasakoju prie lentos. Per pratybas privalo realizuoti (bet kuria programavimo kalba) ir išanalizuoti du algoritmus, atlikti su jais eksperimentus ir viską aprašyti.

Lankomumo reikalavimai

Užsiėmimų lankyti nebūtina. Iki egzamino būtina atsiskaityti bent vieną iš dviejų per pratybas skiriamų užduočių.

Atsiskaitymo reikalavimai

Egzaminas raštu. Į bilietą įeina 2 teoriniai klausimai, 1 uždavinys ir keletas trumpų klausimų kurso suvokimo lygiui nustatyti (pvz. nustatyti kvadratinių matricų daugybos uždavinio sudėtingumą).

Vertinimo būdas

0—4 balai už pratybas (po 2 už kiekvieną užduotį) + 0—7 balai už egzaminą.

Aprobuota katedros

2004 10 04

Patvirtinta Studijų programos komiteto

2004 11 09