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

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

Теперь жду
второй части, она весной была, непонятно когда теперь будет.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

July 2017

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

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 25th, 2017 11:27 am
Powered by Dreamwidth Studios