Способы изучения алгоритмов с

Как освоить алгоритмы?

Nov 2, 2020 · 6 min read

Чтобы что-то было сделано компьютером, нужно указать ему, как это сделать. Нужно написать программу с пошаговым объяснением: какие задачи компьютер должен выполнить и каким образом. В этом нам помогают алгоритмы.

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

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

Первое знакомство

Я начал программировать, когда ещ ё учился в средней школе. А первые шаги делал, создавая калькуляторы и светофоры на Visual Basic. Позже освоил HTML и Java. В то время я разрабатывал настольные и веб-приложения. Я просто писал хоть какой код, о внутренней логике и не задумывался.

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

Из программиста в разработчики

Изучение структур данных и алгоритмов стало поворотным пунктом в моём понимании компьютерного программирования: теперь я думал больше как инженер-разработчик, а не как программист. Почему я так говорю? Приведу несколько примеров.

Пример 1: алгоритмы сортировки

Представьте, что мы делаем приложение для интернет-магазина. Нам надо, чтобы пользователи могли просматривать товары в порядке возрастания цены. Для этого товары нужно отсортировать по цене. Будь я начинающим программистом, добавил бы цены в массив (или список) с записью их индексов и просто вызвал бы встроенный в массив метод sort() . Что на самом деле происходит внутри метода sort() ? Когда я раньше делал приложения, я об этом и понятия не имел.

Алгоритмы сортировки — это одна из базовых тем, которую в первую очередь проходят на курсе по изучению структур данных и алгоритмов в университете.

Различают следующие алгоритмы сортировки:

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

Пример 2: синтаксический анализ математических выражений

При вводе какого-нибудь математического выражения в калькулятор или в ячейку электронной таблицы, например MS Excel, оно автоматически вычисляется, и мы получаем ответ. Вы когда-нибудь задумывались о том, как это выражение высчитывается? А вот нам пришлось разработать программное обеспечение для работы с электронными таблицами и реализовать парсер выражений. Именно тогда я узнал о популярном алгоритме сортировочной станции. В нём используется очередь для хранения значений и стек для хранения операторов. Я узнал о реальных приложениях, в которых применяются такие структуры данных, как очереди и стеки (изучал их на курсе по структурам данных и алгоритмам), и понял лежащую в их основе логику. Меня так и распирала гордость оттого, что удалось самостоятельно реализовать алгоритм сортировочной станции, хотя таких реализаций тогда было уже полным-полно. 😃

Пример 3: списки, множества и словари

Когда нужно сохранить кучу значений, я применяю списки. Раньше я не задумывался, нужно ли соблюдать очерёдность или нужно ли допускать дубли: просто использовал список для всего подряд. Узнав о том, что, помимо списков, существуют ещё словари и множества, я понял, что всё это можно применять в различных сценариях. Так, сделав правильный выбор в той или иной ситуации и отдав предпочтение, скажем словарю, можно фактически ускорить выполнение кода. Например, если надо проверить принадлежность элемента, гораздо быстрее это будет сделать во множестве или словаре (на это требуется константное время), чем при использовании списка (требуется время, пропорциональное длине списка). Кроме того, список допускает наличие дублей, в то время как множество — нет.

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

С чего начать?

Изучаем концепции программирования

Прежде чем приступать к изучению алгоритмов, я бы порекомендовал освоить такие понятия программирования, как переменные, функции, классы и особенно понятия объектно-ориентированного программирования (ООП). Это будет вашим фундаментом для понимания более продвинутых концепций из области компьютерных наук.

Осваиваем алгоритмы и их принципы работы

• анализа временной и пространственной сложности;
• терминов “O” большое и “o” малое;
• рекурсии;
• базовых структур данных, таких как массивы, матрицы, связные списки, стеки, очереди, деревья и т. д.;
• основных алгоритмов, таких как алгоритмы поиска и сортировки.

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

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

Погружаемся в код с головой

На курсе нам предлагалось реализовать различные структуры данных с нуля, используя основные их операции. Например, двоичные деревья поиска (BST) в C++ с операциями вставки, удаления, поиска, обхода с предварительной выборкой, обхода с отложенной выборкой и обхода с порядковой выборкой. Приходилось создавать класс BST и реализовывать все эти операции в виде функций. Предлагалось даже сравнивать время выполнения определённых операций с различными размерами наборов данных. Это был отличный опыт. Я многому научился благодаря этим занятиям и стал лучше разбираться в операциях. Такой учебный процесс с практическими заданиями помог мне лучше понять концепцию алгоритмов.

