DM553: Kompleksitet og beregnelighed

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.

• 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.

• 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.

• 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.

• Introfase (forelæsning) - 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