Yliopiston etusivulle Suomeksi På svenska In English
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Koeluento: Johdatus algebrallisiin algoritmeihin ja algebralliseen vaativuusteoriaan

FT Mikko Koivisto antaa torstaina 4.12. kello 13.15 salissa DK118 opetusnäytteen dosentuuria varten. Tilaisuus on kaikille avoin. Tervetuloa!

Abstrakti:

Algebrallinen laskentaongelma on algebrallisessa rakenteessa, kuten ryhmässä, renkaassa tai kunnassa, esitettävä kuvaus joukolta syötemuuttujia joukolle tulosmuuttujia. Esimerkiksi kahden neliömatriisin kertominen on algebrallinen laskentaongelma, joka on luonnollista esittää renkaassa tai puolirenkaassa. Algebrallinen algoritmi ratkaisee tällaisen laskentaongelman sarjalla kyseisen rakenteen laskentaoperaatioita. Algebrallinen vaativuusteoria tutkii laajemmin myös eri algebrallisten laskentaongelmien ratkaisemiseen tarvittavien laskentaoperaatioiden vähimmäismäärää. Luento johdattelee aihepiirin peruskäsitteisiin.