Kursplan fastställd 2021-02-26 av programansvarig (eller motsvarande).
Kursöversikt
- Engelskt namnDiscrete optimization
- KurskodTDA206
- Omfattning7,5 Högskolepoäng
- ÄgareMPALG
- UtbildningsnivåAvancerad nivå
- HuvudområdeDatateknik, Informationsteknik
- InstitutionDATA- OCH INFORMATIONSTEKNIK
- BetygsskalaTH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd
Kurstillfälle 1
- Undervisningsspråk Engelska
- Anmälningskod 02130
- Max antal deltagare60 (minst 10% av platserna reserveras för utbytesstudenter)
- Blockschema
- Sökbar för utbytesstudenterJa
Poängfördelning
Modul | LP1 | LP2 | LP3 | LP4 | Sommar | Ej LP | Tentamensdatum |
|---|---|---|---|---|---|---|---|
| 0101 Tentamen 7,5 hp Betygsskala: TH | 0 hp | 0 hp | 7,5 hp | 0 hp | 0 hp | 0 hp |
|
I program
- MPALG - DATAVETENSKAP - ALGORITMER, PROGRAMSPRÅK OCH LOGIK, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
- MPCAS - KOMPLEXA ADAPTIVA SYSTEM, MASTERPROGRAM, Årskurs 1 (valbar)
- MPCSN - DATORER, NÄTVERK OCH SYSTEM, MASTERPROGRAM, Årskurs 1 (valbar)
- MPSYS - SYSTEMTEKNIK, REGLERTEKNIK OCH MEKATRONIK, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
Examinator
Devdatt Dubhashi- Professor, Data Science och AI, Data- och informationsteknik
Behörighet
Grundläggande behörighet för avancerad nivåSökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.
Särskild behörighet
Engelska 6Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.
Kursspecifika förkunskaper
Matematik (inklusive diskret matematik och linjär algebra), programmering, algoritmer och / eller datastrukturer.Syfte
Kursen behandlar optimeringsproblem i diskreta strukturer såväl i teori som praktik. Det finns starka kopplingar till optimeringsteori (linjär optimering), datavetenskap (algoritmer och komplexitet), och operationsanalys. Optimeringsproblem uppstår i många olika sammanhang, exempelvis transportlogistik, telekommunikation, industriell planering, ekonomi, bioinformatik, hårdvarudesign och kryptologi. En karaktäristisk egenskap hos sådana problem är att de är svåra att lösa. Kursen syftar till att utveckla förmågan att modellera verkliga problem och att använda matematiska och algoritmiska verktyg för att lösa dem, optimalt eller heuristiskt.Lärandemål (efter fullgjord kurs ska studenten kunna)
- Identifiera optimeringsproblem inom olika tillämpningsområden,- Formulera dem i exakta matematiska modeller som representerar det väsentliga av de verkliga problemen, men fortfarande hanterbarbara genom beräkningsmetoder,
- Bedöma vilka problemklass ett givet problem tillhör,
- Tillämpa linjär optimering, relaterade generiska metoder, och ytterligare heuristik, till beräkningsproblem,
- Förklara geometriska egenskaper av linjär optimering,
- Duala optimeringsproblem och användning av duala former för att bestämma gränser,
- Arbeta med den vetenskapliga litteraturen inom området.
Innehåll
Modellering, (heltal) linjär optimering och deras geometriska egenskaper, dualitet i optimering, branch-and-bound och annan heuristik, några speciella grafalgoritmerOrganisation
Föreläsningar och inlämningsuppgifter.Litteratur
Se separat litteraturlista.Examination inklusive obligatoriska moment
Skriftlig tentamen.Kursens examinator får examinera enstaka studenter på annat sätt än vad som anges ovan om särskilda skäl föreligger, till exempel om en student har ett beslut från Chalmers om pedagogiskt stöd på grund av funktionsnedsättning.