Tietojenkäsittelytieteen teoreettiset perusteet (3 ov)

Luennot 24.1.- 14.4.

Laskuharjoitukset 31.1.-22.4.

Esitiedot

Kurssilla tarvitaan matematiikan ja ohjelmoinnin perustaitoja. Matematiikan taitojesi riittävyydestä saat hyvän käsityksen suorittamalla alkutestin. Mikäli et ole suorittanut matematiikan opintoja, on tänä keväänä hyvä tilaisuus osallistua laitoksen omalle Diskreetit rakenteet -kurssille! Voit myös itse opiskellen kerrata tarvittavaa matematiikkaa oheisesta materiaalista (sama ps:nä).

Ohjelmointia tarvitaan vähemmän. Harjoituksissa on pieniä ohjelmointitehtäviä ja tietysti sinun tulee ymmärtää materiaalin esimerkkitoteutukset.

Kuvaus

1. Laskettavuuden teoria (theory of computability), jossa tutkitaan ongelmien ratkeavuutta ja arvioidaan niiden vaikeutta ennen ratkaisualgoritmin laatimista.
2. Laskennan vaativuusteoria (Theory of computational complexity), jossa arvioidaan ongelman laskennallista tila- ja aikavaativuutta.

Tällä kurssilla käsittelemme vain laskettavuuden teoriaa, mutta kurssin päätteeksi voit tehdä vapaaehtoisen harjoitustyön laskennan vaativuusteoriasta.

Kurssilla saat hyvät eväät arvioida mitä tahansa ongelmia:

1. Onko ongelma luonteeltaan laskennallinen? Ts. voisiko sen edes periaatteessa ratkaista tietokoneella?
2. Jos ongelma on laskennallinen, niin onko se ratkeava? Ts. voiko sille laatia ratkaisuohjelman, joka pysähtyy aina kaikilla syötteillä?
3. Jos ongelma on ratkeava, niin kuinka vaikea se on? Ennen ratkaisualgoritmin laatimista voimme jo erottaa helpot ja nopeasti ratkaistavat ongelmat työläämmistä. Tällä kurssilla jaamme ongelmat Chomskyn hierakian mukaan kolmeen vaikeusluokkaan, joita vastaavat säännölliset kielet, kontekstittomat kielet ja rajoittamattomat kielet.
4. Jos ongelma on ratkeava ja sen vaikeus tunnetaan, niin miten se kannattaa ratkaista? Tämä kysymys menee osittain kurssin aihepiirin ulkopuolelle, mutta tulet oppimaan näppäriä ja tehokkaita menetelmiä tietyn tyyppisiin ongelmiin.

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.

Kurssin suoritus

• 25% harjoitukset + ohjelmointitehtävät
• 75% kokeet

Alustava ohjelma

1. Johdanto
   • Kurssin esittely
   • Ongelmien mallintaminen ja ratkeavuus, formaalit kielet ja niiden hierarkia
   • Äärelliset automaatit ja säännölliset kielet
     • Säännölliset lausekkeet ja kielet
     • Deterministiset äärelliset automaatit
     • Äärellisen automaatin minimointi
     • Epädeterministinen äärellinen automaatti, determinisointi
     • Automaatin muunnos säännölliseksi lausekkeeksi ja säännöllisen lausekkeen muunnos automaatiksi
     • Säännöllisten kielten rajoituksia (Pumppauslemma)
     • Säännöllisten kielten sovellukset?
   • Kieliopit ja jäsentäminen
     • Kontekstittomat kieliopit ja kielet: perusidea
     • kontekstittomat kielet <-> automaatit (lineaarisen kieliopin muunnos automaatiksi ja päinvastoin)
     • *Ekskursio: kasvikieliopit?
     • Pinoautomaatit
     • Rekursiivisesti etenevä jäsentäminen (LL(1)-kieliopit)
     • *Exkursio: Attribuuttikieliopit?
     • CYK-agoritmi
     • Chomskyn normaalimuoto
     • Kontekstittomien kielten sovellukset ja rajoitukset
   • Turingin koneet ja rajoittamattomat kielet
     • Turingin koneet: perusidea
     • Laajennoksia: moniuraiset ja moninauhaiset koneet
     • epädeterministiset <-> deterministiset koneet
     • Rajoittamattomat ja kontekstiset kieliopit
   • Ratkeavuus ja ratkeamattomuus
     • Rekursiiviset ja rekursiivisesti numeroituvat kielet sekä ratkeamattomat ongelmat
     • koneiden itsetutkiskelu, universaalikoneet ja -kielet
     • *Ekskursio: mekaanisen laskettavuuden <-> inhimillisen päättelyn rajat?
     • Ongelmien vertailu ja palautus
   • Laskennan vaativuusteoriaa Vapaaehtoinen projektityö 1 ov
     • Turingin koneiden aika- ja tilavaativuus
     • NP-täydellisyys

Kirjallisuus

Luentomoniste Hämäläinen, W.: Hauskaa ja havainnollista laskennanteoriaa. Rekursiosta. Tai Orponen, Pekka: Automaatit ja kieliopit. Tilauslista täytetään 1. luennolla!

Kurssilla ei ole yhtä virallista kurssikirjaa, mutta sen sijaan joukko suositeltavaa kirjallisuutta (ks. alla). Luentomoniste kattaa koko kurssin sisällön, mutta saattaa olla paikoin tiivis, joten kannattaa ehdottomasti käyttää tukena kirjoja. Luentomoniste sopii hyvin myös omien kattavien muistiinpanojesi rungoksi.

• Sipser, M. Introduction to the Theory of Computation. (Hauskalukuinen, mielenkiintoisia esimerkkejä ja tehtäviä, mutta paikoin liian suppea.)
• Hopcroft, J.E., Motwani, R., Ulman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001. (Varsin perusteellinen, mutta asioita selitetty turhankin pitkästi. Hopcroftin ja Ullmanin vanha painos on tiiviimpi, tosin hieman matemaattisempi.)
• Kinber, E. & Smith, C. Theory of Computing. A Gentle Introduction. Prentice Hall, 2001. (Hyvin havainnollinen, kiltti johdatus aiheeseen :)
• Lewis, H.R. & Papadimitriou, C.H. Elements of the Theory of Computation, Second Edition, Prentice-Hall, 1998. (Klassikko, pätevä ja perusteellinen, mutta ainakin 1. painos aika matemaattinen.)
• Wood, D. Theory of Computation, Harper & Row, 1987.
• Sudkamp, T.A. Languages and Machines. An Introduction to the Theory of Computer Science. (Hyvä käsikirja jos haluat tietää enemmän etkä pelkää matematiikkaa. Varsinkin rekursiiviset ja rekursiivisesti numeroituvat kielet selitetty hyvin, vaatimattomammat kielet löytyvät kauniimmin muista lähteistä.)

Muuta materiaalia

• Kreikkalaiset aakkoset - muistinvirkistykseksi
• Mathematical concepts
• Todella hyvä sanakirja aihepiiristä!
• Sarjakuva Hilbertin Hotellista
• Laulu Hilbertin hotellista Kerrothan, jos löydät melodian kanssa!
• JFLAP-Visualisointityökaluja