E-Book
7 Tage kostenlos im Abo
E-Book
7,99 €

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

Адитья Бхаргава

0,0

Erhalten Sie Zugang zu diesem und mehr als 300000 Büchern ab EUR 5,99 monatlich.

Herausgeber: Питер
Kategorie: Wissenschaft und neue Technologien
Sprache: Russisch

Beschreibung

Алгоритмы — это пошаговые инструкции решения задач, большинство из которых уже были кем-то решены, протестированы и доказали свою эффективность. Второе издание «Грокаем алгоритмы» упрощает изучение, понимание и использование алгоритмов. В этой книге вы найдете простые и внятные объяснения, более 400 забавных иллюстраций и десятки примеров. Ее чтение — лучший способ раскрыть всю мощь алгоритмов и подготовиться к интервью по программированию. Глубоких знаний математики не требуется! Вы узнаете о главных алгоритмах, позволяющих ускорить работу программ, упростить код и решить распространенные проблемы программирования. Начните с сортировки и поиска, а затем развивайте свои навыки для решения сложных задач, таких как сжатие данных и искусственный интеллект. Научитесь сравнивать эффективность различных алгоритмов. Во втором издании даны новые более подробные описания деревьев, NP-полные задачи, а код примеров обновлен на Python 3. Пора грокать алгоритмы по-новому!

Details

Sie lesen das E-Book in den Legimi-Apps auf:

Android

iOS

von Legimi
zertifizierten E-Readern

Kindle™-E-Readern
(für ausgewählte Pakete)

Seitenzahl: 224

Veröffentlichungsjahr: 2024

Das E-Book (TTS) können Sie hören im Abo „Legimi Premium” in Legimi-Apps auf:

Android

iOS

Bewertungen

0,0

Rezensionen(0 Rezensionen)

Leseprobe

Переводчик Е. Матвеев

Адитья Бхаргава

Грокаем алгоритмы. 2-е изд.. — СПб.: Питер, 2024.

ISBN 978-5-4461-4172-2

Отзывы о первом издании

Этой книге удалось невозможное: сделать математику простой и интересной!

Сандер Россел (Sander Rossel), COAS Sotware Systems

А вам бы хотелось изучать алгоритмы так же, как вы читаете свой любимый роман? Если да, то это именно та книга, которая вам нужна!

Санкар Раманатан (Sankar Ramanathan), IBM Analytics

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

Амит Ламба (Amit Lamba), Tech Overture, LLC

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

Кристофер Хаупт (Christopher Haupt), Mobirobo, Inc

Предисловие

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

К сожалению, не у всех имеются равные возможности доступа к программированию. Например, в США среди изучающих программирование очень мало женщин и представителей некоторых этнических/расовых групп. Очень важно, чтобы программирование и computer science получили распространение в разнообразных группах. Решение этой проблемы потребует изменений на многих направлениях, включая преодоление предрассудков, подготовку большего количества преподавателей и обеспечение разнообразного опыта обучения. Нужно помочь «включиться» большему количеству людей.

Книга Бхаргавы мне очень понравилась, потому что она помогает по-новому взглянуть на алгоритмы, которые лежат в основе эффективного программирования. Кто-то скажет, что есть только один способ изучать алгоритмы — найти толстый том по математике, прочитать его и (вроде бы) понять все написанное. Но такой подход хорош для тех, кто может учиться подобным образом, у кого есть на это время, и прежде всего — кому это нравится. Этот метод также основан на том, что мы знаем, для чего хотим изучать алгоритмы. Но, откровенно говоря, это слишком смелое предположение.

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

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

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

Надеюсь, эта книга поможет вам учиться — и тем, кто только пытается освоить алгоритмы, и тем, кому до сих пор не удавалось найти подходящий ресурс. Удачного грокания!

Даниэль Зингаро, Университет Торонто

Введение

