• A
• A
• A
• АБB
• АБB
• АБB
• А
• А
• А
• А
• А
Обычная версия сайта
Аспирантура 2019/2020

## Дискретная оптимизация

Статус: Курс по выбору
Направление: 09.06.01. Информатика и вычислительная техника
Когда читается: 2-й курс, 1 семестр
Формат изучения: Full time
Преподаватели: Боду Лоран
Язык: английский
Кредиты: 4

### Course Syllabus

#### Abstract

This course aims to present methods commonly used when it comes to optimize a function on some discrete space. After a brief introduction, we shall approach the Linear Programming as a all-around tool to model a wide set of problems. We also focus on Dynamic Programming as a technique for designing efficient algorithms. Integer Programming revolves around specific techniques when Linear Program require integrality of variables. Finally we'll consider some usual heuristics when nothing works. #### Learning Objectives

• To give students basic and advanced knowledge on methods used for solving discrete (combinatorial) optimization problems. The course provides both a theoretical understanding and a practical approach of these methods. #### Expected Learning Outcomes

• Understanding of the purpose.
• Ability to model problem and interpret results.
• Ability to design adequate algorithms.
• Full understanding of algorithms and implications.
• Ability to model hard problems.
• Ability to approach problems out of reach by previous methods.
• Understanding the algorithms and its implications. #### Course Contents

• Introduction to discrete optimization
Examples of problems, computational complexity, naive algorithms.
• Linear Programming
Theoretical approach, choosing appropriate model, what can be learned from LP.
• Dynamic Programming
Rules of dynamic programming, examples.
• Milestone problem: max-flow/min-cut
Thorough study of max flow in graphs. Variations (flow of minimum cost). Unexpected use of this problem.
• Integer and Mixed Integer Programming
Linear relaxation, Lagrangian relaxation, Branch-and-Bound.
• Heuristics
Local search, genetic algorithms, etc. Examples for famous problems.
• Milestone problem: Maximum matching
Blossom algorithm (J. Edmonds). Application. #### Assessment Elements

• Project
A small project with a paper writing assignment and oral presentation.
• Exam #### Interim Assessment

• Interim assessment (1 semester)
0.6 * Exam + 0.4 * Project #### Recommended Core Bibliography

• Diestel R. Graph Theory. – Springer, 2017. – 428 pp.