В мае я рассказал на Codeforces о запуске новой специализации по структурам данных и алгоритмам на Coursera, а в сентябре в рамках этой специализации запустился Курс по продвинутым алгоритмам и теории сложности, и о нем хочется рассказать поподробнее.
Темы курса: 1. Потоки в сетях (алгоритмы Форда-Фалкерсона и Эдмондса-Карпа). 2. Линейное программирование (симплекс-метод). 3. NP-полнота (теория, сведения, решение NP-полных задач SAT-solver'ами). 4. Методы борьбы с NP-полнотой (оптимизации полного перебора, решаемые частные случаи, приближенные алгоритмы).
Задачи для этого курса готовили ifsmirnov, ilyakor, Michael, Perlik, romanandreev, Zlobober и Павел Мельничук.