стэнфордский курс по алгоритмам
Закончил еще один онлайн-курс, на этот раз по алгоритмам, стендфордский, 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-элемента, он же по теории игр специалист, а кому он нужен, этот случайный выбор? Никто и никогда его в квиксорте не реализует, не практично. А медиана - практично. Академический снобизм, формальные доказательства против плебейских эвристик?..
А! Стенфордский же курс на неделю позже Принстонского начался, так за месяц где-то опрос приходил от Стенфорда, и вопрос в нем был, мол, записались ли вы на другой курс по алгоритмам? Это я цитирую. Даже соврать хотел, мол, не-не-не, я верен Стенфорду и только ему.
Теперь жду второй части, она весной была, непонятно когда теперь будет.
После этого курса и курса по крипто сложилось впечатление, что Стенфорд из всех присутствующих на курсере университетов оптимально сочетает глубину и простоту изложения своих предметов, не перегружая лишним и не упуская нужного. Их курс по автоматам (конечные автоматы, регулярные выражения etc), кстати сказать, ведет Джеффри Ульман, автор Dragon Book, и курс по компиляторам тоже. Я просто не смог пройти мимо, записался, учу.
А именно про этот курс хорошо написала уважаемая a_d_astra еще в 2012-м году, жаль я не читал ее тогда :-)
Мои впечатления после прохождения тоже положительные: хотя картина мира касательно алгоритмов в голове особо и не поменялась, но если бы послушать такой курс году так в девяностом, то она сложилась бы намного раньше. Для изучавших computer science в провинциальных университетах - так и вообще открытием было бы. Но большинство таких, как правило, считают себя уже готовыми специалистами, в дипломе же написано "программист", куда там дальше теорию учить.
Кода писать много не пришлось, sloccount насчитал всего ~600 строк Питона за шесть недель заданий, вместе с тестами и отладкой, самое сложное задание - поиск связанных компонентов, вполне решаемая вещь, суммарно часов за пять я ее победил. Вообще, сложность именно задач по программированию сравнима с курсом Algoritmic Thinking, не олимпиадный уровень, а закрепление понимания, одобряю.
Из забавного: показалось, что молодой лектор сильно ревнует к аналогичному курсу от Принстонского университета: там курс ведет Седжвик, признанный специалист по алгоритмам и по QuickSort, в частности. В Принстоне упор идет на минимизацию числа шагов и обращений к памяти, все строго на Java, подсчитываются количество байтиков в структурах данных и чуть ли не миллисекунды доступа к ним. Шаг влево, шаг вправо, - сплошная Java. Не понравилось мне, хотя лекции послушал.
А стендфордский профессор такой упор сделал на доказательство корректности своего рандомизированного варианта QuickSort, что даже как-то неудобно за него было. Как из кожи вон лез, сделал кучу лекций, помеченных необязательными, брр.
Там весь смысл квиксорта в том, чтобы выбирать pivot-элемент и уже относительно его перебрасывать остальные элементы сортируемого подмножества массива. Седжвик-то знаменит уже тем, что предложил для pivot выбирать медиану из первого, последнего и среднего элементов подмассива на каждом этапе, а Tim Roughgarden ни разу не упомянул его, медиана только в домашнем задании как один вопрос мельком проскочила. Тщательно везде упоминал авторов, когда и кто что изобрел, а Седжвика прокинул :-) Доказывал корректность алгоритма при случайном выборе pivot-элемента, он же по теории игр специалист, а кому он нужен, этот случайный выбор? Никто и никогда его в квиксорте не реализует, не практично. А медиана - практично. Академический снобизм, формальные доказательства против плебейских эвристик?..
А! Стенфордский же курс на неделю позже Принстонского начался, так за месяц где-то опрос приходил от Стенфорда, и вопрос в нем был, мол, записались ли вы на другой курс по алгоритмам? Это я цитирую. Даже соврать хотел, мол, не-не-не, я верен Стенфорду и только ему.
Теперь жду второй части, она весной была, непонятно когда теперь будет.