Moment 1 (4,5 hp): Teori. Momentet behandlar teorin för diskret modellering, från problemställning och val av modell, via specifik modellformulering och implementation, till utvärdering av modellens lämplighet och effektivitet.
Momentet inleds med allmän teori för uppställande av heltalsprogram utifrån en problembeskrivning, och allmän teori för SAT-formuleringar av optimerings- och beslutsproblem. I anslutning till detta behandlas komplexitetsteori och den generella teorin för polynomiell reduktion från ett problem till ett annat. Heltalsformuleringar och SAT-formuleringar sätts sedan i relation till olika klasser av grafmodeller, särskilt flödesproblem, matchningar, kortaste vägen, graffärgning, och handelsresandeproblemet. Både exakta och heuristiska metoder studeras med avseende på effektivitet. Därefter studeras storskaliga konkreta exempel på tillämpad diskret modellering, och en introduktion till informationssökning inom området diskret modellering ges. Teorimomentet avslutas med en introduktion till simulering med hjälp av slumpmässiga scenarier.
Moment 2 (3 hp): Laborationer. Momentet behandlar implementation av diskreta modeller, och jämförelser mellan olika formuleringar vad gäller deras beräkningsmässiga effektivitet. Vidare implementeras simuleringsmetoder för diskreta modeller.
Förväntade studieresultat
För godkänd kurs ska den studerande kunna
Kunskap och förståelse
redogöra för teori för diskret modellering
redogöra för SAT-formuleringar och deras koppling till komplexitetsteori och problemreduktion
Färdighet och förmåga
från en given problemsituation ställa upp en heltalsmodell och en SAT-modell
ställa upp en grafmodell för vissa problemtyper
genomföra enklare reduktioner från en problemtyp till en annan
muntligen och skriftligen redogöra för modellering av ett konkret problem
generera scenarier för testning av modeller
Värderingsförmåga och förhållningssätt
bedöma rimlighet och effektivitet för olika modellformuleringar
bedöma exakt lösbarhet och möjlighet att uppskatta lösningar för olika instanser av de typer av problem som behandlas under kursen
självständigt söka litteratur och avgöra dess relevans och nytta
Behörighetskrav
För tillträde till kursen krävs 15 hp i programmeringsmetodik, en kurs i linjär programmering, en kurs i heltalsprogrammering på avancerad nivå samt en grundkurs i matematisk statistik eller motsvarande kunskaper. Engelska 5/A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).
Undervisningens upplägg
Undervisningen på moment 1 bedrivs i form av föreläsningar, lektionsövningar och seminarier. Undervisningen på moment 2 bedrivs i form av introducerande föreläsningar, handledning och seminariebehandling av rapportutkast.
Examination
Moment 1 examineras genom muntliga redogörelser för modellering av givna problemställningar, samt skriftlig tentamen för modelleringsteori. Moment 2 examineras genom skriftliga laborationsrapporter. På moment 1 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å moment 2 sätts 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 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 bedömda. Studerande som godkänts i prov får ej undergå förnyat prov för att få ett högre betyg.
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 prefekten för institutionen för matematik och matematisk statistik. Examination baserad på denna kursplan garanteras under minst två år efter studentens förstagångsregistrering på kursen.
Tillgodoräknande Student har rätt att få prövat om tidigare utbildning eller motsvarande kunskaper och färdigheter förvärvade i yrkesverksamhet kan tillgodoräknas för motsvarande utbildning vid Umeå universitet. Ansökan om tillgodoräknande skickas in till Studentcentrum/Examina. Mer information om tillgodoräknande finns på Umeå universitets studentwebb, www.student.umu.se, och i högskoleförordningen (6 kap). Ett avslag på ansökan om tillgodoräknande kan överklagas (Högskoleförordningen 12 kap) till Överklagandenämnden för högskolan. Detta gäller såväl om hela som delar av ansökan om tillgodoräknande avslås.
Litteratur
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen.
Kontakta aktuell institution.
