TTKK Opinto-opas
81260 Johdatus tietojenkäsittelyteoriaan, 4,0 ov
Introduction to Theoretical Computer Science, 4,0 cu
Professori ANTTI VALMARI
Luentoja 56 h. Harjoituksia 28 h.
| Viikottainen Opetus / Periodi |
S1 | S2 | K1 | K2 | Kesä |
|---|
| Luennot (h) | 4+ | 4 |
- | - | - |
|---|
| Harjoitukset (h) | 2+ | 2 |
- | - | - |
|---|
Luentoaika ja -paikka
Tiistai 12-14 TB109, torstai 14-16 TB109.
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.
Vaadittavat esitiedot
73116 Algoritmimatematiikka sekä 81125 Tietorakenteet ja
algoritmit tai 81370 Tietorakenteiden käyttö.
Huomautuksia
Pakollinen ohjelmistotieteen pitkässä ammattiaineessa sekä
ohjelmistotekniikkaan keskittyvissä jatko-opinnoissa.
Linkkejä
Kurssin kotisivu.