582206 Laskennan mallit (ohtk 25.8.2011)

  • Pääteemat
Esitiedot Lähestyy oppimistavoitetta Saavuttaa oppimistavoitteet Syventää oppimistavoitteita
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
28.08.2011 - 18:18 Jyrki Kivinen
01.03.2011 - 04:39 Jyrki Kivinen