В мае я рассказал на Codeforces о запуске новой специализации по структурам данных и алгоритмам на Coursera, а в сентябре в рамках этой специализации запустился Курс по продвинутым алгоритмам и теории сложности, и о нем хочется рассказать поподробнее.
Темы курса: 1. Потоки в сетях (алгоритмы Форда-Фалкерсона и Эдмондса-Карпа). 2. Линейное программирование (симплекс-метод). 3. NP-полнота (теория, сведения, решение NP-полных задач SAT-solver'ами). 4. Методы борьбы с NP-полнотой (оптимизации полного перебора, решаемые частные случаи, приближенные алгоритмы).
Задачи для этого курса готовили ifsmirnov, ilyakor, Michael, Perlik, romanandreev, Zlobober и Павел Мельничук.
Потоки и те алгоритмы для их нахождения, которые есть в специализации, наверно для многих участников Codeforces не звучат как продвинутая тема. Зато это точно популярная тема, задачи на поток сегодня есть почти в каждом контесте, и знать базовые алгоритмы для competitive programming просто необходимо. В подтверждение этому одна из задач на программирование, которые идут в конце темы: Google Code Jam любезно разрешил нам использовать условие задачи Stock Charts с GCJ 2009 R2 (тесты и решения к ней готовил ilyakor). К тому же, на практике оказывается, что в 99% случаев именно алгоритмом Форда-Фалкерсона нужно все решать, потому что и писать быстро, и работает на практике быстро, кроме случаев, когда авторы специально заморочились и подготовили тесты против этого алгоритма — это нетривиально, и мало кто этим занимается.
Линейное программирование никогда не было темой спортивного программирования...вплоть до финала ACM ICPC 2016-го года, когда задача I своим условием просто кричала "напиши Дейкстру и симплекс-метод". В результате задачу на контесте сдала только команда Стэнфорда, а пробовало сдавать только три команды. Стэнфорду повезло: у них в team notebook был симплекс-метод. Однако, судя по происходившему на финале с точки зрения аналитика, им также и не повезло: в нём был баг) В результате они довольно много времени потратили на исправление и сдали задачу только на последнем часу, хотя начали сильно раньше. А сколько команд упустило свой шанс получить результат значительно выше! Ведь не нужно было ничего решать, только реализовать два алгоритма, один из которых многие финалисты могут написать не просыпаясь посреди ночи. romanandreev, готовивший задачу, убедился, что задачу I с финала его алгоритм решает успешно, а вот у студентов на курсере весь форум в обуждениях проблем с точностью и других граблей линейного программирования. Некоторые даже жалуются, что они уже проходили ранее отдельный курс, посвященный только линейному программированию, там эту задачу сдавали, а у нас она не проходит :) Так что оттестировать для team notebook'а можно вполне неплохо)
В отличие от спортивного программирования, в реальной жизни линейное программирование — очень часто встречающаяся задача, возникающая при оптимизации рекламных бюджетов, инвестиционных портфелей, диеты, грузоперевозок, производства, в телекоммуникациях, а также в качестве подзадачи в приближенных алгоритмах — например, для Travelling Salesman Problem.
NP-полнота и методы борьбы с ней, как ни странно,- чуть ли не самый практический раздел курса. Вы скажете, там есть слова "теория сложности", но на практике, во-первых, большинство задач изначально NP-полные, а во-вторых, гораздо продуктивнее сразу распознать в задаче NP-полную и думать об одном из способов борьбы с этим (а эти способы мы и рассказываем в последних двух разделах), а не пытаться придумать какую-нибудь хитрую структуру данных в бесперспективных попытках, не догадываясь об этом, опровергнуть P!=NP. Некоторые задачи в качестве чекера используют SAT-solver, т.к. для решения задачи достаточно свести ее к SAT, а дальше на практике огромнейшие instance'ы решаются современными SAT-solver'ами, основанными на последних достижениях, за секунды.
