Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.
О книге
Я (Адитья Бхаргава) прежде всего стремился к тому, чтобы книга легко читалась. Я избегаю неожиданных поворотов; каждый раз, когда в книге упоминается новая концепция, я либо объясняю ее сразу, либо говорю, где буду объяснять. Основные концепции подкрепляются упражнениями и повторными объяснениями, чтобы вы могли проверить свои предположения и убедиться в том, что не потеряли нить изложения.
В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 2), просто вспомните, как ищете места для компании в кинотеатре. Наверное, вы уже поняли, что я сторонник визуального стиля обучения, — в книге полно рисунков.
Содержимое книги было тщательно продумано. Нет смысла писать книгу с описанием всех алгоритмов сортировки — для этого есть такие источники, как Википедия и Khan Academy. Все алгоритмы, описанные в книге, имеют практическую ценность. Я применял их в своей работе программиста, и они закладывают хорошую основу для изучения более сложных тем.
Структура книги
В первых трех главах закладываются основы:
Глава 1 — вы изучите свой первый нетривиальный алгоритм: бинарный поиск. Также здесь рассматриваются основы анализа скорости алгоритмов с применением «O-большое». Эта запись часто используется в книге для описания относительной быстроты выполнения алгоритмов.
Глава 2 — вы познакомитесь с двумя основополагающими структурами данных: массивами и связанными списками. Эти структуры данных часто встречаются в книге и используются для создания более сложных структур данных, например хеш-таблиц (глава 5).
Глава 3 — вы узнаете о рекурсии — удобном приеме, используемом многими алгоритмами (например алгоритмом быстрой сортировки, о котором рассказано в главе 4).
По моему опыту, темы «O-большое» и рекурсии сложны для новичков, поэтому в этих разделах я снижаю темп изложения и привожу более подробные объяснения. В оставшейся части книги представлены алгоритмы, часто применяемые в разных областях.
Методы решения задач рассматриваются в главах 4, 8 и 9. Если вы столкнулись со сложной задачей и не знаете, как эффективно ее решить, воспользуйтесь стратегией «разделяй и властвуй» (глава 4) или методом динамического программирования (глава 9). А если вы поняли, что эффективного решения не существует, попробуйте получить приближенный ответ с использованием жадного алгоритма (глава 8).
Хеш-таблицы рассматриваются в главе 5. Хеш-таблицы — исключительно полезная структура данных, предназначенная для хранения пар ключей и значений (например имени человека и адреса электронной почты или имени пользователя и пароля). Трудно переоценить практическую полезность хеш-таблиц. Приступая к решению задачи, я обычно прежде всего задаю себе два вопроса: можно ли здесь воспользоваться хеш-таблицей и можно ли смоделировать задачу в виде графа.
Алгоритмы графов рассматриваются в главах 6 и 7. Графы используются для моделирования сетей: социальных, дорожных, нейронных или любых других совокупностей связей. Поиск в ширину (глава 6) и алгоритм Дейкстры (глава 7) предназначены для поиска кратчайшего расстояния между двумя точками сети: с их помощью можно вычислить кратчайший маршрут к точке назначения или количество промежуточных знакомых у двух людей в социальной сети.
Алгоритм k ближайших соседей рассматривается в главе 10. Это простой алгоритм машинного обучения; с его помощью можно построить рекомендательную систему, механизм оптического распознавания текста, систему прогнозирования курсов акций — словом, всего, что требует прогнозирования значений («Мы думаем, что Адит поставит этому фильму 4 звезды») или классификации объектов («Это буква Q»).
Следующий шаг: в главе 11 представлены 10 алгоритмов, которые хорошо подойдут для дальнейшего изучения темы.
Для кого предназначена эта книга
Эта книга предназначена для читателей, которые владеют азами программирования и хотят разобраться в алгоритмах. Может быть, вы уже столкнулись с задачей программирования и пытаетесь найти алгоритмическое решение.
А может, вы хотите понять, где вам могут пригодиться алгоритмы. Ниже приведен короткий и неполный список людей, которым может пригодиться книга:
— программисты-самоучки;
— студенты, начавшие изучать программирование;
— выпускники, желающие освежить память;
— специалисты по физике/математике/другим дисциплинам, интересующиеся программированием.
Об авторе
Адитья Бхаргава работает программистом в Etsy, интернет-рынке авторских работ. Он получил степень магистра по информатике в Чикагском университете и ведет популярный иллюстрированный технический блог adit.io.
» Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок
Для Хаброжителей скидка 25% по купону — Алгоритмы
