Kursa kods DatZ7036
Fakultāte Datorikas fakultāte
Kredītpunkti, lekciju skaits
Kredītpunkti ECTS kredītpunkti Kopējais auditoriju stundu skaits Lekciju stundu skaits Semināru un praktisko darbu stundu skaits Studenta patstāvīgā darba stundu skaits
2 3 32 24 8 48
E-kursi 2DAT7036: Algoritmi sarežģītiem uzdevumiem (2)
Kursa anotācija Kursa mērķis ir iepazīstināt studentus ar algoritmiskām metodēm, kas tiek lietotas NP-sarežģītu problēmu praktiskai risināšanai.
Tradicionāli, algoritmisks uzdevums tiek uzskatīts par „praktiski atrisināmu”, ja tam eksistē algoritms, kas darbojas polinomiālā laikā, un par „praktiski neatrisināmu”, ja problēma ir NP-sarežģīta. Tajā pat laikā, reālajā dzīvē mums bieži nākas saskarties ar situācijām, kad ir jāatrod praktiski noderīgi risinājumi tieši šādām „praktiski neatrisināmām” problēmām.
Kurss iepazīstina ar svarīgākajām metodēm NP-sarežģītu problēmu risināšanai – aproksimācijas algoritmiem, Branch-and-Bound algoritmiem, u.c., un to praktiskas izmantošanas piemēriem, lielāko kursa daļu (ap 60%) veltot, iespējams, visperspektīvākajām šādu problēmu risināšanas metodēm, kas ir strauji attīstījušās pēdējos gados – parametrizētajiem algoritmiem.

Kurss iepazīstina ar parametrizētās sarežģītības un parametrizēta algoritma jēdzienu un zināmajām metodēm, kas var tikt izmantotas parametrizētu algoritmu konstruēšanai. Kursa beigās tiek dots īss ieskats par W[t] sarežģītības hierarhiju un probēmām, kas ir grūti risināmas ar parametrizētajiem algoritmiem.

Kursa atbildīgais Andris Ambainis
Rezultāti Zināšanas
1. Iegūtas zināšanas par nozīmīgākajām metodēm, kas tiek izmantotas NP-sarežģītu problēmu praktiskai risināšanai. (koncepti EM12)
Kompetences
2. Pārzin parametrizētās sarežģītības teoriju, parametrizētajiem algoritmiem un to izstrādes metodēm. (koncepti EM13, realiz. EM34, prakse EM53)
3. Padziļinātas zināšanas vairākās diskrētās matemātikas jomās, kurām ir nozīmīgi pielietojumi algoritmu izstrādē. (koncepti em11)
Prasmes

4. Iegūtas praktiskas iemaņas parametrizēto algoritmu izstrādē konkrētiem uzdevumiem (analīze EM22, realiz. em33)





Kursa plāns 1. Īss nozīmīgāko metožu NP sarežģītu problēmu praktiskai risināšanai raksturojums. (L - 2)
2. P un NP serežģītība (īss pārskats). (L - 2)
3. Pseidopolinomiāli algoritmi. (L - 2)
4. Branch-and-Bound algoritmi sarežģītu problēmu risināšanai. (L - 2, S - 2)
5. Aproksimācijas algoritmi. (L - 2)
6. Parametrizētā sarežģītība. (L - 2)
7. Labi kvazisakārtojumi, to izmantošana algoritmu eksistences pierādījumos. (L - 2, S - 2)
8. Grafu dekompozīcijas un grafu koka platums. (L - 2)
9. Koku automāti un regulāras koku izteiksmes. (L - 2)
10. Grafu parsēšana. (L - 2, S - 2)
11. MSO teorija un tās pielietojumi parametrizētu algoritmu konstruēšanai. (L - 2, S - 2)

12. Ar parametrizētiem algoritmiem grūti risināmas problēmas. (L - 2)

Prasības kredītpunktu iegūšanai 1. Noteiktajā laikā jāizpilda un jāiesniedz mājasdarbi. Kopumā mājasdarbu vērtējums dod līdz 40% no gala atzīmes.
2. Studentam ir jāizvēlas (saskaņojot ar vadītaju) zinātniska publikācija par parametrizētās sarežģītības vai aproksimācijas algoritmu tēmu, un jāuzstājas seminārā ar referātu par šajā publikācijā atspoguļotajiem rezultātiem (40%).
3. Eksāmens (mutvārdu forma - brīva diskusija par kursā aplūkoto un studenta patstāvīgi apgūto materiālu) (20%).

4. Jāizpilda LUIS anketa ar kursa novērtējumu (LU DF dekāna prasība) (0%).



Mācību literatūra 1. Rod G. Downey, Michael R. Fellows. Parametrized complexity. Springer, 1997.
2. J. Flum, M. Grohe. Parameterized Complexity Theory. Springer, 2006.
Vijey V. Vazirani. Approximation algorithms. Springer, 2004.
3. Rolf Niedermeier. Invitation to fixed parameter algorithms. Oxfor University Press, 2006.

4. Juraj Hromkovic. Algorithmics for hard problems. Springer, 2002.

Papildus literatūra 1. Michael R. Garey, David S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freedman and Company, 1979.
2. Vijey V. Vazirani. Approximation algorithms. Springer, 2004.
3. Sanjeev Arora, Boza Barak. Computational Complexity: A Modern Approach. CAmbridge University Press, 2009.

4. Tim Kloks. Treewidth: Computations and Approximations. Springer, 1994.

Periodika un citi informācijas avoti 1. H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305–1317, 1996.
2. H.L. Bodlaender. Treewidth: Algorithmic techniques and results. In I. Privara and P. Ruzicka, editors, Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, volume 1295 of Lecture Notes in Computer Science, pages 29–36. Springer-Verlag, 1997.
3. M. Cesati. The Turing way to parameterized complexity. Journal of Computer and System Sciences, 67(4):654–685, 2003.
4. M. Cesati. Compendium of Parameterized Problems. Manuscript (available from several internet locations), v2.0, 1996.
5. B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 194–242. Elsevier Science, 1990.
6. B. Courcelle. The monadic second-order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics, 54:117–149, 1995. Erratum in Discrete Applied Mathematics 63:199–200,1995.
7. B. Courcelle. The monadic second-order logic of graphs VIII: Orientations. Annals of Pure and Applied Logic, 72:103–143, 1995.
8. M. Frick and M. Grohe. The complexity of first-order and monadic secondorder logic revisited. Annals of Pure and Applied Logic, 130:3–31, 2004.
9. J. Gramm, R. Niedermeier, and P. Rossmanith. Fixed-parameter algorithms for closest string and related problems. Algorithmica, 37:25–42, 2003.
10. M. Grohe. Local tree-width, excluded minors, and approximation algorithms. Combinatorica, 23(4):613–632, 2003.
11. D.S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science (Volume A): Algorithms and Complexity, pages 67–161. MIT Press, 1990.
12. Parameterized Complexity News. Annual newsletter (available from several internet locations). 2005-2010.
13. N. Robertson and P.D. Seymour. Graph minors I–XX. Appearing in Journal of Combinatorial Theory, Series B since 1982.

14. G.J. Woeginger. Exact algorithms for NP-hard problems: A survey. In M. Junger, G. Reinelt, and G. Rinaldi, editors, Combinatorial Optimization - Eureka, You Shrink!, Papers Dedicated to Jack Edmonds, 5th International Workshop, volume 2570 of Lecture Notes in Computer Science, pages 185–208. Springer Verlag, 2001.

Studiju programmas Datorzinātnes
Datorzinātnes