DM565: Formelle sprog og dataprocessering

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser
EKA: N330042102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Bachelor

STADS ID (UVA): N330042101
ECTS-point: 10

Godkendelsesdato: 25-03-2019


Varighed: 1 semester

Version: Arkiv

Kommentar

NYT kursus E19

Indgangskrav

Ingen

Faglige forudsætninger

Studerende, der følger kurset, forventes at have kendskab til centrale elementer i kurser om algoritmer og datastrukturer, samt diskret matematik, herunder viden om træer, rekursive definitioner, basale bevisteknikker, søgetræer og hashtabeller, samt at have en vis programmeringserfaring, herunder kendskab til assemblerprogrammering.
Kurset kan ikke følges af studerende, der har taget DM546.    

Formål

Kurset har til formål at sætte de studerende i stand til at udtrykke formelle sprog i forskellige formalismer, herunder at vælge den rette udtryksform for et givent problem under hensyntagen til effektivitet.

Der findes tusindvis af dataformater, og realistiske projekter vil ofte trække på mange forskellige på samme tid. Kurset skal sætte de studerende i stand til at processere dataformater automatisk, herunder at transformere et dataformat til et andet.

En af de mest avancerede former for datatransformation er den, en oversætter realiserer ved oversættelse fra et højniveausprog til et lavniveausprog. Kurset vil udstyre de studerende med viden om de essentielle teknikker i den proces.

Endelig vil de studerende blive introduceret til innovative processer, konkretiseret gennem et eget projekt.

Kurset bygger oven på den viden, der er erhvervet i kurser om algoritmer og datastrukturer, diskret matematik og computerarkitektur, og giver et fagligt grundlag for at studere komplekistet og beregnelighed, der er placeret senere i uddannelsen.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at give den studerende kompetencen til at udtrykke sig gennem formalismer til specifikation af formelle sprog, genkende essentielle elementer af dataformater, samt at kunne transformere både simple og komplekse formater til andre, herunder at kunne vælge den bedste teknik til det forhåndenværende problem. Desuden skal den studerende opnå kompetencer i værdiskabelse gennem innovative processer under anvendelse af bl.a. centrale elementer fra kurset.

Målbeskrivelse

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:

  • kunne konstruere endelige automater og regulære udtryk for simple sprog og konvertere mellem disse.
  • formulere kontekstfri grammatikker for kontekstfri sprog.
  • kunne transformere mellem et udvalg af dataformater.
  • formulere sig ved hjælp af regulære udtryk og anvende disse til at konstruere scannere til leksikal analyse.
  • afgøre om en grammatik er LL(1) eller LR(1) og justere den, hvis den ikke er, og at kunne konstruere parsere til syntaksanalyse baseret på disse klasser.
  • kunne designe abstrakte syntakstræer og opbygge disse under parsning.
  • kunne anvende astrakte syntakstræer til forskellige formål som f.eks. typecheck af programmeringssprog under anvendelse af symboltabeller.
  • kunne håndtere processen omkring at transformere et abstrakt syntakstræ for et højniveau sprog til et lavniveau sprog.
  • udføre en process indeholdende innovativ informationsprocessering gennem et projekt, hvor eksisterende data ekstraheres, transformeres og kombineres med henblik på værdiskabelse med udgangspunkt i en forretningsmodel.

Indhold

Kurset indeholder følgende faglige hovedområder:

  • regulære udtryk
  • endelige automater
  • kontekstfri grammatikker
  • dataformater og datatransformation
  • LL(1) og LR(1) sprog og grammatikker
  • top-down og bottom-up parsningsteknikker
  • intern repræsentation
  • typecheck
  • oversættelse
  • innovation

Litteratur

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Januar

Udprøvninger

Skriftlig eksamen og projekt med mundtligt forsvar

EKA

N330042102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Tilladt, nærmere beskrivelse af eksamensreglerne vil blive offentliggjort under 'Course Information' på kursets side i BlackBoard.

ECTS-point

10

Uddybende information

Den skriftlige eksamen vægtes højest ved den endelige karakter
Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen.

Vejledende antal undervisningstimer

62 timer per semester

Undervisningsform

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

  • Introfase (forelæsning, holdtimer) - Antal timer: 34 timer
  • træningsfase: Antal timer: 28, heraf eksaminatorie: 28 timer

I introfasen benyttes en modificeret udgave af klassisk forelæsning, hvor fagets grundbegreber og metoder præsenteres, med såvel teori som eksempler baseret på konkrete data. I disse timer er der mulighed for spørgsmål og diskussion. I træningsfasen arbejdes der med opgaver og diskussionsemner, som relaterer sig til indholdet i de forudgående introfasetimer. I disse timer er der mulighed for at arbejde specifikt med særligt vanskelige emner. I studiefasen arbejder de studerende selvstændigt med projekt og relationen til fagets termer. Der er efterfølgende mulighed for at bringe spørgsmål op.

Studiefaseaktiviteter: I studiefasen arbejder de studerende selvstændigt med projekt og relationen til fagets termer. Der er efterfølgende mulighed for at bringe spørgsmål op.

Ansvarlig underviser

Navn E-mail Institut
Kim Skak Larsen kslarsen@imada.sdu.dk

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil Uddannelse Semester Udbuds periode