582421 Satunnaisalgoritmit, 8 op (kevät 2009)

Ajankohtaista

Kurssi on päättynyt ja tulokset saatavilla.

Muista antaa kurssista palautetta! (Vastauksia 4.5. mennessä kolme kappaletta.)

Annettava opetus

Luento- ja laskuharjoitusajat olivat toiset kuin alun perin ilmoitettiin.

Luennot Jyrki Kivinen 13.1.–19.2. ja 10.3.–23.4. ti 8–10, to 10–12 C222

Laskuharjoitukset Pauli Miettinen 22.1.–19.2. ja 12.3.–23.4. to 12–14 C221

Kurssikokeet

1. ma 23.2. klo 16–19 salissa A111.
   • koealue
     • kurssikirjan sivut 1–136 (mukaanlukien lauseiden todistukset yms.)
     • luentokalvot 1–205
     • laskuharjoitukset 1–5.
   • tehtävät PS / PDF
   • ratkaisuja PS / PDF
2. ke 29.4. klo 16–19 salissa B123
   • koealue
     • kurssikirjan sivut 136–224 ja 252–284
     • luentokalvot 206–421
     • laskuharjoitukset 6–11.
   • tehtävät PS / PDF
   • varsinaisia malliratkaisuja ei ole, mutta muutama kommentti koetehtävistä.

Kurssin sisältö ja opetusmuodot olivat oleellisesti samat kuin syksyllä 2005.

Oppikirja

Kurssi perustui kirjaan

Michael Mitzenmacher and Eli Upfal: Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press 2005.

joka opiskelijoilla oletettiin olevan käytössään. Kurssilla käsiteltiin suunnilleen lukujen 1–8 ja 10–11 asiat sekä lyhyesti (koealueen ulkopuolelta) lukua 12.

Korjauksia kurssikirjan paino- ym. virheisiin:

• ensimmäinen painos
• toinen painos

Luennot

Luentomateriaali (sivut 1–436): PDF / PS (4 sivua/arkki).

Korjauksia luentomateriaalin virheisiin:

• sivulla 304 lemman 8.2 kaava oli väärin (korjattu 24.3.)
• sivulla 303 E[X] oli väärin (korjattu 24.3.)
• sivun 268 ensimmäisessä kaavassa oli P_i,j, kun piti olla P_j,i (korjattu 16.3.)
• sivulla 164 oli käytetty samasta luvusta sekaisin merkintöjä m ja n (korjattu 10.2.)
• sivulla 161 derivaatan g'(k) ensimmäisen termin pitää olla ln(1-exp(...)) (korjattu 10.2.)
• sivulla 41 keskimmäisellä kaavarivillä oli virheellisesti (1-p)ⁿ, pitää olla (1-p)^n-1 (korjattu 28.1.)

Luentojen eteneminen:

pvm	aihe	luentokalvot	kirjan sivut (suunnilleen)
13.1.	johdanto; todennäköisyyslaskennan kertaus	1–25	xiii–11
15.1.	satunnaismuuttujat; ehdollinen odotusarvo	26–39	12–30
20.1.	geometrinen jakauma; Markovin ja Tšebyševin epäyhtälö	40–55	30–50
22.1.	Markovin ja Tšebyševin epäyhtälö (sovelluksia); momenttigeneroiva funktio	56–70	50–62
27.1.	Chernoffin rajat	71–93	63–74
29.1.	satunnaiset reititysalgoritmit	94–118	74–83
3.2.	pallot ja lokerot -malli	119–138	90–99
5.2.	Poisson-approksimaatio	139–158	100–108
10.2.	sovelluksia: hajautus, satunnaisverkot	159–179	109–119
12.2.	probabilistinen menetelmä: odotusarvomenetelmä, derandomisointi, toisen momentin menetelmä	180–205	126–136
17.2.	ehdollisen odotusarvon epäyhtälö, Lovászin paikallislemma	206–222	136–143
19.2.	Lovászin paikallislemma (jatkoa)	223–239	143–148
10.3.	Markovin ketjut: johdanto	240–257	153–163
12.3.	Markovin ketjut: tilojen luokittelu, tasapainojakauma	258–276	163–173
17.3.	Markovin ketjut: tasapainojakauman sovelluksia	277–293	173–181
19.3.	luento peruutettu	—	—
24.3.	tasainen jakauma, eksponenttijakauma	294–311	188–198
26.3.	eksponenttijakaumien minimi; Poisson-prosessi	311–328	198–205
31.3.	Poisson-prosessien yhdistäminen; Markov-prosessi	329–347	205–214
2.4.	Markov-jonomalli; Monte Carlo -menetelmän perusteet	348–363	214–218; 252–254
7.4.	lukumäärän arvioiminen otannalla	364–381	255–262
16.4.	Metropolis-algoritmi; Markovin ketjujen sekoittuminen (johdanto)	382–393	263–266; 271–274
21.4.	Markovin ketjujen sekoittuminen (jatkoa)	394–409	274–280
23.4.	Markovin ketjujen sekoittuminen (lisää jatkoa); lyhyt yhteenveto	410–421; 435–436	280–284

