Opinto-opas 2008-2009 Perus
Perus	Pori	KV	Jatko	Avoin
\|Tutkinnot\| \|Opintokokonaisuudet\| \|Opintojaksot\|

Opinto-opas 2008-2009

OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op
Introduction to Theoretical Computer Science

Opintojakson vastuuhenkilö

Tapio Elomaa

Toteutuskerrat

Luentoajat ja -paikat Kohderyhmä, jolle suositellaan

Toteutus 1

Per 1 :
Torstai 14 - 16, TC133
Tiistai 14 - 16, TC103
Per 2 :
Tiistai 14 - 16, TB219
Torstai 12 - 14, TB224
Maanantai 14 - 16, TC163
3.-n. vuosikurssi
Tieto- ja sähkötekniikan tiedekunta

Suoritusvaatimukset

Laskuharjoitukset, tentti.
Osasuoritusten pitää liittyä samaan toteutuskertaan

Opetukseen ja oppimiseen liittyvät periaatteet ja lähtökohdat

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

Opintojakson arvostelu

Tentti

Arvosteluasteikko:

Opintojaksolla käytetään numeerista arviointiasteikkoa (1-5)

Osasuoritukset:

Osasuoritusten pitää liittyä samaan toteutuskertaan

Oppimateriaali

Tyyppi Nimi Tekijä ISBN URL Painos,saatavuus... Tenttimateriaali Kieli

Kirja Introduction to the Theory of Computation Michael Sipser Second Edition Englanti

Esitietovaatimukset

Opintojakso	P/S
MAT-20600 Diskreetti matematiikka	Pakollinen
OHJ-2150 Algoritmien analyysi	Pakollinen

Esitietoketju (Vaatii kirjautumisen POPiin)

Vastaavuudet

Opintojakso	Vastaa opintojaksoa	Selite
OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op	8101100 Johdatus tietojenkäsittelyteoriaan, 4 ov
OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op	OHJ-2306 Introduction to Theoretical Computer Science, 0 op

Tarkempia tietoja toteutuskerroittain

Kuvaus Opetusmuodot Toteutustapa

Toteutus 1 Kurssin tavoitteena on tutustua ohjelmoinnin ja laskennan pohjimmaisiin mahdollisuuksiin - mitä ongelmia periaatteessa voidaan ohjelmallisesti ratkaista ja mitkä ongelmat voidaan lisäksi ratkoa tehokkaasti. Lisäksi pyritään vetämään näiden tulosten yhteyksiä käytännön ohjelmistotyöhön. Kurssi on 6 opintopisteen laajuinen, syksyllä 2008 kurssi luennoidaan periodeilla I ja II. Jatko-opintokelpoinen. Pakollinen ohjelmistotieteen syventävissä opinnoissa. Kurssi käsittää luennot, laskuharjoitukset joista voi ansaita porkkanapisteitä sekä tentin. Harjoitustöitä ei tällä kurssilla ole. Lähiopetus: 0 %
Etäopetus: 0 %
Itseopiskelu: 0 %

Viimeksi muokattu 27.08.2008

Muokkaaja Outi Soiniaho

	Luentoajat ja -paikat	Kohderyhmä, jolle suositellaan
Toteutus 1	Per 1 : Torstai 14 - 16, TC133 Tiistai 14 - 16, TC103 Per 2 : Tiistai 14 - 16, TB219 Torstai 12 - 14, TB224 Maanantai 14 - 16, TC163	3.-n. vuosikurssi Tieto- ja sähkötekniikan tiedekunta

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

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

	Kuvaus	Opetusmuodot	Toteutustapa
Toteutus 1	Kurssin tavoitteena on tutustua ohjelmoinnin ja laskennan pohjimmaisiin mahdollisuuksiin - mitä ongelmia periaatteessa voidaan ohjelmallisesti ratkaista ja mitkä ongelmat voidaan lisäksi ratkoa tehokkaasti. Lisäksi pyritään vetämään näiden tulosten yhteyksiä käytännön ohjelmistotyöhön. Kurssi on 6 opintopisteen laajuinen, syksyllä 2008 kurssi luennoidaan periodeilla I ja II. Jatko-opintokelpoinen. Pakollinen ohjelmistotieteen syventävissä opinnoissa. Kurssi käsittää luennot, laskuharjoitukset joista voi ansaita porkkanapisteitä sekä tentin. Harjoitustöitä ei tällä kurssilla ole.		Lähiopetus: 0 % Etäopetus: 0 % Itseopiskelu: 0 %

Opinto-opas 2008-2009 Perus

Opinto-opas 2008-2009

OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op Introduction to Theoretical Computer Science