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

syk­sy 2019

Si­vu olen­nai­ses­ti päi­vi­tet­ty 6.9.2019
Si­vu pe­rus­tet­tu 14.6.2019

Tent­tiin 6.11.2019 pe­rus­tu­va it­se­opis­ke­lu­si­vu

Es­seen oh­jeet ja ai­hei­ta tääl­tä

Teh­tä­vät

de­mot	pa­kol­li­set teh­tä­vät	kol­mas­osa­pa­kol­li­set teh­tä­vät
22.‒23.10.	31. Ly­him­män rei­tin et­sin­tä 32. Lue tä­mä ja kir­joi­ta ly­hyt ra­port­ti, jos­sa ku­vai­let omia ko­ke­muk­sia­si kurs­sin asioi­den op­pi­mi­ses­ta. Pa­lau­ta ra­port­ti­si sa­mal­la ta­val­la kuin teh­tä­väs­sä 27.	33. Täs­tä nu­me­ro 1 34. sa­mas­ta nro 2 35. sa­mas­ta nro 4 36. Täs­tä nu­me­ro 1(abcde) 37. Et­si vir­hei­tä teh­tä­vän 32 jul­kai­sun esi­mer­keis­sä.
15.‒16.10.	26. Li­sää BNF-har­joi­tuk­sia 27. Lu­ke­mis­teh­tä­vä: NP-täy­del­li­syys	28. Täs­tä nu­me­ro 32 29. Täs­tä nu­me­ro 3 30. Täs­tä nu­me­ro 4
8.‒9.10.	21. Backus–Naur Form 22. Vuo­rot­te­le­van bi­tin pro­to­kol­la	23. Täs­tä nu­me­ro 26 24. sa­mas­ta nro 23 25. sa­mas­ta nro 22
1.‒2.10.	16. NFA:n muun­ta­mi­nen DFA:ksi 17. Da­tan pak­kaa­mi­nen ja Kol­mo­go­rov-komp­lek­si­suus	18. Täs­tä nu­me­ro 15 19. sa­mas­ta nro 17 20. sa­mas­ta nro 18
24.‒25.9.	11. DFA-pe­rus­asioi­ta 12. Li­sää py­säh­ty­mi­sen tes­taa­mi­ses­ta	13. Täs­tä nu­me­ro 5 14. sa­mas­ta nro 13 15. sa­mas­ta nro 14
17.‒18.9.	6. Väit­tei­den to­tuus­ar­vot 7. Py­säh­ty­mis­tes­te­rin mah­dot­to­muus	8. Täs­tä nu­me­ro 4 9. sa­mas­ta nro 9 10. sa­mas­ta nro 8
10.‒11.9.	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

Yleis­tie­dot

Opet­ta­jat: Ant­ti Val­ma­ri ja Jo­han­na Ran­ta­la

Kurs­si pi­de­tään 9.9.‒25.10.2019.

Al­la ko­keil­laan val­lan­ku­mouk­sel­li­sen in­no­va­tii­vis­ta ta­paa esit­tää kurs­sin viik­ko­ai­ka­tau­lu.

	maa­nan­tai	tiis­tai	kes­ki­viik­ko	tors­tai	per­jan­tai
8:15‒ 9:45		luen­to Ag Alfa
10:15‒11:45
12:15‒13:45		de­mo Ag C233.1	de­mo Ag C233.1
14:15‒15:45	luen­to Ag Alfa
16:00‒17:30		de­mo Ag C233.1

Kurs­sin suo­rit­ta­mi­nen

Kurs­sil­la on pa­kol­li­sia teh­tä­viä, mui­ta teh­tä­viä ja pa­kol­li­nen tent­ti. Pa­kol­li­set teh­tä­vät pi­tää teh­dä kaik­ki ja muis­ta teh­tä­vis­tä pi­tää teh­dä yh­teen­sä ai­na­kin kol­mas­osa. Ar­vo­sa­na mää­räy­tyy pel­käs­tään ten­tis­tä.

