Pagrīdes universitāte

"Pagrīdes universitāte" piedāvā lekcijas par tēmām uz matemātikas un datorzinātnes robežas. Tā ir iespēja paplašināt savas zināšanas vai vienkārši pavingrināt „pelēkās šūniņas”.

Šie lekciju kursi neprasa klausītāju reģistrēšanos, tādēļ tos var apmeklēt gan klausītāji, kas nav droši par savām zināšanām un vēlēšanos par kursu saņemt atzīmi, gan cilvēki ar jau pietiekamu kredītpunktu apjomu. (Ja kādam ir vēlme - var arī reģistrēties kā uz specsemināru (datorzinātņu bakalaura programma) un saņemt 2 kredītpunktus.)

„Pagrīdes universitāte” savu darbību sāka 2009.gadā, kad profesors A. Ambainis pavasara semestrī visiem interesentiem lasīja un skaidroja grafu teorijas tēmas, bet profesors R. M. Freivalds semestra otrajā pusē – par nekonstruktīviem automātiem. Klausītāju atsaucības dēļ tika nolemts „Pagrīdes universitāti” turpināt nākošajos semestros.

Šajā semestrī tiek plānots lekciju cikls:

Prof. Andris Ambainis:

- Laiks: piektdienas, 14:30 (sākot ar 14. septembri);

- Vieta: Raiņa 19, 12. auditorija;

- Tēma: optimizācija.

1) Dažādu optimizācijas uzdevumu piemēri un algoritmi to risināšanai. Piemēram:

- Traveling salesman problem: dotas n pilsētas un attālumi starp tām. Atrast īsāko ceļu, kas iziet caur visām pilsētām;

- Shortest superstring: dotas vairākas simbolu virknes. Atrast īsāko simbolu virkni, kas satur visas šīs simbolu virknes.

2) Lineārā programmēšana: metode, kā aprakstīt un risināt daudzas optimizācijas problēmas.

Tēmas pa lekcijām

Datums	Tēmas	Literatūra
14. septembris	Ievads optimizācijā. Vertex cover problēma.	Vazirani, 1.1 nodaļa vai Trevisan, 1. lekcija
21. septembris	Alkatīgie algoritmi. Set cover un max cut problēmas.	Vazirani 2.1 nodaļa un2.1 uzdevums
19. oktobris	Alkatīgie algoritmi. K-center problēma un uzdevumu plānošana uz vienādiem serveriem.	Williamson, 2.2 un 2.3 nodaļa

Literatūra

L. Trevisan. Combinatorial Optimization: Exact and Approximate Algorithms. Lecture Notes, Stanford University, 2011.

V. Vazirani. Approximation Algorithms. Springer, 2001.

D. Williamson, D. Shmoys. Design of Approximation Algorithms, Cambridge University Press, 2010.