Грокаем алгоритмы

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

• программисты-самоучки;

• студенты, начавшие изучать программирование;

• выпускники, желающие освежить память;

• специалисты по физике/математике/другим дисциплинам, интересующиеся программированием.

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

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

Код примеров книги можно загрузить на сайте издательства по адресу www.manning.com/books/grokking-algorithms или https://github.com/egonschiele/grokking_algorithms.

Я считаю, что мы лучше всего учимся тогда, когда нам это нравится, — так что получайте удовольствие от процесса… и запускайте примеры кода!

Об авторе

Адитья Бхаргава работает программистом в Etsy, интернет-рынке авторских работ. Он получил степень магистра по информатике в Чикагском университете и ведет популярный иллюстрированный технический блог adit.io.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

1. Знакомство с алгоритмами

В этой главе

• Закладываются основы для остальных глав книги.

• Вы напишете свой первый алгоритм поиска (бинарный поиск).

• Вы узнаете, как описывается время выполнения алгоритма («O-боль­шое»).

• Будет представлен стандартный прием, часто применяемый при проектировании алгоритмов (рекурсия).

Введение

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

• В главе 1 речь пойдет о бинарном поиске и о том, как алгоритмы могут ускорить работу кода. В одном примере алгоритм сокращает количество необходимых действий с 4 миллиардов до 32!

• Устройство GPS использует алгоритмы из теории графов (об этом в главах 6, 7 и 8) для вычисления кратчайшего пути к точке назначения.

• При помощи методов динамического программирования (см. главу 9) можно создать алгоритм для игры в шашки.

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

Что вы узнаете об эффективности алгоритмов

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

Что вы узнаете о решении задач

Вы освоите методы решения задач, которые вам сейчас, возможно, неизвестны. Примеры:

• Если вы любите создавать видеоигры, вы можете написать систему на базе искусственного интеллекта, моделирующую действия пользователя с применением алгоритмов из теории графов.

• Вы узнаете, как построить рекомендательную систему на базе k ближайших соседей.

• Некоторые проблемы не решаются за разумное время! В части книги, посвященной NP-полноте задач, рассказано о том, как идентифицировать такие задачи и построить алгоритм для получения приближенного ответа.

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