Kursplan - Beräkningskomplexitet
Omfattning
7.5 hp
Kurskod
MAA513
Giltig från
Hösttermin 2020
Utbildningsnivå
Avancerad nivå
Successiv fördjupning
A1N (Avancerad nivå, har endast kurs/er på grundnivå som förkunskapskrav).
Huvudområde(n)
Matematik/Tillämpad matematik
Akademi
Akademin för utbildning, kultur och kommunikation
Fastställd
2019-12-09
Litteraturlistor
Kurslitteraturen är preliminär till 8 veckor innan kursstart. Kurslitteratur kan vara giltig över flera terminer.
-
Böcker
The nature of computation
Oxford : Oxford University Press, 2011 - 985 s.
ISBN: 9780199233212 LIBRIS-ID: 11354166
Syfte
Kursen syftar till att ge studenten möjlighet att tillägna sig grundläggande kunskaper om teorin för beräkningskomplexitet och dess tillämpningar.
Lärandemål
Efter avklarad kurs ska studenten kunna
1. definiera komplexitetsklasserna P, NP, PSPACE, BPP och BQP och ange hur de är relaterade
2. redogöra för några centrala NP-svåra problem, som till exempel handelsresandeproblemet och 3-SAT, samt några problem i P
3. genomföra enklare reduktionsbevis för att visa att ett problem är NP-svårt
4. beskriva approximationsalgoritmer för vissa NP-svåra problem
5. förklara förväntade användningsområden och begränsningar av kvantdatorer
Innehåll
- Turingmaskiner, formella språk, booleska kretsar
- Ordonotation
- Komplexitetsklasser: P, NP, PSPACE, BPP, BQP
- NP-svåra problem, reduktioner
- Approximationsalgoritmer och approximerbarhet
- Kvantalgoritmer, begränsningar av kvantdatorer
- Tillämpningar inom optimering, maskininlärning, dataanalys, matematisk bevisföring
Särskild behörighet
Diskret matematik, 7,5 hp , Sannolikhetslära, 7,5 hp och Programmering 7,5 hp, eller motsvarande. Dessutom krävs Svenska B/Svenska 3 samt Engelska A/Engelska 6. I de fall kursen ges på engelska görs undantag från kravet på Svenska B/Svenska 3.
Examination
TEN1, salstentamen, 7,5 hp, individuell skriftlig tentamen avseende lärandemål 1-5, betyg Underkänd (U), 3, 4 eller 5.
En student som har ett intyg från MDU avseende sin funktionsnedsättning har möjlighet att anmäla önskemål om anpassning vid salstentamina eller annan examinationsform i enlighet med Regler och anvisningar för examination på grundnivå och avancerad nivå vid Mälardalens högskola (2020/1655). Det är examinator som, utifrån det intyg som utfärdats, beslutar om eventuell anpassning och i så fall vilken anpassning som ska gälla.
Misstankar om vilseledande vid examination (fusk) anmäls, enligt högskoleförordningen, till universitetets rektor och prövas av universitetets disciplinnämnd. Om disciplinnämnden anser att en student gjort sig skyldig till en disciplinförseelse fattar nämnden beslut om en disciplinär åtgärd, vilket är varning eller avstängning.
Betyg
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd