Kursen behandlar grundläggande byggstenar nödvändiga för konstruktion och analys av algoritmer. Fokus ligger på viktiga designtekniker som divide-and-conquer, greedy methods, dynamisk programmering samt söktekniker som backtracking och branch-and-bound;
kunskaper om beräkningskomplexitet och frågor rörande hanterbarhet (computational tractability) av olika problem;
kunskaper och färdigheter för att utvärdera prestanda för datorprogram (performance evaluation of software)
Förväntade studieresultat
Efter avslutad kurs ska studenten kunna:
Konstruera algoritmer för olika problem baserade på designtekniker som divide-and-conquer, greedy methods, dynamisk programmering, samt söktekniker som backtracking och branch-and-bound.
Utföra formella analyser med hjälp av olika matematiska verktyg.
Skapa programvara för att experimentellt analysera algoritmer samt använda den för att mäta prestation för en algoritms olika uppförande.
Redogöra för grundprinciperna för beräkningskomplexitet och frågor rörande hanterbarhet.
Behörighetskrav
Univ: För tillträde till kursen krävs 60 hp i huvudområdet daravetenskap eller 2 års studier inkluderande, kurserna Envariabelanalys I (5MA009), Envariabelanalys II (5MA011), Diskret matematik (5MA006), Datastrukturer och algoritmer (5DV043), Datavetenskapens grunder (5DV037) och Systemprogrammering (5DV006) eller motsvarande kunskaper
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 genom en eller flera skriftliga tentamina under kursens gång. Dessutom ingår obligatoriska datorlaborationer och uppgifter. Examinationens olika delar poängsätts. Totalt summerar detta till en maximal poängsumma. Normalt krävs att hälften av denna poängsumma uppnås för att kursen ska betraktas som Godkänd.
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.
För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle.
Studerande som två gånger underkänts i prov, har rätt att hos styrelsen för institutionen för datavetenskap begära att annan lärare utses för att sätta betyg på honom/henne. Den som godkänts i ett prov får ej undergå förnyat prov för högre betyg.
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.
