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.