Algoritmų projektavimas ir analizė
Dalyko anotacija lietuvių kalba
Kursas supažindina su svarbiausiais algoritmais, kurie yra sudedamosios dalys, kuriant kitus sudėtingesnius algoritmus. Kursas apima pagrindines duomenų struktūras, svarbiausius grafų teorijos ir simbolių sekų apdorojimo algoritmus, pristato algoritmų sudėtingumo analizę. Baigę kursą studentai sugebės projektuoti efektyvius algoritmus, teoriškai įvertinti ir pagrįsti projektavimo pasirinkimus. Efektyvūs algoritmai leis optimaliai išnaudoti skaičiavimo resursus ir taip įgalinti algoritmus spręsti didelės apimties taikomuosius uždavinius.
Dalyko anotacija užsienio kalba
This course introduces algorithms that are used as building blocks for constructing more complex algorithms. The course covers elementary data structures, sorting and searching algorithms, graph and string-processing algorithms, introduces students to the theory of algorithmic complexity. Upon successful completion of the course, students will be able to design efficient algoritms and to present theoretical justifications for their design decisions. Efficient algorithms will enable optimum allocation of computational resources and computationally addressing large problems.
Būtinas pasirengimas dalyko studijoms
Aukštoji matematika 1, Aukštoji matematika 2, Programavimo pagrindai
Dalyko studijų rezultatai
1. Sudaryti ir suderinti programą, kai žinomas algoritmo pseudokodas.
2. Mokėti parinkti efektyvią paieškos, rikiavimo ir duomenų modifikavimo strategiją bei tinkamą fizinę duomenų saugojimo struktūrą, sprendžiant didelės apimties (skaičiavimo resursų prasme) taikomuosius uždavinius.
3. Mokėti formuluoti taikomuosius uždavinius grafų teorijos kalba, mokėti taikyti grafų teorijos algoritmus.
4. Mokėti formuluoti taikomuosius uždavinius kaip simbolių sekų manipuliavimo uždavinius, mokėti taikyti simbolių sekų apdorojimo algoritmus.
5. Skirti kompiuteriu sprendžiamus ir kompiuteriu nesprendžiamus (pilno perrinkimo) uždavinius.
Dalyko turinys
1. Algoritmo suirinkimas iš "statybinių blokų". Algoritmų pseudokodas ir jo skaitymas.
2. Duomenų struktūros: aibės ir jų apjungimas, binarinė paieška, stekai, eilės, krepšiai. Algoritmų sudėtingumo įvertinimas.
3. Rikiavimo algoritmai: rikiavimas įterpimo būdu, rikiavimas išrinkimo būdu, Šelo rikiavimo algoritmas, greitojo rikiavimo algoritmas, 3 dalių greitojo rikiavimo algoritmas, rikiavimas sąlajos būdu, rikiavimas krūvos būdu.
4. Binarinės krūvos, binariniai paieškos medžiai, raudoni-juodi medžiai.
5. Dėstymo lentelė (hash) ir tiesinis dėstymas.
6. Graham‘o skenavimo algoritmas ir k-d medžiai.
7. Grafai ir jų vaizdavimo būdai. Rikiavimo ir paieškos grafuose algoritmai: paieška į gylį, paieška į plotį, topologinis rikiavimas.
8. Keliai ir jungiantieji medžiai grafe. Trumpiausioeji keliai ir trumpiausieji jungiantieji medžiai: Kosaraju algoritmas, Kruskal'io algoritmas, Parnik-Prim-Dijkstra algoritmas, Dijkstra algoritmas, Bellman-Ford algoritmas, Ford-Fulkerson metodas.
9. Skaitmeninins rikiavimas (radix sort) pagal reikšmingiausią ir nereikšmingiausią bitus, 3 dalių skaitmeninis rikiavimas.
10. Daugianariai prefiksų medžiai, trinariai paieškos medžiai.
11. Rikiavimas ir paieška simbolių sekose: Knuth-Morris-Pratt algoritmas, Boyer-Moore paieškos algoritmas, Rabin-Karp algoritmas.
12. Reguliariosios išraiškos.
13. RLE kodavimas, Hofmano kodavimas.
14. LZW duomenų suspaudimo algoritmas, Burrows-Wheeler transformacija.
15. P, NP ir NP pilnoji sudėtingumo klasės, kompiuteriu spręstini ir nespręstini uždaviniai, algoritmų sudėtingumo įvertinimas.
Dalyko studijos valandomis
Paskaitos (P) 45 val.
Laboratoriniai darbai (L) 22,5 val.
Savarankiškas darbas 52,5 val.
Iš viso 120 val.
Studijų rezultatų vertinimas
Tarpinis atsiskaitymas – 17%, laboratoriniai darbai – 33%, baigiamasis egzaminas – 50%.
Literatūra
1. 2009 Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms (3rd Ed.) The MIT Press http://ebook-dl.com/item/introduction_to_algorithms_clrs/
2. 2012 Levitin A., Introduction to the design & analysis of algorithms (3rd Ed.) Pearson http://ebook-dl.com/item/introduction_to_the_design_and_analysis_of_algorithms_3rd_edition_anany_levitin/
3. 2008 Heineman G.T., Pollice G., Selkow S., Algorithms in a Nutshell O‘Reilly Media http://ebook-dl.com/item/algorithms_in_a_nutshell_george_t_heineman_gary_pollice_stanley_selkow/
Papildoma literatūra
1. 1997 Skiena S.S., The Algorithm Desig Manual (1st Ed.) Springer-Verlag http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK/BOOK.HTM
2. 2016 Wayne K, Sedgewick R., Algorithms Part I, Part II (nuotolinio mokymo kursas) Princeton University / Coursera https://www.coursera.org/course/algs4partI
2002 K.Plukas, E.Mačikėnas, B.Jarašiūnienė, I.Mikuckienė. Taikomoji diskrečioji matematika. Technologija