Сначала программирование было для меня простым увлечением. Я изучил азы по книге «Visual Basic для чайников», а потом стал читать другие книги, чтобы узнать больше. Но алгоритмы мне никак не давались. Помню, как я смаковал оглавление своей первой книги по алгоритмам и думал: «Наконец-то я все узнаю!» Но материал оказался слишком сложным, и я сдался через несколько недель. Только благодаря хорошему преподавателю теории алгоритмов я понял, насколько простые и элегантные идеи заложены в ее основу.

Я написал свое первое иллюстрированное сообщение в блоге в 2012 году. Сам я визуал, поэтому мне нравится наглядный стиль изложения. С тех пор я создал немало иллюстрированных материалов по функциональному программированию, Git, машинному обучению и параллелизму. Кстати говоря, в начале своей карьеры я писал довольно посредственно. Объяснять научные концепции трудно. Чтобы придумать хорошие примеры, требуется время, чтобы объяснить сложную концепцию — тоже. Проще всего умолчать о сложных моментах. Я думал, что у меня все хорошо получается, пока после одной из моих популярных публикаций ко мне не обратился коллега со словами: «Я прочитал твой материал, но все равно ничего не понял». Мне еще предстояло многое узнать о том, как пишутся научные тексты.

В самом разгаре работы над иллюстрированными публикациями в блоге ко мне обратилось издательство Manning с предложением написать иллюстрированную книгу. Оказалось, что редакторы Manning хорошо умеют объяснять научные концепции, и они показали мне, как следует учить других. У меня была совершенно определенная цель: мне хотелось создать книгу, которая объясняла бы сложные научные темы и легко читалась.

Первое издание книги вышло в 2016 году. С тех пор книгу прочитало более 100 000 человек. Мне приятно, что очень многим подошел ее наглядный стиль обучения.

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

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

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

Благодарности

Спасибо издательству Manning, которое дало мне возможность написать эту книгу и предоставило большую творческую свободу в ходе работы. Я благодарен издателю Марджану Бейсу (Marjan Bace), Майку Стивенсу (Mike Stephens) за то, что он ввел меня в курс дела, и Иэну Хоу (Ian Hough) — невероятно отзывчивому редактору, всегда готовому прийти на помощь. Спасибо всем участникам производственной группы Manning: Полу Веллсу (Paul Wells), Дебби Хольмгрен (Debbie Holmgren) и всем остальным. Кроме того, я хочу поблагодарить всех, кто читал рукопись и делился своим мнением: Даниэля Зингаро (Daniel Zingaro), Бена Вайнегара (Ben Vinegar), Александра Мэннинга (Alexander Manning) и Мэгги Венгер (Maggie Wenger). Спасибо Дэвиду Айзенштату (David Eisenstat), моему научному редактору, и Тони Холдройду (Tony Holdroyd), техническому корректору Manning, за исправление множества моих ошибок.

Спасибо всем, кто помог мне в достижении цели: Берту Бейтсу (Bert Bates), который научил меня писать на научные темы, сотрудникам Flashkit, научившим меня программировать; многочисленным друзьям, которые помогали мне в работе — рецензировали главы, делились советами и предлагали разные варианты объяснений. Это были Бен Вайнгер (Ben Vinegar), Карл Пьюзон (Karl Puzon), Алекс Мэннинг (Alex Manning), Эстер Чан (Esther Chan), Аниш Бхатт (Anish Bhatt), Майкл Гласс (Michael Glass), Никрад Махди (Nikrad Mahdi), Чарльз Ли (Charles Lee), Джаред Фридман (Jared Friedman), Хема Маникавасагам (Hema Manickavasagam), Хари Раджа (Hari Raja), Мурали Гудипати (Murali Gudipati), Шриниваса Варадан (Srinivas Varadan) и другие; также спасибо Джерри Брэди (Gerry Brady), моему учителю по теории алгоритмов. Отдельное большое спасибо таким классикам алгоритмов, как CLRS1, Кнут и Стрэнг; безусловно, я стою на плечах гигантов.

Папа, мама, Приянка и все родные: спасибо за вашу неустанную поддержку. Огромное спасибо моей жене Мэгги и моему сыну Йоги. Впереди у нас много прекрасных моментов, и мне уже не придется проводить вечер пятницы за переписыванием книги.

