DM553: Kompleksitet og beregnelighed (10 ECTS)
STADS: 15016101
Niveau
Bachelorkursus
Undervisningsperiode
Kurset er placeret i forårssemesteret.
Ansvarlige undervisere
Email: jbj@imada.sdu.dk
Skemaoplysninger
Hold |
Type |
Dag |
Tidsrum |
Lokale |
Uger |
Kommentar |
Fælles |
I |
Mandag |
10-12 |
U156 |
9 |
|
Fælles |
I |
Mandag |
10-12 |
U151 |
13 |
|
Fælles |
I |
Mandag |
10-12 |
U154 |
14 |
|
Fælles |
I |
Mandag |
12-14 |
U155 |
17 |
|
Fælles |
I |
Tirsdag |
12-14 |
U154 |
6-7,9-13,16,18-20 |
|
Fælles |
I |
Onsdag |
08-10 |
U155 |
5-6,8 |
|
Fælles |
I |
Onsdag |
08-10 |
U154 |
17 |
|
Fælles |
I |
Fredag |
10-12 |
U153 |
5 |
|
H1 |
TE |
Tirsdag |
12-14 |
U154 |
14,21 |
|
H1 |
TE |
Onsdag |
16-18 |
U154 |
12 |
|
H1 |
TE |
Onsdag |
08-10 |
U154 |
16 |
|
H1 |
TE |
Onsdag |
12-14 |
U154 |
21 |
|
H1 |
TE |
Torsdag |
08-10 |
U154 |
5-8,10-12,14,17-20 |
|
H1 |
TE |
Torsdag |
14-16 |
U155 |
9 |
|
H1 |
TE |
Torsdag |
10-12 |
U154 |
16 |
|
H1 |
TE |
Fredag |
14-16 |
U154 |
7 |
|
Vis hele skemaet
Vis personligt skema for dette kursus.
Kommentar:
Ubegrænset deltagerantal.
Indgangskrav:
Ingen
Faglige forudsætninger:
Studerende, der følger kurset, forventes at:
- Have kendskab til grundlæggende datastrukturer
- Have kendskab til basale algoritmer for manipulering af (repræsentationer af) talsæt og grafer, samt implementering af sådanne i et imperativt programmeringssprog
- Have kendskab til basal matematisk argumentation, herunder bevis ved induktion, bevis ved modstrid og logiske udtryk.
- Have kendskab til brugen af kombinatoriske samt probabilistiske teknikker indenfor algoritmeudvikling.
FormålKurset 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.
- Opskrive 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 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 kurserne DM507 Algoritmer og datastrukturer samt DM551 Algoritmer og sandsynlighed
Kurset giver et fagligt grundlag for at gennemføre et bachelorprojekt samt 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.
I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:
- 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 endelige automater og regulære udtryk for simple sprog
- 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.
MålbeskrivelseFor 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 endelige automater og regulære udtryk for simple sprog
- 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.
IndholdKurset 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
LitteraturMeddeles ved kursets start.
Kursets hjemmeside
Dette kursus benytter
e-learn (blackboard).
Forudsætningsprøver
Ingen
Eksamen- og censurform:
- Et opgavesæt som skal løses selvstændigt og tæller som en del af den endelige eksamen a).
- To opgavesæt som må laves i grupper på op til 3 og tæller som en del af den endelige eksamen a).
- Mundtlig eksamen. Karakteren gives ud fra et samlet indtryk af de tre opgaver samt den mundtlige eksamen. Censor vil have adgang til at se besvarelserne af opgaverne. Ekstern censur, 7-trinsskala. (10 ECTS). (15016102).
Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 38 timer
Træningsfase: 38 timer, heraf:
- Eksaminatorie: 38 timer
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
UndervisningsformI 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.
Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.
Bemærkninger
Kurset kan ikke følges af studerende, der har bestået DM508.
Kursustilmelding
Se tilmeldingsfrister.
Pris for åben uddannelse
Se priser for enkeltkurser.
Denne kursusbeskrivelse var gyldig fra 1. februar 2017 til 31. januar 2018.