Heltalsprogrammering, 7,5 hp

Innehåll

Kursen är indelad i två moment.

Moment 1 (6,0 hp): Matematisk teori för heltalsoptimering. 
I momentet ges fördjupade kunskaper om optimering. Särskild vikt läggs vid heltalsprograms egenskaper och tekniker för att lösa dessa. Metoder som behandlas är dynamisk programmering, trädsökning och plansnittning.  Olika familjer av plansnitt studeras och används både för att lösa och ge starkare formuleringar av heltalsproblem. Heuristiker för att hitta bra övre och undre gränser för målfunktionen behandlas, till exempel giriga tekniker samt linjärprograms- eller Lagrangerelaxation. Begreppen konvext hölje och fullständig unimodularitet behandlas. En introduktion till komplexitetsteori ges med exempel på problem i olika komplexitetsklasser samt hur polynomiell reduktion mellan probleminstanser används.

Moment 2 (1,5 hp): Laborationer. 
I momentet används datorstöd för att implementera och tillämpa någon teknik för heltalsoptimering.

Förväntade studieresultat

För godkänd kurs ska studenten kunna

Kunskap och förståelse

• ingående redogöra för teorin för heltalsprogrammering
• redogöra för några heuristiker inom heltalsprogrammering
• ingående redogöra för teorin för plansnitt
• redogöra för och exemplifiera komplexitetsklasserna P, NP, NP-komplett och NP-svår

Färdighet och förmåga

• självständigt lösa heltalsproblem
• tillämpa heuristiker för att begränsa målfunktionen

Värderingsförmåga och förhållningssätt

• bedöma komplexiteten hos heltalsproblem
• välja lämpliga tekniker för att angripa givna heltalsproblem.

Behörighetskrav

För tillträde till kursen krävs 15 hp i programmeringsmetodik och en kurs i linjär algebra samt en kurs i linjär programmering eller motsvarande. 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 och lektioner. Undervisningen på moment 2 bedrivs i form av laborationer och seminarier. 

Examination

Moment 1 examineras genom skriftlig tentamen. Moment 2 examineras genom seminarier och 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 något av 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). Betyg på hel kurs avgörs av betyg på moment 1. För att bli godkänd på hela kursen krävs att samtliga moment är godkända. Betyget sätts först när alla obligatoriska moment är bedömda.

Den som erhållit godkänt betyg på kursen kan ej examineras för högre betyg. För studerande som inte blivit godkända 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 prefekten för institutionen för matematik och matematisk statistik. Examination baserad på denna kursplan garanteras under 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.
 

Övriga föreskrifter

I en examen får denna kurs ej ingå tillsammans med en annan kurs med likartat innehåll, till exempel Optimering 3 (5MA155). Vid osäkerhet bör den studerande rådfråga studierektor i matematik och matematisk statistik.