MM850: Kompleksitet og beregnelighed

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

Kurset bygger oven på den viden, der er erhvervet i kurset MM541 Kombinatorisk matematik.

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

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 approksimations-algoritmer 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-fuldstændigt eller uafgørligt.
Give præcise definitioner samt beviser for ovenstående.

Indhold

Kurset indeholder følgende faglige hovedområder:

Regulære sprog 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 litteraturlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Juni

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

25 minutter per studerende

Hjælpemidler

Ingen hjælpemidler tilladt

ECTS-point

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

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (matematik)

Team hos 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.