Kursplan - Formella språk, automater och beräkningsteori
Omfattning
7.5 hp
Kurskod
DVA337
Giltig från
Hösttermin 2015
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
Litteraturlistor
Kurslitteraturen är preliminär till 8 veckor innan kursstart. Kurslitteratur kan vara giltig över flera terminer.
-
Böcker
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
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
Ö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, vilket innebär att kunna förklara och använda begrepp och strukturer samt teoretiska ramverk och verktyg samt förstå deras inneboende relationer. I synnerhet kunna konstruera och uttolka funktionen av automater och redogöra för sambandet mellan automater och språk,
2. tillämpa praktiska kunskaper, vilket i huvudsak gäller förmågan att lösa problem och demonstrera härledningar, och simuleringar av teoretiska 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, laborationer och ett seminarium.
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), skriftlig tentamen, 6 hp, betyg Underkänd (U), 3, 4 eller 5. Examinerar lärandemål 1 och 2.
Inlämningsuppgift (INL1), En kortare uppsats som presenteras och diskuteras i ett seminarium, 1,5 hp, Betyg Underkänd (U) eller Godkänd (G). Examinerar lärandemål 3.
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.