Engelskt namn: Computational Complexity
Denna kursplan gäller: 2024-09-02 och tillsvidare
Kurskod: 5DV200
Högskolepoäng: 7,5
Utbildningsnivå: Avancerad nivå
Huvudområden och successiv fördjupning:
Datavetenskap: Avancerad nivå, har kurs/er på avancerad nivå som förkunskapskrav
Betygsskala: TH teknisk betygsskala
Ansvarig institution: Institutionen för datavetenskap
Beslutad av: Teknisk-naturvetenskapliga fakultetsnämnden, 2018-10-03
Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden, 2024-02-14
Vissa algoritmer löser ett beräkningsproblem effektivare än andra. En viktig aspekt av datavetarens jobb är att hitta effektiva sätt att lösa ett givet problem. Ibland lyckas man väl med det, ibland inte. Men hur vet man om det i det senare fallet beror på ens egen oförmåga eller ligger i problemets natur, dvs om problemet överhuvud taget går att lösa effektivt? Varje problem har en inneboende beräkningskomplexitet som avgör om och i så fall hur effektivt det kan lösas. Detta leder till en kategorisering av problem i olika klasser med avseende på deras inneboende komplexitet. Att förstå sig på detta är viktigt eftersom det visar vilken effektivitet man rimligen kan förvänta sig, vilket å ena sidan leder till effektivare algoritmer i den utsträckning det är möjligt och å andra sidan förhindrar att energi läggs ner på att försöka åstadkomma det omöjliga.
Kursen behandlar och formaliserar denna inneboende komplexitet hos beräkningsproblem, som resulterar i kategoriseringen av problem i olika komplexitetsklasser, kända och okända samband mellan dessa klasser samt begreppet av fullständiga problem. Följande aspekter behandlas: Formalisering av beräkningskomplexitet (främst med avseende på tid och minnesutrymme) och dess praktiska betydelse, "speedup"-teoremet och den utvidgade Church-Turing-tesen, deterministiska och icke deterministiska komplexitetsklasser (främst (N)TIME(f(n)), (N)SPACE(f(n), P, NP, (N)EXPTIME, L, NL, PSPACE; komplementklasser till dessa) och vad man vet eller inte vet om deras inbördes relation, reduktion av ett problem till ett annat, fullständighet.
Modul 1, Koncept, resultat och bevis, 3 hp, introducerar och diskuterar begrepp, resultat och bevismetoder enligt innehållsbeskrivningen ovan i lärarledda lektioner. Varje lektion är kopplad till ett eller flera avsnitt i kursboken. Lektionen ger en introduktion till innehållet utan att ge sig in på detaljer. Målet är att göra det lättare för studenten att fördjupa sig i respektive avsnitt genom eget arbete.
Modul 2, Fördjupning, reflexion och diskussion, 4,5 hp, består av eget arbete och studentledda diskussioner av materialet. utgörs av att studenten, efter att läraren introducerat ett tema, läser motsvarande avsnitt i kursboken och förbereder en enkel presentation av materialet som kan användas för att diskutera det med klasskamraterna. En sammanfattning av de väsentliga punkterna lämnas in skriftligt inför nästa lektion (ungefär en sida). Inlämningen ska i synnerhet ta upp aspekter studenten inte lyckades förstå eller är osäker på och även tankar kring eventuella övningsuppgifter specificerade av läraren. Studenter blir sedan i slumpmässig ordning utvalda för att presentera materialet baserat på den egna förståelsen och leda diskussionen med resten av klassen. Varje student behöver presentera minst en gång.
Kunskap och förståelse
Efter avslutad kurs ska studenten med matematisk noggrannhet kunna definiera, förklara och diskutera
Färdighet och förmåga
Efter avslutad kurs ska studenten kunna
Värderingsförmåga och förhållningssätt
Efter avslutad kurs ska studenten kunna
Minst 90 hp varav 60 hp datavetenskap. Minst 7,5 hp diskret matematik; 7,5 hp datastrukturer och algoritmer; och 7,5 hp formella språk. Engelska för grundläggande behörighet för högskolestudier.
Undervisningen sker som beskrivet under innehåll och består av både lärarledda lektioner och studentledda presentationer och diskussioner av materialet.
Modul 1 (FSR 1-4, 6-8) examineras genom en skriftlig salstentamen. På denna modul 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).
Modul 2 (FSR 1-8) examineras genom skriftliga inlämningsuppgifter och muntliga presentationer. På Modul 2 ges något av betygen Underkänd (U) eller Godkänd (G).
På kursen i sin helhet 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). Betyget på kursen som helhet bestäms av betyget på Modul 1.
Anpassad examination
Examinator kan besluta om avsteg från kursplanens examinationsform. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Student som har behov av en anpassad examination ska senast 10 dagar innan examinationen begära anpassning hos Institutionen för datavetenskap. Examinator beslutar om anpassad examination som sedan meddelas studenten.
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 och/eller programansvarig för sitt program.
Om kursplanen har upphört att gälla eller kursen slutat erbjudas garanteras en student som någon gång registrerats på kursen minst tre provtillfällen (inklusive ordinarie provtillfälle) enligt denna kursplan under en tid av maximalt två år från det att kursplanen upphört att gälla eller kursen slutat erbjudas.
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen. Kontakta aktuell institution.