Tik-79.240 Laskennallisen vaativuuden erikoiskurssi 3 ov

Syksy 1998


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.

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 seminaarimuotoinen ja suoritetaan pitämällä esitelmiä ja laskemalla kotilaskuja.