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

Opinto-opas 2006-2007

OHJ-2300 JOHDATUS TIETOJENKÄSITTELYTEORIAAN, 6 op
Introduction to Theoretical Computer Science

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

  • Tentti

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

  • 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

  • Opintojakson osasuoritusten pitää liittyä samaan toteutuskertaan.

  • Opintojakso soveltuu jatko-opinnoiksi.

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

  • Arvioitu opintojakson toteutustapa
  • - Lähiopetuksen osuus: 45 %
    - Etäopetuksen osuus: 0 %
    - Opiskelijan itseopiskelun osuus: 55 %

    Mitoitus
    OpetusmuodotTuntia
    Luennot 120
    Harjoitukset 44
    Kaikki yhteensä 164

    Opintojaksokorvaavuus
    8101100 Johdatus tietojenkäsittelyteoriaan

    Opintojakson kotisivu

    Viimeksi muokattu 27.01.2006
    MuokkaajaTapio Elomaa