OHJ-2650 Algoritmiikan vaihtuva-aiheinen kurssi, 5 op

Todennäköisyys ja laskenta

Prof. Tapio Elomaa

Lkv 2005-2006, periodit III ja IV

Luennot: 5.12.-14.3.: ma 14-16 ja ti 12-14 TC210

Opintopiiri: ma 12-14 TC210

Kurssikoe: ke 22.3. 17-20

Ajankohtaista

Kotikokeen tehtäväpapereita saa toisen kerroksen lokerosta nro 214. .

Seuraava tentti 8. toukokuuta 2006.

Yleistä

Kurssin pääsivu.

Syventäviin opintoihin kuuluva ohjelmistotieteen vaihtoehtoinen opintojakso, joka soveltuu erityisesti jatko-opintoihin.

Ensimmäisen toteutuksen aihe on Todennäköisyys ja laskenta, eli satunnaisalgoritmit ja algoritmien satunnaistettu analyysi. (Tulevien vuosien aiheiksi on kaavailtu koneoppimista ja approksimointialgoritmeja).

Kurssi on normaali luentokurssi.

Opintopiiri

• Tehtäviä saa paperilla toisen kerroksen lokerosta nro 214.
• Kurssin opintopiiri kokoontuu maanantaisin klo 12-14 salissa TC210.
• Opintopiirissä keskustellaan osallistujien kesken edellisellä viikolla annettujen tehtävien ratkaisuista.
• Mikäli konsensusta tehtävän ratkaisusta ei opintopiirissä löydetä, on luennoija luvannut toimittaa mallivastauksen.

Luennot

Kurssilla seurataan uskollisesti oppikirjaa, Kirjaa pyritään käymään läpi mahdollisimman paljon, ihan kaikkea ei millään ehditä.

Kurssikirja: Michael Mitzenmacher, Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Oppikirja on saatavana Juveneksen kirjakaupasta hintaan 55 e

Viikko	Päivät	Kalvot	Harjoitukset	Kirjan luvut
1	5.12.	PS ja PDF	-	-
2	12.-13.12.	PS ja PDF	1.3, 1.6, 1.13, 1.15, 1.21	Chapter 1
3	19.-20.12.	PS ja PDF	2.4, 2.6, 2.14, 2.16, 2.22	Chapter 2
4	9.-10.1.	PS ja PDF	3.4, 3.7, 3.16, 3.24, 4.3	Chapter 3, Section 4.1
5	16.-17.1.	PS ja PDF	4.5, 4.8, 4.13, 5.2	Chapter 4, Section 5.1
6	23.-24.1.	PS ja PDF	5.5, 5.9, 5.12, 5.14(a), 5.21	Sections 5.2-5.4
7	6.-7.2.	PS ja PDF	5.16, 5.19, 5.22	Sections 5.5-5.6
8	13.-14.2.	PS ja PDF	6.1, 6.4, 6.8, 6.10	Sections 6.1-6.6
9	20.-21.2.	PS ja PDF	6.17, 7.2, 7.3, 7.6	Sections 6.7, 7.1
10	27.-28.2.	PS ja PDF	7.11, 7.13, 7.17(a), 7.19	Sections 7.2-7.4
11	6.-7.3.	PS ja PDF	9.5, 9.7, 9.15	Chapter 9
12	13.-14.3.	PS ja PDF	-	Chapter 10

Sisältö

Kurssin sisältösuunnitelma on (bold = jo toteutunut):

1. Tapahtumat ja todennäköisyys
2. Diskreetit satunnaismuuttujat ja odotusarvo
3. Momentit ja poikkeamat
4. Chernoffin rajat
5. Pallot, uurnat ja satunnaisverkot
6. Probabilistinen menetelmä
7. Markovin ketjut ja satunnaiskulut
8. Jatkuvat satunnaismuuttujat ja Poisson-prosessit
9. Entropia, satunnaisuus ja informaatio
10. Monte Carlo -menetelmä
11. Martingaalit

Kirjallisuutta

• Michael Mitzenmacher, Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
• Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
• Juraj Hromkovic: Algorithms for Hard Problems (Chapter 5: Randomized Algorithms), Springer 2001.
• 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ä

Mar. 23, 2006