Text

Kursplan - Formella språk, automater och beräkningsteori

Omfattning

7.5 hp

Kurskod

DVA337

Giltig från

Hösttermin 2020

Utbildningsnivå

Grundnivå

Successiv fördjupning

G2F (Grundnivå, har minst 60 hp kurs/er på grundnivå som förkunskapskrav).

Huvudområde(n)

Datavetenskap

Akademi

Akademin för innovation, design och teknik

Fastställd

2014-06-24

Reviderad

2020-01-24

Litteraturlistor

Kurslitteraturen är preliminär till 8 veckor innan kursstart. Kurslitteratur kan vara giltig över flera terminer.

    • Beslutsdatum: 2020-06-29
    • Senaste uppdatering: 2020-06-29

    Böcker

    Linz, Peter

    An introduction to formal languages and automata

    5th ed. : Sudbury, MA : Jones & Bartlett Learning, c2012 - xiii, 437 p.

    ISBN: 978-1-4496-3739-2 (hft.) LIBRIS-ID: 12418450

    http://books.google.se/books?id=hsxDiWvVdBcC&printsec=frontcover&hl=sv&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false

    Obligatorisk

    Salling, Lennart

    En introduktion till formella språk, automater och beräkningar

    [Ny utg.] : [Uppsala : Lennart Salling], cop. 1998 - 264 s.

    ISBN: 91-630-7707-8 LIBRIS-ID: 7453571

    Obligatorisk

    Övrigt

    OBS! Endast en av ovanstående titlar behöver användas.

    Akademin för innovation, design och teknik,

Syfte

Kursen skall ge inblick i de teoretiska grunderna för formella språk, automata och beräkningsteori - frågeställningar som ingår i olika former i all datavetenskap.

Lärandemål

Efter avslutad kurs skall studenten kunna:

1. visa på grundläggande teoretiska kunskaper, både vad gäller sambandet mellan grammatiker, automater och språk och vad gäller fundamentala begränsningar i vad som är beräkningsbart,
2. tillämpa praktiska kunskaper, både vad gäller förmågan att konstruera och simulera formella maskiner och grammatiker samt,
3. visa förmåga att reflektera i skriftlig form över kursens innehåll i relation till olika beräkningsparadigmer.

Innehåll

Reguljära språk och finita automater.
Sammanhangsfria språk och pushdown-automater.
Restriktionsfria språk och turingsmaskiner.
Den universiella turingsmaskinen.
Oavgörbarhet - Stopp-problemet.
Beräkningsteoretiska paradigmer.

Undervisning

Undervisningen bedrivs i form av föreläsningar, räkneövningar och laborationer.

Särskild behörighet

Programmeringskunskaper i ett högnivåspråk och kunskaper i diskret matematik. Detta kan uppnås genom att ha avslutat kurserna Programmering 7,5 hp och Diskret matematik 7,5 hp eller motsvarande.

Examination

Tentamen (TEN1), Salstentamen, 6 hp, examinerar lärandemål 1 och 2, betyg Underkänd (U), 3, 4 eller 5. 
Inlämningsuppgift (INL1), en kortare uppsats,1,5 hp, examinerar lärandemål 3, betyg Underkänd (U) eller Godkänd (G).

En student som har ett intyg från MDU avseende sin funktionsnedsättning har möjlighet att anmäla önskemål om anpassning vid salstentamina eller annan examinationsform i enlighet med Regler och anvisningar för examination på grundnivå och avancerad nivå vid Mälardalens högskola (2020/1655). Det är examinator som, utifrån det intyg som utfärdats, beslutar om eventuell anpassning och i så fall vilken anpassning som ska gälla.

Misstankar om vilseledande vid examination (fusk) anmäls, enligt högskoleförordningen, till universitetets rektor och prövas av universitetets disciplinnämnd. Om disciplinnämnden anser att en student gjort sig skyldig till en disciplinförseelse fattar nämnden beslut om en disciplinär åtgärd, vilket är varning eller avstängning.

Betyg

Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd

Övergångsbestämmelser och övriga föreskrifter

Kursen överlappar helt med CD5560, CDT314 och DVA325 Formella, språk, automater och beräkningsteori 7,5 hp.