Teknillinen korkeakoulu, 
     Tietojenkäsittelyteorian laboratorio

T-79.240 Laskennallisen vaativuuden erikoiskurssi (3 ov)

Syksy 2002

Laskennallinen vaativuus on tietojenkäsittelyn keskeisimpiä tutkimuskohteita, jossa kehitetään menetelmiä sekä algoritmien että ratkaistavien ongelmien laskennallisen vaativuuden (muisti, suoritusaika, kommunikaatio) järjestelmälliseen ja luotettavaan arviointiin. Tällaiset menetelmät ovat oleellisia tietojenkäsittelyn ammattilaiselle hänen joutuessaan arvioimaan esimerkiksi kehitetyn algoritmin/järjestelmän suorituskykyä ja vasteaikoja, ehdotetun algoritmin optimaalisuutta ratkaistavaan ongelmaan tai mahdollisuuksia löytää tehokas tietokoneratkaisu esitettyyn ongelmaan.

Kurssin tavoitteena on perehdyttää opiskelija menetelmiin ja niiden alla olevaan teoriaan, joiden avulla voidaan vastata esimerkiksi seuraavanlaisiin kysymyksiin.

  • Minkälaiset ongelmat ovat ratkaistavissa tehokkaasti tietokoneella?
  • Miten tilanne muuttuu, kun (i) käytettävissä olevan muistin määrää rajataan, (ii) otetaan käyttöön epädeterministinen tai satunnaistettu laskenta ja halutaan, että laskenta päättyy oikeaan tulokseen suurella todennäköisyydellä, (iii) laskenta on rinnakkaista tai (iv) halutaan likimääräisesti oikea vastaus?
  • Minkälaiset laskennalliseen vaativuuteen liittyvät tulokset ja oletukset ovat salausalgoritmien ja kryptografisten protokollien turvallisuuden taustalla?
Opintojaksolla käydään läpi keskeisimmät vaativuusluokat (P, NP, PSPACE, NC, polynominen hierarkia, ...) ja niihin liittyvät menetelmät, joilla ongelmien vaativuusanalyysia voidaan tehdä. Lisäksi tarkastellaan satunnaistetun sekä rinnakkaisen laskennan tarjoamia mahdollisuuksia ja tutustutaan kryptografiaan laskennallisen vaativuuden kannalta.

Opintojakso soveltuu kaikille, joita kiinnostaa syvällinen ymmärtämys algoritmien ja ongelmien laskennallisesta vaativuudesta sekä tietojenkäsittelyn mahdollisuuksista ja rajoista. Erityisen suositeltava kurssi on jatko-opiskelijoille ja jatko-opintoja suunnitteleville.

Kurssi on koostuu luennoista, seminaariesitelmistä ja laskuharjoituksista. Kurssi suoritetaan pitämällä esitelmä ja laskemalla kotilaskuja.

  • Kirjallisuus: C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  • Luennot: Keskiviikkoisin klo 14-17, sali TB353. (Ensimmäinen luento ke 11.9.2002)
  • Laskuharjoitukset: Torstaisin klo 16-18, sali T353
  • Vastaava opettaja: Prof. Ilkka Niemelä
    puh. 451 3290, e-mail: Ilkka.Niemela@hut.fi, URL: http://www.tcs.hut.fi/~ini/
  • Assistentti: TkL Tommi Junttila
    puh. 451 2896, e-mail: Tommi.Junttila@hut.fi, URL: http://www.tcs.hut.fi/~tjunttil/
  • Esitiedot: T-79.148 Tietojenkäsittelyteorian perusteet
  • Kurssin kotisivu: http://www.tcs.hut.fi/Studies/T-79.240/