Mat-1.190 Laskennan vaativuusanalyysi (2 ov)
Kurssi on luennoitu viimeisen kerran syksyllä 2004, ja poistuu
opetusohjelmasta
Kurssin sisältö
Kurssi on käsitellyt algoritmien ns. laskennallista kompleksisuutta.
Esimerkkien valossa on tarkasteltu eräiden algoritmien suorittamisen
vaatimaa työmäärää ja tutkittu mahdollisuuksia valita toiminnaltaan
nopeita algoritmeja ko. tehtävien suorittamiseen.
Kurssin sisältöä:
- Hitaat ja nopeat algoritmit, suuruusluokka-arvioita,
rekursiiviset algoritmit.
- Graafialgoritmeja, matriisituloista, nopea Fourier-muunnos.
- Virtausverkot: Ford-Fulkersonin algoritmi ja MPM-algoritmi.
- Lukuteoriaa, pseudoalkuluvut, kryptografiaa, tekijöihin jakamisesta,
alkuluvuksi todistamisesta.
- Ratkaisuprobleemoista, Turingin koneista, tyydytettävyysprobleema.
- NP-täydellisyys.
Kirjallisuus
Oppikirja, jonka voi korvata opetusmonisteella,
on Herbert S. Wilf: Algorithms and Complexity, Prentice-Hall 1986.
Esitiedot
Matematiikan perustiedot, esim. peruskurssien 1 - 2 laajuudessa.
Kurssin suorittaminen
Yhdellä tentillä sopimuksen mukaan.
Kurssin opettaja
Lehtori
Seppo Ilkka.
Seppo Ilkka
11.1.2006