TIES5303 Laskennan mallit (3–5 op)

Opinnon taso:
Syventävät opinnot
Arviointiasteikko:
0-5
Suorituskieli:
suomi
Vastuuorganisaatio:
Informaatioteknologian tiedekunta
Järjestävä organisaatio:
Kokkolan yliopistokeskus Chydenius
Opetussuunnitelmakaudet:
2020-2021, 2021-2022, 2022-2023

Avainteksti

Kurssi suoritetaan Kokkolan yliopistokeskus Chydeniukseen

Kuvaus

Automaattien ja formaalien kielten peruskäsitteitä, äärelliset automaatit ja säännölliset kielet, kieliopit ja context-free kielet, pinoautomaatti, rekursiivisesti etenevä jäsentäminen, Turingin koneet ja laskettavuus, lyhyesti muista yleisistä laskennan malleista

Osaamistavoitteet

Opintojakson suoritettuaan opiskelija osaa selittää kurssilla esitettyjen äärellisten automaattien, pinoautomaattien ja Turingin koneiden eroavaisuudet laskennan malleina ja tunnistaa niihin liittyvät rajoitteet ja mahdollisuudet sekä osaa yhdistää ne eri kieliperheisiin. Hän osaa selittää käsitteiden laskennallinen ongelma, ratkeava ongelma, osittain ratkeava ongelma ja ratkeamaton ongelma keskeisen sisällön ja niiden väliset erot. Lisäksi hän osaa selittää laskennallisten ongelmien ja kurssilla käsiteltävien laskennan mallien välisen yhteyden sekä osaa tulkita Turingin koneelle esitettyjen tulosten koskevan myös tietokoneita ja niille kirjoitettuja ohjelmia. Hän osaa selittää mitä aika- ja tilakompleksisuudella yleisesti tarkoitetaan ja mikä on niiden merkitys ongelmien ratkaisemisen kannalta. Hän osaa lisäksi soveltaa esitettyjä automaattimalleja ohjelmien suunnittelussa ja ratkaisemisessa.Hänellä on valmiudet etsiä ja omaksua tietoa muista laskennan malleista ja laskennallisesta vaativuudesta.

Esitietojen kuvaus

Matematiikan perusteet (esimerkiksi Diskreetit rakenteet tai matematiikan aineopintoja), algoritmien perusteet (esimerkiksi Algoritmit 1, Algoritmit 2) ja ohjelmoinnin perustaidot (esimerkiksi Ohjelmointi 1, Ohjelmointi 2)

Oppimateriaalit

Kurssilla käytävät asiat löytyvät suurelta osin luentomonisteesta Johdatus automaatteihin ja formaaleihin kieliin (Hakala, 2015), jota tullaan täydentämään kurssin aikana.

Kirjallisuus

  • Introduction to Automata Theory, Formal Languages, and Computation, (Motwani, Hopcroft, Ullman)
  • Introduction to the Theory of Computation, (Sipser, 1997)
  • Automata and Formal Languages, (Keller, 1995)

Suoritustavat

Tapa 1

Valitaan kaikki merkityt osat
Suoritustapojen osat
x

Verkko-opetus (3–5 op)

Tyyppi:
Itsenäinen työskentely
Arviointiasteikko:
0-5
Suorituskieli:
suomi
Ei julkaistua opetusta