Kurssin asema ja sisältö
Tietotekniikan laudaturkurssi, 2 ov
- Mahd. myös matematiikan l-erikoiskurssiksi?
Esitiedot:
- Automaatit ja kieliopit
- Algoritmien teoria
Aihepiiri kl-99: laskennan vaativuusteoriaa
Sisältö (alustava):
- Peruskäsitteet: deterministiset ja epädet. Turingin koneet ja niiden vaativuusluokat; vaativuusluokkien perusominaisuudet; palautukset ja täydellisyys
- Laskentaongelmien tilavaativuudesta
- Polynominen aikavaativuushierarkia
- Oraakkelikoneet ja laskentaongelmien relativointi
- Alternoivat Turingin koneet
- NP-täydellisten kielten rakenteesta
- Luokan NP hienorakenne
- Epäuniformit vaativuusmitat: neuvofunktiot ja kombinaatiopiirit
- Probabilistiset Turingin koneet ja niiden vaativuus
- Merkkijonojen Kolmogorov-kompleksisuus
- Vuorovaikutteiset todistukset ja todistusten tarkastaminen