Что такое грокать алгоритмы

«Грокаем алгоритмы»: обзор самой лучшей книги по алгоритмам

Вот мы и добрались до обзора книги, так любимой многими программистами. И не важно, на каком языке вы пишете — вы обязательно о ней слышали. «Грокаем алгоритмы» научит вас алгоритмически мыслить и думать рационально, что очень важно в программировании.

Python изучили, web-фреймворк Django тоже, про машинное обучение вообще молчим… Но это всё практически бесполезно без знания алгоритмов. Стоит учитывать, что при собеседованиях на Junior позиции, независимо от того, на каком языке вы программируете, будут их спрашивать. А если вы middle или senior dev, то и алгоритмы будут посложнее.

Немного об авторе

Адитья Бхаргава — программист из компании Etsy. В свое время даже получил степень магистра математических наук (а, как вы знаете, алгоритмы и математика безразрывно связаны). В данный момент еще и ведет свой блог с картинками на техническую тематику.

Содержание

Пройдемся по оглавлению, чтобы понять, с чем нам придется работать:

А в чем суть?

Книга «Грокаем алгоритмы»отличается от других своим максимально дружелюбным подходом к читателю. Это своеобразная детская книга для взрослых. Множество картинок и упражнений вкупе с манерой подачи материала добьются невероятного эффекта. Примеры сопровождают вас буквально на каждом шагу. А то, что эти примеры взяты из реальной жизни, поможет вам еще быстрее влиться к курс дела и разобраться с тем или иным алгоритмом.

Подведем итоги

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

Скачать книгу можно из нашего Telegram-канала — «Грокаем алгоритмы».

Источник

Книга «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих»

Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?

Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

О книге

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

В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 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% по купону — Алгоритмы

Источник

Конспект книги «Грокаем алгоритмы» Адитья Бхаргава

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

Как работает?

Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.

Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.

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

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

Реализация алгоритма на JavaScript:

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

Глава 2. Сортировка выбором

Как работает?

находим номер минимального значения в текущем списке

производим обмен этого значения со значением первой неотсортированной позиции

теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

Реализация алгоритма на JavaScript:

Глава 3. Рекурсия

Каждая рекурсивная функция состоит из двух случаев: базовый и рекурсивный.

Пример рекурсивной функции для подсчёта суммы элементов массива:

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

Все вызовы функций сохраняются в стеке вызовов.

4. Быстрая сортировка

Один из самых быстрых универсальных алгоритмов сортировки массивов. Из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Как работает?

Выбрать опорный элемент из массива.

Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

Реализация алгоритма на JavaScript:

Совет: когда вы пишите рекурсивную функцию, в которой задействован массив, базовым случаем часто оказывается пустой массив или массив из одного элемента.

Среднее время выполнения быстрой сортировки составляет O(n log n).

5. Хэш-таблицы

Хэш-функция должна соответствовать требованиям:
— Должна быть последовательной
— Разным словам должны соответствовать разные числа

Хэш-функция неизменно связывает название с одним индексом, связывает разные строки с разными индексами, знает размер массива и возвращает только действительные индексы.

хэш-таблица = хэш-функция + массив

Хэш-таблица состоит из ключей и значений.

Примеры использования хэш-таблиц:
— Поиск
— Исключение дубликатов
— Кэш

Преимущества кэширования:
— Скорость
— Меньшая затрата ресурсов сервера

Кешируемые данные хранятся в хэше.

Хорошая хэш-функция создаёт минимальное число коллизий.

В среднем хэш-таблицы выполняют любые операции за время O(1). То есть при любом размере хэш-таблицы выборка данных займёт одинаковое время.

Для предотвращения коллизий необходимы:
— низкий коэффициент заполнения
— хорошая хэш-функция

6. Поиск в ширину

Позволяет найти кратчайшее расстояние между двумя объектами.

Алгоритм работает с графами. Он помогает ответить на вопросы:
— существует ли путь от узла A к узлу B?
— как выглядит кратчайший путь от узла A к узлу B?

Как работает?

Поместить узел, с которого начинается поиск, в изначально пустую очередь.

Извлечь из начала очереди узел U и пометить его как развёрнутый.

Если узел U является целевым узлом, то завершить поиск с результатом «успех».

В противном случае, в конец очереди добавляются все преемники узла U, которые ещё не развёрнуты и не находятся в очереди.

Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».

Реализация алгоритма на JavaScript:

