Text

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.

    • Beslutsdatum: 2021-02-01
    • Senaste uppdatering: 2021-02-01

    Böcker

    Moore, Cristopher; Mertens, Stephan

    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.

Handbok under studietiden

Betyg

Ges något av betygen 5, 4, 3