Kun­kin vii­kon teh­tä­vät teh­dään omal­la ajal­la en­nen de­moa, ja de­mos­sa nii­tä käy­dään lä­pi. Teh­tä­väs­sä voi ol­la mon­ta ala­koh­taa. Osa teh­tä­vis­tä on pit­kiä vep­pi­si­vu­ja, jois­sa on ky­sy­mys­ten ja vas­tauk­sil­le va­rat­tu­jen ruu­tu­jen li­säk­si asiaa se­lit­tä­vää teks­tiä. Teh­tä­vä kat­so­taan teh­dyk­si, jos it­se ar­vioit, et­tä jos sa­ma teh­tä­vä oli­si ten­tis­sä, niin sai­sit ai­na­kin 80 % sen ala­koh­dis­ta oi­kein. Ei hait­taa, jos et saa ala­koh­taa he­ti oi­kein, mut­ta jos niin käy, niin yri­tä op­pia ala­koh­dan asia niin et­tä ten­tis­sä osaat sen.

Ole kilt­ti ja ker­ro de­mos­sa, jos jo­kin ala­koh­ta oli liian vai­kea! Yri­täm­me ko­vas­ti ke­hit­tää teh­tä­viä pa­rem­mik­si, ja pa­laut­tee­si on sii­nä tär­keää. Jos jo­kin asia on mo­nien mie­les­tä vai­kea, voim­me yrit­tää teh­dä sii­tä uu­den, pa­rem­min se­lit­tä­vän teh­tä­vä­si­vun myö­hem­mäl­le vii­kol­le.

De­mois­sa käyn­ti ei ole ai­van eh­dot­to­man vält­tä­mät­tö­män pa­kol­lis­ta, mut­ta ota huo­mioon, et­tä de­mot ovat mai­nio ti­lai­suus ky­syä epä­sel­vik­si jää­neis­tä asiois­ta, jo­ten niis­sä käy­dyt kes­kus­te­lut voi­vat ol­la tär­kei­tä ten­tin lä­päi­se­mi­sek­si. Jos et jo­nain viik­ko­na käy de­mos­sa, niin il­moi­ta te­ke­mä­si teh­tä­vät säh­kö­pos­tit­se Jo­han­na Ran­ta­lal­le seu­raa­vaan lauan­tai-il­taan men­nes­sä. Teh­tä­vien te­ke­mi­nen suu­rin piir­tein ai­ka­tau­lus­sa on pa­kol­lis­ta, kos­ka opet­ta­ja luu­lee, et­tä ta­sai­nen työs­ken­te­ly 7 vii­kon ajan joh­taa pal­jon pa­rem­paan tu­lok­seen kuin hur­ja opis­ke­lu­ru­pea­ma juu­ri en­nen tent­tiä.

Ten­tin es­see­teh­tä­vä

Yk­si teh­tä­vä ten­tis­sä tu­lee ole­maan es­see­teh­tä­vä. Sen pai­no­ar­vo on 10 % … 15 %. Es­seen ai­heen pi­tää ol­la jo­kin kurs­sil­la kä­si­tel­ty tai kurs­siin liit­ty­vä ai­he, jo­ta ei kä­si­tel­ty har­joi­tuk­sis­sa. Saat va­li­ta ai­hee­si ihan it­se ym. ra­jauk­sel­la. Voit val­mis­tel­la es­see­tä etu­kä­teen, mut­ta se pi­tää tuo­da tent­tiin pääs­sä ei­kä pa­pe­ril­la.

Pis­tey­tyk­ses­sä an­ne­taan pal­jon pai­noa il­mai­sun täs­mäl­li­syy­del­le ja sil­le, et­tä es­sees­tä il­me­nee, et­tä ai­he on ym­mär­ret­ty sy­väl­li­ses­ti. Es­seen so­pi­va pi­tuus on puo­les­ta si­vus­ta yh­teen si­vuun.

