В мае я рассказал на Codeforces о запуске новой специализации по структурам данных и алгоритмам на Coursera, а в сентябре в рамках этой специализации запустился Курс по продвинутым алгоритмам и теории сложности, и о нем хочется рассказать поподробнее.
Темы курса:
- Потоки в сетях (алгоритмы Форда-Фалкерсона и Эдмондса-Карпа).
- Линейное программирование (симплекс-метод).
- NP-полнота (теория, сведения, решение NP-полных задач SAT-solver'ами).
- Методы борьбы с 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-полную и думать об одном из способов борьбы с этим (а именно об этом мы и рассказываем в двух разделах про NP-полноту), а не пытаться придумать какую-нибудь хитрую структуру данных в бесперспективных попытках, не догадываясь об этом, опровергнуть P!=NP. Некоторые задачи в качестве чекера используют SAT-solver, т.к. для решения задачи достаточно свести ее к SAT, а дальше на практике огромнейшие instance'ы решаются современными SAT-solver'ами, основанными на последних достижениях, за секунды.
Стриминг — крайне актуальная на сегодня тема, т.к. при обработке огромных объемов данных очень часто нужно посчитать какую-то статистику (количество различных ключей, самый частотный ключ, оценить размер пересечения множеств) по тера- или петабайтам, затратив на это очень ограниченное количество памяти и прочтя данные, желательно, только один раз, ну или два. Эту тему у нас читает приглашенный лектор — Михаил Капралов. Впоследствии у нас появится и задача на применение стриминг-алгоритмов. Для того, чтобы отделить стриминг-алгоритмы от обычных в рамках типичных time limit'ов, нужно постараться, но вроде это принципиально уже получилось, осталось оформить.
