Вирт, Кормен и диалекты Basic: что изучить про алгоритмы и структуры данных разработчикам на С++
Попросили инженеров YADRO поделиться избранными материалами про алгоритмы и структуры данных для «плюсовиков». Вспомнили и «классику» вроде книги Никлауса Вирта, и более современные источники, а также рассказали, почему стоит посвятить им время.
Статьи, лекции и курсы из подборки помогут опытным специалистам «вспомнить все» перед собеседованием или погрузиться в тему алгоритмов, если вы пока в ней не сильны.
Дисклеймер: некоторые ссылки открываются только с VPN.
Курс Algorithms от Стэндордского университета
Почему стоит смотреть: На мой взгляд, автор курса Тим Роугарден — отличный лектор. В Data Structures and Algorithms он буквально на пальцах объясняет базовую теорию и дает практические задания, которые проверяются на платформе Coursera автоматически. На внутреннем форуме можно обсудить решения и ошибки с другими студентами или кураторами курса.
Новый поток стартовал 14 августа, поэтому вы еще успеваете присоединиться. Курс займет 5 месяцев, если уделять учебе 10 часов в неделю.
Лекции Павла Маврина
Почему стоит смотреть: Автор лекций преподает курс по алгоритмам и структурам данных в ИТМО. А еще он чемпион мира ACM ICPC 2004 и занимает высокие места в соревнованиях по спортивному программированию типа TopCoder и Google Code Jam, что говорит о его высокой компетенции в этой сфере. Я слушал его лекции во время учебы в ИТМО. Из личного опыта: после курсов Павла я наконец-то начал понимать, как работают алгоритмы на графах. В лекциях, как правило, используется псевдокод, но я не считаю это проблемой. Главное — понимать принципы работы алгоритмов, а умение реализовать их на определенном языке программирования вторично.
- Лекции курса
Выступление Романа Панова на C++ Russia «Дерево смещений: работаем с динамически изменяемыми сегментированными массивами»
Почему стоит смотреть: В прошлом веке Николаус Вирт написал книгу с говорящим названием «Алгоритмы + Структуры данных = Программы». Кажется, что данное утверждение сохраняет истинность и сегодня. Когда я пишу на С++, меня увлекают вещи вроде системного или библиотечного интерфейса, времени исполнения программы, асинхронности, многопоточности и синхронизации. В этих бесчисленных аспектах теряется фокус на том, какие структуры данных и алгоритмы я использую.
Если сравнивать с другими языками, стандартная библиотека С++ достаточно скудна относительно структур данных, которые она предоставляет. Хочешь использовать структуру данных, которой нет в стандартной библиотеке, — приходится обращаться за помощью к сторонним библиотекам или писать свою реализацию. А результат редко оправдывает усилия. Но каждый раз, когда возникает потребность в собственной реализации структуры данных, более того, когда задача требует ad hoc-структуры данных, становится невероятно интересно. Как раз под этот случай и попадает дерево смещений.
Отмечу, что пока запись доклада доступна только тем, у кого есть билет, но скоро видео выложат на каналы конференции.
«Алгоритмы. Построение и анализ», Томас Кормен, Чарльз Эрик Лейзерсон, Рональд Линн Ривест, Клиффорд Штайн
Почему стоит читать: На вводном уровне Кормен — это непреходящая классика, даже лучшем, чем Вирт. В книге рассматривают множество алгоритмов и задач, как очень простых, чтобы не выпадать из материала, так и сложных, уровня исследовательских проектов. Работа «Алгоритмы. Построение и анализ» — хорошая ступенька к более серьезной литературе, например, «Искусству программирования» Кнута. Кроме того, у Кормена простой и понятный псевдокод, что позволяет одновременно изучать алгоритмы и прокачиваться в реализации на вашем любимом языке.
Что ещё советуют разработчики на С++
- Курс Introductions To Algorithms.
- Сборник из 145 алгоритмов для самостоятельной практики.
- Книга «Диалекты Basic для ZX Spectrum» под редакцией Родионова Н. Ю., Ларченко А. А.
- Выступление Джонатана Боккара на CppCon 2018 105 STL algorithms in less than an hour.
Какими материалами об алгоритмах на С++ вы бы дополнили подборку? Пишите в комментариях.