Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

582421 Satunnaisalgoritmit (8 op, 4 ov)

Opetus syksyllä 2005

Kurssi on päättynyt ja tulokset valmiina.

Kiitos myös kurssikyselyyn vastanneille!

Luennot
Jyrki Kivinen 7.09.-14.10. ja 2.11.-09.12. ke 14-16, pe 12-14 salissa D122
Laskuharjoitukset
Kari Laasonen 14.9.-12.10. ja 2.11.-7.12. ke 12-14 salissa CK111
Kurssikokeet
  1. ma 17.10. kello 9-12 (koealue laskuharjoitusten 1-5 asiat)
  2. ma 12.12. kello 9-12

Asema opetuksessa

Laudaturkurssi, joka kelpaa valinnaiseksi ainakin algoritmien erikoistumislinjalla.

Esitietoina edellytetään Algoritmien suunnittelu ja analyysi ja Johdatus todennäköisyyslaskentaan tai vastaavat tiedot.

Yleistä

Kurssilla esitellään satunnaisalgoritmien analysoimisessa tarvittavia todennäkäisyyslaskennan menetelmiä ja niiden soveltamista.

Kurssikirja ja luennot

Kurssi noudattaa kirjaa

Michael Mitzenmacher and Eli Upfal: Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press 2005.
joka opiskelijoilla oletetaan olevan käytössään. Syksyn 2005 kurssilla käsiteltiin lukujen 1-8 ja 10-11 asiat sekä lyhyesti (koealueen ulkopuolelta) lukua 12.

Luentomuistiinpanot on tarkoitettu käytettäväksi kurssikirjan ja luentojen ohella, eivät itseopiskeluun.

Laskuharjoitukset

Harjoitustehtävien ratkaisut palautetaan kirjallisesti Kari Laasosella (huone A321).

Tehtävänumerot viittaavat kurssikirjaan. Malliratkaisut ovat toistaiseksi intranetissä.

  1. tehtävät 1.6, 1.13, 1.15, 1.18 ja 1.21; malliratkaisut
  2. tehtävät 2.6, 2.16, 2.26, 2.32, 3.16; malliratkaisut
  3. tehtävät 3.24, 4.3, 4.5, 4.8, 4.13; malliratkaisut
  4. tehtävät 4.11, 4.24, 5.2, 5.5, 5.12; malliratkaisut
  5. tehtävät 5.9, 5.14, 5.16, 5.21, 5.22 malliratkaisut
  6. tehtävät 6.1, 6.4, 6.8, 6.10, 6.13; malliratkaisut
  7. tehtävät 6.15(b-d), 6.17, 7.2, 7.3, 7.6; malliratkaisut
  8. tehtävät 7.11, 7.13, 7.17, 7.19, 7.24; malliratkaisut
  9. tehtävät 8.5, 8.9, 8.13, 8.16,8.19; malliratkaisut
  10. tehtävät 8.20, 8.22, 10.3, 10.5, 10.13; malliratkaisut
  11. tehtävät 10.6, 10.10, 10.12, 11.11, 11.14; malliratkaisut

Oheismateriaali

Kurssilla aiemmin käytetty oppikirja

Rajeew Motwani and Prabhakar Raghavan: Randomized algorithms. Cambridge University Press 1995.
sisältää paljon hyvää lisämateriaalia.


Jyrki Kivinen