Algoritmų analizė (MIT)
Dalyko anotacija lietuvių kalba
Kurse supažindinama su algoritmais, kurie naudojami sudėtingesnių algoritmų kūrimui, grafų teorija, grafų algoritmais, algoritmų sudėtingumu, baigtinių automatų teorija, Tiuringo mašina, universalia Tiuringo mašina ir jų taikymu procesų modeliavimui.
Dalyko anotacija užsienio kalba
Course introduces algorithms that are used as building blocks for bigger algorithm construction, graph theory and algorithms on graphs, algorithm complexity, finite automata theory, Turing machine and universal Turing machine and their application for modelling of computational processes.
Būtinas pasirengimas dalyko studijoms
Matematika 1, Matematika 2, Programavimo pagrindai
Dalyko studijų rezultatai
Suprasti grafų teorijos principus.
Suprasti algoritmų sudėtingumo principus.
Suprasti baigtinių būsenų automatų principus.
Gebėti naudoti grafų teorijos algoritmus sprendžiant praktinius uždavinius
Gebėti naudoti baigtinių būsenų automatus sprendžiant praktinius uždavinius.
Gebėti naudoti grafų teorijos algoritmus įvairiuose srityse
Gebėti įvertinti uždavinių sudėtingumą ir atskirti pilno perrinkimo uždavinius nuo kitų.
Gebėti taikyti baigtinių būsenų automatus skaitmeninių procesų modeliavimui.
Dalyko turinys
- Grafai ir jų vaizdavimo būdai. Algoritmų pseudo-kodai ir jų interpretavimas.
- Keliai ir jungiantys medžiai grafuose.
- P, NP ir NP-pilnos klasės sudėtingumas.
- Baigtinių būsenų automatai.
- Tiuringo mašina.
- Paieška platyn ir paieška gilyn grafuose
- Trumpiausi keliai ir trumpiausi jungiantys medžiai.
- Oilerio ir Hamiltono ciklai grafuose. Kiti grafų teorijos uždaviniai
- Baigtinių būsenų automatai.
- Tiuringo mašina.
- Algoritmų sudėtingumas. Grafų uždavinių sudėtingumas.
- Pilno perrinkimo uždavinių sudėtingumo įvertinimas. Rekursinių algoritmų sudėtingumas.
- Baigtinių būsenų automatai ir skaitmeninių procesų modeliavimas.
- Tiuringo mašina ir jos naudojimas skaitmeninių procesų modeliavime.
Dalyko studijos valandomis
Paskaitos 30 val.
Laboratoriniai darbai 30 val.
Iš viso kontaktinio darbo val. 60 val.
Savarankiškas darbas 74 val.
Iš viso 134 val.
Studijų rezultatų vertinimas
Kolokviumas – 20%, Laboratoriniai darbai – 30%, Egzamino užduotis – 50%
Literatūra
1. 2002 K.Plukas, E.Mačikėnas, B.Jarašiūnienė, I.Mikuckienė. Taikomoji diskrečioji matematika
2. 2011 A.Levitin, Introduction to the design and analysis of algorithms, 3rd edition https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Introduction%20to%20the%20Design%20and%20Analysis%20of%20Algorithms%20%283rd%20ed.%29%20%5BLevitin%202011-10-09%5D.pdf
Papildoma literatūra
1. 2002 T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms
2. 2010 H. Straubing, P. Weil. An introduction to finite automata and their connection to logic https://www.researchgate.net/publication/47860229_An_Introduction_to_Finite_Automata_and_their_Connection_to_Logic/link/555c717108ae6aea08176044/download
