FSF3843 Heltalsprogrammering - praktiska algoritmer 7,5 hp

Kursen behandlar teori och algoritmer för linjära heltalsprogrammeringsproblem och inkluderar teori för giltiga olikheter, dualitet och relaxering, generella algorimer och specialiserade metoder. Dessutom ingår områden som modellformulering, linjärprogrammering, beräkningsmässig komplexitet och polyederteori på ett översiktligt plan.

Att studenten ska förvärva en djup förståelse för den matematiska teorin och de praktiska algoritmerna för heltalsprogrammering.

Efter avslutad kurs ska studenten kunna

• Definiera grundläggande begrepp inom polyederteori
• Ange olika sätt att definiera giltiga olikheter
• Förklara generella metoder för att lösa heltalsprogrammeringsproblem.
• Förklara några specialiserade metoder för heltalsprogrammering.
• Förklara grundläggande begrepp i beräkningsmässig komplexitet.

Civilingenjörs- eller Masterexamen med minst 30 hp inom matematik (en- och flervariabelanalys, linjär algebra, differentialekvationer och transformer) samt minst 6 hp inom matematisk statistik, 6 hp inom numerisk analys och 6 hp inom optimeringslära.

Lämpliga förkunskaper är kurserna SF2812 Tillämpad linjär optimering och SF2520 Tillämpad numerisk analys, eller motsvarande förkunskaper.

Annonseras vid kursstart.

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

• INL1 - Inlämningsuppgift, 7,5 hp, betygsskala: P, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Examination sker genom hemuppgifter och en muntlig sluttentamen.

Hemuppgifter, Muntlig slutexamen.

Anders Forsgren

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.