Optimering 3, 7,5 hp

Innehåll

Kursen är indelad i två moment.
 
Moment 1 (6,0 hp): Matematisk teori för heltalsoptimering. I momentet behandlas den generella teorin för heltalsoptimering. Särskild vikt läggs vid heltalsprograms egenskaper och tekniker för att lösa dessa. Metoder som behandlas är plansnittning, trädsökning och även dynamisk programmering. Olika familjer av plansnitt studeras och de används i kursen 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

• redogöra för några heuristiker inom heltalsoptimering
• redogöra för teorin för plansnitt
• redogöra för och exemplifiera komplexitetsklasserna P, NP, NPC och NP-svår

Färdighet och förmåga

• tillämpa trädsöknings- och plansnittningsmetoder
• tillämpa heuristiker för att begränsa målfunktionen
• genomföra enklare reduktioner mellan olika problem
• med datorstöd angripa heltalsproblem med tekniker som behandlas på kursen

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

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

Behörighetskrav

För tillträde till kursen krävs kursen Optimering 1, 7,5h hp alternativt Operationsanalys 1, 7,5 hp samt Datastrukturer och algoritmer, 7,5 hp eller motsvarande kunskaper. Engelska 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 lektionsövningar.  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 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). På moment 2 ges endast betygen Underkänd (U) eller Godkänd (G). På hela kursen ges något av betygen betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). Betyg för hel kurs utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla delar är bedömda.

Den som godkänts i prov får ej undergå förnyat prov för högre betyg. För studerande som inte blivit godkänd 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 prefekt 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.

Övriga föreskrifter

I en examen får denna kurs ej ingå tillsammans med en annan kurs med likartat innehåll. Vid osäkerhet bör den studerande rådfråga studierektorn i matematik och matematisk statistik.