Можно начать программировать с языков, поддерживающих ООП. Это легко с очень простыми в освоении языками:

Для новичков один из этих языков будет в самый раз.

Ресурсы для обучения

Онлайн-курсы

Можно заниматься дистанционно на:

и многие другие платформы. Для лучшего понимания можно попробовать приведённые там упражнения.

Средства интерактивной визуализации алгоритмов

Кроме того, можно попробовать платформы визуализации алгоритмов:

Они доступны в Интернете и понимают пошаговый механизм работы алгоритмов.

Упражнения на закрепление

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

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

Подводя итоги

Резюмируем статью списком из десяти рекомендаций для тех, кто приступает к изучению алгоритмов:

1. Начинайте с изучения основ.
2. Сформируйте чёткое понимание того, что происходит в алгоритме.
3. Прорабатывайте шаги алгоритма с примерами.
4. Обстоятельно разберитесь в анализе сложности.
5. Попробуйте самостоятельно реализовывать алгоритмы.
6. Записывайте всё важное, чтобы вернуться к этому в будущем.
7. Занимайтесь дистанционно на онлайн-курсах платформ для обучения.
8. Следите за онлайн-лекциями, опубликованными известными университетами.
9. Закрепляйте пройденный материал в упражнениях.
10. Если среди упражнений вам попались трудные задачи, не расстраивайтесь. После завершения упражнения можно будет почитать специальную инструкцию и понять, где вы застряли.

Дополнительные материалы для чтения

Если хотите узнать больше о структурах данных и алгоритмах, то можете ознакомиться со следующими статьями:

Заключение

Не забывайте о том, что путь к совершенству — практика!

Надеюсь, для вас эта статья была полезной и познавательной.

Источник

Как лучше всего изучать алгоритмы

Авторизуйтесь

Как лучше всего изучать алгоритмы

Нам пришел вопрос от подписчика Tproger, которым мы хотим поделиться с вами:

«Как лучше всего изучать алгоритмы?»

Мы обратились за разъяснением к нашим экспертам, а полученные ответы предоставляем вашему вниманию.

преподаватель курса профессия frontend-разработчик университета онлайн-профессий Нетология

Я не рекомендую сразу углубляться в алгоритмы и изучать их тем, кто только начинает программировать. Это сложная область computer science, и изучать ее без должной подготовки непросто. Также важно сразу определить конечную цель изучения алгоритмов: расширить общий кругозор (хочу что-то понимать), подготовиться к собеседованию или научиться решать конкретные задачи и улучшить свой код. Каждый сценарий определяет, насколько глубоко нужно нырнуть, чтобы достичь цели.

1-й уровень: вы хотите что-то понимать в алгоритмах. В этом случае вам поможет учебная литература, и я бы рекомендовал книгу «Грокаем алгоритмы». В ней понятно изложена суть без лишних деталей, много иллюстраций, а вся необходимая математика объясняется по ходу. Если вы владеете английским, то лучше читать английскую версию. А если не любите читать книги, то на Khan Academy есть вводный курс для начинающих.

2-й уровень: подготовка к собеседованию. Будет полезно повторить основные понятия и алгоритмы и поупражняться в их использовании. Для тренировки алгоритмических задач на любом из языков есть специализированные сервисы: HackerRank, Codewars и LeetCode. Ваша задача — научиться решать задачи уровня medium и выше. С литературой сложнее. Есть классические книги Кормена, Скиены, Седжвика. В первую очередь, обращайте внимание на книги с алгоритмами на вашем языке программирования. Например, для Python есть «Problem Solving with Algorithms and Data Structures using Python», много подобной литературы издано для Java и C/C++. Если вам интересны видеокурсы, то стоит посмотреть курсы Принстонского или Стенфордского университета. Они нудноваты, но объясняют основы.

3-й уровень: хочу быть лучше. Если вы хотите лучше решать поставленные задачи, то стоит четко определить, алгоритмы из какой области знаний нужно изучить. Если очертить круг алгоритмов не удается — обратитесь за помощью к более опытным коллегам. Они всегда подскажут с чего начать, подскажут с литературой и курсами.

руководитель отдела разработки REG.RU

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

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

