стэнфордский курс по алгоритмам

[llivejo]

Закончил еще один онлайн-курс, на этот раз по алгоритмам, стендфордский, by Tim Roughgarden. Для истории: Statement Of Accomplishment (PDF)

После этого курса и курса по крипто сложилось впечатление, что Стенфорд из всех присутствующих на курсере университетов оптимально сочетает глубину и простоту изложения своих предметов, не перегружая лишним и не упуская нужного. Их курс по автоматам (конечные автоматы, регулярные выражения etc), кстати сказать, ведет Джеффри Ульман, автор Dragon Book, и курс по компиляторам тоже. Я просто не смог пройти мимо, записался, учу.



А именно про этот курс хорошо написала уважаемая a_d_astra еще в 2012-м году, жаль я не читал ее тогда :-)

Мои впечатления после прохождения тоже положительные: хотя картина мира касательно алгоритмов в голове особо и не поменялась, но если бы послушать такой курс году так в девяностом, то она сложилась бы намного раньше. Для изучавших computer science в провинциальных университетах — так и вообще открытием было бы. Но большинство таких, как правило, считают себя уже готовыми специалистами, в дипломе же написано "программист", куда там дальше теорию учить.

Кода писать много не пришлось, sloccount насчитал всего ~600 строк Питона за шесть недель заданий, вместе с тестами и отладкой, самое сложное задание — поиск связанных компонентов, вполне решаемая вещь, суммарно часов за пять я ее победил. Вообще, сложность именно задач по программированию сравнима с курсом Algoritmic Thinking, не олимпиадный уровень, а закрепление понимания, одобряю.

Из забавного: показалось, что молодой лектор сильно ревнует к аналогичному курсу от Принстонского университета: там курс ведет Седжвик, признанный специалист по алгоритмам и по QuickSort, в частности. В Принстоне упор идет на минимизацию числа шагов и обращений к памяти, все строго на Java, подсчитываются количество байтиков в структурах данных и чуть ли не миллисекунды доступа к ним. Шаг влево, шаг вправо, — сплошная Java. Не понравилось мне, хотя лекции послушал.

А стендфордский профессор такой упор сделал на доказательство корректности своего рандомизированного варианта QuickSort, что даже как-то неудобно за него было. Как из кожи вон лез, сделал кучу лекций, помеченных необязательными, брр.

Там весь смысл квиксорта в том, чтобы выбирать pivot-элемент и уже относительно его перебрасывать остальные элементы сортируемого подмножества массива. Седжвик-то знаменит уже тем, что предложил для pivot выбирать медиану из первого, последнего и среднего элементов подмассива на каждом этапе, а Tim Roughgarden ни разу не упомянул его, медиана только в домашнем задании как один вопрос мельком проскочила. Тщательно везде упоминал авторов, когда и кто что изобрел, а Седжвика прокинул :-) Доказывал корректность алгоритма при случайном выборе pivot-элемента, он же по теории игр специалист, а кому он нужен, этот случайный выбор? Никто и никогда его в квиксорте не реализует, не практично. А медиана — практично. Академический снобизм, формальные доказательства против плебейских эвристик?..

А! Стенфордский же курс на неделю позже Принстонского начался, так за месяц где-то опрос приходил от Стенфорда, и вопрос в нем был, мол, записались ли вы на другой курс по алгоритмам? Это я цитирую. Даже соврать хотел, мол, не-не-не, я верен Стенфорду и только ему.

Теперь жду второй части, она весной была, непонятно когда теперь будет.