TIES5303 Models of Computation (3–5 cr)

Study level:
Advanced studies
Grading scale:
0-5
Language:
Finnish
Responsible organisation:
Faculty of Information Technology
Coordinating organisation:
Kokkola University Consortium Chydenius
Curriculum periods:
2020-2021, 2021-2022, 2022-2023, 2023-2024

Tweet text

Kurssi suoritetaan Kokkolan yliopistokeskus Chydeniukseen

Description

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

Learning outcomes

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.

Description of prerequisites

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

Study materials

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.

Literature

  • 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)

Completion methods

Method 1

Select all marked parts
Parts of the completion methods
x

Online teaching (3–5 cr)

Type:
Independent study
Grading scale:
0-5
Language:
Finnish
No published teaching