T-79.5103 Laskennan vaativuusteoria (5 op) LSyksy 2007 (Opetusjaksot I ja II)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.
Kurssilla 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. Kurssi 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 ja laskuharjoituksista ja se suoritetaan kahdella välikokeella ja tekemällä kotitehtäviä.
|