Es­see TIEP1020 ke­vät 2019

Yleis­tä

Ten­tis­sä tu­lee ole­maan ky­sy­mys, jos­sa si­nua pyy­de­tään kir­joit­ta­maan en­nal­ta val­mis­te­le­ma­si es­see. Es­seen 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.

Al­la on eh­do­tuk­sia es­seen ai­heek­si. Niis­sä on help­po­ja ja vai­kei­ta. Sik­si kan­nat­taa eh­kä tu­tus­tua muu­ta­maan en­nen oman ai­heen va­lin­taa. Ai­he saa ol­la myös it­se kek­si­mä­si, kun­han se täyt­tää seu­raa­vat eh­dot:

• Sil­lä tu­lee ol­la jo­kin si­säl­löl­li­nen yh­ty­mä­koh­ta kurs­siin. Esi­mer­kik­si komp­lek­si­lu­vut ovat liian kau­ka­na kurs­sin tee­mas­ta.
• De­mois­sa pe­rus­teel­li­ses­ti kä­si­tel­tyä ai­het­ta ei saa va­li­ta. Esi­mer­kik­si sil­muk­kain­va­riant­ti on tul­lut de­mois­sa useas­ti, jo­ten si­tä ei saa va­li­ta. De­mo­jen tois­ta­mi­nen ei tuo opis­ke­lul­le li­säar­voa.
• Muil­la kurs­seil­la pe­rus­teel­li­ses­ti ope­tet­tu asia ei kel­paa. Älä tee es­see­tä esi­mer­kik­si ylei­sim­mis­tä tie­to­ra­ken­teis­ta, kos­ka nii­tä ope­te­taan pal­jon muil­la kurs­seil­la. Mui­den kurs­sien asian tois­ta­mi­nen ei tuo li­säar­voa.

Täl­lä kurs­sil­la luen­noi­dut asiat, joi­ta ei ole kä­si­tel­ty de­mois­sa, kel­paa­vat ai­heik­si. NP-täy­del­li­syys ja bi­nää­ri­pää­tös­kaa­viot (ROBDD) ovat täs­tä esi­merk­ke­jä. Es­see ei kui­ten­kaan saa ol­la suo­ra ko­pio kurs­sin ai­neis­tos­ta ei­kä mis­tään muus­ta­kaan läh­tees­tä.

Es­seen so­pi­va pi­tuus on puo­les­ta si­vus­ta yh­teen si­vuun. Jos es­sees­tä uh­kaa tul­la pal­jon pi­tem­pi, muu­ta ot­sik­koa niin et­tä ai­he muut­tuu ka­peam­mak­si. Jos es­sees­tä uh­kaa tul­la ly­hyem­pi, 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ääa­siaan. 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.

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 saa käyt­tää, ja muu­ta­kin jos ha­luaa. Läh­de­viit­tei­tä ei tar­vit­se ol­la.

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. 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­see kan­nat­taa miet­tiä etu­kä­teen, mut­ta se pi­tää tuo­da tent­tiin pääs­sä ei­kä pa­pe­ril­la. Es­seen pai­noar­vo ten­tis­sä on vain noin 13%, jo­ten sen val­mis­te­lus­ta ei kan­na­ta teh­dä elä­mää suu­rem­paa asiaa.

Ai­hei­ta

Mo­du­loa­rit­me­tiik­ka

• po­tens­si­las­ku mo­du­loa­rit­me­tii­kas­sa
• syt(n, m) muo­dos­sa xn + ym
• Fermat'n pie­ni lau­se (Fermat's little theorem — Wi­ki­pe­dia)

Pro­po­si­tio­lo­giik­ka

• to­tuus­funk­tioi­den ra­ken­ta­mi­nen mah­dol­li­sim­man vä­hil­lä ope­raat­to­reil­la
• kon­junk­tii­vi­sen nor­maa­li­muo­don ko­ko
• ROBDD
• re­so­luu­tio­päät­te­ly (Re­so­lu­tion (lo­gic) — Wi­ki­pe­dia)
• SAT-rat­kai­si­jat (Boo­lean sa­tis­fia­bi­li­ty prob­lem — Wi­ki­pe­dia)
• kol­mas to­tuu­sar­vo ”mää­rit­te­le­mä­tön”

Pre­di­kaat­ti­lo­giik­ka

• Prenex normal form — Wi­ki­pe­dia
• Skolemin nor­maa­li­muo­to (Skolem normal form — Wi­ki­pe­dia)
• luon­nol­lis­ten lu­ku­jen in­duk­tio­ak­sioo­mas­kee­ma
• pi­no mää­ri­tel­ty­nä pre­di­kaat­ti­lo­gii­kal­la
• jo­no mää­ri­tel­ty­nä pre­di­kaat­ti­lo­gii­kal­la
• Gödelin täy­del­li­syys­lau­se
• Gödelin en­sim­mäi­nen epä­täy­del­li­syys­lau­se
• hei­koin esieh­to (Pre­di­ca­te trans­for­mer se­man­tics — Wi­ki­pe­dia)

Las­ken­nal­li­nen vaa­ti­vuus

• NP-täy­del­li­syys
• PSPA­CE-täy­del­li­syys
• Savitch's theorem — Wi­ki­pe­dia
• Kol­mo­go­rov-komp­lek­si­suus

Jouk­ko-op­pi

• sun­nat­tu­jen ja suun­taa­mat­to­mien graa­fien mää­ri­tel­mät
• graa­fien iso­mor­fis­mi (Graph iso­morp­hism — Wi­ki­pe­dia)
• graa­fien iso­mor­fis­min komp­lek­si­suus (Graph iso­morp­hism prob­lem — Wi­ki­pe­dia)
• bi­si­mi­laa­ri­suus (Bi­si­mu­la­tion — Wi­ki­pe­dia)

Muu­ta

• si­to­vuus­sään­nöt ma­te­ma­tii­kas­sa
• liu­ku­lu­ku­jen esi­tys tie­to­ko­nees­sa
• UTF-8
• jous­ta­van ko­koi­sen tau­lu­kon suo­ri­tus­te­hok­kuus