MM850: Kompleksitet og beregnelighed

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N310053112, N310053102
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: Kandidat

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

Godkendelsesdato: 31-10-2023


Varighed: 1 semester

Version: Arkiv

Kommentar

Kurset samlæses med: DM553: Kompleksitet og beregnelighed (10 ECTS)
Kurset er valgfrit for følgende studieordninger: Matematik, Matematik-Økonomi, Anvendt matematik

Indgangskrav

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

Faglige forudsætninger

Studerende, der følger kurset, forventes at:

  • Have kenskab 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 algoritmeudvikling.

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 element 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 kurset MM541 Kombinatorisk matematik.
Kurset giver et fagligt grundlag for at gennemføre 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.

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
  • Regulære sprog og kontekstfrie sprog
  • 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

N310053112

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)


Eksamenselement a)

Tidsmæssig placering

Juni

Forudsætninger

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

Udprøvninger

Mundtlig eksamen

EKA

N310053102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

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

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

  • Introfase (forelæsning) - 40 timer
  • træningsfase: 30 timer, heraf 30 timers eksaminatorier

Bemærk, at en del af introtimerne vil blive afholdt som videoforelæsninger som de studerende ser og gør sig klar til at diskutere de væsentligste pointer ved de fysiske forelæsninger.

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
Lene Monrad Favrholdt lenem@imada.sdu.dk Institut for Matematik og Datalogi

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (matematik)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil Uddannelse Semester Udbuds periode

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.