Essee TIEA241 syksy 2019
Yleistä
Tentissä tulee olemaan kysymys, jossa sinua pyydetään kirjoittamaan ennalta
valmistelemasi essee.
Esseen tavoitteena on osoittaa, että olet ymmärtänyt kurssin
aihepiiriin kuuluvan tai aihepiiriä lähellä olevan jonkin asian hyvin, ja että
osaat ilmaista asioita täsmällisesti.
Essee kannattaa miettiä etukäteen, mutta se pitää tuoda tenttiin
päässä eikä paperilla.
Alinna on ehdotuksia esseen aiheeksi.
Niissä on helppoja ja vaikeita.
Siksi kannattaa ehkä tutustua muutamaan ennen oman aiheen valintaa.
Aihe saa olla myös itse keksimäsi, kunhan se täyttää
seuraavat ehdot:
- Sillä tulee olla jokin sisällöllinen yhtymäkohta kurssiin.
Esimerkiksi tietokonegrafiikka on liian kaukana kurssin teemasta.
- Demoissa perusteellisesti käsiteltyä aihetta ei saa valita, koska demojen
toistaminen ei tuo opiskelulle lisäarvoa.
Esimerkiksi pysähtymistesterin mahdottomuus on tullut demoissa useasti, joten
sitä ei saa valita.
Jos kuitenkin löydät aiheeseen uuden näkökulman, saat valita sen, vaikka aihe
itsessään olisi lähellä demoja.
Esimerkiksi osittaisia pysähtymistestereitä on muunkinlaisia kuin demoissa
käsitellyt.
Ne kelpaavat aiheeksi.
- Muilla kursseilla perusteellisesti opetettu asia ei kelpaa.
Älä tee esseetä esimerkiksi tietorakenteista, koska niitä opetetaan paljon
muilla kursseilla.
Muiden kurssien asian toistaminen ei tuo lisäarvoa.
(Tietorakenteita saa totta kai käyttää apuvälineenä jonkin
tietojenkäsittelyteoreettisen asian esittämisessä.)
Tällä kurssilla luennoidut asiat, joita ei ole käsitelty demoissa,
kelpaavat aiheiksi.
Yhteysriippumattomien kielten pumppauslemma ja Turingin koneet ovat tästä
esimerkkejä.
Kuitenkaan essee ei saa olla suora kopio kurssin aineistosta
eikä mistään muustakaan lähteestä.
Esseen sopiva pituus on puolesta sivusta yhteen sivuun.
Jos esseestä uhkaa tulla paljon pitempi, muuta otsikkoa niin että aihe muuttuu
kapeammaksi.
Jos esseestä uhkaa tulla lyhyempi, tarkista, oletko huomannut ja kertonut
kaiken olennaisen mikä aiheeseen liittyy.
Koska essee ei saa olla kovin pitkä, keskity pääasiaan.
Tarkoituksena ei siis ole kirjoittaa valitusta aiheesta mahdollisimman paljon,
vaan jokin yksittäinen asia mahdollisimman hyvin.
Voit olettaa, että lukija tietää kaiken tarvittavan taustatiedon, mutta voit
myös kirjoittaa taustatietoja, jos essee jäisi muutoin liian lyhyeksi.
Englanninkieliset Wikipedia-sivut ovat yleensä hyviä
tietolähteitä.
Usein ne riittävät lähteeksi eikä muita lähteitä tarvitse käyttää, paitsi jos
Wikipedia-sivu on selvästi poikkeuksellisen huono.
Tietysti myös kurssin luentoaineistoa ja siihen linkitettyjä ilmaiskirjoja saa
käyttää, ja muutakin jos haluaa.
Lähdeviitteitä ei tarvitse olla, koska niitä olisi liian
vaikea tuoda tenttiin omassa päässä.
Pisteitä antaessani kiinnitän huomiota ennen kaikkea
siihen, kuinka hyvin essee osoittaa asian ymmärtämistä, sekä ilmaisun
täsmällisyyteen.
Täydet pisteet vaativat edes hieman järkevästi käytettyä matematiikkaa, mutta
osan pisteistä voi saada ilmankin.
Asiavirheet alentavat pisteitä.
Valitse itsellesi sopiva strategia: jos yrität liian kunnianhimoista esseetä,
on vaarana, että yksityiskohdat menevät ratkaisevasti pieleen ja pisteet
jäävät vähäisiksi.
Voit pienentää tätä riskiä selostamalla vaikeiden kaavojen sisällöt myös
sanallisesti.
Esseen painoarvo tentissä on vain noin 13%, joten sen
valmistelusta ei kannata tehdä elämää suurempaa asiaa.
Aiheita
Säännöllisiin kieliin liittyviä
- tästä numero 21 (ε-kaarten
poistaminen NFA:sta hyväksytyn kielen muuttumatta)
- tästä numero 24 (DFA, joka
hyväksyy annetun DFA:n hyväksymät merkkijonot takaperin)
- tästä numero 25 (kielten unioni
tuloautomaatilla ja |:n NFA-konstruktiolla)
- kaksisuuntainen äärellinen automaatti (two-way finite automaton)
- unambiguous finite automaton (Tästä voi valita myös osa-aiheita, esim. sen
selvittäminen, onko annettu NFA unambiguous.)
- local language / local automaton
- Lex (eräs leksikaalianalysaattorin automaattinen muodostaja)
- Mooren ja Mealyn koneiden vertailu
- Linuxin grep (Huomaa, että se käyttää Boyer-Moore -algoritmia;
ja että siinä on piirteitä, jotka eivät selity säännöllisten kielten
teorialla.)
Yhteysriippumattomat kieliopit ja kielet
- Chomskyn normaalimuoto (Chomsky normal form)
- Greibachin normaalimuoto (Greibach normal form)
- Cocke–Younger–Kasami-algoritmi eli CYK-algoritmi
- yhteysriippumattomien kielten pumppauslemma
- Earleyn jäsennin (Earley parser)
- LR(1)-jäsentäminen
- atribuuttikielioppi (attribute grammar)
- yacc (eräs jäsentimien automaattinen muodostaja)
- bison (eräs jäsentimien automaattinen muodostaja)
NP-täydellisyys
- NP:n matemaattinen määritelmä
- NP-täydellisyyden matemaattinen määritelmä, olettaen NP:n
matemaattinen määritelmä tunnetuksi
- tehtävän todistaminen NP-täydelliseksi olettaen jokin näennäisesti
helpompi tehtävä NP-täydelliseksi (esimerkiksi 3-CNF:n
NP-täydellisyyden todistaminen olettaen kaavan tyydytettävyys
NP-täydelliseksi)
- jos P = NP, niin miksi kaikki P:n kielet kahta
lukuunottamatta ovat NP-täydellisiä, ja ne kaksi eivät ole
- jokin NP:hen kuuluva tehtävä, jonka uskotaan olevan P:n
ulkopuolella mutta ei NP-kova
- polynomial-time approximation scheme tai muu NP-täydellisiä
tehtäviä vastaavien optimointitehtävien likimääräisten ratkaisujen etsimiseen
liittyvä aihe
Muuta
- Nick's class
- Post correspondence problem
- Ackermannin funktio
- Turingin koneet
- ahkera majava (busy beaver)
- osittaisten pysähtymistesterien lajeja