Tietojenkäsittelyteorian perusteet |
- joukko-opin ja logiikan alkeet (Johd.diskr. matem.)
- todistamisen perustekniikat (Johd. diskr. matem.)
- perustelee yksinkertaisen algoritmin oikean toiminnan invariantin avulla (Tietorakenteet)
|
- kuvaa algoritmisen ongelman käyttäen täsmällisesti luonnollista kieltä ja yksinkertaista matemaattista formalismia; lukee ja tulkitsee tällaisia kuvauksia
- muodostaa yksinkertaisia päättelyketjuja kurssilla määriteltävien käsitteiden pohjalta
|
- selittää omin sanoin perusoppikirjatasoista tietojenkäsittelyteoreettista tekstiä konstruktioiden yksityiskohdat ja todistukset mukaanlukien
- muodostaa päteviä, rakenteeltaan johdonmukaisia ratkaisuja yksinkertaisiin todistustehtäviin kurssilla esitettyjen käsitteiden pohjalta
|
- lukemalla tietojenkäsittelyteoreettisen artikkelin muodostaa yleiskuvan sen ongelmanasettelusta ja tuloksista
- muodostaa täsmällisiä, ei-triviaaleja argumentteja algoritmin toiminnasta
|
Automaatit ja kieliopit |
- joukko-opin alkeet (Johd. diskr. matem.)
- verkkojen perusmääritelmät (Johd. diskr. matem.)
- käyttää pinoa, jonoa, listaa ja puurakenteita osana normaalia ohjelmointia (Tietorakenteet)
- soveltaa verkon läpikäyntejä, polunetsintää ja virittäviä puita erilaisten verkko-ongelmien ratkaisemiseksi (Tietorakenteet)
|
- muodostaa automaatteja ja kielioppeja yksinkertaisille formaaleille kielille sanallisen tai matemaattisen kuvauksen pohjalta; kääntäen kuvailee automaattia tai kielioppia vastaavan kielen
- soveltaa tunnettuja muunnosalgoritmeja automaatin saamiseksi kieliopista ja kääntäen
|
- toteaa kielen ei-säännöllisyyden tunnetuilla menetelmillä
- soveltaa kieliluokkien sulkeumaominaisuuksia ja muita perusominaisuuksia ja esittää niiden taustalla olevat konstruktiot
|
- käyttää äärellisiä automaatteja, kielioppeja ja niihin perustuvia työkaluja ohjelmointitehtävien ratkaisemiseen
- käyttää tila-automaatteja esim. hajautetun laskennan mallintamiseen
|
Ratkeavuus ja vaativuus |
kuten edellä |
- selittää Churchin-Turingin teesin ja sen keskeiset perustelut ja seuraukset
- tunnistaa joitain keskeisiä ratkeamattomia ongelmia ja selittää niiden ratkeamattomuuden merkityksen käytännön ohjelmoinnille
|
- todistaa ratkeavuuteen liittyviä perustuloksia
- tunnistaa perusesimerkkejä polynomisesta ja eksponentiaalisesta aikavaativuudesta ja NP-täydellisyydestä; selittää näiden seikkojen merkityksen hyvin karkealla tasolla
|
- tarkastelee formaalin päättelyn ratkeavuutta (Matem. logiikka)
- tunnistaa useita erilaisia NP-täydellisiä ongelmia
- ratkaisee NP-täydellisiä ongelmia heuristisilla ja approksimaatioalgoritmeilla
|