Курс по Алгоритмам от Тима из Стэнфорда
На Coursera снова начинается курс по Алгоритмам от Тима из Стэнфорда. И я не могу про него не написать. А в свете вот этого поста про дистанционное образование так тем более.
Начну с того, что это самый интересный курс, который мне вообще когда-либо приходилось брать. А я провела во всяких не самых худших университетах немало лет. Курс называется Algorithms: Design and Analysis. Рассказывается в курсе про разные алгоритмы для графов, обсуждаются подходящие структуры данных для каждого алгоритма, присутствует теория и краткие доказательства этих алгоритмов. Во второй части рассказывается в том числе про P=NP проблему и алгоритмы с неполиномиальным временем.
Почему этот курс мне так понравился. Потому что лектор невероятно классный! Он настолько вовлечен, он так все это рассказывает. И потом каждую неделю надо запрограммировать новый алгоритм (на языке по собственному выбору) и найти с помощью своей имплементации ответ на вопрос. Ответ на вопрос засабмитить на сайте, и еще раз, пока не получится правильный ответ. Каждую неделю, как я сказала, новый алгоритм. И соответственно дедлайны. Мотивировало меня это просто сумасшедше: я бежала домой с работы и я не расставалась с алгоритмами по выходным, я ездила в отпуск, сидела на вершине самой высокой точки страны и программировала merge sort.
Я ждала полгода, чтобы снова объявили о его начале, чтобы посоветовать его другим людям, потому что для меня это было как найденный клад.
В качестве примера вот картинка, как я находила решаемость 2SAT проблемы рандомным алгоритмом.
2SAT-проблема: есть некоторый набор булиневых переменных {X1, …, Xn}, заданы ограничительные условия в виде (X1 OR X5), (¬X2 OR X3), (X5 OR X9),… Задача состоит в том, чтобы определить, возможно ли удовлетворить всем этим условиям одновременно.
Предложенный в курсе алгоритм берет и рандомным образом изменяет значение одной из переменных в одном из неудовлетворенных условий.
На картинке по оси х — число рандомных переворотов (за прогон по сету), по у — число неудовлетворенных условий. Было дано 6 разных сетов таких условий, и надо было определить, какие из них разрешимы (удовлетворяемы), а какие нет. Если сет условий — удовлетворяем, то такой рандомной альтерацией находится решение. Если нет — то число неудовлетворенных условий начинает колебаться вокруг некоторого значения. Например на второй слева линии на картинке видно, что после какого-то времени система сошлась к паре взаимно-неудовлетворяемых условий и эти рандомные альтерации колебают систему в пределах нескольких случайных вариаций.
Сейчас мне кажется, что это были топ 4 месяца моей жизни по концентрации интересного, когда шёл этот курс. И я ещё думаю, может вы мне дадите советов, в какого плана компаниях и на каких должностях нужно ежедневно иметь дело с такими вот штучками.
UPD:
Как альтернативу, глубоко рекомендую во многом похожий курс от Princeton:
Algorithms, Part I
Algorithms, Part IIНапример, из интересных заданий:
— A* для поиска решений для пятнашек,
— контекстное изменение размеров изображения seamcarving,
— простенький архиватор
UPD:
Лучший курс про алгоритмы, который я слушал, был из MIT OpenCourseWare: www.youtube.com/playlist?list=PL8B24C31197EC371C
