«Инструкция для смузихлёбов и барбершоперов». Как освоить алгоритмы с нуля

31 января 2018, 08:40

iOS-разработчик Антон Марченко написал для dev.by колонку о том, как приступить к освоению алгоритмов.  

Читать далее…

В связи с последними измениями в белорусской айтишечке и уже проявившейся разницей в бизнес-моделях между продуктовой и аутсорс-разработкой, меня заинтересовал вопрос об отличиях в качестве программистов, которые работают по данным моделям.

Любопытно, что в аутсорсе алгоритмы почти не спрашивают, в то время как во многих «приличных домах» без этих знаний отказывают. Это как с высшим образованием, на мой взгляд. С одной стороны, оно и не нужно, какого-то особого конкурентного преимущества не даёт. А с другой, без него смотрят настороженно, ещё и опасаются, что человек имеет свойство не доводить начатое до конца и может, например, куда-нибудь уплыть с проекта в самый неподходящий момент.

Поэтому я решил некоторым образом систематизировать знания о том, как мне удалось поднять алгоритмы. Получилась своего рода инструкция, ориентированная в первую очередь на смузихлёбов, бывших доставщиков пицц и барбершоперов. Прошу меня простить за использование терминологии, которой я нахватался на некоторых ресурсах с пониженной социальной ответственностью.

Поднять алгоритмы мне удалось только с пятого или шестого захода. Книги Вирта, Кнута, Кормена достаточно долгое время лежали мёртвым грузом, и уже казалось, что алгоритмы — это только для элитных бородатых C++ программистов, сидящих в тёмных подвалах и только иногда выбирающихся на свет божий на своих Ferrai Testarossa.

thesun.co.uk

0. Начало

Начать в первую очередь стоит с поднятия самооценки, посредством прочтения книги «Грокаем Алгоритмы» Адитьи Бхаргавы. Она рассчитана на любопытствующих восьмиклассниц, поэтому читается очень хорошо. Хорошей идеей будет помочь перевести примеры из книги с Python на ваш экзотический выбор. Автор — доброжелательный умница.

Данная книга позволит понять (вспомнить) самые базовые представления о следующих темах:

  • «О-большое» (Big-O notation)
  • Сортировка выбором
  • Рекурсия
  • Быстрая сортировка
  • Перестать бояться хеш-таблиц
  • Поиск в ширину
  • Алгоритм Дейкстры
  • Жадные алгоритмы
  • Динамическое программирование
  • Алгоритм к-ближайших соседей
  • Фильтры Блума
  • Обмен ключами Диффи-Хеллмана

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

0.1 Понимать применение

Опционально, для мотивации и расширения кругозора, можно ещё почитать «Алгоритмы, по которым стоит жить» Брайана Кристина и Тома Гриффинса. В книге содержатся очень классные примеры реального использования паттернов на бытовые темы: например, когда стоит жениться, или про то, что использование Merge Sort для сортировки реальной «офлайновой» библиотеки — не лучший выбор.  

Перевод книги Кормена содержит серьёзные отличия от оригинала. Так, например, в главе 24 «Кратчайшие пути из одной вершины» в русском переводе водителю автомобиля нужно найти самый короткий путь из Киева в Запорожье. Хотя в оригинале профессор Патрик едет из Феникса в Индианаполис.

0.5 Подготовка

Итак, для успешного освоения алгоритмов нам понадобится

  • английский язык (если с ним всё плохо, то будет матч мо профитэбел сфокусироваться всё же в первую очередь на нём),
  • бумажная книга Кормена (желательно купленная за свои деньги),
  • качественный блокнот и хорошая ручка (шутки шутками, но для приобретения хороших привычек нужно иметь положительное подкрепление, которое легко достичь приятными тактильными ощущениями от качественных вещей. Поэтому дешёвые ручки и блокноты с надписями «we are hiring» лучше выбросить)
  • и где-то $300 на всё про всё.

I. Собственно обучение

Курс, который я рекомендую, — это Стэнфордская специализация Тим Рафгардена. В отличие от Принстонского Algorithms, Part I, он не завязан на конкретный язык программирования (в моём случае было критично выполнять задание на Swift, который Coursera ещё не поддерживает).

Полученные знания шлифовать открытым курсом MIT на youtube. Эрик Демейн, которого все зовут Эрик, канадский вундеркинд, прекрасно объясняет и очень хорошо острит. Иногда, правда, заставляет чувствовать себя неловко. Например, рассказывая, как самостоятельно написал Depth-first search в возрасте семи лет.

Итак, ещё раз. Вся «вода» сверху и снизу написана ради этих предложений:

  • Проходим курс Стэнфорда.
  • Ведём англоязычный конспект.
  • Читаем необходимые главы из Кормена.
  • Шлифуемся МIT-овским курсом.
  • Дисциплина (на одном энтузиазме красно-чёрное дерево не сбалансируется)

Проходить просто аудирование будет не достаточно. Весь цимус в самостоятельном решении заданий. Заставить себя ночью реализовывать алгоритмы без проверки решений будет сложновато. Привычка вкладываться в своё обучение (покупкой книг и курсов) — это самая ценная привычка, которая только может быть у современного программиста.

Прежде чем поехать на гироскутере по своим хипстерским делишкам, можно ещё шлифануться вишенкой на торте — курсом Cracking the Code Review на HackerRank (основанным на одноимённой книге Гейл Макдауэлл). И уже точно избавиться от всех этих комплексов.

  • Изучение алгоритмов сделает из меня хорошего программиста?
  • Нет.
  • Может, как человек я стану получше?
  • Ответ опять отрицательный.
Обсуждение