Dalyko sando aprašas

 

Dalyko sando kodas

(Course unit code)

bus suteiktas registruojant į DB

(Senas sando kodas - MDIS7114)

Dalyko sando pavadinimas (Course unit title)

Diskrečioji matematika ir algoritmai

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

(Name and title of lecturer)

Prof. habil. dr. Eugenijus Manstavičius

Katedra, centras

Tikimybių teorijos ir skaičių teorijos katedra

Fakultetas, padalinys

Matematikos ir informatikos fakultetas

Dalyko sando lygis

(Level of course)

Antrosios pakopos

Semestras

(Semester)

Rudens (1)

ECTS kreditai

(ECTS credits)

7,5

VU kreditai

(VU credits)

5

Auditorinės valandos

Iš viso dalyko  80

 

Paskaitų  64

 

Seminarų  16

 

Pratybų 

 

Laboratorinių darbų

 

Konsultacijų

Reikalavimai

(Prerequisites)

Kombinatorika ir grafų teorija, programavimo pradmenys

 

Dėstomoji kalba

(Language of instruction)

Lietuvių

Dalyko sando tikslai ir numatomi gebėjimai

(Objectives and learning outcomes)

Įsisavinti diskrečiosios matematikos klasikinius rezultatus, susipažinti su naujovėmis bei jos taikymų sritimis. Išmokti generuoti kombinatorines struktūras kompiuteryje, įsisavinti ir analizuoti grafų algoritmus; 

Dalyko sando turinys

(Course unit content)

Kombinatorinių struktūrų pavyzdžiai. Jų skaičiavimo metodai. Kombinatorinių struktūrų klasės. Struktūrų generuojančios funkcijos.Skirtingi aibių šeimos atstovai. Hall’o vedybų problema. Ekstremaliosios aibių teorijos elementai.  Sperner’io šeima. Steiner’io trejetų sistemos. Ramsey’io skaičių įverčių pavyzdžiai.

Grafų algoritmai. Paieška į plotį, paieška į gylį.Minimalūs jungiantieji medžiai, Kruskalio ir Primo algoritmai. Trumpiausi keliai iš vienos viršūnės, Dijkstros ir  Belmano-Fordo algoritmai. Trumpiausi keliai tarp visų viršūnių porų, Floydo-Varšalo bei Džonsono algoritmai.

Srautų digrafai. Maksimalaus srauto ir minimalaus srauto problema. Menger’o ir Hall’o teoremos. Maksimalaus srauto algoritmai, Fordo-Fulkersono metodas, priešsraučio stūmimo bei perkėlimo į priekį algoritmai.

Pagrindinės literatūros sąrašas (Reading list)

1.      P. Cameron, Combinatorics:Topics, Techniques, Algorithms,  Cambridge University Press,  1996.

2.      Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms; McGraw-Hill Book Company, 1993.

3.      E. Manstavičius, Paskaitų konspektas, http://www.mif.vu.lt/katedros/ttsk/bylos/man/files/grman.pdf.

Papildomos literatūros sąrašas

1.      Ph.Flajolet, R.Sedgewick, Analytic Combinatorics, Internetas,

2.      M.Aigner, G.M.Ziegler, Proofs from the BOOK, Springer, 2nd ed., 2001.

3.      H. Wilf, Generatingfunctionology, Academic Press, San Diego, sec. edn., 1994.

4.      V.N. Sačkov, Diskrečiosios matematikos kombinatorinių metodų įvadas, „Nauka“, Maskva, 1982

Mokymo metodai

(Teaching methods)

Paskaitos. Teiginiai iliustruojami pavyzdžiais, algoritmai pateikiami simboliniais kodais. Griežtai analizuojamas kompleksiškumas ir korektiškumas. Seminare studentai paaiškina namuose parašytų programų principus bei demonstruoja jų veikimą nešiojamame kompiuteryje.

Lankomumo reikalavimai (Attendance requirements)

Paskaitų 70%, seminarų 100 %.

 

Atsiskaitymo reikalavimai (Assessment requirements)

Egzaminas raštu. Techniškų įrodymų detales mokėti paaiškinti pagal konspektą. Būtina parašyti tris veikiančias  programas.

 

Vertinimo būdas

(Assessment methods)

Už egzamino bilieto klausimą – 7 balai, už programas – 3 balai.

Aprobuota katedros

2006-03-27

Patvirtinta Studijų programos komiteto

2006-04-13