Heltalsprogrammering, 7,5 hp

Innehåll

Kursen är indelad i två moduler

Modul 1 (6,0 hp): Matematisk teori för heltalsoptimering. 
I modulen 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

Modul 2 (1,5 hp): Laborationer. 
I modulen 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 heuristiker inom heltalsprogrammering
• ingående redogöra för teorin för plansnitt
• förklara och exemplifiera begreppet komplexitetsklass

Färdighet och förmåga

• självständigt lösa heltalsproblem
• använda datorstöd för att implementera och tillämpa tekniker för heltalsoptimering
• skriftligt kommuniera frågeställningar, metod och resultat

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

• välja lämpliga tekniker för att angripa givna heltalsproblem.
• kritiskt tillämpa heuristiker för att begränsa målfunktionen

Behörighetskrav

För tillträde till kursen krävs 90 hp inkluderande 15 hp i programmeringsmetodik och en kurs i linjär algebra samt en kurs i linjär programmering eller motsvarande. Engelska och svenska för grundläggande behörighet för högskolestudier.

Undervisningens upplägg

Undervisningen på modul 1 bedrivs i form av föreläsningar och lektioner. Undervisningen på modul 2 bedrivs i form handledning av laborationer

Examination

Modul 1 examineras genom skriftlig tentamen. Modul 2 examineras genom skriftliga laborationsrapporter. På modul 1 sätts något av omdömena Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). På modul 2 sätts något av omdömena 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 omdömet på modul 1. För att bli godkänd på hela kursen krävs att samtliga moduler är godkända. Betyget sätts först när alla obligatoriska moduler ä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. Kursen kan ingå i en examen som en kurs i huvudområdet beräkningsteknik.