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

-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

ViikkoPäivätKalvotHarjoitukset 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

- Linkkejä


Mar. 23, 2006