Сварщик Ненастоящий (llivejo) wrote,
Сварщик Ненастоящий
llivejo

Categories:

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

Закончил еще один онлайн-курс, на этот раз по алгоритмам, стендфордский, 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-элемента, он же по теории игр специалист, а кому он нужен, этот случайный выбор? Никто и никогда его в квиксорте не реализует, не практично. А медиана — практично. Академический снобизм, формальные доказательства против плебейских эвристик?..

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

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

  • пугающие русские фамилии в названиях

    Куорсеровский курс Model Thinking, одна из лекций: That's it, that's the theorem. I know it sounds sort of frightening, right? Lyapunov, it…

  • криптокурсы

    Стенфордский курс по криптографии. Очень, очень рекомендую. Один из самых полезных курсов из всех, когда-либо мной пройденных. Вроде и до этого…

  • (no subject)

    Ну что ж, традиционно - итоги года. В 2020: • утопил обручальное кольцо на маями-бич (в январе!) • поменял работу, получил 2x к зарплате • месяц…

  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments