MM850: Kompleksitet og beregnelighed

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 inden for algoritme-udvikling.

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

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 inden for 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 kandidat-kurser, 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 inden for algoritmiske og kompleksitets-teoretiske emner.

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

• Vurdere kompleksiteten af (afgørelses-)problemer.
  
• Vurdere beregningsstyrken af forskellige modeller for beregning.
• Konstruere stak-automater og 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, stak-automat 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 approksimations-algoritmer til et givet problem, som i natur ligner dem, der er behandlet i kurset
• Bevise, at et givet afgørelses-problem, som i natur ligner dem, der er behandlet i kurset, er NP-fuldstændigt eller uafgørligt.
• Definere fixed parameterized kompleksitet og forklare et eksempel.
• Give præcise definitioner samt beviser for ovenstående.
  

Kurset indeholder følgende faglige hovedområder:

• Endelige automater og stak-automater
  
• Regulære sprog og kontekstfrie sprog
• Grammatikker
• Turing-maskiner
• Afgørlighed
• Problem-reduktioner
• Nedre grænser (informations-teoretiske og modstander-argumenter)
• Kompleksitetsklasserne P og NP
• Teorien for NP-fuldstændighed
• Approksimations-algoritmer
• Parametriseret kompleksitet
  

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

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