Ну, и главное, конечно, использовать эти знания в работе над реальными задачами. Многие считают, что алгоритмика — это удел 1% программистов, которые делают какой-то rocket science. Это не так. Понимание теории алгоритмов и структур данных поможет вам быстрее находить решения многих повседневных задач, правильно оценивать формальную корректность программ и принципиальную достижимость желаемого результата, не писать код, который тормозит на ровном месте, более глубоко понимать, как работают базы данных и тому подобное.

аналитик в syndicate.one

(ответ подготовлен совместно с Михаилом Субботиным, преподавателем израильской высшей школы IT и безопасности HackerU)

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

ведущий специалист департамента информационных решений компании РДТЕХ

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

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

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

декан факультета веб-разработки GeekUniversity, онлайн-университет Mail.Ru Group

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

Необходимость в знакомстве с алгоритмами обычно возникает в двух случаях: 1. при изучении программирования в институте, где реализацию алгоритмов, например, на С включают в практическую программу обучения; 2. При столкновении в работе с некой редкой ситуацией, когда встроенных средств языка уже не хватает.

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

Теперь, когда мы разобрались в том, что реализовывать сортировку пузырьком самостоятельно — полезно, возникает вопрос: как именно к этому подступиться? Обычно при поиске информации по алгоритмам начинается хождение по запутанным статьям в Википедии. Но начинать надо с основ — тех вещей, при помощи которых описываются алгоритмы:
1. Блок-схемы
2. О-нотация («О» большое и «о» малое)
3. Псевдокод

Многие базовые вещи для тех, кто интересуется алгоритмами, неплохо описаны в книге Томаса Кормена «Алгоритмы. Вводный курс». Эта книга рассказывает об аспектах реализации алгоритмов в программировании. Для людей, которые лучше воспринимают визуальную информацию, есть очень много иллюстраций работы сортировок: в виде анимаций с примерами кода; в виде видео.

После этого можно попробовать поработать с фундаментальным типом алгоритмов — сортировкой. Такие алгоритмы не требуют специализированных знаний, о которых мы ещё поговорим ниже, и используют для своей работы базовые конструкции: циклы, массивы и ветвления. Стоит изучить различные сортировки — перечислю несколько видов по мере увеличения их сложности: сортировка пузырьком, шейкерная сортировка, сортировка расчёской, вставками, сортировка Шелла, быстрая сортировка и т.д. Также стоит узнать, какая из сортировок используется в вашем языке программирования при вызове встроенных методов сортировки. Основная идея состоит в том, чтобы, во-первых, реализовать сортировку в коде, во-вторых — проверить соответствие своей реализации оценке сложности алгоритма (см. О-нотации), т.е. действительно ли ваша реализация тратит ожидаемое время и потребляет ожидаемый объём памяти в зависимости от размера полученных на вход данных. Иными словами при изменении объёма данных в два раза алгоритм должен будет работать, к примеру (для линейной сложности), в два раза дольше.

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

Как только вы освоитесь с алгоритмами сортировки, нужно приступать к алгоритмам поиска. И здесь не обойтись без более сложных структур данных, таких как графы и деревья. Эти структуры изучает дискретная математика. Её идеи лежат в основе информатики и многих современных компьютерных технологий. Например, любимая всеми рекурсия описывается именно в этом разделе математики. Для изучения этой науки хорошо подойдёт книга Фёдора Новикова «Дискретная математика для программистов», которая рассказывает про основы науки и описывает важные алгоритмы при помощи дискретных структур данных.

Изучить и реализовать стоит алгоритмы
— Беллмана-Форда,
— Дейкстры,
— двоичного поиска (и двоичные деревья как инструмент),
— поиска в глубину и ширину.

Вообще, алгоритмов на тех же графах очень много, выбрать есть из чего. Самое главное здесь — много практики и анализа полученных результатов, без которых изучение алгоритмов будет просто галочкой для себя и работой в стол.

Книги по теме:
— Томас Х. Кормен «Алгоритмы. Вводный курс»
— Род Хаггарти «Дискретная математика для программистов»
— Фёдор Новиков «Дискретная математика для программистов»
— Стивен Скиена «Алгоритмы. Руководство по разработке»
— Роберт Седжвик «Фундаментальные алгоритмы на С++»
— Ричард Берд «Жемчужины проектирования алгоритмов»

Источник