Moment 1, teoridel, 4.5 högskolepoäng
Kursen behandlar deterministiska och icke deterministiska turingmaskiner som en formell bas för att undersöka algoritmisk komplexitet; formell definition av komplexitetsmått för algoritmiska problem, i synnerhet (N)TIME och (N)SPACE; komplexitetsklasserna L, NL, P, NP, (N)PSPACE och deras förhållande till varandra; reduktion och kompletthet; exempel på reduktioner; viktiga resultat och bevis i samband med kompletthet, i synnerhet P=NP-frågan och Cooks teorem.
Moment 2, laborationsdel, 3 högskolepoäng
Delmomentet utgörs av en laborationskurs med ett antal obligatoriska inlämningsuppgifter
Förväntade studieresultat
Efter avslutad moment 1 ska studenten kunna:
- definiera komplexitetsmåtten (N)TIME och (N)SPACE baserat på (icke)-deterministiska turingmaskiner samt förklara och motivera dessa definitioner
- definiera komplexitetsklasserna L, NL, P, NP, (N)PSPACE och bevisa att L ( NL ( P ( NP ( PSPACE = NPSPACE
- definiera begreppen reduktion och kompletthet samt formulera och bevisa de viktigaste implikationerna i samband med dem, i synnerhet sammanhanget med P=NP-frågan
- beskriva några reduktioner och argumentera för deras korrekthet
- identifiera och förklara viktiga algoritmiska tekniker som används i bevis
Efter avslutat moment 2 ska studenten självständigt kunna
- formalisera icke triviala koncept och bevis
Behörighetskrav
Univ:För tillträde till kursen krävs 60 hp inom huvudområdet datavetenskap eller 2 års avklarade studier, i båda fallen inkluderande Datavetenskapens grunder (5DV037), Datastrukturer och algoritmer (5DV043), Logik för datavetare (5DV007) och Diskret matematik för teknologer (5MA008) eller motsvarande kunskaper.
Engelska A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).
Undervisningens upplägg
Undervisningen bedrivs i form av föreläsningar, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.
Examination
Examinationen sker dels genom skriftlig tentamen (på teoridelen) dels genom ett laborationsmoment. På en skriftlig tentamen sätts något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). På laborationsmomentet ges endast betygen Underkänd (U) eller Godkänd (G). På hela kursen ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). För att bli godkänd på hela kursen krävs att samtliga prov och obligatoriska moment är godkända. Betyget utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla obligatoriska moment är godkända. Den som godkänts i ett prov får ej undergå förnyat prov för högre betyg.
För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle.
En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till styrelsen för Institutionen för datavetenskap.
TILLGODORÄKNANDE
I en examen får denna kurs ej ingå, helt eller delvis, samtidigt med en annan kurs med likartat innehåll. Vid tveksamheter bör den studerande rådfråga studievägledare vid Institutionen för datavetenskap.
Litteratur
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen.
Kontakta aktuell institution.
