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:
- tee säännöllistä lauseketta R vastaava tilakone
- tee kielioppia G vastaava pinoautomaatti
- tee kielen L = { x | P(x) } generoiva yhteydetön kielioppi
- muuta tilakone A deterministiseksi
- todista, että kieli L ei ole yhteydetön
- jne.
Kurssissa on materiaalia aika paljon, joten tenttiin kannattaa lukea
seuraavassa järjestyksessä:
- lukujen alussa oleva yleensä 1-2 sivua pitkä selittävä osuus
- peruskäsitteiden määritelmät
- erilaiset todistukset ja konstruktiot (usein todistusten
yhteydessä), allaolevassa lukukohtaisessa listassa on mainittu
tärkeimmät
- 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]
- luvun alkuosan matematiikan peruskäsitteet (voinut tulla esiin
myös matematiikan kursseissa)
- merkkijonoihin liittyvät käsitteet ja operaatiot
- kielen määrittely (joukkona predikaatin avulla)
- kieliin liittyvät operaatiot (kielten katenaatio, Kleenen tähti,
joukko-opin operaatiot)
- säännöllinen lauseke ja sen esittämä kieli
Luku 2, kokonaan
- deterministisen tilakoneen (äärellinen automaatti) määritelmä ja
toiminta
- epädeterministisen tilakoneen määritelmä ja toiminta
- epädeterministisen tilakoneen muuttaminen deterministiseksi
- tilakoneiden tunnistaman kieliperheen sulkeumaominaisuudet,
todistuksessa esitetty tilakoneiden yhdistäminen
- tilakoneisiin liittyvät ratkeavat ongelmat, perustelut
ratkeavuudelle
- säännöllisten kielten pumppauslemma
- deterministisen tilakoneen muodostaminen säännöllisestä
lausekkeesta
Luku 3, ei kohtaa 3.7 [3.6, eikä sivuja 127-130]
- yhteydettömän kieliopin määritelmä ja käyttö, merkkijonojen
produsointi
- säännöllisen kieliopin määritelmä
- pinoautomaatin määritelmä ja toiminta
- yhteydetöntä kielioppia vastaavan pinoautomaatin muodostaminen
(lemma 3.4.1 [3.4.3])
- yhteydettömien kielten sulkeumaominaisuudet
- yhteydettömien kielten pumppauslemma
- yhteydettömiin kieliin liittyvät ratkeavat ongelmat
("algoritmiset ominaisuudet")
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.
- Turingin koneen määritelmä ja toiminta
- Turing-laskettava funktio, määritelmä (Turing-computable)
- Turing-ratkeava kieli, määritelmä (Turing-decidable)
- Turing-hyväksyttävä kieli, määritelmä (Turing-acceptable)
- Turingin koneen laajentaminen konekaavioiden avulla
- Turingin koneen laajennukset (tavallisella Turingin koneella
voidaan simuloida erilaisia laajennettuja, esim. useampinauhaisia,
koneita, todistusten ideat olisi osattava kuvata sanallisesti, ei
formaalisti)
- epädeterministinen Turingin kone, määritelmä ja toiminta
- epädet. ja det. Turingin koneen vastaavuus, todistuksen idea
olisi osattava selittää, ei formaalia esitystä.
- Churchin teesi, sisältö
- yleisen (rajoittamattoman, tyypin 0) kieliopin määritelmä
- kieliopillinen laskettavuus, määritelmä
- primitiivirekursiivinen funktio, määritelmä (perusfunktiot,
yhdistämissäännöt) ja muodostaminen
- rajoitettu ja rajoittamaton minimointi, määritelmät
- mu-rekursiivinen funktio, määritelmä
- Turingin koneiden, yleisten kielioppien ja rekursiivisten
funktioiden ilmaisuvoiman ekvivalenssi
- Turingin koneiden koodaaminen
- universaalin Turingin koneen määritelmä ja periaatteellinen
rakenne
- Turingin koneiden pysähtymisongelma, määritelmä
- Turingin koneisiin liittyvät ratkeamattomat ongelmat,
määritelmät, todistukset
Luvut 6 ja 7, ainoastaan kohdat 6.1, 6.4, 7.1-2 [7.1,
7.4, 7.5]
- Aikarajoitteinen laskenta, ongelmaluokat P ja
NP, NP-täydellisyys
Latest update: January 16, 2001
by Tommi.Syrjanen@hut.fi