Как и для чего изучать алгоритмы

Иногда студенты, коллеги и знакомые задают мне вопросы о том

• почему нужно изучать алгоритмы?
• какой смысл в понимании оценок алгоритмов?
• для чего так много времени уделять алгоритмам, которые реализованы в стандартных библиотеках?
• пригождаются ли все эти знания в повседневной работе программиста?
• стоит ли разбираться javascript-разработчику с тем во что компилируется код на C и ассемблером вообще?

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

Почему стоит изучать алгоритмы?

Когда я только начинал преподавать алгоритмы, мне казалось, что это примерно как знание высшей алгебры: теория и только теория, потому что для решения задачи я всё равно достану sympy. То есть знание алгоритмов никак не пригождалось в моей работе программистом. Но через некоторое время проекты, на которых я работал, становились сложнее и в определённый момент мне потребовалось реализовать один из тех алгоритмов, которые я рассказывал на лекциях. Затем ещё один и ещё. Тогда я подумал: «Вот оно! Теперь я могу честно говорить студентам, что в работе нужны разбираемые алгоритмы!» Но на самом деле это является правдой лишь отчасти. Конечно, мне помогло то, что я знал эти алгоритмы, но их пришлось сильно переделывать под конкретную прикладную задачу. Более того в некоторых из задач решение в лоб, без использования специальных алгоритмов и структур данных не оказалось бы катастрофически плохим. И вот теперь, спустя 4 года преподавания я понял, что надо рассказывать не алгоритмы, а задачи. Итак,

Что можно получить от прохождения курса?

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

При этом не стоит забывать, что компьютеры развиваются очень быстро, меняются архитектуры процессоров, типы памяти, протоколы. Подходы придуманные 20 лет назад оказываются неэффективны на современном железе и наоборот, то, что было неоптимально в 70-е годы прошлого века внезапно становится эффективным. Компьютеры являются ограничениями в решении задач. Для правильного решения задачи необходимо понимание этих ограничений. Необходимо ли программисту понимать как работает процессор, как устроены фреймы памяти, стек вызовов, линии кешей и прочее? Однозначного ответа нет. Я бы сказал, что мешать эти знания не будут, и потратить время и силы на ознакомление с этим хотя бы поверхностно будет выгодным вложением своего времени.

Каждый алгоритм анализируется с разных сторон:

• сложность реализации;
• сложность по времени выполнения;
• сложность по количеству инструкций;
• сложность по памяти;
• сложность по количеству и размеру сетевых сообщений;
• локальность данных и кеш-независимость;
• учётная стоимость операций:
• параллелизуемость отдельных шагов;
• корректность и доказуемость решений или оценка возможных погрешностей.

При этом целью такого анализа является не разбор конкретного алгоритма, а умение анализировать алгоритмы и решения в целом.

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

Если подвести итог, то курс по большей своей части направлен на анализ ограничений задач и выбору подходящего плана решения. Сами же рассматриваемые алгоритмы являются лишь иллюстрацией для этого анализа. Алгоритмы описаны во множестве литературы, статьях, а многие из них уже реализованы в стандартных библиотеках языков. Конечно, знание алгоритмов на зубок может пригодиться в жизни, как, например, может пригодиться знание фразы «Шалость удалась» на школьном чемпионате по игре «Что? Где? Когда?». И тут стоит перейти к следующему вопросу.

На чём сосредоточиться и на что обращать внимание?

Вы когда-нибудь задумывались о том для чего в школе преподают литературу? Рекомендую ознакомиться с рабочей программой курса литературы 5–9 классов по крайней мере в части целей курса. Не смотря на бюрократический формализм сего произведения в нём прослеживаются интересные мысли, которые ускользнули лично от меня в школьные годы. Позже я дошёл до этого сам, сопоставляя рекомендации по изучению иностранных языков и уроков средней школы. Одна из важнейших целей изучения литературы — научиться правильно формулировать мысли. Есть отдельно русский язык, разбирающий особенности правил написания, есть культура речи, разбирающая подходы к построению предложений и фраз. Это похоже на изучение конкретного языка программирования и шаблонов проектирования. А литература показывает примеры хорошо выраженных мыслей, учит анализировать произведения, выделять значимые их части, рассматривает решения различных задач выражения смыслов.

Алгоритмы это литература в области программирования. Произведения классиков: Дейкстра, Вирт, Кнут, Адельсон-Вельский и Ландис, Форд и Фалкерсон, Лэмпорт и многие другие. При этом также как и в литературе, в реальной жизни почти не требуется знание этих произведений наизусть. Также как литературное достояние, найти описание того или иного алгоритма не составляет труда. Но изучение устройства этих произведений, их анализ, позволяет решать более сложные задачи, используя их как приёмы, как кусочки решения.

Поэтому основное внимание надо сосредоточить на следующих вещах:

• определение ограничений задачи;
• анализ решений;
• декомпозиция задачи и переиспользование решений;

Эти навыки находят непосредственные применения в программировании, проектировании и оценке сложности задач.

Для чего нужна практика и теоретические задачи?

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

Курс не привязан к какому-то конкретному языку программирования по двум причинам:

1. язык программирования является лишь инструментом, необходимо уметь решать задачу вне рамок языка;
2. выбор языка это всегда баланс между сложностью среды исполнения и объёмом вспомогательного кода: в первом случае из-за недостатка контроля могут исчезнуть некоторые оптимизации (а иногда и вовсе замедлить код), во втором случае сложность и объём вспомогательного кода заслоняют собой изящность рассматриваемого алгоритма.

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

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

Куда двигаться дальше?

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

• тестирование (модульные, функциональные, интеграционные, property-based, фазинг и многие другие);
• архитектура приложений (как правильно выделять сущности и связи, как разделить уровни ответственности модулей, SOLID, DI, гексогональная и слоистая архитектуры);
• шаблоны проектирования (знаменитый труд банды четырёх, а также множество статей и книг с его критикой);
• функциональное и реактивное программирование (смена парадигмы позволяет посмотреть на задачи с другой стороны, а также легче понять параллельные вычисления);
• сетевое взаимодействие (модель ISO OSI, фреймы и кадры, шифрование, протоколы и соединения);
• архитектура современных компьютеров и модели исполнения кода;
• криптография;
• машинное обучение и статистическая обработка больших данных;