Oppimistavoitteet kurssilla Laskennan mallit
Pääteema Esitiedot Lähestyy Saavuttaa Syventää
oppimistavoitteita oppimistavoitteet oppimistavoitteita Tietojenkäsittelyteorian
perusteet • joukko-opin ja logiikan al-
keet (Johd. diskr. mat.)
• todistamisen perustekniikat (Johd. diskr. mat.)
• perustelee yksinkertaisen al- goritmin oikean toiminnan invarianttien avulla (Tietora- kenteet)
• kuvaa algoritmisen ongelman käyttäen täsmällisesti luon- nollista kieltä ja yksinkertais- ta matemaattista formalismia;
lukee ja tulkitsee tällaisia ku- vauksia
• muodostaa yksinkertaisia päättelyketjuja kurssilla määriteltävien käsitteiden pohjalta
• selittää omin sanoin perusop- pikirjatasoista tietojenkäsit- telyteoreettista tekstiä kon- struktioiden yksityiskohdat ja todistukset mukaanlukien
• muodostaa päteviä, raken- teeltaan johdonmukaisia ratkaisuja yksinkertaisiin todistustehtäviin kurssil- la esitettyjen käsitteiden pohjalta
• lukemalla tietojenkäsittely- teoriaa käsittelevän artikkelin muodostaa yleiskuvan sen ongelmanasettelusta ja tuloksista
• muodostaa täsmällisiä, ei- triviaaleja argumentteja algoritmien toiminnasta
Automaatit ja kieliopit • joukko-opin alkeet (Johd.
diskr. mat.)
• verkkojen perusmääritelmät (Johd. diskr. mat.)
• käyttää pinoa ja jonoa osana normaalia ohjelmointia (Tie- torakenteet)
• soveltaa verkon läpikäynte- jä verkko-ongelmien ratkai- semiseksi (Tietorakenteet)
• muodostaa automaatteja ja kielioppeja yksinkertai- sille formaaleille kielille sanallisen tai matemaattisen kuvauksen pohjalta; kään- täen kuvailee automaattia tai kielioppia vastaavan kielen
• soveltaa tunnettuja muunnos- algoritmeja automaatin saa- miseksi kieliopista ja kään- täen
• toteaa kielen ei-
säännöllisyyden tunnetuilla menetelmillä
• soveltaa kieliluokkien sul- keumaominaisuuksia ja mui- ta perusominaisuuksia ja esit- tää niiden taustalla olevat konstruktiot
• käyttää äärellisiä automaatte- ja, kielioppeja ja niihin pe- rustuvia työkaluja ohjelmoin- titehtävien ratkaisemiseen
• käyttää tila-automaatteja esim. hajautetun laskennan mallintamiseen
Ratkeavuus ja vaativuus • joukko-opin alkeet (Johd.
diskr. mat.)
• verkkojen perusmääritelmät (Johd. diskr. mat.)
• käyttää pinoa ja jonoa osana normaalia ohjelmointia (Tie- torakenteet)
• soveltaa verkon läpikäynte- jä verkko-ongelmien ratkai- semiseksi (Tietorakenteet)
• selittää Churchin-Turingin teesin ja sen keskeiset perustelut ja seuraukset
• tunnistaa joitakin keskeisiä ratkeamattomia ongelmia ja selittää niiden ratkeamatto- muuden merkityksen käytän- nön ohjelmoinnille
• todistaa ratkeavuuteen liitty- vien perustuloksia
• tunnistaa perusesimerkkejä polynomisesta ja eksponen- tiaalisesta aikavaativuudesta ja NP-täydellisyydestä;
selittää näiden seikkojen merkityksen hyvin karkealla tasolla
• tarkastelee formaalin päätte- lyn ratkeavuutta (Matem. lo- giikka)
• tunnistaa useita erilaisia NP- täydellisiä ongelmia
• ratkaisee NP-täydellisiä on- gelmia heuristisilla ja approk- simaatioalgoritmeilla
