University of Joensuu - Computer Science

Tietojenkäsittelytieteen teoreettiset perusteet (3 ov)

Theoretical Foundations of Computer Science
Luennot 26.1.- 5.4. ma 12-14 ja to 10-12 TD106 Wilhelmiina Hämäläinen (ilman skandeja etunimi.sukunimi@cs.joensuu.fi)

Laskuharjoitukset (2.2. - 21.4.)

 ma 14-16 B179 Wilhelmiina Hämäläinen
ke 16-18 B180 Yevgeny Yusha (englanninkielinen ryhmä)
ke 16-18 B179 Anssi Kautonen

Ajankohtaista

Kuvaus

Kurssin keskeisenä sisältönä on ongelmien formaali mallintaminen ja ratkaiseminen. Formaali mallintaminen voi kuulostaa tylsältä, mutta se kätkee taakseen hyvin tärkeitä ja kiinnostavia löytöjä. Ennen kuin ongelmaan voi alkaa suunnitella parasta mahdollista ratkaisualgoritmia, täytyy tietää, kuinka vaikeasta ongelmasta on kyse tai onko ongelma ylipäätänsä ratkaistavissa. Toisaalta itse ratkaisu - sen olemassaolo tai tehokkuus - on riippumaton käytettävästä ohjelmointikielestä tai muusta laskennallisesta välineestä ja siksi puhtaan abstrakti ratkaisu on useimmiten helpommin analysoitavissa. Ekskursioina kurssi esittelee myös joukon kiinnostavia käytännön sovelluksia formaaleille työkaluille, joihin tutustutaan (mm. hahmontunnistus, kääntäjät, kasvikieliopit). Tietojenkäsittelytieteen teoria antaa myös hyvät eväät filosofisille pohdinnoille tietokoneiden luomasta maailmasta sekä ihmisen ja koneen kilpajuoksusta.

Esitiedot

Esitietoina edellytetään Johdatus tietojenkäsittelytieteeseen ja matematiikan perusopintojakso tai vastaavat valmiudet. Kurssin alussa kerrataan tarvittavat matemaattiset peruskäsitteet.

Kurssin suoritus

Kurssin voi periaatteessa suorittaa kolmella vaihtoehtoisella tavalla:
  1. Ongelmalähtöisesti (4 ov), jolloin suoritus koostuu ongelmaraporteista, opimispäiväkirjasta sekä laskuharjoituksista. Välikokeet ovat pakolliset, mutta voivat vain korottaa arvosanaa! Ongelmalähtöisestä menetelmästä tarkemmin alla.
  2. Itseopiskellen, jolloin suoritus koostuu kahdesta välikokeesta ja laskuharjoituksista. Luentoja pidetään n. puolet normaalista. Välikokeet to 18.3. ja to 22.4.
  3. Loppukokeella.
Ongelmalähtöinen vaihtoehto on suositeltavin ja tutkimusten mukaan myös oppimistulokset ovat sillä tavalla parhaimpia. Mikäli haluat valita tämän luovan syväoppimismenetelmän, ole valmis osallistumaan aktiivisesti "luentoihin" ja harjoituksiin sekä panostamaan opiskeluun myös kotona. Vastineeksi ongelmalähtöiseen oppimiseen osallistuvat saavat yhden ylimääräisen opintoviikon!

Ongelmalähtöinen oppiminen

Ongelmat

Ongelmalähtöinen oppiminen merkitsee sitä, että perinteisten luentojen sijasta asioita opitaan ongelmia ratkomalla. Aina välillä luennoija pitää pieniä opetustuokioita tarpeen mukaan. Kuten lienet huomannutkin, ei tietoa voi "kaataa päähän", vaan se on itse opittava. Ongelmalähtöisessä oppimisessa se kuitenkin tapahtuu melkeinpä varkain ongelmia ratkoessa. Ainoana ehtona on, että olet ennakkoluuloton ja valmis heittäytymään uusien ongelmien kimppuun sekä tarpeeksi sinnikäs selättämään ne. Sinun ei kuitenkaan tarvitse selviytyä yksin vaikeista asioista, vaan ongelmia pohjustetaan ryhmissä ja itseopiskelun jälkeen tulokset puretaan samassa ryhmässä. Tämän jälkeen luennoija voi vielä syventää opittua ja paneutua juuri niihin asioihin, jotka olivat vaikeimpia. Ongelmalähtöinen oppimisprosessi koostuu seuraavista vaiheista:

  1. Epäselvien käsitteiden selventäminen
  2. Ongelman määrittely
  3. Aivoriihi
  4. Ilmiötä kuvaavan selitysmallin rakentaminen
  5. Oppimistavoitteiden määrittely
  6. Itsenäinen opiskelu
  7. Opiskelutulosten purkusessio
Ongelmalähtöiseen metodiin tutustutaan ensimmäisellä luentokerralla. Siksi on tärkeää, että olet paikalla heti ensimmäisellä luennolla! Toimiva ongelmalähtöinen oppiminen edellyttää myös aktiivista osallistumista luentoihin (=ongelmien pohjustus- ja purkutilaisuuksiin). Jokainen ongelmanratkaisija palauttaa viikottain ongelmaraportin sekä palan luentopäiväkirjaa, joka sisältää ongelmaraportin sekä pohdintoja niin opitusta kuin oman oppimisen edistymisestä.

Alustava ohjelma

Yksityiskohtainen aikataulu
  1. Johdanto
  2. Äärelliset automaatit ja säännölliset kielet
  3. Kieliopit ja jäsentäminen
    Kaikki materiaali tähän saakka

    VIIKKO 8:
    TAIDENÄYTTELY luennolla 15.3.
    Välikoe luennolla 18.3.

  4. Turingin koneet ja rajoittamattomat kielet pdf
    • Turingin koneet: perusidea (viikko 9)
    • Laajennoksia: moniuraiset ja moninauhaiset koneet (viikko 9)
    • epädeterministiset <-> deterministiset koneet (viikko 9)
    • Rajoittamattomat ja kontekstiset kieliopit (viikko 10)
  5. Ratkeavuus ja ratkeamattomuus
  6. Laskennan vaativuusteoriaa Vapaaehtoinen projektityö 1 ov

Kirjallisuus

Kurssilla ei ole yhtä virallista kurssikirjaa, mutta sen sijaan joukko suositeltavaa kirjallisuutta (ks. alla). Kannattaa silti tutustua omatoimisesti muuhunkin kirjallisuuteen! Lisäksi pistän verkkoon luentomateriaalia, joka kattaa koko kurssin sisällön (ja joista luennoidaan tarpeen mukaan) pdf:nä - niitä voi käyttää runkona, joista itse täydentää mieleisensä muistiinpanot. Paras tapa oppia on laatia oma oppimateriaali!

Muuta materiaalia