TCS / Teaching / Tik-79.148 / Examination requirements

Tik-79.148 Tenttivaatimukset, kevät 2001

Tämä on alustava luettelo kurssilla Tik-79.148 Tietojenkäsittelyteorian perusteet käsiteltävistä asioista. Suuria muutoksia ei siihen tule, mutta jotain pieniä viilailuja saattaa tapahtua suuntaan jos toiseenkin.

Yleistä

Kurssin tavoitteena on opettaa tietojenkäsittelyteorian peruskäsitteet ja -ominaisuudet. Peruskäsitteet olisi siis osattava määritellä (mitä tarkoittaa esim. Turing-ratkeavuus, kieliopillinen laskettavuus, primitiivirekursiivinen funktio, säännöllinen kieli, minkä operaatioiden suhteen kieliperheet ovat suljettuja jne.). Liitteenä on kaksi kuvaa, joiden pohjalta kurssilla käsiteltävä aineisto jäsentyy.

Lisäksi käsitteitä olisi osattava käyttää. Käyttäminen tulee esiin erilaisissa konstruktioissa ja todistuksissa. Tällaisia ovat esimerkiksi:

Kurssissa on materiaalia aika paljon, joten tenttiin kannattaa lukea seuraavassa järjestyksessä:
  1. lukujen alussa oleva yleensä 1-2 sivua pitkä selittävä osuus
  2. peruskäsitteiden määritelmät
  3. erilaiset todistukset ja konstruktiot (usein todistusten yhteydessä), allaolevassa lukukohtaisessa listassa on mainittu tärkeimmät
  4. muut todistukset
Kurssissa käsiteltävä aineisto on sijoitettavissa (Chomskyn) kielihierarkiaan (liitteenä), mikä voi helpottaa asioiden muistamista (kieliperhe, kieliperheen kielten keskinäinen määrittely ja kielten tunnistaminen, kieliperheiden keskinäiset suhteet, eri esitystapojen riippuvuude: automaatista kielioppi ja päinvastoin, jne.).

Oppikirjasta tulevat kohdat

Oppikirjasta ''Lewis-Papadimitriou: Elements of the theory of computation 2nd ed'' tulevat seuraavat kohdat (lukujen kohdalla on lueteltu luvun keskeisimmät asiat kurssin kannalta, [suluissa olevat lukunumerot ovat kirjan ensimmäisestä painoksesta]):

Luku 1, erityisesti kohdat 1.7-1.8 [1.8-1.9]

Luku 2, kokonaan

Luku 3, ei kohtaa 3.7 [3.6, eikä sivuja 127-130]

Luvut 4 ja 5, ei kohtia 4.4, 5.5-5.6 [6.4.2-3, 6.5]

Lukujen 4 ja 5 kohdalla oppikirjan eri painokset käsittelevät asioita eri järjestyksessä. Vanhemmassa painoksessa käsitellään yleiset kieliopit ja rekursiiviset funktiot vasta luvussa 5, mutta uudessa painoksessa molemmat ovat luvussa 4. Gödel-numerointi on poistettu kokonaan oppikirjan uudesta painoksesta. Gödel-numerointi käydään kuitenkin läpi luennolla ja laskuharjoituksissa. Asia esitellään myös opetusmonisteissa tarvittavassa laajuudessa. Myös rekursiiviset funktiot käsitellään luennoilla hieman laajemmin kuin mitä oppikirjan uudessa painoksessa esitetään.

Luvut 6 ja 7, ainoastaan kohdat 6.1, 6.4, 7.1-2 [7.1, 7.4, 7.5]

Kaavio Chomskyn kielihierarkiasta

Kielioppien ja automaattiluokkien vastaavuudet


Latest update: January 16, 2001 by Tommi.Syrjanen@hut.fi