Спасибо всем рецензентам:

Абишеку Косервалю (Abhishek Koserwal), Алексу Лукасу (Alex Lucas), Андресу Сакко (Andres Sacco), Аруну Сахе (Arun Saha), Бекки Хьют (Becky Huett), Сезару Аугусто Ороско Манотасу (Cesar Augusto Orozco Manotas), Кристиану Саттону (Christian Sutton), Диогинешу Гольдони (Diogines Goldoni), Дирку Гомесу (Dirk Gomez), Эду Бахеру (Ed Bacher), Эдер Андрес Авила Ниньо (Eder Andres Avila Nino), Франсу Оилинки (Frans Oilinki), Ганешу Сваминатану (Ganesh Swaminathan), Джампиеро Гранателле (Giampiero Granatella), Глену Ю (Glen Yu), Грегу Крейтеру (Greg Kreiter), Явиду Асгарову (Javid Asgarov), Жоао Ферейре (Joao Ferreira), Жобинешу Пурушотаману (Jobinesh Purushothaman), Джо Куэвасу (Joe Cuevas), Джошу Макадамсу (Josh McAdams), Кришне Анипинди (Krishna Anipindi), Кшиштофу Камычеку (Krzysztof Kamyczek), Кирилу Калиниченко (Kyrylo Kalinichenko), Лакшминараянану АС (Lakshminarayanan AS), Лоду Бентилу (Laud Bentil), Маттео Батисте (Matteo Battista), Микаэлю Бистрому (Mikael Bystrom), Нику Ракоши (Nick Rakochy), Нинославу Черкесу (Ninoslav Cerkez), Оливеру Кортену (Oliver Korten), Оои Кван Сану (Ooi Kuan San), Пабло Вареле (Pablo Varela), Патрику Регану (Patrick Regan), Патрику Ванъяу (Patrick Wanjau), Филиппу Конраду (Philipp Konrad), Петру Пинделу (Piotr Pindel), Раджешу Монахану (Rajesh Mohanan), Ранжиту Сахаи (Ranjit Sahai), Рохини Уппулари (Rohini Uppuluri), Роману Левченко, Самбарану Хазре (Sambaran Hazra), Сету Макферсону (Seth MacPherson), Шанкару Свами (Shankar Swamy), Шрихари Шридхарану (Srihari Sridharan), Тобиасу Копфу (Tobias Kopf), Вивеку Веераппану (Vivek Veerappan), Вильяму Джамиру Сильве (William Jamir Silva) и Сян Бо Мао (Xiangbo Mao) — ваши предложения помогли сделать эту книгу лучше.

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

1 Авторы классической книги по алгоритмам: Кормен, Лейзерсон, Ривест, Штайн. — Примеч. пер.

О книге

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

В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 2), просто вспомните, как ищете места для компании в кинотеатре. Наверное, вы уже поняли, что я сторонник визуального стиля обучения — в книге полно рисунков.

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

Приятного чтения!

Как работать с этой книгой

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

