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)
   • tehtävät (also in English)
   • tulokset
   • malliratkaisut
2. ma 12.12. kello 9-12
   • tehtävät (also in English)
   • kurssin tulokset
   • malliratkaisut ovat vihdoin valmiina.

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