DM553: Kompleksitet og beregnelighed

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N330048112, N330048102
Censur: Intern prøve, en bedømmer, Ekstern prøve
Bedømmelse: Bestået/Ikke bestået, 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Bachelor

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

Godkendelsesdato: 02-10-2019


Varighed: 1 semester

Version: Arkiv

Kommentar

15016101(tidligere UVA) er identisk med denne kursusbeskrivelse.
Kurset samlæses med: MM850.

Indgangskrav

Ingen

Faglige forudsætninger

Studerende, der følger kurset, forventes at:

  • Have
    kendskab til basale algoritmer for manipulering af (repræsentationer
    af) talsæt og grafer, samt analyse af algoritmer
  • Have kendskab til basal matematisk argumentation, herunder bevis ved induktion, bevis ved modstrid og logiske udtryk.
  • Have kendskab til brugen af kombinatoriske teknikker indenfor algoritme udvikling.

Formål

Kurset har til formål at sætte den studerende i stand til at 

  • Anvende formalismer for formelle sprog til at formulere f.eks. afgørelsesproblemer præcist.
  • Arbejde med endelige automater, regulære udtryk, stakautomater og kontekstfrie
    grammatikker som et elementer i en algoritmisk løsning af større
    problemer.
  • Afgøre kompleksiteten af nye problemer ud fra kendskab til kompleksiteten af en lang række vigtige eksempler fra kurset.
  • Vurdere om et problem kan løses ved hjælp af  en computer eller om det er uafgørligt.
  • Argumentere for  NP-komplethed af  problemer.
  • Vurdere muligheden for at udvikle en approksimationsalgoritme eller parametericeretalgoritme for et givet optimeringsproblem der vides at være NP-hårdt.
  • Give nedre grænser for kompleksiteten af problemer der ligner dem som studeres i kurset.

Disse
færdigheder er vigtige både når der skal udvikles nye algoritmer til et
givet problem og når man skal vurdere om et givet problem vil kunne
løses (evt. kun approksimativt) ved hjælp af  en algoritme indenfor
rimelig tid.

Kurset bygger oven på den viden, der er erhvervet i
kurserne DM507 Algoritmer og datastrukturer samt DM565 Formelle sprog og dataprocessering,  eller MM541 Kombinatorisk matematik.

Kurset giver et fagligt grundlag for at gennemføre
et bachelorprojekt samt valgfrie kandidatkurser der indeholder et eller
flere af følgende elementer: kompleksitet af algoritmer,
approksimationsalgoritmer og beregnelighed.

Desuden giver kurset,
suppleret med ovennævnte type af kurser, et fagligt grundlag for at
 lave et speciale indenfor algoritmiske og kompleksitetsteoretiske
emner.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

  • Give kompetence til at kunne vurdere kompleksiteten af (afgørelses)problemer.
  • Give viden om beregningsstyrken af forskellige modeller for beregning.
  • Give den studerende evnen til at kunne konstruere stakautomater og kontekstfrie grammatiker til simple sprog.
  • Udstyre
    den studerende med vigtige redskaber til at vise at et givet sprog ikke
    kan genkendes ved hjælp af en endelig automat, stakautomat eller en
    Turing maskine.
  • Give den studerende evnen til at kunne bevise nedre grænser for kompleksiteten af algoritmer til et givet problem.
  •  Udstyre den studerende med vigtige redskaber til at  kunne designe nye approksimationsalgoritmer.
  • Udstyre den studerende med vigtige redskaber til at bevise at et givet afgørelsesproblem er NP-komplet eller uafgørligt.

Målbeskrivelse

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

  • Kunne vurdere kompleksiteten af (afgørelses)problemer.
  • Kunne vurdere  beregningsstyrken af forskellige modeller for beregning.
  • Konstruere stakautomater og kontekstfrie grammatiker til simple sprog.
  • Vise
    at et givet sprog, der ligner dem som er studeret i kurset, ikke kan
    genkendes ved hjælp af en endelig automat, stakautomat eller en Turing
    maskine.
  • Kunne bevise nedre grænser for kompleksiteten af
    algoritmer til et givet problem som i natur  ligner dem der er behandlet
    i kurset.
  • Designe nye approksimationsalgoritmer til et givet problem som i natur  ligner  dem der er behandlet i kurset
  • Kunne  bevise at et givet afgørelsesproblem, som i natur ligner dem der er behandlet i kurset, er NP-komplet eller uafgørligt.
  • Kunne definere fixed parametericeret kompleksitet og forklare en eksampel.
  • Give præcise definitioner samt beviser for ovenstående.

