Нам пришел вопрос от подписчика Tproger, которым мы хотим поделиться с вами:
«Как лучше всего изучать алгоритмы?»
Мы обратились за разъяснением к нашим экспертам, а полученные ответы предоставляем вашему вниманию.
Я не рекомендую сразу углубляться в алгоритмы и изучать их тем, кто только начинает программировать. Это сложная область computer science, и изучать ее без должной подготовки непросто. Также важно сразу определить конечную цель изучения алгоритмов: расширить общий кругозор (хочу что-то понимать), подготовиться к собеседованию или научиться решать конкретные задачи и улучшить свой код. Каждый сценарий определяет, насколько глубоко нужно нырнуть, чтобы достичь цели.
1-й уровень: вы хотите что-то понимать в алгоритмах. В этом случае вам поможет учебная литература, и я бы рекомендовал книгу «Грокаем алгоритмы». В ней понятно изложена суть без лишних деталей, много иллюстраций, а вся необходимая математика объясняется по ходу. Если вы владеете английским, то лучше читать английскую версию. А если не любите читать книги, то на Khan Academy есть вводный курс для начинающих.
2-й уровень: подготовка к собеседованию. Будет полезно повторить основные понятия и алгоритмы и поупражняться в их использовании. Для тренировки алгоритмических задач на любом из языков есть специализированные сервисы: HackerRank, Codewars и LeetCode. Ваша задача — научиться решать задачи уровня medium и выше. С литературой сложнее. Есть классические книги Кормена, Скиены, Седжвика. В первую очередь, обращайте внимание на книги с алгоритмами на вашем языке программирования. Например, для Python есть «Problem Solving with Algorithms and Data Structures using Python», много подобной литературы издано для Java и C/C++. Если вам интересны видеокурсы, то стоит посмотреть курсы Принстонского или Стенфордского университета. Они нудноваты, но объясняют основы.
3-й уровень: хочу быть лучше. Если вы хотите лучше решать поставленные задачи, то стоит четко определить, алгоритмы из какой области знаний нужно изучить. Если очертить круг алгоритмов не удается — обратитесь за помощью к более опытным коллегам. Они всегда подскажут с чего начать, подскажут с литературой и курсами.
Для начала нужно освоить теоретический фундамент: основные структуры данных, их свойства и методы работы с ними, анализ и сложность алгоритмов, их основные типы и классы. Не надо заучивать наизусть все виды сортировок или мудрёных деревьев — это вряд ли возможно и абсолютно бесполезно. Нужно понимать, чем они могут друг от друга отличаться и как выбрать правильный алгоритм или структуру данных в конкретном случае. Теорию можно получить из разных источников: есть много отличных книг, видеокурсов, сайтов, посвящённых этой теме. Какой вариант выбрать — вопрос личных предпочтений к формату обучения.
После этого нужно набить руку и научиться применять эти знания. Довольно много подходящих задач на HackerRank и других подобных ресурсах. Они разного уровня сложности, начиная с самого базового, и затрагивают много разных тем. Что важно — для их решения недостаточно знать какой-то базовый алгоритм, нужно уметь приспособить его к конкретной ситуации, модифицировать, совместить с другими подходами.
Ну, и главное, конечно, использовать эти знания в работе над реальными задачами. Многие считают, что алгоритмика — это удел 1% программистов, которые делают какой-то rocket science. Это не так. Понимание теории алгоритмов и структур данных поможет вам быстрее находить решения многих повседневных задач, правильно оценивать формальную корректность программ и принципиальную достижимость желаемого результата, не писать код, который тормозит на ровном месте, более глубоко понимать, как работают базы данных и тому подобное.
(ответ подготовлен совместно с Михаилом Субботиным, преподавателем израильской высшей школы IT и безопасности HackerU)
Изучать алгоритмы лучше всего по книжкам, но с реальными задачами. Если просто читать про алгоритмы и не использовать их, они быстро забудутся. Алгоритмами — логическим мышлением построения — владеют не так уж и много программистов. Это подтверждает весенний тест-опрос портала Tproger. Алгоритмы подразумевают хорошие математические знания или способность быстро определить, какой алгоритм лучше подходит под данную задачу. Ещё интереснее доработать существующий алгоритм. Самый «жирный» способ — разработать алгоритмы самостоятельно. Это уже ближе к Computer Science.
На мой взгляд, изучение алгоритмов требует очень ответственного подхода. Поскольку алгоритмы имеют под собой математическую подоплеку, изучающему для их освоения следует обладать прочными знаниями математики и очень желательно алгоритмическим мышлением.
В процессе изучения теории алгоритмов важно абстрагироваться от инструментария, «забыть» о языках программирования; недаром лучшие книги по алгоритмам содержат в себе примеры «программ», реализованных на псевдоязыках, так называемом псевдокоде, что позволяет не задумываться о реализации и тонкостях языка программирования и сконцентрироваться на логике.
И, конечно, не стоит ориентироваться исключительно на теорию: после изучения каждого алгоритма старайтесь реализовывать его, находить ему применение для какой-либо первой пришедшей в голову задачи. Здесь уже потребуются знания одного из языков программирования или даже нескольких — на ваш выбор.
Для многих программистов уровня Junior и даже Middle реализация классических алгоритмов сортировки, поиска и работы со структурами данных долгое время остаётся в стороне. Это объяснимый факт — большинство современных языков высокого уровня предоставляют встроенные инструменты для решения этих задач, и этих инструментов зачастую вполне хватает для применения в повседневной практике.
Необходимость в знакомстве с алгоритмами обычно возникает в двух случаях: 1. при изучении программирования в институте, где реализацию алгоритмов, например, на С включают в практическую программу обучения; 2. При столкновении в работе с некой редкой ситуацией, когда встроенных средств языка уже не хватает.
Однако знакомство с разными видами тех же самых сортировок и их самостоятельная реализация даёт программисту совершенно иной угол взгляда на язык программирования, с которым он работает, а также на структуры данных, которые в нём используются. Это дает импульс к изучению устройства внутренних механизмов языка и, как следствие, рождает более глубокое понимание.
Теперь, когда мы разобрались в том, что реализовывать сортировку пузырьком самостоятельно — полезно, возникает вопрос: как именно к этому подступиться? Обычно при поиске информации по алгоритмам начинается хождение по запутанным статьям в Википедии. Но начинать надо с основ — тех вещей, при помощи которых описываются алгоритмы:
1. Блок-схемы
2. О-нотация («О» большое и «о» малое)
3. Псевдокод
Многие базовые вещи для тех, кто интересуется алгоритмами, неплохо описаны в книге Томаса Кормена «Алгоритмы. Вводный курс». Эта книга рассказывает об аспектах реализации алгоритмов в программировании. Для людей, которые лучше воспринимают визуальную информацию, есть очень много иллюстраций работы сортировок: в виде анимаций с примерами кода; в виде видео.
После этого можно попробовать поработать с фундаментальным типом алгоритмов — сортировкой. Такие алгоритмы не требуют специализированных знаний, о которых мы ещё поговорим ниже, и используют для своей работы базовые конструкции: циклы, массивы и ветвления. Стоит изучить различные сортировки — перечислю несколько видов по мере увеличения их сложности: сортировка пузырьком, шейкерная сортировка, сортировка расчёской, вставками, сортировка Шелла, быстрая сортировка и т.д. Также стоит узнать, какая из сортировок используется в вашем языке программирования при вызове встроенных методов сортировки. Основная идея состоит в том, чтобы, во-первых, реализовать сортировку в коде, во-вторых — проверить соответствие своей реализации оценке сложности алгоритма (см. О-нотации), т.е. действительно ли ваша реализация тратит ожидаемое время и потребляет ожидаемый объём памяти в зависимости от размера полученных на вход данных. Иными словами при изменении объёма данных в два раза алгоритм должен будет работать, к примеру (для линейной сложности), в два раза дольше.
Считается, что правильнее всего учиться реализации сортировок на С, так как этот язык наиболее близок в работе к памяти и не имеет множества прослоек между своими структурами данных и памятью. Если же вы решитесь реализовывать алгоритм на привычном вам языке, то есть риск того, что сложность алгоритма не будет соответствовать реальному времени его работы и потреблению памяти.
Как только вы освоитесь с алгоритмами сортировки, нужно приступать к алгоритмам поиска. И здесь не обойтись без более сложных структур данных, таких как графы и деревья. Эти структуры изучает дискретная математика. Её идеи лежат в основе информатики и многих современных компьютерных технологий. Например, любимая всеми рекурсия описывается именно в этом разделе математики. Для изучения этой науки хорошо подойдёт книга Фёдора Новикова «Дискретная математика для программистов», которая рассказывает про основы науки и описывает важные алгоритмы при помощи дискретных структур данных.
Изучить и реализовать стоит алгоритмы
— Беллмана-Форда,
— Дейкстры,
— двоичного поиска (и двоичные деревья как инструмент),
— поиска в глубину и ширину.
Вообще, алгоритмов на тех же графах очень много, выбрать есть из чего. Самое главное здесь — много практики и анализа полученных результатов, без которых изучение алгоритмов будет просто галочкой для себя и работой в стол.
Книги по теме:
— Томас Х. Кормен «Алгоритмы. Вводный курс»
— Род Хаггарти «Дискретная математика для программистов»
— Фёдор Новиков «Дискретная математика для программистов»
— Стивен Скиена «Алгоритмы. Руководство по разработке»
— Роберт Седжвик «Фундаментальные алгоритмы на С++»
— Ричард Берд «Жемчужины проектирования алгоритмов»
Лучший метод изучения — реализация. Можно прочитать статьи/книги, посмотреть чужие решения, но лучше написать самому. И надо понимать, что чем больше «усвоено» подобных алгоритмов — например, шифрования или сортировки данных — тем легче будет даваться альтернативный.
Во многих источниках материал изложен таким образом, что подразумевается, что вы имеете некую базу знаний по дискретной математике. При этом довольно часто встречаются разработчики-самоучки, которые хотят идти в ногу со временем, изучая материал на понятном им языке.
Для начала было бы неплохо иметь общее представление об алгоритмах, не вдаваясь в подробности. В этом может помочь книга «Грокаем алгоритмы» от Адитьи Бхаргавы. Книга читается легко и не требует особых знаний, но при этом дает четкое представление о том, что такое алгоритмы, где они применяются и какие структуры данных существуют.
Если человек задался целью изучить алгоритмы, то, вероятно, он уже знает как минимум один язык программирования. В таком случае, можно продолжить изучение, прочитав книгу «Структуры данных и алгоритмы в Java» от Роберта Лафоре. В ней более развернуто описаны примеры сортировок и структур данных.
Если у вас есть знания по дискретной математике, то можно сразу читать книгу «Алгоритмы. Построение и анализ» Томаса Кормена и его друзей. По-хорошему, эту книгу должен прочитать каждый, кто хочет изучить алгоритмы.
А если вы хотите изучить дискретную математику быстро и сердито, то есть потрясающий курс математики для программистов MIT. В курсе 25 видео-лекций от преподавателей MIT. Материал изложен на английском языке и в сжатом виде, но очень интересно. Возможно, некоторые вещи будут непонятны, тогда можно пройтись по определенным темам математики на сайте Khan Academy, очень рекомендую.
Помимо курсов дискретной математики на портале университета MIT есть немалое количество материала по алгоритмам. Теория теорией, но ее необходимо подкреплять практикой. Есть отличный ресурс Hacker rank, где собрано достаточное количество задачек по алгоритмам и не только. Также в таких языках как Java или C#, например, из коробки реализовано много структур данных, с которыми было бы полезно поработать. Помимо этого, очень много библиотек написаны для языка Python.
Если этого будет недостаточно, то можно собраться духом и прочитать все тома «Искусства программирования» Дональда Кнута. А что делать дальше, думаю каждый уже решит сам.
Напоминаем, что вы можете задать свой вопрос экспертам, а мы соберём на него ответы, если он окажется интересным. Вопросы, которые уже задавались, можно найти в списке выпусков рубрики. Если вы хотите присоединиться к числу экспертов и прислать ответ от вашей компании или лично от вас, то пишите на experts@tproger.ru, мы расскажем, как это сделать.