Я настоятельно рекомендую самостоятельно выполнять код всех примеров. Вы не поверите, насколько это важно. Просто введите мои примеры кода «с листа» (или загрузите их по адресу https://www.manning.com/books/grokking-algorithms-second-edition или https://github.com/egonschiele/grokking_algorithms) и выполните. Так у вас в памяти останется гораздо больше, чем просто при чтении.

Также я рекомендую выполнить упражнения, приведенные в книге. Упражнения не займут много времени — обычно задачи решаются за минуту или две, иногда за 5–10 минут. Упражнения помогут проверить правильность понимания материала. Если вы где-то сбились с пути, то узнаете об этом, не заходя слишком далеко.

Для кого предназначена эта книга

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

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

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

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

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

Структура книги

В первых трех главах закладываются основы.

• Глава 1: вы изучите свой первый нетривиальный алгоритм: бинарный поиск. Также здесь рассматриваются основы анализа скорости алгоритмов с применением «O-большое». Эта запись часто используется в книге для описания относительной быстроты выполнения алгоритмов.

• Глава 2: вы познакомитесь с двумя основополагающими структурами данных: массивами и связанными списками. Эти структуры данных часто встречаются в книге и используются для создания более сложных структур данных, например хеш-таблиц (глава 5).

• Глава 3: вы узнаете о рекурсии — удобном приеме, используемом многими алгоритмами (например, алгоритмом быстрой сортировки, о котором рассказано в главе 4).

По моему опыту, темы «O-большое» и рекурсии сложны для новичков, поэтому в соответствующих разделах я снижаю темп изложения и привожу более подробные объяснения.

В оставшейся части книги представлены алгоритмы, часто применяемые в разных областях.

• Методы решения задач рассматриваются в главах 4, 10 и 11. Если вы столкнулись со сложной задачей и не знаете, как эффективно ее решить, воспользуйтесь стратегией «разделяй и властвуй» (глава 4) или методом динамического программирования (глава 11). А если вы поняли, что эффективного решения не существует, попробуйте получить приближенный ответ с использованием жадного алгоритма (глава 10).

• Хеш-таблицы рассматриваются в главе 5. Хеш-таблицы — исключительно полезная структура данных, предназначенная для хранения пар ключей и значений (например имени человека и адреса электронной почты или имени пользователя и пароля). Трудно переоценить практическую полезность хеш-таблиц. Приступая к решению задачи, я обычно прежде всего задаю себе два вопроса: можно ли здесь воспользоваться хеш-таблицей и можно ли смоделировать задачу в виде графа.

• Графы и деревья рассматриваются в главах 6, 7, 8 и 9. Графы используются для моделирования сетей: социальных, дорожных, нейронных или любых других совокупностей связей. Поиск в ширину (глава 6) и алгоритм Дейкстры (глава 9) предназначены для поиска кратчайшего расстояния между двумя точками сети: с их помощью можно вычислить кратчайший маршрут к точке назначения или количество промежуточных знакомых у двух людей в социальной сети. Деревья — разновидность графа. Они используются в базах данных (обычно B-деревья), браузерах (DOM-деревья) или файловой системе.

• Алгоритм k ближайших соседей рассматривается в главе 12. Это простой алгоритм машинного обучения; с его помощью можно построить рекомендательную систему, механизм оптического распознавания текста, систему прогнозирования курсов акций — словом, всего, что требует прогнозирования значений («Мы думаем, что Адит поставит этому фильму четыре звезды») или классификации объектов («Это буква Q»).

• Следующий шаг: в главе 13 представлен еще ряд алгоритмов, которые хорошо подойдут для дальнейшего изучения темы.

О коде в книге

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

Исполняемые фрагменты кода можно загрузить из версии liveBook (электронной) по адресу https://livebook.manning.com/book/grokkingalgorithms-second-edition. Полный код примеров книги доступен для загрузки на сайте Manning https://www.manning.com и по адресу https://github.com/egonschiele/grokking_algorithms.

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

Форум liveBook

Приобретая книгу, вы получаете бесплатный доступ к закрытому веб-форуму издательства Manning (на английском языке), на котором можно оставлять комментарии о книге, задавать технические вопросы и получать помощь от автора и других пользователей. Чтобы получить доступ к форуму, откройте страницу https://livebook.manning.com/book/grokking-algorithms-second-edition. За информацией о форумах Manning и правилах поведения на них обращайтесь по адресу https://livebook.manning.com/discussion.

В рамках своих обязательств перед читателями издательство Manning предоставляет ресурс для содержательного общения читателей и авторов. Эти обязательства не подразумевают конкретную степень участия автора, которое остается добровольным (и неоплачиваемым). Задавайте автору хорошие вопросы, чтобы он не терял интереса к происходящему! Форум и архивы обсуждений доступны на веб-сайте издательства, пока книга продолжает издаваться.

Об авторе

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

О научном редакторе

Дэвид Айзенштат (David Eisenstat) — инженер-исследователь программного обеспечения. Он получил степень PhD в области computer science в Университете Брауна.