Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

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:

Luennot

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

Korjauksia luentomateriaalin virheisiin:

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