Какие алгоритмы должен знать уважающий себя программист?
В этом выпуске попросили наших экспертов перечислить алгоритмы, которые, по их мнению, должен знать каждый уважающий себя программист.
В этом выпуске попросили экспертов перечислить алгоритмы, которые должен знать каждый уважающий себя программист. Рекомендуем дочитать до конца, там есть развёрнутый ответ в виде эссе по алгоритмической подготовке.
***Какие алгоритмы должен знать уважающий себя программист?
Сейчас в … “ненаучном” программировании алгоритмы не так важны. Хорошая алгоритмическая подготовка и смекалка пригодится в специфических областях, например в Big Data или компьютерном моделировании физических, социологических и других процессов реального мира. Даже игровая индустрия уже пережила тот период, когда как воздух требовались новые классные алгоритмы, на “стандартных” в большинстве случаев вполне можно жить.
Так что если говорить “в среднем”, то программист должен уметь подобрать для решения своей задачи необходимые готовые компоненты, разобраться в предоставляемых ими интерфейсах и заставить их работать вместе.
Он должен уметь выводить алгоритмы, а не знать их. Ровно как и математик должен уметь выводить доказательства.
На каких алгоритмах стоит потренироваться в выводе:
- сортировки — от пузырька, до параллельной кеш-независимой сортировки;
- динамическое программирование;
- алгоритмы сжатия данных — кодирование Хаффмана, арифметическое кодирование, сжатие подпоследовательностей;
- символические вычисления — как организовать;
- как сделать статическую структуру динамической — как сделать быструю (O(logN)) вставку в упорядоченный массив.
Материалы по перечисленным темам:
- Наша статья, посвященная пяти основным алгоритмам сортировки.
- Введение в динамическое программирование для начинающих.
- Книга, посвященная методам сжатия данных. Несколько тем, рассмотренных в книге: кодирование источников данных без памяти (канонический алгоритм Хаффмана, арифметическое сжатие, векторное квантование), словарные методы сжатия данных, методы контекстного моделирования и другие.
- Введение в структуры данных для новичков: динамический массив.
Где можно «потренировать» мозги:
Еще больше сайтов с задачками вы можете найти в нашей статье «28 сайтов, на которых можно порешать задачи по программированию».
***Материалы для изучения упомянутых Александром тем:
- Алгоритмы поиска пути в графе.
- Алгоритм двоичного (бинарного) дерева поиска.
- Введение в Хеш-таблицы.
- 8 сервисов для визуализации алгоритмов.
- Введение в анализ сложности алгоритмов.
Несколько статей, которые помогут вам получить хорошую алгоритмическую подготовку:
- Алгоритмы интеллектуального анализа данных.
- Материалы по продвинутым алгоритмам и структурам данных.
- Курс по алгоритмам от Стэнфордского университета.
- Основы компьютерных наук от университета Райса.