Laskuharjoitukset

Jos ei muuta mainita, niin tehtävät ovat suoraan kurssikirjasta. Ratkaisut palautetaan etukäteen kirjallisesti (paperilla tai PDF-tiedostona) Pauli Miettiselle.

Laskuharjoitustilaisuuksiin osallistuminen on vapaaehtoista. Jos et osallistu, voit hakea arvostellut ratkaisusi Pauli Miettiseltä laskuharjoitusten jälkeen.

1. laskuharjoitus to 22.1., ratkaisujen palautus viimeistään ti 20.1. klo 18.00
   tehtävät 1.6, 1.15, 2.6, 2.16 ja 2.26; ratkaisuja
2. laskuharjoitus to 29.1., ratkaisujen palautus viimeistään ti 27.1. klo 18.00
   tehtävät 2.15, 2.32, 3.10, 3.21, 3.24; ratkaisuja
3. laskuharjoitus to 5.2., ratkaisujen palautus viimeistään ti 3.2. klo 18.00
   tehtävät 4.3, 4.4, 4.8, 4.21, 4.24; ratkaisuja
4. laskuharjoitus to 12.2., ratkaisujen palautus viimeistään ti 10.2. klo 18.00
   tehtävät 5.5, 5.9, 5.12, 5.14, 5.21; tehtävän 5.14 osalta ks. errata; ratkaisuja
5. laskuharjoitus to 19.2., ratkaisujen palautus viimeistään ti 17.2. klo 18.00
   tehtävät 5.22, 5.26, 6.1, 6.4, 6.10; ratkaisuja
6. laskuharjoitus to 12.3., ratkaisujen palautus viimeistään ti 10.3. klo 18.00
   tehtävät 6.8, 6.9, 6.13, 6.15 (vain (b) ja (c)), 6.17; ratkaisuja
7. laskuharjoitus to 19.3., ratkaisujen palautus viimeistään ti 17.3. klo 18.00
   tehtävät 7.2, 7.5, 7.12, 7.13, 7.19; ratkaisuja
8. laskuharjoitus to 26.3., ratkaisujen palautus viimeistään to 26.3. klo 18.00
   tehtävät 7.22, 7.26 (vain kaksi tehtävää, kummastakin maksimi 6 pistettä); ratkaisuja
9. laskuharjoitus to 2.4., ratkaisujen palautus viimeistään ti 31.3. klo 18.00
   tehtävät 8.2, 8.6, 8.9, 8.13, 8.19; ratkaisuja
10. laskuharjoitus to 16.4., ratkaisujen palautus viimeistään ti 7.4. klo 18.00
    tehtävät 8.16, 8.20, 8.22, 10.1, 10.3; ratkaisuja
11. laskuharjoitus to 23.4., ratkaisujen palautus viimeistään ti 21.4. klo 18.00
    tehtävät 10.5, 10.6, 10.10, 10.12, 10.13; ratkaisuja

Lisämateriaali

Vanhempi oppikirja

Rajeew Motwani and Prabhakar Raghavan: Randomized algorithms. Cambridge University Press 1995.

on hyvä oheislukemisto.

---

4. toukokuuta 2009 Jyrki Kivinen