DM553: Kompleksitet og beregnelighed

Studienævn for naturvidenskabelige IT-uddannelser

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N330048102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Bachelor

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

Godkendelsesdato: 09-01-2026


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

Kurset samlæses med: MM850: Kompleksitet og beregnelighed (10 ECTS)

Indgangskrav

Kurset kan ikke følges af studerende, der har bestået MM850.

Faglige forudsætninger

Studerende, der følger kurset, forventes at have kendskab til følgende (eks. fra DM578):
  • basale algoritmer for manipulering af (repræsentationer af) talsæt og grafer, samt analyse af algoritmer,
  • basal matematisk argumentation, herunder bevis ved induktion, bevis ved modstrid og logiske udtryk og
  • 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ørelses-problemer præcist.
  • Arbejde med endelige automater, regulære udtryk og kontekstfrie grammatikker som elementer i en algoritmisk løsning af større problemer.
  • Vurdere, om et problem kan løses ved hjælp af en computer, eller om det er uafgørligt.
  • Argumentere for NP-fuldstændighed af problemer.
  • Vurdere muligheden for at udvikle en approksimations-algoritme eller parametriseret algoritme for et givet optimeringsproblem.
Disse kompetencer 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 inden for rimelig tid.

Målbeskrivelse

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:
  • Vurdere kompleksiteten af afgørelsesproblemer.
  • Vurdere beregningsstyrken af forskellige modeller for beregning.
  • Konstruere endelige automater, regulære udtryk eller kontekstfrie grammatikker 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 eller en Turing maskine.
  • Designe nye approksimationsalgoritmer til et givet problem som i natur ligner dem der er behandlet i kurset
  • Bevise at et givet afgørelsesproblem, som i natur ligner dem der er behandlet i kurset, er NP-komplet eller uafgørligt.
  • Give præcise definitioner samt beviser for ovenstående.

Indhold

Kurset indeholder følgende faglige hovedområder:
  • Regulære og kontekstfrie sprog
  • Turing-maskiner
  • Afgørlighed
  • Problem-reduktioner
  • Kompleksitetsklasserne P og NP
  • Teorien for NP-fuldstændighed
  • Approksimations-algoritmer
  • Eksakte algoritmer

    Litteratur

    Se itslearning for litteraturhenvisninger.

    Eksamensbestemmelser

    Eksamenselement a)

    Tidsmæssig placering

    Juni

    Udprøvninger

    Mundtlig eksamen

    EKA

    N330048102

    Censur

    Ekstern prøve

    Bedømmelse

    7-trinsskala

    Identifikation

    Fulde navn og SDU brugernavn

    Sprog

    Følger, som udgangspunkt, undervisningssprog

    Varighed

    25 minutter per studerende uden forberedelse

    Hjælpemidler

    Ingen hjælpemidler tilladt

    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

    72 timer per semester

    Undervisningsform

    Skemalagte undervisningstimer:
    Antal undervisningstimer i alt: 72
    Heraf:
    Fællestimer i klasselokale/auditorium: 36
    Holdtimer i klasselokale: 36

    I fællestimerne introduceres nyt stof. Dette vil have form af forelæsning, afbrudt af diskussion og spørgsmål (både fra underviser til studerende og omvendt). I holdtimerne diskuteres opgaver, som de studerende har forsøgt at løse på forhånd.

    Andre planlagte undervisningsaktiviteter: 
    • 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å fællestimer
    • Repetition op til eksamen

    Ansvarlig underviser

    Navn E-mail Institut
    Lene Monrad Favrholdt lenem@imada.sdu.dk Institut for Matematik og Datalogi

    Skemaoplysninger

    Administrationsenhed

    Institut for Matematik og Datalogi (datalogi)

    Team hos Registratur

    NAT

    Udbudssteder

    Odense

    Anbefalede studieforløb

    Overgangsordninger

    Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.
    Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
    Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.