Tik-79.240 Laskennallisen vaativuuden erikoiskurssi 3 ov
Syksy 1999
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ä esitelmiä ja
laskemalla kotilaskuja.
- Kirjallisuus:
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
- Tilaisuudet:
Luennot keskiviikkoisin klo 16-19, sali TB353
Laskuharjoitukset torstaisin klo 12-14, sali TB353
- Ensimmäinen luento ke 8.9.1999.
- Vastaava opettaja:
Dos. Ilkka Niemelä, puh. 451 3290, e-mail: Ilkka.Niemela@hut.fi,
URL: http://www.tcs.hut.fi/~ini
- Assistentti:
DI Tommi Junttila, puh. 451 2896, e-mail: Tommi.Junttila@hut.fi,
URL: http://www.tcs.hut.fi/~tjunttil
- Kurssin kotisivu: http://www.tcs.hut.fi/Teaching/Tik-79.240