Indhold

Kurset indeholder følgende faglige hovedområder:
  • Endelige automater og stakautomater
  • Kontekstfrie sprog og grammatiker
  • Turing-maskiner
  • Afgørlighed
  • Problem reduktioner
  • Nedre grænser (informationsteoretiske og modstanderargumenter)
  • Kompleksitetsklasserne P og NP
  • Teorien for NP-fuldstændighed
  • Approksimationsalgoritmer
  • Parametericeret kompleksitet

    Litteratur

    Se itslearning for pensumlister og yderligere litteraturhenvisninger.

    Eksamensbestemmelser

    Forudsætningsprøve a)

    Tidsmæssig placering

    Forår

    Udprøvninger

    Skriftlig aflevering

    EKA

    N330048112

    Censur

    Intern prøve, en bedømmer

    Bedømmelse

    Bestået/Ikke bestået

    Identifikation

    Fulde navn og SDU brugernavn

    Sprog

    Følger, som udgangspunkt, undervisningssprog

    Hjælpemidler

    Oplyses på kurset. 

    ECTS-point

    0

    Uddybende information

    Forudsætningsprøven består i at uploade et dokument med ens navn og bekræftigelse af deltagelse i mundtlig eksamen.  Forudsætningsprøven er en forudsætning for deltagelse i eksamenselement a)

    Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen.

    Eksamenselement a)

    Tidsmæssig placering

    Juni

    Forudsætninger

    Type Forudsætningsnavn Forudsætningsfag
    Delprøve Forudsætningsprøve a) N330048101, DM553: Kompleksitet og beregnelighed

    Udprøvninger

    Mundtlig eksamen

    EKA

    N330048102

    Censur

    Ekstern prøve

    Bedømmelse

    7-trinsskala

    Identifikation

    Studiekort

    Sprog

    Følger, som udgangspunkt, undervisningssprog

    Varighed

    30 minutter per studerende og 30 minutter til forberedelse

    Hjælpemidler

    Oplyses på kurset

    ECTS-point

    10

    Uddybende information

    Mundtlig eksamen samt et antal opgavesæt afleveret i løbet af kurset. Karakter baseres på et samlet indtryk af elementerne, som indgår i evaluering. Censor vil have adgang til besvarelserne af opgaverne.

    Reeksamen er en mundtlig eksamen, der bedømmes med ekstern censur og karakter efter 7 trinsskalaen.

    Vejledende antal undervisningstimer

    76 timer per semester

    Undervisningsform

    Undervisningsaktiviteter udmønter sig i en anslået vejledende fordeling af arbejdsindsatsen hos en gennemsnitsstuderende på følgende måde:
    • Introfase (forelæsning, holdtimer) - 38 timer
    • Træningsfase: 38 timer

    I introfasen introduceres og perspektiveres begreber, teorier og modeller.
    I træningsfasen træner de studerende færdigheder og trænger dybere ned i det stof.

     Aktiviteter i studiefasen:

    • Selvstudium af lærebogen og andet undervisningsmateriale
    • Løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne.
    • Skriftlige hjemmeopgaver som en del af eksamen
    • Selvstændig opsamling på intro- og træningsfasen
    • Repetition op til eksamen

    Ansvarlig underviser

    Navn E-mail Institut
    Jørgen Bang-Jensen jbj@imada.sdu.dk Algorithms

    Skemaoplysninger

    Administrationsenhed

    Institut for Matematik og Datalogi (datalogi)

    Team hos Uddannelsesjura & Registratur

    NAT

    Udbudssteder

    Odense

    Anbefalede studieforløb

    Profil Uddannelse Semester Udbuds periode