582421 Satunnaisalgoritmit (4ov)

Prof. Tapio Elomaa

Laskuharjoitusassistentti: FM Matti Kääriäinen

Kevät 2003, 28.1.-16.4.

Luennot: ti 12-14, ke 10-12 B450
Laskarit: ke 12-14 A216
Kurssikoe: ti 6. 5. klo 16-20 Auditorio

Ajankohtaista

Kurssin tulokset (Intranet).

Course exam (Intranet). Please send us a message indicating that you are taking part in the home exam, when downloading the file. In case of problems or questions, please do not hesitate to contact Tapio / Matti.

Viimeinen laskuharjoitus salissa B453 maanantaina 28.4. klo 14-16 (pääsiäisloman takia)

Kaikki (tähänastiset) luentokalvot yhtenä tiedostona 4/arkki

Luentoviikko	Luentokalvot	Laskarit/Exercises	Sections in Course Book
1: 28.-29. 1.	2/arkki 4/arkki	Feb. 5, 2003	Appendix C, Preface, 1-1.2, 1.5
2: 4.-5. 2.	2/arkki 4/arkki	Feb. 12, 2003	Chapter 2
3: 11.-12. 2.	2/arkki 4/arkki	Feb. 19, 2003	3.1-3.3, 3.5-3.6
4: 18.-19. 2.	2/arkki 4/arkki	Feb. 26, 2003	4.1, 4.3, 4.4.1
5: 25.-26. 2.	2/arkki 4/arkki	March 5, 2003	4.4, 8.1-8.2
6: 4.-5. 3.	2/arkki 4/arkki	March 12, 2003	8.3-8.5
7: 11.-12. 3.	2/arkki 4/arkki	March 19, 2003	10.1, 10.3
8: 18.-19. 3.	2/arkki 4/arkki	March 26, 2003	5.1-5.3, 5.5
9: 25.-26. 3.	2/arkki 4/arkki	April 2, 2003	6.1-6.6
10: 1.-2. 4.	2/arkki 4/arkki	April 9, 2003	Appendix B, 6.7, 11.1
11: 8.-9. 4.	2/arkki 4/arkki	April 16, 2003	11.2, 11.4, 13.1
12: 15.-16. 4.	2/arkki 4/arkki	April 28, 2003	13.2-13.5

Yleistä

English summary

Monen ongelman ratkaisualgoritmeista yksinkertaisin ja nopein on satunnaistettu algoritmi. Kurssilla tutustutaan satunnaisalgoritmien (todennäköisyys)teoreettiseen taustaan ja niiden sovelluksiin mm. tietorakenteissa, geometrisissä menetelmissä, verkkoalgoritmeissa sekä rinnakkaisissa ja hajautetuissa algoritmeissa.

Satunnaisalgoritmit on uusi laudatur-kurssi, joka soveltuu myös jatko-opintoihin.

Kurssikirja on Motwanin ja Raghavanin Randomized Algorithms (Cambridge Univ. Press, 1995). Se löytyy kurssikirjahyllystä (katso myös kurssimappi).

Kurssin arvostelussa noudatetaan normaalia 60 pisteen skaalaa. Kokeen maksimipistemäärä on 54, mutta laskuharjoituksien aktiivisesta tekemisestä voi saada jopa 10 lisäpistettä.

Esitiedot

Algoritmien suunnittelu ja analyysi. Matematiikan opintoja (erityisesti todennäköisyyslaskenta, lisäksi lineaarialgebra).

Sisältö

0. Peruskäsitteitä (Appendix C)

1. Johdanto (Preface, Chapter 1)

• Satunnaisuuden hyödyllisyydestä
• Satunnainen Quicksort
• Min-Cut -algoritmi
• Las Vegas / Monte Carlo

2. Peliteoreettisia tekniikoita (Chapter 2)

• Pelipuun evaluointi
• Minimax-periaate
• Satunnaisuus ja ei-uniformisuus

3. Momentit ja poikkeamat (Chapter 3)

• Varausongelmia
• Markovin ja Chebyshevin epäyhtälöt
• Satunnainen valinta
• Vakaat naimakaupat
• Kuponkien kerääjän ongelma

4. Häntäepäyhtälöitä (Chapter 4)

• Chernoff raja
• Johdotusongelma
• Martingaalit

5. Tietorakenteet (Chapter 8)

• Treapit
• Hyppylistat
• Hajautusrakenteet
• Hajautus ja pahimman tapauksen vakiovaativuus

6. Verkkoalgoritmit (Chapter 10)

• Kaikkien parien lyhimmät polut
• Pienin virittävä puu

7. Probabilistinen menetelmä (Chapter 5)

• Maksimaalinen toteutuvuus
• Laajenevat verkot
• Lovaszin lokaali lemma

8. Markov-ketjut ja satunnaiskulut (Chapter 6, Appendix B)

• 2-SAT esimerkki
• Markov-ketjut
• Satunnaiskulut verkoissa
• Sähköiset virtapiirit
• Peittoajat
• Verkon yhtenäisyys
• Ekspanderit ja nopeasti sekoittuvat satunnaiskulut

9. Approksimatiivinen laskenta (Chapter 11)

• Satunnaiset approksimointiskeemat
• DNF-laskentaongelma
• Tilavuuden arviointi

10. Online-algoritmit (Chapter 13)

• Sivutusongelma
• Vastustajamallit
• Mukautumaton vastustaja ja sivutus
• Vastustajien suhteet
• Mukautuva online-vastustaja

Kirjallisuutta

• Juraj Hromkovic: Algorithms for Hard Problems (Chapter 5: Randomized Algorithms), Springer 2001
• Rajeev Motwani & Prabhakar Raghavan: Randomized Algorithms, Cambridge University Press, 1995
• Rajeev Motwani & Prabhakar Raghavan: An Overview of Randomized Algorithms, pp. 93-115 in M. Habib, C. McDiarmid, J. Ramirez-Alfonsin & B. Reed (eds.), Probabilistic Methods for Algorithmic Discrete Mathematics, Springer 1998

Linkkejä

elomaa@cs.helsinki.fi