TIEA241 Au­to­maa­tit ja kie­li­opit

ke­vät 2022

Si­vu pe­rus­tet­tu 31.1.2022

Mää­rä­päi­vät

	V1	V2	V3	V4	V5	V6	V7	V8
no­pea	27.1.	3.2.	10.2.	17.2.	24.2.	3.3.	10.3.	17.3.
hi­das	27.1.	10.2.	24.2.	10.3.	24.3.	7.4.	28.4.	12.5.

Teh­tä­viin pää­set klik­kaa­mal­la V1, V2 jne. Teh­tä­viä jul­kais­taan si­tä mu­kaa kuin ke­vät ete­nee.

Teh­tä­vien vas­tauk­sia pi­tää pa­laut­taa jo­ko ker­ran vii­kos­sa (jol­loin hom­ma tu­lee val­miik­si maa­lis­kuul­la) tai jo­ka toi­nen viik­ko (ve­nyy tou­ko­kuul­le). Jo­kai­nen saa it­se va­li­ta, kum­paa ai­ka­tau­lua nou­dat­taa. Pää­siäi­se­nä on yli­mää­räi­nen tau­ko­viik­ko. Saat­te vaih­taa ai­ka­tau­lua. Ai­noa, mi­kä on kiel­let­ty, on ai­ka­tau­lun tois­tu­va ve­ny­mi­nen.

Teh­tä­vät

Osa teh­tä­vis­tä on Math­Check-teh­tä­viä ja osa pe­rin­tei­siä. Pa­laut­ta­kaa pe­rin­teis­ten vas­tauk­set pdf-tie­dos­to­na ja ker­to­kaa jo­ko sii­nä tai mei­lis­sä Math­Check-teh­tä­vis­tä, mi­tä koh­tia et­te saa­neet teh­dyk­si esi­mer­kik­si tyy­liin ”T1 kaik­ki teh­ty, T2 puut­tuu K7, 11”. An­nan ko­ti­teh­tä­vien pa­lau­tuk­sis­ta pa­lau­tet­ta sen mu­kaan kuin ai­ka­tau­lu­ni sal­lii. Jos jo­kin Math­Check-teh­tä­vä­si­vuis­ta ei toi­mi, niin ot­ta­kaa pian yh­teyt­tä.

	lue	pa­kol­li­set	ai­na­kin yk­si
1	1‒16	1. Pro­po­si­tio­lo­gii­kan pe­rus­ope­raat­to­rit  2. Merk­ki­jo­not	3. Täs­tä nu­me­ro 1  4. sa­mas­ta nro 6 pait­si (j)  5. sa­mas­ta nro 20
2	17‒26	6. DFA-pe­rus­asioi­ta  7. Loo­gi­sia ta­so­ku­vioi­ta	8. Täs­tä nu­me­ro 4  9. sa­mas­ta nro 9 10. sa­mas­ta nro 8
3	27‒40 41‒47	11. Ma­te­maat­ti­ses­ta päät­te­le­mi­ses­tä 12. Täs­tä nu­me­ro 20 13. sa­mas­ta nro 13 14. sa­mas­ta nro 14	15. mi­kä ta­han­sa aiem­min tur­haan teh­ty teh­tä­vä 16. Täs­tä nu­me­ro 7 17. sa­mas­ta nro 12
4	48‒64	18. NFA:n muun­ta­mi­nen DFA:ksi 19. Täs­tä nu­me­ro 15 (b) 20. sa­mas­ta nro 16 (c) 21. sa­mas­ta nro 17	22. Täs­tä nu­me­ro 18 23. sa­mas­ta nro 21 24. sa­mas­ta nro 22
5	65‒86	25. Täs­tä nu­me­ro 23 26. sa­mas­ta nro 24 27. sa­mas­ta nro 26	28. Täs­tä nu­me­ro 25 29. sa­mas­ta nro 28
6	87‒95 106‒116	30. Py­säh­ty­mis­tes­te­rin mah­dot­to­muus 31. Täs­tä nu­me­ro 32	32. Bac­kus–Naur Form 33. Li­sää BNF-har­joi­tuk­sia
7	117, 123‒140	34. Li­sää py­säh­ty­mi­sen tes­taa­mi­ses­ta 35. Ra­tio­naa­li­lu­ku­jen jouk­ko on nol­la­mi­tal­li­nen	36. Täs­tä nu­me­ro 34
8	141‒144 Täs­tä 144‒156	37. Täs­tä nu­me­ro 36 38. Da­tan pak­kaa­mi­nen ja Kol­mo­go­rov-komp­lek­si­suus

Yleis­tä

Opet­ta­ja on Ant­ti Val­ma­ri.

