| |
T-79.240 Laskennallisen vaativuuden erikoiskurssi (3 ov)
Syksy 2004
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:
Tiistaisin klo 12-15, sali TB353. (Ensimmäinen luento ti 14.9.2004)
- Laskuharjoitukset: Tiistaisin klo 16-18, sali TB353
- Vastaava opettaja:
Prof. Ilkka Niemelä
ilkka.niemela(at)hut.fi,
http://www.tcs.hut.fi/~ini/
- Assistentti:
Matti Järvisalo
mjj(at)tcs.hut.fi,
http://www.tcs.hut.fi/~mjj/
- Esitiedot: T-79.148 Tietojenkäsittelyteorian perusteet
- Kurssin kotisivu: http://www.tcs.hut.fi/Studies/T-79.240/
|
