Kurssin asema ja sisältö
Tietotekniikan laudaturkurssi, 3 ov
- Ohjelmistotekniikan linjalla pakollinen (1997 alkaen)
- Mahd. myös matematiikan l-erikoiskurssiksi?
Esitiedot:
- Tietorakenteet ja algoritmit 1, 2
- Automaatit ja kieliopit (loppupuolella)
Sisältö:
- Algoritmianalyysin menetelmiä
- Tietorakenteita
- Tasapainoiset puut
- Keot, binomimetsät
- Erilliset joukot
- Hyppylistat
- Algoritmitekniikoita
- Syvyyshaku
- Likimääräisalgoritmit
- Satunnaisalgoritmit
- Laskennan vaativuusteoriaa
- Laskennan mallit (Turingin kone, RAM), vaativuusmitat ja vaativuusluokat
- NP-täydellisyysteoriaa (SAT-ongelman NP-täydellisyys, NP-täydellisyystodistuksia)