Tä­tä kurs­sia vas­taa­va kurs­si on ol­lut maail­mal­la ylei­nen esi­mer­kik­si ni­mel­lä Int­ro­duc­tion to Theo­re­ti­cal Com­pu­ter Scien­ce tai Au­to­ma­ta, Com­pu­ta­bi­li­ty, and Comp­le­xi­ty. Tyy­pil­li­ses­ti sel­lai­sel­la käy­dään lä­pi kes­kei­sim­mät asiat ää­rel­li­sis­tä au­to­maa­teis­ta ja sään­nöl­li­sis­tä kie­lis­tä, yh­teys­riip­pu­mat­to­mis­ta kie­li­opeis­ta, las­ket­ta­vuu­den ra­jois­ta ja eh­kä las­ken­nal­li­ses­ta vaa­ti­vuu­des­ta (ai­na­kin NP-täy­del­li­syys).

Nä­mä asiat on pe­rin­tei­ses­ti ope­tet­tu si­ten kuin ma­te­maa­ti­kot asioi­ta opet­ta­vat, sil­lä seu­rauk­sel­la et­tä ne me­ne­vät ei-niin-ma­te­maat­ti­sil­ta oh­jel­moin­ti-ih­mi­sil­tä yli hil­seen (1980-lu­vul­la käy­tös­sä ol­lut il­maus, jo­ka tar­koit­taa, et­tä ei opit­tu). Olen omil­la kurs­seil­la­ni koet­ta­nut löy­tää oh­jel­moi­ja­lä­hei­sem­pää ta­paa se­lit­tää asiat.

Esi­tie­dot

Kurs­sin vi­ral­li­si­na esi­tie­to­vaa­ti­muk­si­na on oh­jel­moin­tia ai­na­kin kah­den en­sim­mäi­sen kurs­sin ver­ran ja ma­te­ma­tiik­kaa ai­na­kin yh­den yli­opis­to­kurs­sin ver­ran. Va­li­tet­ta­vas­ti kurs­sin to­teu­tuk­set syk­syl­lä 2018 ja 2019 osoit­ti­vat, et­tä se ei rii­tä.

Teh­kääm­me niin, et­tä jo­kai­nen saa aloit­taa ja kat­som­me pa­ri en­sim­mäis­tä pa­lau­tus­ker­taa, mi­ten su­juu, riit­tää­kö taus­ta ja se oh­jaus jo­ta pys­tyn an­ta­maan.

Työ­mää­rä

Va­rat­kaa kurs­sin suo­rit­ta­mi­seen riit­tä­väs­ti ai­kaa. No­peam­mal­la tah­dil­la va­rat­kaa 13 opis­ke­lu­tun­tia / viik­ko ja hi­taam­mal­la tah­dil­la 6,5. Opis­ke­lu­tun­ti koos­tuu 45 mi­nuu­tis­ta opis­ke­lua ja 15 mi­nuu­tis­ta tau­koa. To­ki saat­te ryt­mit­tää tauot opis­ke­lun lo­maan ku­ten it­se ha­luat­te, mut­ta kaik­kiaan va­rat­kaa opis­ke­lu­ai­kaa ym. mu­kai­ses­ti.

Es­see

Es­see on vä­hin­tään yh­den ja enin­tään kol­men A4-si­vun pi­tui­nen kir­joi­tus opet­ta­jan kans­sa so­vit­ta­vas­ta ai­hees­ta (esim. gra­du­poh­jan si­vu­ja, noin 90 merk­kiä / ri­vi ja 30 ri­viä / si­vu). Sen ta­voit­tee­na on osoit­taa, et­tä olet ym­mär­tä­nyt kurs­sin ai­he­pii­riin kuu­lu­van tai ai­he­pii­riä lä­hel­lä ole­van jon­kin asian hy­vin, ja et­tä osaat il­mais­ta asioi­ta täs­mäl­li­ses­ti.

Jos es­sees­tä uh­kaa tul­la liian pit­kä, muu­ta ot­sik­koa niin et­tä ai­he muut­tuu ka­peam­mak­si. Jos es­sees­tä uh­kaa tul­la liian ly­hyt, tar­kis­ta, olet­ko huo­man­nut ja ker­to­nut kai­ken olen­nai­sen mi­kä ai­hee­seen liit­tyy. Kos­ka es­see ei saa ol­la ko­vin pit­kä, kes­ki­ty pää­asiaan. Tar­koi­tuk­se­na ei siis ole kir­joit­taa va­li­tus­ta ai­hees­ta mah­dol­li­sim­man pal­jon, vaan jo­kin yk­sit­täi­nen asia mah­dol­li­sim­man hy­vin. Voit olet­taa, et­tä lu­ki­ja tie­tää kai­ken tar­vit­ta­van taus­ta­tie­don, mut­ta voit myös kir­joit­taa taus­ta­tie­to­ja, jos es­see jäi­si muu­toin liian ly­hyek­si.