Поиск в ширину выполняется за время O(кол-во вершин + кол-во рёбер).

7. Алгоритм Дейкстры

Алгоритм Дейкстры вычисляет кратчайший путь во взвешенном графе.

Как работает?

Найти узел с наименьшей стоимостью

Обновить стоимости соседей

Повторять, пока это не будет сделано для всех узлов графа

Вычислить итоговый путь

Реализация алгоритма на JavaScript:

Алгоритм Дейкстры работает только с направленными ациклическими графами.

Ключевая идея Алгоритма Дейкстры: в графе ищется путь с наименьшей стоимостью. Пути к этому узлу с меньшими затратами не существует.

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

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

Алгоритм Дейкстры не может использоваться при наличии рёбер с отрицательным весом. Для этого используется алгоритм Беллмана-Форда.

8. Жадные алгоритмы

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

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

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

Рассуждение завершается по индукции.

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

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

Эффективность приближенного алгоритма оценивается по:
— быстроте
— близости полученного решения к оптимальному

9. Динамическое программирование

Динамическое программирование применяется для оптимизации какой-либо характеристики при заданных ограничениях.

10. Алгоритм k ближайших соседей

Если вы пытаетесь выполнить классификацию чего-либо, сначала попробуйте применить алгоритм k ближайших соседей.

Основные применения: классификация и регрессия:
1. классификация = распределение по категориям
2. регрессия = прогнозирование ответа (в числовом выражении)

Источник

Обзор на книгу «Грокаем алгоритмы» Адитья Бхаргава

Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих» и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

Абсолютно непонятное и страшное название. К тому же, каждого начинающего программиста кидало в дрожь от одного слова — «алгоритмы». И эта книга тоже должна вызывать ужас. Но уже одна обложка расслабляет ваш мозг. Эти мышки — просто любовь.

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

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

Среди тем, рассмотренных в этой книге — бинарный поиск, понятие О-большое, сортировка выбором и быстрая сортировка, различные структуры данных (такие как массивы, связанные списки и хеш-таблицы), графы, алгоритм Дейкстры и многое другое. Меня очень пугало такое содержание, но на деле все оказалось более, чем понятно расписано даже для гуманитария. Во всех примерах используется Python2.7

Более того, в книге еще есть множество упражнений (с ответами), на которых можно закрепить пройденный материал и проверить, насколько он реально был усвоен.

ПРИМЕР ЗАДАЧИ В примере с Netflix сходство между двумя пользователями оцени­валось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятер­ки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть разли­чия в стратегиях выставления оценок?

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

Обязательно рекомендую к прочтению начинающим программистам и всем интересующимся.

Читайте лучшие книги по программированию: «Грокаем алгоритмы» — одна 18 книг по разработке (и не только), которые мы советуем прочитать всем начинающим программистам.

Источник

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

Посоветуйте книгу друзьям! Друзьям – скидка 10%, вам – рубли

Эта и ещё 2 книги за 299 ₽

Отзывы 20

Отличная книга! Есть ошибки, но как я понял, ошибки, конкретно в этом издании, смотрел более свежее издание в книжном магазине, там уже все исправлено. Если возможно добавьте его.

Отличная книга! Есть ошибки, но как я понял, ошибки, конкретно в этом издании, смотрел более свежее издание в книжном магазине, там уже все исправлено. Если возможно добавьте его.

Отличная книга для старта или освежения знаний

Единственный недостаток – после прочтения хочется продолжения по теме в таком же стиле

Отличная книга для старта или освежения знаний

Единственный недостаток – после прочтения хочется продолжения по теме в таком же стиле

Хорошая книга. Для начинающих программистов будет полезной. Можно использовать при преподавании информатики и курсов программированиия.

Хорошая книга. Для начинающих программистов будет полезной. Можно использовать при преподавании информатики и курсов программированиия.

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

Особенно выразительны примеры:

разделяй и властвуй

алгоритм задачи коммивояжера

рекурсия, массивы и списки, сетка алгоритмов

дерево, поиск в ширину, алгоритм Дейкстры

динамическое программирование (git diff, расстояние Левенштейна)

нормализация и рекомендательная система

введение в ML (OCR, фильтры и прогнозы forex)

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

Сделала заметки, рекомендую к чтению: все 288 страниц можно использовать как справочник!

Мне не хватило списка литературы, но я полагаю, что заценю и английский оригинал данной книги «Grokking Algorithms by Aditya Y. Bhargava»

Источник