Kursa kods DatZ7025
Fakultāte Datorikas fakultāte
Kredītpunkti, lekciju skaits
Kredītpunkti ECTS kredītpunkti Kopējais auditoriju stundu skaits Lekciju stundu skaits Studenta patstāvīgā darba stundu skaits
2 3 32 32 48
E-kursi 2DAT7018: Algoritmu sarežgītība
Kursa anotācija Algoritmu sarežģītība pēta dažādus skaitļošanas modeļus un skaitļošanas procesā izmantojamus resursus. Šajā kursā tiks apskatīti sekojoši skaitļošanas modeļi: determinētie algoritmi, nedeterminētie algoritmi, varbūtiskie algoritmi un loģiskās shēmas un divi svarīgākie skaitļošanā izmantojamie resursi: skaitļošanas laiks un izmantotā atmiņa (telpa).

Kursa atbildīgais Juris Smotrovs
Rezultāti Zināšanas
1. Students pārzin galvenās algoritmu sarežģītības klases (P, NP, PSPACE) un sakarības starp tām (koncepti em11, EM12).
2. Students prot pamatot, kāpēc konkrētas problēmas ir NP-pilnas vai pilnas citām sarežģītības klasēm (piemēram, PSPACE vai LOGSPACE). (koncepti em12, analīze EM22)
Prasmes
3. Students pārzin dažādus skaitļošanas modeļus (Tjūringa mašīnas, loģiskās shēmas, izvēles kokus) un spēj pierādīt sakarības starp tiem. (koncepti em11, EM12)
Kompetences
4. Students pārzin interaktīvu pierādījumu pamatjēdzienus un prot tos pielietot vienkāršām skaitļošanas problēmām (koncepti em12, realiz. em34, prakse em52)

5. Students zin galvenās sakarības starp dažādām varbūtiskās sarežģītības klasēm (BPP, PP, #P) un spēj tās pamatot (koncepti em12, prakse em52)





Kursa plāns 1. Pamatjēdzieni: lielā O apzīmējums, Tjūringa mašīnas (2st. lekcijas, 3 st. pst. darbs).
2. Polinomiāls laiks, klases P un NP (4st. lekcijas, 6 st. pst. darbs).
3. Laika un telpas sarežģītība, klase PSPACE (6st. lekcijas, 9st. pst. darbs).
4. Polinomiālā hierarhija (3 st. lekcijas, 4st. pst. darbs).
5. Loģiskās shēmas un ar tām saistītās sarežģītības klases (3 st. lekcijas, 5st. pst. darbs).
6 Varbūtiskie algoritmi (3 st. lekcijas, 4st. pst. darbs).
7. Sarežģītības klase #P (4 st. lekcijas, 6st. pst. darbs).
8. Interaktīvie pierādījumi, klase IP (4 st. lekcijas, 6st. pst. darbs).

9. Izvēles koki kā alternatīvs skaitļošanas modelis (3 st. lekcijas, 5st. pst. darbs).
Prasības kredītpunktu iegūšanai Atzīmi veido:
1. 3 vai 4 mājas darbi: 60% no atzīmes.

2. Eksāmens (uzstāšanās ar prezentāciju par neseniem zinātniskiem rakstiem, par tēmu, kas saskaņota ar pasniedzēju): 40% no atzīmes.


Mācību literatūra 1. Sanjeev Arora, Boaz Barak, Complexity Theory: A Modern Approach. Cambridge University Press, 2008. (LUB pieejams 1 eksemplārs).
2. Christos H. Papadimitriou. Computational Complexity. Addison Wesley, 1995 (LUB pieejams 1 eksemplārs).

3. Oded Goldreich. Computational Complexity: A Conceptual Approach. Cambridge University Press, 2008 (LUB pieejams 1 eksemplārs).



Papildus literatūra 1. Michael Sipser. Introduction to the Theory of Computation. Course Techology, 2005 (LUB pieejams 1 eksemplārs).
2. M. R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979 (LUB pieejams 1 eksemplārs).
3. Lane A. Hemaspaandra, Mitsunori Ogihara. The Complexity Theory Companion. Springer, 2002 (LUB pieejams 1 eksemplārs).

4. Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer, 1999 (LUB pieejams 1 eksemplārs).



Periodika un citi informācijas avoti 1. Kursa materiāli Moodle e-studiju vidē.

2. John Savage. Models of Computation: Exploring the Power of Computation. http://www.cs.brown.edu/people/jes/book/



Studiju programmas Datorzinātnes
Datorzinātnes