Kurssin asema ja sisältö
Matematiikan valinnainen laudaturkurssi, 5 ov
- Tietojenkäsittelyteorian linjalla pakollinen
Esitiedot (kurssit tai vastaavat tiedot):
- Johdatus diskreettiin matematiikkaan
- Todennäköisyyslaskenta
- Algebra
- Automaatit ja kieliopit
- Matemaattinen logiikka (hyödyllinen)
Sisältö:
- Laskettavuusteoriaa
- ratkeavat ja ratkeamattomat ongelmat
- rekursioteorian alkeita
- Laskennan vaativuusteoriaa
- NP-täydellisyys
- vaativuusmittojen ja -luokkien ominaisuuksia
- kombinaatiopiirit
- Kolmogorov-kompleksisuus
- Satunnaisalgoritmeista
- NP-täydellisten ongelmien approksimointiteoriaa
- Kryptologiaa