FSF3846 Kombinatorisk optimering 7,5 hp

Studier av några fundamentala kombinatoriska optimeringsproblem: algoritmer, komlexitet och tillämpningar.

Algoritmer: Maxflöde-minsnittssatsen. Primal-duala metoder för linjärprogrammering med tillämpning inom flödesproblem. Effektiva algoritmer för maxflödesproblem. Matchning. Minimala spännande träd. Matroider.

Komplexitet: NP-fullständighet, grundläggande begrepp och relevanta exempel.

Tillämpningar: Heuristiska metoder för några intressanta problemklasser

Att studenten ska förvärva en djup förståelse för den matematiska teorin och några praktiska algoritmer för kombinatorisk optimering.

Efter avslutad kurs ska studenten kunna

• Förklara grundläggande begrepp inom beräkningsmässig komplexitet.
• Förklara metoder för fundamentala flödesproblem.
• Förklara metoder för matchning.
• Förklara fundamentala begrepp inom heltalsprogrammering.
• Förklara några viktiga heuristiska metoder.

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 kursen SF2812 Tillämpad linjär optimering, 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.