Курс по продвинутым алгоритмам и теории сложности

Правка ru10, от Michael, 2016-10-04 04:01:01

В мае я рассказал на Codeforces о запуске новой специализации по структурам данных и алгоритмам на Coursera, а в сентябре в рамках этой специализации запустился Курс по продвинутым алгоритмам и теории сложности, и о нем хочется рассказать поподробнее.

Темы курса:

  1. Потоки в сетях (алгоритмы Форда-Фалкерсона и Эдмондса-Карпа).
  2. Линейное программирование (симплекс-метод).
  3. NP-полнота (теория, сведения, решение NP-полных задач SAT-solver'ами).
  4. Методы борьбы с NP-полнотой (оптимизации полного перебора, решаемые частные случаи, приближенные алгоритмы).
  5. Стриминговые (потоковые) алгоритмы.

Задачи для этого курса готовили 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'ов, нужно постараться, но вроде это принципиально уже получилось, осталось оформить.

Теги coursera, вшэ, фкн, алгоритмы, структуры данных, acm, acm icpc

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru10 Русский Michael 2016-10-04 04:01:01 2 Мелкая правка: 'ы курса:\n1. Поток' -
en8 Английский Michael 2016-10-03 19:26:02 19 (published)
ru9 Русский Michael 2016-10-03 19:23:21 117
en7 Английский Michael 2016-10-03 19:21:41 1 Tiny change: ' 2009 R2 ( [user:ilya' -> ' 2009 R2 ([user:ilya'
en6 Английский Michael 2016-10-03 19:21:26 3 Tiny change: 'ust screams "implemen' -> 'ust screamed "implemen'
en5 Английский Michael 2016-10-03 19:20:59 7
en4 Английский Michael 2016-10-03 19:20:35 5
en3 Английский Michael 2016-10-03 19:20:14 13
en2 Английский Michael 2016-10-03 19:19:23 5
ru8 Русский Michael 2016-10-03 19:18:56 52
en1 Английский Michael 2016-10-03 19:18:00 5324 Initial revision for English translation
ru7 Русский Michael 2016-10-03 19:15:51 10433 Возвращено к ru5
ru6 Русский Michael 2016-10-03 19:14:57 10433
ru5 Русский Michael 2016-10-03 18:51:58 241
ru4 Русский Michael 2016-10-03 18:16:25 36
ru3 Русский Michael 2016-10-03 18:15:14 505
ru2 Русский Michael 2016-10-03 18:11:25 4448
ru1 Русский Michael 2016-10-03 17:51:27 931 Первая редакция (сохранено в черновиках)