Esi­tie­to­vaa­ti­muk­set

Oh­jel­moin­ti­tai­toa pi­tää ol­la ai­na­kin kah­den en­sim­mäi­sen kurs­sin ver­ran.

Ma­te­ma­tiik­kaa pi­tää ol­la ai­na­kin yh­den yli­opis­to­kurs­sin ver­ran.

Työ­mää­rä

Opet­ta­ja pyr­kii sii­hen, et­tä kurs­sin työ­mää­rä oli­si oi­kea. 5 op on vi­ral­li­ses­ti 133 tun­tia me­diaa­ni­opis­ke­li­jan työ­tä kaik­ki työ huo­mioi­den. Kos­ka kurs­si kes­tää 7 viik­koa, se tar­koit­tai­si n. 19 tun­tia / viik­ko, mi­kä on koh­tuut­to­man pal­jon!

Oli­si­ko 13 tun­tia / viik­ko koh­tuul­li­nen? Se pe­rus­tuu aja­tuk­seen, et­tä 60 op vuo­des­sa vas­taa 15 op pe­rio­dis­sa, jo­ten yh­den pe­rio­din 5 op kurs­si vas­taa kol­mas­osaa työ­ajas­ta pe­rio­din ajan. Nor­maa­li viik­ko­työ­ai­ka on va­jaa 40 tun­tia, jo­ten kol­mas­osa on noin 13 tun­tia. Se koos­tuu 4 tun­nis­ta luen­to­ja, 2 tun­nis­ta de­mo­ja ja 7 tun­nis­ta työ­tä ko­to­na.

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

Maheshwari, Smid: Introduction to Theory of Computation Var­sin tar­kas­ti TIEA241:sta vas­taa­va kir­ja.

Savage: Models Of Computation: Exploring the Power of Computing 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: Building Blocks for Theoretical Computer Science Tä­mä voi aut­taa pää­se­mään si­säl­le tar­vit­ta­vaan ma­te­ma­tiik­kaan.

Evans, Dylla: Dori-Mic and the Universal Machine Mel­ko help­po­lu­kui­nen, mut­ta ei rii­tä tent­ti­kir­jak­si.

Van­hat tie­dot­teet

[24.9.2019] Etä­opis­ke­li­jat huo­mio! Muis­tat­te­han, et­tä myös mui­ta kuin pa­kol­li­sia teh­tä­viä pi­tää teh­dä mi­ni­mi­mää­rä. Tä­män ko­ros­ta­mi­sek­si ot­sik­ko on nyt ”kol­mas­osa­pa­kol­li­set teh­tä­vät”.

[23.9.2019] Tiis­tain vii­mei­nen de­mo on ylei­sön pyyn­nös­tä siir­ret­ty al­ka­maan klo 16 ta­san.

[6.9.2019] Sil­tä va­ral­ta, et­tä il­moit­tau­tu­mi­se­si oli­si ka­don­nut, tie­dok­si: Kurs­sil­le mah­tuu vie­lä. De­mo 3 on täyn­nä, mut­ta de­moi­hin 1 ja 2 mah­tuu vie­lä.

[14.6.2019] Al­la on osa syk­syn 2019 to­teu­tuk­sen tie­dois­ta, ja lo­put täy­den­ty­vät tän­ne vii­meis­tään elo­kuus­sa. Syk­syn 2018 to­teu­tuk­sen tie­to­ja voit kat­sel­la täs­tä, mut­ta va­rau­du sii­hen, et­tä kurs­si voi muut­tua pal­jon­kin. Muu­tos­ten ta­voit­tee­na on so­vit­taa kurs­si opis­ke­li­joi­den läh­tö­tie­toi­hin pa­rem­min kuin syk­syl­lä 2018 oli.

---