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ørelses-problemer præcist.
• Arbejde med endelige automater, regulære udtryk, stak-automater og kontekstfrie grammatikker som elementer i en algoritmisk løsning af større problemer.
• Afgøre kompleksiteten af nye problemer ud fra kendskab til kompleksiteten af en 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-fuldstændighed af problemer.
• Vurdere muligheden for at udvikle en approksimations-algoritme eller parametriseret algoritme for et givet optimeringsproblem.
• Give nedre grænser for kompleksiteten af problemer, der ligner dem, som studeres i kurset.

• Vurdere kompleksiteten af (afgørelses)problemer.
• 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.
• 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
• Bevise at et givet afgørelsesproblem, som i natur ligner dem der er behandlet i kurset, er NP-komplet eller uafgørligt.
• Definere fixed parameterized kompleksitet og forklare et eksempel.
• Give præcise definitioner samt beviser for ovenstående.

• Introfase (forelæsning) - 40 timer
  
• Træningsfase: 30 timer
• Studiefase: 180 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 stoffet.

 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ænings-fasen
• Repetition op til eksamen