Opintojaksot   |Tutkinnot| |Opintokokonaisuudet| |Kaikki| |Jatko| |KV|  |Haku|

Opintojakson vastuuhenkilö
Tapio Elomaa

Luentoajat ja -paikat
Per I,II: Maanantai 12 - 14, TB222
Per I,II: Torstai 14 - 16, TB222

Toteutuskerrat

	Periodi 1	Periodi 2	Periodi 3	Periodi 4	Periodi 5	Kesä
Luento	4 h/vko	4 h/vko	-	-	-	-
Harjoitus	2 h/vko	2 h/vko	-	-	-	-
Tentti

(Lukuvuoden 2006-2007 aikataulu)

Tavoitteet
Tutustuminen ohjelmoinnin ja laskennan pohjimmaisiin mahdollisuuksiin - mitä ongelmia periaatteessa voidaan ohjelmallisesti ratkaista ja mitkä ongelmat voidaan lisäksi ratkoa tehokkaasti.

Sisältö

Sisältöalue	Ydinaines	Täydentävä tietämys	Erityistietämys
1.	Laskennan mallit, Turingin kone	Muita laskennan universaaleja malleja: rajoittamattomat kieliopit ja RAM-kone	Laskennan universaalien mallien suhteellinen tehokkuus
2.	Laskettavuusteoria, laskennallisten ongelmien ratkeavuus
3.	Laskennan vaativuusteoria, aika- ja tilavaativuushierarkian perusteet	Aika- ja tilavaativuusluokkien yksityiskohtaiset suhteet

Suoritusvaatimukset
Laskuharjoitukset, tentti.

Opintojakson arviointikriteerit

Oppimateriaali

Tyyppi	Nimi	Tekijä	ISBN	URL	Painos,saatavuus...	Tenttimateriaali	Kieli
Kirja	Introduction to the Theory of Computation	Michael Sipser			Second Edition	Ei ole	Englanti

Esitiedot

Tunnus	Nimi	OP	P/S
MAT-20600	MAT-20600 Diskreetti matematiikka	3	Pakollinen
OHJ-2150	OHJ-2150 Algoritmien analyysi	4	Pakollinen

Esitietoketju (Vaatii kirjautumisen TTY Intranetiin)

Huomautuksia

Tieto- ja viestintätekniikan (TVT) käyttö opetuksessa

- Lähiopetuksen osuus: 45 %
- Etäopetuksen osuus: 0 %
- Opiskelijan itseopiskelun osuus: 55 %

Mitoitus

Opetusmuodot	Tuntia
Luennot	120
Harjoitukset	44
Kaikki yhteensä	164

Opintojaksokorvaavuus
8101100 Johdatus tietojenkäsittelyteoriaan

Opintojakson kotisivu

Viimeksi muokattu	27.01.2006
Muokkaaja	Tapio Elomaa