Tik-79.148 TIETOJENKÄSITTELYTEORIA
Tenttivaatimukset, kevät 1998
Kurssin tavoitteena on ollut 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.).
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
- osoita että funktio f(x,y) on Turing-laskettava
- jne.
Kurssissa on materiaalia aika paljon, joten tenttiin kannattaa lukea seuraavassa järjestyksessä:
1. lukujen alussa oleva yleensä 1-2 s. pitkä selittävä osuus
2. peruskäsitteiden määritelmät
3. erilaiset todistukset ja konstruktiot (usein todistusten yhteydessä), alla olevassa lukukohtaisessa listassa on mainittu tärkeimmät
4. muut todistukset
Kurssissa käsitelty aineisto on sijoitettavissa (Chomskyn) kielihierarkiaan (liitteenä), mikä voi helpottaa asioiden muistamista (kieliperhe, kieliperheen kielten määrittely ja kielten tunnistaminen, kieliperheiden keskinäiset suhteet, eri esitystapojen riippuvuudet: automaatista kielioppi ja päinvastoin jne.).
Oppikirjasta tulevat kohdat
Oppikirjasta "Lewis-Papadimitriou: Elements of the theory of computation" tulevat seuraavat kohdat (lukujen kohdalla on lueteltu luvun keskeisimmät asiat kurssin kannalta):
Luku 1, erityisesti kohdat 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 (proseduurin runko liitteenä)
Luku 3, ei sivuja 127 - 130, ei kohtaa 3.6
- 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.3)
- yhteydettömien kielten perheen sulkeumaominaisuudet
- yhteydettömien kielten pumppauslemma
- yhteydettömiin kieliin liittyvät ratkeavat ongelmat ("algoritmiset ominaisuudet")
Luku 4, kokonaan
- Turingin koneen määritelmä ja toiminta
- Turnig-laskettava funktio, määritelmä (Turing-computable)
- Turing-ratkeava kieli, määritelmä (Turing-decidable)
- Turing-hyväksyttävä kieli, määritelmä (Turing-acceptable)
- Turingin koneen rakentaminen 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ä
Luku 5, kokonaan
- Churchin teesi (sivulla 223), sisältö
- yleisen (rajoittamattoman, tyypin 0) kieliopin määritelmä
- kieliopillinen laskettavuus (grammatically computable), määritelmä
- todistus (teoreema 5.2.1), että jokainen Turing-laskettava funktio on kieliopillisesti laskettava
- primitiivirekursiivinen funktio, määritelmä (perusfunktiot, yhdistämissäännöt) ja muodostaminen
- kappaleessa 5.3 on esimerkkejä prim.rek. funktioiden määrittelystä sekä joitakin termejä (rajoitetut kvanttorit, rajoitettu minimointi, predikaatit ym.), jotka tulisi osata
- Gödel-numerointi, periaate. Kappaleessa 5.4 määritellään joukko predikaatteja, joita käytetään teoreeman 5.5.1 todistuksessa, sitä varten ne kannattaa lukea läpi
- rajoittamaton minimointi, määritelmä
- -rekursiivinen funktio, määritelmä
- todistus (teoreema 5.5.1), että kieliopillisesti laskettava funktio on -rekursiivinen
- todistus (teoreema 5.6.1), että -rekursiiviset funktiot ovat Turing-laskettavia
Nämä kaksi teoreemaa yhdessä teoreema 5.2.1:n kanssa luovat yhteyden Turing-laskettavien funktioiden ja -rekursiivisten funktioiden välillä (kaksi eri lähtökohdista lähtenyttä laskettavuuden määrittelyä johtaa ekvivalentteihin laskennan malleihin, mikä osaltaan lisää uskoa Churchin teesiin)
- Turingin koneiden koodaaminen
- universaalin Turingin koneen määritelmä ja periaatteellinen rakenne
Luku 6, erityisesti kohta 6.1, ei kohtia 6.4.2 - 6.4.3, ei kohtaa 6.5
- Turingin koneiden pysähtymisprobleema, määritelmä (sivulla 227)
- Turingin koneisiin liittyvät ratkeamattomat ongelmat (teoreema 6.3.1), määritelmät, todistukset
Luku 7, kohdat 7.1, 7.4 ja 7.5. Tästä luvusta erityisesti termien määritelmät ja teoreemojen sisällöt. Kaikkia todistuksia tai esimerkkejä ei tarvitse käydä läpi.
Kaikki lihavoiduilla kirjasimilla painettu terminologia on osattava määritellä tai selittää. Liitteenä on kopiot muutamista luentokalvoista, jotka toivottavasti selventävät joitakin kirjassa esitettyjä asioita.
Tärkeimmät teoreemat ja lemmat:
T2.3.1 Deterministisen ja epädeterministisen äärellisen automaatin vastaavuus
T2.4.1 Säännöllisten kielten sulkeumaominaisuudet
T2.4.2 Äärellisten automaattien ominaisuuksia
T2.5.1 Äärellisten automaattien ja säännöllisten kielten vastaavuus
T2.6.1 Pumppauslemma säännöllisille kielille
T3.4.1, L3.4.3, T3.4.4
Pinoautomaattien ja yhteydettömien kielten vastaavuus
T3.5.1 Yhteydettömien kielten sulkeumaominaisuudet
T3.5.3 Pumppauslemma yhteydettömille kielille
L4.6.1, T4.6.1 Deterministisen ja epädeterministisen Turingin koneen vastaavuus
L5.2.1, T5.2.1 Kieliopillinen laskettavuus ja Turing-laskettavuus
T5.5.1 Kieliopillisesti laskettavien funktioiden ja - rekursiivisten funktioiden
vastaavuus
T5.6.1 - rekursiivisten funktioiden ja Turing-laskettavien funktioiden vastaavuus
T6.1.5 Turingin koneiden pysähtymisprobleema
T6.2.1 - T6.2.4'
Turingin koneiden hyväksymät kielet
T6.3.1 - T6.3.2
Ratkeamattomia ongelmia
T6.4.1 Kielioppeihin liittyviä ratkeamattomia ongelmia
D7.1.1 TIME(T):n määritelmä
T7.1.1 Vakiokertoimien merkitys aikarajoissa
D7.4.1 Kieliluokan P määritelmä
D7.4.2 Kieliluokan NP määritelmä
T7.4.1 NDTM ja DTM:n laskentojen välinen yhteys
D7.5.1 "polynomial time computable"
D7.5.2 "polynomial-time transformations
D7.5.3 NP-täydelliset kielet
T7.5.1 P=NP? teoreema
T7.5.2 N0 on NP-täydellinen