8101100
JOHDATUS TIETOJENKÄSITTELYTEORIAAN,
INTRODUCTION TO THEORETICAL COMPUTER SCIENCE, 4 ov
Tietoa luennoitsijoista
Professori ANTTI VALMARI
Luentoja ja harjoituksia
Luentoja yhteensä 56. Harjoituksia yhteensä 26 h.
Luentoajat ja -paikat
Tiistai 12 - 14, K1703
Torstai 13 - 15, TB109
Viikottainen opetus/periodi |
|
|
|
|
|
Luennot (h): |
- |
- |
4+ |
4 |
- |
Harjoitukset (h): |
- |
- |
2+ |
2 |
- |
Tavoitteet
Tutustua ohjelmoinnissa keskeisiin tietojenkäsittelyteorian osiin. Painopiste on tuloksissa, jotka ovat joko käytännössä tärkeitä (esim. koneellisesti käsiteltävän kielen suunnittelussa) tai maailmankuvallisesti merkittäviä (kuten ratkeavuustulokset). Tavoitteena on myös oppia täsmällistä päättelyä ja tietojenkäsittelytieteen ajattelutapaa.
Sisältö
Automaattien ja kielten teoriaa ohjelmoinnin näkökulmasta, äärettömät joukot, laskettavuus- eli ratkeavuusteoriaa, epädeterminismi, Turingin koneet, laskennallisen vaativuuden teoriaa, NP-kovien tehtävien käsittely.
Tutkintovaatimukset
Pakolliset laskuharjoitukset ja tentti.
Kirjallisuus
Luentomonisteet. Tukena voi käyttää mm. kirjoja Moret: The Theory of Computation; Garey & Johnson: Computers and Intractability.
Esitiedot
Numero |
Nimi |
|
|
8100310 |
5 |
Pakollinen |
|
8100500 |
3 |
Pakollinen |
Huomautuksia
Pakollinen ohjelmistotieteen pitkässä ammattiaineessa sekä ohjelmistotekniikkaan keskittyvissä jatko-opinnoissa.