Eng­lan­nin­kie­li­set Wi­ki­pe­dia-si­vut ovat yleen­sä hy­viä tie­to­läh­tei­tä. Usein ne riit­tä­vät läh­teek­si ei­kä mui­ta läh­tei­tä tar­vit­se käyt­tää, pait­si jos Wi­ki­pe­dia-si­vu on sel­väs­ti poik­keuk­sel­li­sen huo­no. Tie­tys­ti myös kurs­sin luen­to­ai­neis­toa ja sii­hen lin­ki­tet­ty­jä il­mais­kir­jo­ja saa käyt­tää, ja muu­ta­kin jos ha­luaa.

Pis­tei­tä an­taes­sa­ni kiin­ni­tän huo­mio­ta en­nen kaik­kea sii­hen, kuin­ka hy­vin es­see osoit­taa asian ym­mär­tä­mis­tä, se­kä il­mai­sun täs­mäl­li­syy­teen. Täy­det pis­teet vaa­ti­vat edes hie­man jär­ke­väs­ti käy­tet­tyä ma­te­ma­tiik­kaa, mut­ta osan pis­teis­tä voi saa­da il­man­kin. Asia­vir­heet alen­ta­vat pis­tei­tä. Va­lit­se it­sel­le­si so­pi­va stra­te­gia: jos yri­tät liian kun­nian­hi­mois­ta es­see­tä, on vaa­ra­na, et­tä yk­si­tyis­koh­dat me­ne­vät rat­kai­se­vas­ti pie­leen ja pis­teet jää­vät vä­häi­sik­si. Voit pie­nen­tää tä­tä ris­kiä se­los­ta­mal­la vai­kei­den kaa­vo­jen si­säl­löt myös sa­nal­li­ses­ti.

Es­seen ai­he-eh­do­tuk­sia jul­kais­taan myö­hem­min.

Lo­pus­sa on tai ei ole tent­ti

Tä­mä to­teu­tus kurs­sis­ta on yli­mää­räi­nen. Kurs­si on pois­tet­tu ope­tus­oh­jel­mas­ta vuon­na 2020. Tä­mä to­teu­tus imp­ro­vi­soi­tiin ly­hyel­lä va­roi­tus­ajal­la ja sik­si osa asiois­ta rat­keaa vas­ta kurs­sin ai­ka­na. To­teu­tuk­sen tar­koi­tus on lie­vit­tää nii­tä on­gel­mia, joi­ta opis­ke­li­joil­le ai­heu­tui, kun ke­vät­lu­ku­kau­den 2022 al­kaes­sa ei voi­tu­kaan pa­la­ta lä­hi­ope­tuk­seen. Ha­lut­tiin laa­jen­taa opis­kel­ta­vien kurs­sien va­li­koi­maa.

Ar­vo­sa­no­jen aset­ta­mi­sek­si on jo­ten­kin mi­tat­ta­va opis­ke­li­joi­den osaa­mi­nen ja han­kit­ta­va riit­tä­vä luot­ta­mus sii­hen, et­tä opis­ke­li­joi­den osaa­mi­ses­taan an­ta­mat näy­töt ovat hei­dän it­sen­sä te­ke­mät. Ta­voit­tee­na on, et­tä näyt­tö muo­dos­tuu pa­lau­te­tuis­ta ko­ti­teh­tä­vis­tä ja es­sees­tä. Tar­vit­taes­sa lo­pus­sa pi­de­tään suul­li­nen Zoom-tent­ti tai pe­rin­tei­nen läs­nä­tent­ti. Läs­nä­ten­tin jär­jes­tä­mi­nen on epä­to­den­nä­köis­tä.

Lail­li­ses­ti il­mai­sia kir­jo­ja

Boaz Ba­rak: Int­ro­duc­tion to Theo­re­ti­cal Com­pu­ter Scien­ce Har­var­din yli­opis­tos­sa käy­tet­ty kir­ja. No­pean vil­kai­sun pe­rus­teel­la se­lit­tää asiat to­si hy­vin! Vä­hän eri pai­no­tuk­set kuin TIEA241:llä, mut­ta ei hait­taa.

Ma­hesh­wa­ri, Smid: Int­ro­duc­tion to Theo­ry of Com­pu­ta­tion Var­sin tar­kas­ti TIEA241:sta vas­taa­va kir­ja.

Sa­va­ge: Mo­dels Of Com­pu­ta­tion: Exp­lo­ring the Po­wer of Com­pu­ting Asian­tun­te­va. Mu­ka­na kaik­ki tar­vit­ta­va ja hy­vin pal­jon muu­ta. Alun pe­rin kau­pal­li­ses­ti kus­tan­net­tu.

Fleck: Buil­ding Blocks for Theo­re­ti­cal Com­pu­ter Scien­ce Tä­mä voi aut­taa pää­se­mään si­säl­le tar­vit­ta­vaan ma­te­ma­tiik­kaan.

Evans, Dyl­la: Do­ri-Mic and the Uni­ver­sal Mac­hi­ne Mel­ko help­po­lu­kui­nen, mut­ta ei rii­tä tent­ti­kir­jak­si.

Van­hat tie­dot­teet

Ei vie­lä ole.

---