Diskret optimering

Kursen kan ingå i följande program:

1. Computer Science, masterprogram (N2COS)
2. Applied Data Science, masterprogram (N2ADS)
3. Software Engineering and Management, masterprogram (N2SOF)
4. Datavetenskapligt program (N1COS)
5. Matematiska vetenskaper, masterprogram (N2MAT)

• 7,5 hp grundkurs i programmering, Python, Java eller liknande
• 7,5 hp grundkurs i matematisk analys
• 7,5 hp grundkurs i linjär algebra

Följande kunskapsnivå i Engelska krävs: Engelska 6/Engelska nivå 2 eller motsvarande från ett erkänt internationellt test, t.ex. TOEFL, IELTS.

Kursen ger en introduktion till hur man kan använda linjär programmering (LP) och linjär heltals programmering (ILP) för att lösa olika optimeringsproblem. Under kursens gång kommer följande att studeras: Simplexmetoden för att lösa LP-problem. LP-relaxeringar av ILP-problem för att få approximativa lösningar. LP-dualitet och hur det kan användas för att designa approximativa lösningar. Vektorprogrammering för att modellera diskreta optimeringsproblem och hur dem kan relaxeras till semi-definita program (SDP).

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• Definiera vad ett linjär program (LP) samt linjärt heltals program (ILP) är.
• Beskriva geometrin av ett LP genom grafisk visualisering.
• Beskriva förhållandet mellan ett ILP och dess LP relaxering.

Färdigheter och förmåga

• Formulera ett kontinuerligt optimeringsproblem som ett LP-problem.
• Formulera ett diskret problem som ett ILP-problem, relaxera det till ett LP-problem och få en approximativ diskret lösning ifrån den optimala LP-lösningen.
• Använda simplex-metoden för att lösa LP-problem.
• Formulera dualen till ett LP-problem och relatera det till original problemet.
• Använd LP-dualitet för att designa optimeringsalgoritmer.
• Formulera ett diskret optimeringsproblem som ett vektorprogram och relaxera det till ett SDP-problem. Gå från lösningen av SDP-problemet till en diskret lösning för ursprungsproblemet.

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

• Förstå vilket typ av optimeringsproblem ett givet problem kan bli modellerat som.
• Bedöma vilka optimeringsalgoritmer som är effektiva för ett givet problem.

Föreläsningar två gånger i veckan och övningssessioner.

Undervisningsspråk: engelska

Kursen examineras med en skriftlig tentamen (uppgifter kan användas för bonuspoäng).

Om en student som har underkänts två gånger på samma examinerande moment önskar byta examinator inför nästa examinationstillfälle ska en sådan begäran bifallas om det inte finns särskilda skäl däremot (6 kap. 22 § HF).

Om en student har fått besked om pedagogiskt stöd från Göteborgs universitet med rekommendation om anpassad examination och/eller anpassad examinationsform kan examinator, i det fall det är förenligt med kursens lärandemål och förutsatt att inte orimliga resurser krävs, besluta att bevilja studenten anpassad examination och/eller anpassad examinationsform.

Om en kurs har avvecklats eller genomgått en större förändring ska studenten erbjudas minst två examinationstillfällen, utöver ordinarie examinationstillfälle. Dessa tillfällen fördelas under en tid av minst ett år, dock som längst två år efter det att kursen avvecklats/förändrats. Vad gäller praktik och verksamhetsförlagd utbildning (VFU) gäller motsvarande, men med begränsning till endast ett ytterligare examinationstillfälle.

Om en student har fått besked om att denne uppfyller kraven för att vara student vid Riksidrottsuniversitetet (RIU-student) har examinator rätt att besluta om anpassning vid examination, om detta görs i enlighet med Lokala regler gällande RIU-studenter vid Göteborgs universitet

Delkurser

1. Skriftlig salstentamen, 7,5 hp
   Betygsskala: Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U)

För att få godkänt på kursen måste samtliga obligatoriska moment vara godkända. För att få ett högre betyg än godkänt så krävs ett högre viktat genomsnitt på de obligatoriska momenten.

Kursen utvärderas genom möten, både under och efter kursen, mellan lärare och studentrepresentanter. Ett anonymt skriftligt frågeformulär skickas även ut till studenterna efter kursens slut. Resultaten av utvärderingarna används för att förbättra kursinnehållet och som indikation till vilka delar som skulle kunna läggas till, tas bort, förbättras eller ändras.

Kursen är samläst med Chalmers.

Kursen ersätter kursen DIT370, 7,5 hp. Den här kursen kan inte ingå i en examen som innehåller DIT370. Den kan inte heller ingå i en examen som bygger på en annan examen där DIT370 ingår.