Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.
О книге
Я (Адитья Бхаргава) прежде всего стремился к тому, чтобы книга легко читалась. Я избегаю неожиданных поворотов; каждый раз, когда в книге упоминается новая концепция, я либо объясняю ее сразу, либо говорю, где буду объяснять. Основные концепции подкрепляются упражнениями и повторными объяснениями, чтобы вы могли проверить свои предположения и убедиться в том, что не потеряли нить изложения.
В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 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% по купону — Алгоритмы
Комментарии (67)
greybax
06.03.2017 20:04+20Алгоритмы — это всего лишь пошаговые алгоритмы решения задач
неплохое начало статьи
776166
06.03.2017 20:28+19Может, это про рекурсивные рекурсии? Ведь рекурсия, это всего лишь рекурсия рекурсии.
fabervox
07.03.2017 00:22Но ведь рекурсия в рекурсии, при проведении аналогий с циклами, может быть как итерацией цикла, так и циклом в цикле, а значит и нечто большее чем цикл, больше чем просто рекурсия. Ну и алгоритм больше чем алгоритм.
Просто проверка, воспринимаете ли вы сущности как сущности, или вам обязательно нужно разложить их по полочкам. Нужно разложить, значит ваше понимание книги в дальнейшем затруднится. Возможно настолько, что даже это определение займет не мало времени)776166
07.03.2017 00:36Тогда у меня плохие новости. Если сущность этой книги надо воспринимать, как сущности, не раскладывая по полочкам, то это религия, т.е. антинаучная ересь. Причём, алгоритмизированная и рекурсивно зацикленная. Что хорошо подтверждается расхожим выражением «больше рекурсий богу рекурсий».
sbnur
06.03.2017 20:49+2Сначала бинарный поиск (где), а потом массивы — это индийский подход или я не догоняю
kmu1990
06.03.2017 20:54+11. Бинарный поиск используется не только для поиска в массивах.
2. Что, не исключает индийский подход.sbnur
06.03.2017 21:19Поясните — для бинарного поиска нужна упорядоченная совокупность элементов для применения понятия больше(меньше) или слева(справа)
Приведите пример поиска в сущностях, не имеющих элементов или имеющих элементы без признака упорядоченияkmu1990
06.03.2017 21:22+1Например, для поиска нуля монотонной функции — массив не нужен в явном виде, достаточно уметь вычислять функцию в точке.
Про отсутствие элементов или порядка я ничего не говорил, только про отсутствие массива.sbnur
06.03.2017 21:35-3вы никогда не уйдете от упорядочения -есть элементы — точки, они упорядочены
kmu1990
06.03.2017 21:37+1А я разве где-то говорил, что нужно уйти от порядка или отказаться от элементов?
sbnur
06.03.2017 21:45-3элементы и порядок — это массив — хотя конечно лучше взглянуть непосредственно как излагается в книге, чтобы не спорить беспредметно.
Меня удивило, что сначала поиск, а потом структуры —
Просто поиск — одна из операций со структурами
Пример из первого класса — сначала цифры, потом числа, потом операции — логика преподаванияkmu1990
06.03.2017 21:50+2элементы и порядок — это массив
Ничего подобного, массив, какое бы определение вы не использовали, всегда предполагает нумерацию, т. е. как максимум счетное множество (я бы даже сказал конечное, но да это не важно). А бинарный поиск можно использовать и не на счетном множестве. Я уже приводил пример монотонной функции, множество точек которой совсем не обязательно должно быть счетно.sbnur
06.03.2017 22:00-3Нумерация это и есть порядок
Больше спорить не хочется — лучше потом гляну как там изложено у автора
kmu1990
06.03.2017 22:03+1Нумерация, несмоненно, задает порядок, но не каждый порядок сводится к нумерации, просто потому что не каждое множество счетное и, соответственно, не каждое множество можно занумеровать.
Я спорю не о том как написано у автора, а с вашим мнением, о том, что для бинарного поиска нужен массив — это не правда.
daiver19
06.03.2017 22:07Таки скорее всего речь идет о методе бисекции. С учетом фразы «алгоритм — это алгоритм», могу предположить, что в первой статье речьи идет о нем или о дихотомии в целом.
lorc
06.03.2017 21:23Можно пояснить бинарный поиск на примере словаря (тот, который бумажный и содержит все слова в лексикографическом порядке); не вводя понятие «массив» в том смысле, в котором его используют программисты.
sbnur
06.03.2017 21:29-1От того, что вместо слова массив вы будете использовать слово словарь, суть то не изменится — есть элементы, есть их нумерация, есть и порядок
lorc
06.03.2017 22:07Так я и не спорю. Но мы вроде говорим об учебнике для «программистов и любопытствующих», а не о справочнике.
Конечно же, правильно написанный серьезный учебник должен начать с понятия множества, потом перейти к бинарным отношениям на элементах множеств, потом к отношениям линейного порядка, а потом уже можно будет говорить и о бинарном поиске. Это, безусловно, самый точный подход.
Но, к счастью, понятие об алгоритме бинарного поиска можно дать не погружаясь в теорию множеств. Формально доказать правильность алгоритма — да, без теории множеств будет невозможно. Но объяснить как он работает — запросто.
Кстати, заметьте, что я ни разу не упомянул слово «массив».sbnur
06.03.2017 22:16-2да понятно — излагать можно, как хочется автору — просто я выразил свое удивление
Zet_Roy
07.03.2017 08:27Конечно же, правильно написанный серьезный учебник должен начать с понятия множества, потом перейти к бинарным отношениям на элементах множеств, потом к отношениям линейного порядка, а потом уже можно будет говорить и о бинарном поиске. Это, безусловно, самый точный подход.
Зачем нагружать учебник ненужной чепухой, лично я выбрав именно эту книгу для изучения алгоритмов, потому что там объясняется по простому сложные вещи, а в серьезном учебнике ни хрена непонятно, всякие ненужные непонятные математические конструкции.
В этой книге я наконец то понял как работает бинарный поиск после горы пересмотреных книг по алгоритмам.abyrkov
07.03.2017 13:31-1Если для вас математика — ненужная чепуха, у меня для вас плохие новости…
Zet_Roy
07.03.2017 13:37+1Математика должна быть к месту, ненужно приплетать ее туда где она совсем ненужна.
abyrkov
07.03.2017 15:00Я вас разочарую: что-то, сложнее Hello World'а, будет базироваться на этой же математике. А без этой математики… либо автор будет объяснять для совсем маленьких и тупых, извращаясь, либо очень поверхностно.
Но математика не к месту тоже бывает, соглашусь.Zet_Roy
07.03.2017 15:03-1Не смеши меня, сколько занимаюсь программированием мне НИГДЕ не пригодилась математика, там где в книгах встречалась математика сразу все становилось запутанным и непонятным.
abyrkov
07.03.2017 15:27Для начала, просто замечу, если считать математикой 1 + 1, то возникает логичный вопрос: чем вы таким занимаетесь, если вы даже ничего не складываете, программируя?
Так что, скорее всего, вы под словом «математика» подразумеваете «высшую математику»(она же так называется, нет?) или просто относительно сложную математику, то соглашусь — да, ее использовать приходится нечасто, но лишь потому, что она уже «под капотом».
Насчет того, что там где в книгах непонятная математика — то нужно в ней разобраться. Потому, что иначе получается замкнутый цикл: более сложные вещи базируются на основе тех вещей, в которых вы не разобрались или не смогли разобраться, и разобраться в них у вас не получится.Zet_Roy
07.03.2017 19:41+1Да имел виду что в программировании ненужно знать высшую математику, за исключением какого то научного софта.
NaHCO3
06.03.2017 21:05+4А разве бывает что-то более простое и разжёванное чем Кнут?
abbath0767
07.03.2017 11:36+1Кнут очень дорого стоит для «ознакомления»
Ogoun
07.03.2017 17:50Взял на Новом Арбате в открытых книжных точках, стоил 100р. за книгу. Б/У, но состояние неплохое.
abbath0767
07.03.2017 18:01Кто ищет тот всегда найдет) Видимо я плохо искал и рассматривал варианты покупок только в магазинах. Там цены конечно конские.
Благодарю за наводку)
oisee
06.03.2017 23:22Это только у меня купленная версия в .epub битая? (Не открывается в iBooks.)
kolyvan
07.03.2017 09:43+2Судя по всему Грокаем_алгоритмы.epub был сгенерирован через Adobe InDesign из pdf-ки и затем никем не был просмотрен. А там битые ссылки в оглавлении, отсутствует обложка, пустые метаданные. Вот зачем уважаемое издательство Питер такое выпускает?
Igor_Sib
07.03.2017 08:01+2А что значит грокаем? Первый раз такое слово слышу.
kolipass
07.03.2017 08:11+3@eugenius_nsk :
Слово to grok изобретено Хайнлайном и имеет два смысла: 1) понять во всей максимально возможной полноте и 2) съесть (по сюжету романа эти два значения связаны между собой). Так что переводчики романа (равно как и вы) поступили совершенно правильно, изобретя аналогичное слово для русского языка.
GlebSemenov
07.03.2017 15:08Я не осуждаю переводчика, я не понимаю редактора. Книжка с неясной семантикой заголовка вызывает отторжение. Автор книжку писал или желает пооргинальничать? К тому же, если на эту тему уже написано «over 10000» книг :)
fabervox
07.03.2017 18:37Перевод как жена, либо не красивый, но верный, либо верный но не красивый.
По ссылке, перевод статьи, и также слово в названии, с объяснением но без его перевода. Вероятно что случай не единичный, и вероятность его внедрения, обратнопропорциональна критике его применения.
Это нормально для любого нового слова, но во-первых указанное изобрели аналогичное, кощунственно звучит. У нас не только любому глаголу, можно придать такое склонение, но и любому существительному, слову, да и вообще любому набору символов, другое дело что на фоне других слов, может плохо выглядеть, и тогда вряд ли приживется.
Впрочем что-бы приживалось, достаточно набрать попутной популярности, например хорошая книжка или статья, с таким названием, может популяризовать слово.
Хорошо ли это или плохо? То что смог найти сходу, я лично не заметил там особых оттенков. Если бы мне был, так уж важен перевод этого слова, я бы посмотрел как употребляют и употребляют ли слово в экономических статьях.
В отсутствие противоречий или самого применения, гроканью вполне подошло бы поглощение, тут и внять целиком, и отобедать оставив или не оставив лишь косточки, в зависимости от того что вы за существо и что ели.
amberovsky
08.03.2017 01:57Я честно говоря подумал про grok фильтр в elasticsearch — он парсит и структурирует входную строку.
И даже подошло по смыслу :)
50kiloofcabbage
07.03.2017 09:43Отличная книга.
Прекрасно подойдет для тех, кто хочет размяться и подготовиться к чтению чего-то фундаментального, например, того же Кнута.
immaculate
07.03.2017 09:56В отрывке все описано очень примитивно, как для младшего школьного возраста. Есть ли смысл покупать подобную книгу для подготовки, например, к собеседованию? Или там все в таком же стиле написано и имеет смысл только для обучения школьников?
Bandicoot
07.03.2017 11:41я как раз для прохождения будущих собеседований и купил. Эту книгу хорошо дополняет «Карьера программиста», там тоже алгоритмы разжеваны в контексте собеседований
AlxRaven
07.03.2017 13:24+2Когда первый-же, программный пример в книге приведен с ошибками, непонятно стоит ли читать эту книгу дальше.
Bandicoot
07.03.2017 15:14там действительно есть ошибки и опечатки в программном коде, но в этом есть положительный момент — пока их исправишь, лучше поймешь тему)
cleaner_it
08.03.2017 13:44Подтверждаю! Пока разберёшься в ошибке — раз пять материал перечитаешь, и перепроверишь много раз. Брал книги Питера ещё в начале 2000х, ошибки в печатных изданиях были, есть и будут
NaHCO3
08.03.2017 14:01Надо просто уметь делать из багов фичу. Вот одна замечательная книга построена по такому принципу:
— В большую часть доказательств сознательно внесены опечатки, столь оживляющие чтение математического текста. Эти опечатки являются моей электронной подписью и делают доказуемым каждый случай прямого несанкционированного включения текста этой книги в другие произведения.
Так-то. И что самое поразительное, автор не шутит, в случайность некоторых обнаруженных мною ошибок крайне трудно поверить.
klirichek
11.03.2017 18:05Да пример-то ладно, в правильном виде есть на гитхабе (хотя там тоже опечатка).
Но даже с ошибкой он работает (просто бинарный поиск превращается в линейный, но кого это волнует в массиве из четырёх элементов?
Тут, можно сказать, переводчики или редактор недосмотрел.
Но вот график внизу 35-й страницы — там уже РУКОПИСНЫЙ. Т.е. опечаток вроде быть и может.
Однако и там какое-то странное значение 1.7с вылезло, написанное рукой.
Zet_Roy
07.03.2017 13:34Отличная книга для тех кто хочет понимать как работают базовые алгоритмы, всем новичкам и нетолько рекомендую.
Bandicoot
07.03.2017 15:18Книга действительно стоящая. Я ее только начал читать, но уже понял, в чем принципиальная разница между массивами и связными списками, и зачем нужны последние. Для тех, кому сложно дается алгоритмика или нет толковых преподавателей — то, что доктор прописал
abbath0767
13.03.2017 10:28Отличная книга для начинающих.
Если честно повелся на рекламу (ну люблю я когда сложные вещи объясняют просто и с картинками, хоть и не люблю хедфирст), купил. Прочитал. Для начинающих самое оно и как по мне так дается достаточно больше количество информации для любого джуна который «плавает» в этой теме.
BasicWolf
Хайнлайн в гробу перевернулся. Но тем не менее, судя по описанию, книга стоящая — людям пришедшим в программирование, минуя прикладную математику — в самый раз.
BasicWolf
Для товарищей, не знакомых со словом «Grok».
Впервые его использовал в романе «Stranger in a Strange Land» американский писатель-фантаст Роберт Хайнлайн. О произведении стоит как минимум сказать, что в 1962 году, роман был награждён престижнейшей в мире НФ премией Hugo. А слово «grok» стало популярно у прогрессивной молодёжи в контексте «вникнуть во все тонкости и нюансы».
Почему лично мне перевод «Грокаем» сильно режет слух: в русском языке такого слова нет. Для тех, кто не знаком с его оригинальным значением, оно ничего не будет значить. Я читал два перевода (к сожалению не знаю имена переводчиков), в которых, в одном случае «grok» переводится и спрягается как «грок», «грокнул», «грокать» и т.д., и в другом — «вникнуть», «вникнул», «вникать» и т.д. При чтении разница сильно ощутима. И если в английском языке «to grok» ложится на слух, то «грокать» вызывало желание горхнуть переводчика и редактора вместе взятых.
massimus
В английском тоже не было до Хайнлайна. В романе это марсианское слово, и с чего ему быть русским в русском переводе?
Мне кажется, второй перводчик не грокнул слово «грокать». «Вникать в тонкости» — это про анализ, а «грокать» — про целостное восприятие. И как, интересно, слово «вникать» использовалось во втором значении «съесть»?
Что касается использования «непонятного» слова в названии книжки про алгоритмы — полного и точного соответствия этому марсианизму в русском нет так же, как и в английском, а не знакомые с термином легко найдут его в интернете, пополнят словарный запас не самой бесполезной единицей и, возможно, тоже прочтут этот отличный роман.