Diskret modellering, 7,5 hp

Innehåll

Kursen är indelad i två moment.

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 matchningar och handelsresandeproblemet. Därutöver studeras Hamiltoncykler, Eulercykler, tillordningsproblem och stabila matchningar.
Både exakta och heuristiska metoder studeras med avseende på effektivitet. Vidare behandlas artificiell intelligens genom en kort introduktion till genetiska algoritmer, särskilt för handelsresandeproblemet.
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. För att hantera problem där lösning till optimalitet inte är genomförbar implementeras simuleringsmetoder för diskreta modeller. Vidare behandlas metoder från området artificiell intelligens, som genetiska algoritmer och simulated annealing.

Förväntade studieresultat

För godkänd kurs ska den studerande kunna

Kunskap och förståelse

• ingående redogöra för teori för diskret modellering
• ingående redogöra för SAT-formuleringar och deras koppling till komplexitetsteori och problemreduktion

Färdighet och förmåga

• självständigt modellera givna problemsituationer med en heltals-, SAT-och grafformulering
• självständigt genomföra 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 90 hp inkluderande 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 omdömena 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 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). 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. Via frivilliga extrauppgifter på laborationerna finns möjlighet att erhålla bonuspoäng som kan höja ett godkänt kursbetyg. Bonuspoängen gäller endast vid kurstillfällets två första tentamenstillfällen.

Avsteg från kursplanens examinationsform kan göras för en student som har beslut om pedagogiskt stöd på grund av funktionsnedsättning. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Efter begäran av studenten ska kursansvarig lärare, i samråd med examinator, skyndsamt besluta om anpassad examinationsform. Beslutet ska sedan meddelas studenten.

Den som erhållit betyget godkänt på kursen kan ej examineras 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 prefekten vid 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. Vid osäkerhet bör den studerande rådfråga studierektorn i matematik och matematisk statistik.