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

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



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

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

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

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

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

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

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

Теперь жду
второй части, она весной была, непонятно когда теперь будет.
llivejo: (monster)
Куорсеровский курс Model Thinking, одна из лекций:

That's it, that's the theorem. I know it sounds sort of frightening, right?
Lyapunov, it sounds really scary, and I'm sure when you looked at the syllabus, you thought, oh my gosh, Lyapunov functions! This is gonna be hard. Maybe I'll skip this lecture.

I thought about calling it Dave functions, or Maria functions, because then it wouldn't sound so frightening if I said, we're gonna study Maria functions, you know, so, ha, that's probably gonna be pretty easy, or Dave functions.

It's just that with these Russian surnames, you sorta think, oh my goodness, this is frightening.

It's not, very, very easy.
llivejo: (monster)


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

Вроде и до этого не был профаном в криптографии, Брюса нашего Шнайера читал, но этот курс дал понимание от самых основ, очень как-то цельно и правильно всё подается, ощущение было "ну что сложного было разобраться, почему я не изучил это раньше?!". И в то же время плотно так, без лишней воды: раз-раз — и ты уже в качестве задания по программированию взламываешь RSA-шифрование на плохо выбранных простых числах, например.

Несколько раз, когда застревал, лез на форумы, находил подсказки. Было забавно, один из студентов придумал выкладывать решения, пошифрованные симметричным PGP, ключом шифрования является ответ к задаче. Мол, мы же тут все шифропанки собрались, PGP/GPG во все поля...

Вот принял курсеровский автогрейдер твой с таким трудом найденный ответ, — молодец, можешь скачать и расшифровать решения других студентов. Кто на чем пишет: ява, яваскрипт, PHP, хаскель. Но в основном питон, конечно. Я тоже один раз выложил свое решение, похвастался, чо.

Задания по программированию все необязательные, но если сделаешь хотя бы 70% из них, — в Statement of Accomplishment будет написано "с отличием".

В резюме такой сертификат, конечно, не вставишь (как SDN, например), по-моему, Стенфорд вообще не дает Курсере выдавать сертификаты даже за деньги, но польза именно этого курса — не в бумажках.


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

July 2017

S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526272829
3031     

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 20th, 2017 09:41 pm
Powered by Dreamwidth Studios