TIEA241 Automaatit ja kieliopit

Lukuvuosi 2013–2014 — itseopiskelukurssi

Talven 2013-2014 TIEA241 Automaatit ja kieliopit -opintojakson itseopiskelukurssi on päättynyt. Kurssin järjestetään seuraavan kerran keväällä 2015 yhteistyössä Kokkolan yliopistokeskuksen kanssa (ks. Korppi); kurssin vastuuopettaja vaihtuu.

Toimintaohjeet

Ilmoittaudu Korpissa ensin. Katso luentovideot. Tee tehtävät ja toimita ne minulle kommentoitavaksi yhden tai kahden luennon tehtävät kerralla (tarkemmat ohjeet löytyvät tehtävälistan alusta). Tee joko tentti tai sovi harjoitustyöstä. Pakollista on vain tentin tai harjoitustyön (ei kuitenkaan molempien) tekeminen.

Tenttiajat: 29.11.2013, 18.12.2013, 21.3.2014, 21.5.2014, 13.6.2014 ja 11.7.2014. Aiempien kurssien tenttikysymyksiä arviointiperusteineen on saatavilla.

Harjoitustyön osalta noudatetaan soveltuvin osin kesän 2013 kurssin harjoitustyöohjetta. Harjoitustyön tekeminen kannattaa aloittaa aikaisintaan, kun luennot 1–11 on opiskeltu; myös joitakin luennoilla 12–17 käsiteltyjä asioita tarvitaan harjoitustyössä. Pyydä palautusohjeet erikseen, kun palauttaminen alkaa olla ajankohtaista. Harjoitustyö tulee palauttaa 15.6.2014 mennessä. Voit halutessasi täydentää jo palauttamaasi harjoitustyötä arvosanan korotuksen tarkoituksessa aina 31.7.2014 asti.

Kurssilla on vapaaehtoinen IRC-kanava #auki @ IRCnet (kanava-avain: jyu), jossa minä olen ibid.

Akateeminen rehellisyys

Noudata kurssilla ehdotonta akateemista rehellisyyttä. Tee selväksi, mikä on omaa tuotostasi ja minkä olet lainannut tai kopioinut muualta. Anna selkeä ja tarkka lähdeviite, kun käytät (lainaten tai muuten) muiden tuottamaa materiaalia. Jos olet tehnyt jotain yhteistyössä toisen opiskelijan kanssa, kaikkien tekemiseen osallistuneiden nimi tulee mainita ja tarpeen mukaan kertoa, mitä kukakin teki. Tämä koskee ainakin harjoitustehtävien ratkaisujasi sekä mahdollista harjoitustyötäsi.

Merkitse suorat lainaukset selkeästi. Jos käytät tekstissä jonkun muun kirjoittamaa tekstiä sellaisenaan tai vähän muokattuna, laita se lainausmerkkeihin tai käytä muuta helposti ymmärrettävää tapaa tekemään selväksi, että kyse on suorasta lainauksesta. Tämä koskee myös tilanteita, joissa lainaat vieraskielistä lähdettä itse suomentaen (ilmoita tästä lähdeviitteessä, esim. "suomennos minun"). Jos käytät jonkun muun laatimaa kuvaa, taulukkoa tai ohjelmakoodia sellaisenaan tai vähän muokattuna, kerro siitä kuvatekstissä tai muussa sopivassa kohdassa niin, että asia ei jää epäselväksi. Pelkkä lähdeviite ei koskaan yksin riitä ilmoittamaan, että kyse on lainauksesta.

Kaikki lainausmerkeillä tai muuten merkittyyn lainaukseen tekemäsi muokkaukset on merkittävä. Jos poistat tekstilainauksen keskeltä sanoja, merkitse se kahdella peräkkäisellä ajatusviivalla (esim. "Jos käytät tekstissä jonkun muun kirjoittamaa tekstiä – –, laita se lainausmerkkeihin"). Jos lisäät suoraan tekstilainaukseen sanoja tai korvaat sanoja toisilla, laita nämä lisätyt tai korvaavat sanat hakasulkeisiin (esim. "Jos käytät tekstissä jonkun muun kirjoittamaa tekstiä sellaisenaan tai vähän muokattuna, – – [tee] selväksi, että kyse on suorasta lainauksesta."). Jos lisäät tai poistat kursivoinnin, mainitse siitä lähdeviitteessä (esim. "kursiivi minun", jos olet sen lisännyt).

Selkeä ja tarkka lähdeviite on sellainen, jonka avulla lukija pystyy selvittämään, mistä lähteestä on kyse ja kuinka sen voisi saada itselleen luettavaksi. Lähteen tarkat bibliografiatiedot (mm. tekijä, nimi ja julkaisuvuosi sekä kirjasta julkaisija, lehtiartikkelista lehden nimi ja numero, verkkolähteestä URL ym) on annettava joko erillisessä lähdeluettelossa, johon lähdeviiteellä viitataan, tai suoraan lähdeviitteessä. Ilmoita mahdollisuuksien mukaan tarkka sivunumero tai muu vastaava tarkentava tieto.

Tarkemmin hyvästä lainaus- ja viittauskäytännöstä voit lukea akateemisen kirjoittamisen oppaista, esimerkiksi luvusta 6.3 "Mitä lainataan ja miten viitataan?" sivuilla 357–366 kirjassa Sirkka Hirsjärvi, Pirkko Remes ja Paula Sajavaara: Tutki ja kirjoita. 15. uudistettu painos. Helsinki: Tammi, 2009. Myös englanninkielinen Purduen yliopiston sivu lainaamisesta ja omin sanoin kirjoittamisesta on hyödyllinen.

Plagiointia on mm. muiden tuottaman materiaalin käyttäminen ilman asianmukaisia lähdeviitteitä tai ilman mahdollisten suorien lainausten merkitsemistä. Ei ole merkitystä, onko tällainen käyttäminen ollut tekijänoikeudellisesti sallittua vai kiellettyä.

Havaittu plagiointi estää kurssisuorituksen hyväksymisen. Mikäli kyse on opettajan harkinnan mukaan taitamattomuudesta, asia voidaan käsitellä opettajan ja opiskelijan kesken oppimistilanteena, jonka yhteydessä plagiointi poistetaan opiskelijan työstä. Kaikki muut plagiointi- ja vilppitapaukset on vietävä virallisesti laitoksen johtajan tutkittavaksi, ja tutkinnan seurauksena vilppiin syyllistynyt opiskelija voidaan mm. erottaa yliopistosta määräajaksi. Plagiointi- ja vilppiepäilyn käsittelyssä noudatetaan tiedekunnan ohjetta ja rehtorin vahvistamaa yliopistotasoista ohjetta.

Tietoa plagioinnista ja muusta vilpistä löytyy lisäksi suomeksi mm. Helsingin yliopiston Älä kopsaa -sivustosta ja englanniksi mm. Purduen yliopiston sivuilta. Plagiointia on myös luonnehdittu edellä linkitetyssä rehtorin vahvistamassa yliopistotason ohjeessa.

Luentovideot ja muu materiaali

Luentovideot on kuvattu kesän 2013 kurssilla. Huomaa, että videoilla esitetyt kurssin käytänteet koskevat tuota mennyttä kurssia eikä tätä itseopiskelukurssia.

Luentokalvot, esimerkkiohjelmat ja jälkiprujut ovat myös peräisin kesäkurssilta 2013. Ne täydentävät asiaa ja kuuluvat kurssin koealueeseen. Jälkiprujut on tarkoitettu luettavaksi luentovideon katsomisen jälkeen. Lisäprujut ovat ylimääräistä materiaalia, joka (pääsääntöisesti) ei kuulu kurssin varsinaiseen sisältöön. Ensimmäisen luennon lisäpruju on poikkeus: siihen tulee tutustua.

Kaikki kurssin harjoitustehtävät: PDF, LaTeX

#Aihe ja videolinkkiLuentokalvotEsimerkkiohjelmatJälkiprujuLisäprujut
Aloitus
1AloitusluentoPDF, LaTeXPDF, LaTeXPDF, LaTeX. Huomaa, että egrep-ohjelmaa voi testata esim. halava- ja jalava-koneilla kuten luennolla tehtiin
Säännölliset kielet
2Deterministiset äärelliset automaatit (DFA:t)PDF, LaTeXautom3.c Autom3.java Autom3.hsPDF, LaTeX
3Säännölliset kieletPDF, LaTeXgrep-ohjelman alkuaPDF, LaTeX
4Epädeterministiset äärelliset automaatit (NFA:t)PDF, LaTeXNFA:t grepissäPDF, LaTeX
5Säännölliset lausekkeet, Kleenen lausePDF, LaTeXPDF, LaTeX
6DFA:n minimointi ja DFA:iden kielten samuusPDF, LaTeXPDF, LaTeXLisäluettavaa regexp-hauista (ei kuulu koealueeseen): Laurikari 2000, Laurikari 2001 (PDF), Cox 2007, Becchi & Crowley 2008, Haber ym. 2013
Kontekstittomat kielet
7Säännöllisten kielten pumppaus, kontekstittomat kieliopitPDF, LaTeXPDF, LaTeX
8Kontekstittomat kieliopit, johdot, jäsennyspuut, moniselitteisyysPDF, LaTeXPDF, LaTeXEräiden syntaktisten metakielten alkuperäistekstejä lisäluettavaksi: Revised Algol 60 Report, RFC 5234, vuoden 1974 C-kielen manuaali; vaihtoehto CFG:ille on Parsing Expression Grammars -formalismi
9Pinoautomaatit, Earleyn algoritmiPDF, LaTeXPDF, LaTeXPDF, LaTeX (e.y, y.output); linkki Earleyn paperiin
10Ennustava jäsennysPDF, LaTeXrdesim.txt, rdesim2.txtPDF, LaTeX
11Attribuuttikieliopit, YaccPDF, LaTeXlaskin_bt.c, laskin_pp.c, laskin_ag.c, laskin_y.y, [laskin_ly.llaskin_ly.y], shiftred.y, redred.yPDF, LaTeX
Rekursiivisesti lueteltavat kielet
12Kontekstittoman kielen pumppaus, kontekstiset ja yleiset kieliopit, Turingin koneetPDF, LaTeXPDF, LaTeX
13Turingin koneet, Turingin teesiPDF, LaTeXPDF, LaTeXKaksi artikkelia Turingin teesin historiasta: Computability and Recursion, Computability and Incomputability
14Turingin koneen muunnelmia ja vaihtoehtojaPDF, LaTeXPDF, LaTeX
15Laskennan rajat: päätösongelmat, diagonaalikieli, universaalikone, pysähtymisongelmaPDF, LaTeXPDF, LaTeXGeoffrey K. Pullum: Scooping the loop snooper: A proof that the Halting Problem is undecidable
16Ratkeavuutta, Ricen lausePDF, LaTeXPDF, LaTeXPDF, LaTeX
Lopetus
17Rekursioteoria, λPDF, LaTeXPDF, LaTeXlambdalaskinmalli
18Yhteenvetogrep-ohjelma valmis

Kannustin tehtävien tekoon

Tekemistäsi ja minulle kommentoitavaksi lähettämistäsi tehtävistä saat oikeuden hyväksytyn arvosanan korotukseen seuraavasti:

Tehtävien määrä 0–13 14–27 28–40 41–54 55–
Arvosanan korotus 0 ½ 1 2

Otan huomioon kaikki vastauksesi, jotka osoittavat vähintään hyvää yritystä ratkaista tehtävä. Jos jätän jonkin vastauksesi huomiotta, sanon siitä; voit tällöin halutessasi täydentää vastaustasi.

Lähetän kommenttieni mukana sinulle mallivastaukset sellaisiin tehtäviin, joiden vastauksesi on hyvä yritys mutta sen verran puutteellinen, että mallivastauksesta on arvioni mukaan sinulle hyötyä. Voit halutessasi pyytää mallivastauksia myös muihin tehtäviin, joihin olet jo antanut oman vastauksesi tai joiden ratkaisemista et aio enää yrittää.

Jos olet tehnyt demoja TIEA241-kurssilla keväällä 2011, keväällä 2012 tai kesällä 2013, ota yhteyttä niin keskustellaan, kannattaisiko silloin saamasi demohyvitys kopioida sellaisenaan tälle kurssille.

Vain ne tehtävät otetaan huomioon tentin tai harjoitustyön arvosanan korotuksessa, jotka olet arviointihetkeen mennessä palauttanut. Myöhemmin palautetut tehtävät otetaan huomioon mahdollisen uusintatentin tai harjoitustyön täydennyspalautuksen yhteydessä.


2014-06-18 antti-juhani.kaijanaho@jyu.fi