Anti(C) · 17-Ноя-22 04:26(2 года 8 месяцев назад, ред. 04-Янв-23 16:54)
Грокаем алгоритмы. Иллюстрированное пособие для программистов Год издания: 2022 Автор: Адитья Бхаргава Переводчик: Е. Матвеев Жанр или тематика: Алгоритмы в программировании Издательство: Питер ISBN: 978-5-4461-0923-4 Серия: Библиотека программиста Язык: Русский Формат: PDF+EPUB Качество: Издательский макет или текст (eBook) Интерактивное оглавление: Да Количество страниц: 288 Описание: Я прежде всего стремился к тому, чтобы книга легко читалась. Я избегаю неожиданных поворотов; каждый раз, когда в книге упоминается новая концепция, я либо объясняю ее сразу, либо говорю, где буду объяснять.
Основные концепции подкрепляются упражнениями и повторными объяснениями, чтобы вы могли проверить свои предположения и убедиться в том, что не потеряли нить изложения.
В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 2), просто вспомните, как ищете места для компании в кинотеатре. Наверное, вы уже поняли, что я сторонник визуального стиля обучения, — в книге полно рисунков.
Содержимое книги было тщательно продумано. Нет смысла писать книгу с описанием всех алгоритмов сортировки — для этого есть такие источники, как Википедия и Khan Academy. Все алгоритмы, описанные в книге, имеют практическую ценность. Я применял их в своей работе программиста, и они закладывают хорошую основу для изучения более сложных тем.
Приятного чтения!
Примеры страниц
Оглавление
Предисловие 11
Благодарности 12
О книге 14
Структура книги 15
Как работать с этой книгой 16
Для кого предназначена эта книга 16
Условные обозначения и загружаемые материалы 17
Об авторе 17
От издательства 17 Глава 1 Знакомство с алгоритмами 18
Введение 18
Что вы узнаете об эффективности алгоритмов 19
Что вы узнаете о решении задач 19
Бинарный поиск 20
Более эффективный поиск 23Упражнения 27
Время выполнения 28
«O-большое» 29
Время выполнения алгоритмов растет с разной скоростью 29
Наглядное представление «O-большое» 32
«O-большое» определяет время выполнения в худшем случае 34
Типичные примеры «O-большого» 35
Упражнения 36
Задача о коммивояжере 37
Шпаргалка 39 Глава 2 Сортировка выбором 40
Как работает память 41
Массивы и связанные списки 43
Связанные списки 45
Массивы 46
Терминология 47
Упражнения 48
Вставка в середину списка 49
Удаление 50
Упражнения 51
Сортировка выбором 53
Пример кода 57
Шпаргалка 58
Глава 3 Рекурсия 59
Рекурсия 60
Базовый случай и рекурсивный случай 63
Стек 65
Стек вызовов 66
Упражнения 68
Стек вызовов с рекурсией 69
Упражнения 73
Шпаргалка 74
Глава 4 Быстрая сортировка 75
«Разделяй и властвуй» 76
Упражнения 85
Быстрая сортировка 85
Снова об «O-большом» 92
Сортировка слиянием и быстрая сортировка 93
Средний и худший случай 95
Упражнения 99
Шпаргалка 99 Глава 5 Хеш-таблицы 100
Хеш-функции 103Упражнения 107
Примеры использования 107
Использование хеш-таблиц для поиска 108
Исключение дубликатов 110
Использование хеш-таблицы как кэша 112
Шпаргалка 116
Коллизии 116
Быстродействие 119
Коэффициент заполнения 122
Хорошая хеш-функция 124Упражнения 125
Шпаргалка 126 Глава 6 Поиск в ширину 127
Знакомство с графами 128
Что такое граф? 131
Поиск в ширину 132
Поиск кратчайшего пути 135
Очереди 136Упражнения 137
Реализация графа 138
Реализация алгоритма 141
Время выполнения 146Упражнения 147
Шпаргалка 150 Глава 7 Алгоритм Дейкстры 151
Работа с алгоритмом Дейкстры 152
Терминология 157
История одного обмена 160
Ребра с отрицательным весом 167
Реализация 170
Упражнения 181
Шпаргалка 181 Глава 8 Жадные алгоритмы 182
Задача составления расписания 183
Задача о рюкзаке 185
Упражнения 187
Задача о покрытии множества 187
Приближенные алгоритмы 189
Упражнения 196
NP-полные задачи 196
Задача о коммивояжере — шаг за шагом 197
Как определить, что задача является NP-полной? 202
Упражнения 205
Шпаргалка 205 Глава 9 Динамическое программирование 206
Задача о рюкзаке 206
Простое решение 207
Динамическое программирование 208
Задача о рюкзаке: вопросы 217
Что произойдет при добавлении элемента? 217
Упражнения 220
Что произойдет при изменении порядка строк? 220
Можно ли заполнять таблицу по столбцам, а не по строкам? 221
Что произойдет при добавлении меньшего элемента? 221
Можно ли взять часть предмета? 221
Оптимизация туристического маршрута 223
Взаимозависимые элементы 224
Может ли оказаться, что решение требует более двух «подрюкзаков»? 225
Возможно ли, что при лучшем решении в рюкзаке остается пустое место? 226
Упражнения 226
Самая длинная общая подстрока 226
Построение таблицы 228
Заполнение таблицы 229
Решение 230
Самая длинная общая подпоследовательность 232
Самая длинная общая подпоследовательность — решение 233
Упражнения 235
Шпаргалка 235 Глава 10 Алгоритм k ближайших соседей 236
Апельсины и грейпфруты 236
Построение рекомендательной системы 239
Извлечение признаков 240
Упражнения 245
Регрессия 245
Выбор признаков 248Упражнения 249
Знакомство с машинным обучением 249
OCR 250
Построение спам-фильтра 251
Прогнозы на биржевых торгах 252
Шпаргалка 252 Глава 11 Что дальше? 254
Деревья 254
Инвертированные индексы 258
Преобразование Фурье 259
Параллельные алгоритмы 260
MapReduce 261
Для чего нужны распределенные алгоритмы? 261
Функция map 261
Функция reduce 262
Фильтры Блума и HyperLogLog 263
Фильтры Блума 265
HyperLogLog 265
Алгоритмы SHA 266
Сравнение файлов 267
Проверка паролей 268
Локально-чувствительное хеширование 269
Обмен ключами Диффи—Хеллмана 270
Линейное программирование 272 Эпилог 273 Ответы к упражнениям 274
Дополнительно
Приложил архив примеров (Python 2.х) и исправленный список опечаток с официального сайта.
Это то ли второй, то ли третий тираж книги в издательстве Питер, но до сих пор не все опечатки исправлены! А список опечаток на сайте издательства (ссылку удалил во избежание путаницы) также содержит по крайней мере 2 ошибки. В списке из раздачи (не в самой книге!!!) эти ошибки поправлены, но дальнейшую вычитку никто не делал.
Поэтому, когда смотрите на примеры алгоритмов и сомневаетесь, смотрите код из архива, он соответствует коду из репозитория автора и по идее в нем все должно быть ровно.
Также смотрите авторский список ошибок с пояснениями к английской версии.
Я прежде всего стремился к тому, чтобы книга легко читалась
Он бы прежде всего вычитку книги перед публикацией сделал бы. Позорище, а не книга. Просто немыслимое кол-во ошибок в коде. Всё настолько плохо, что они даже прилагают отдельно список: "Замеченные ошибки и опечатки". А тот, кто локализовал книгу на русский язык даже не соизволил исправить код в соответствии с файлом "Замеченные ошибки и опечатки". Они просто перевели как есть на русский язык и приложили файл с замеченными ошибками англоязычной версии. Но и этот файл не особо подходит к русскоязычной версии: номера страниц на которых ошибки, указаны для англоязычной версии, и с русскоязычной версией номера страниц не совпадают. В "Замеченные ошибки и опечатки" указана далеко не вся дичь, с которой вы неминуемо столкнётесь:
- Использование функции Print без скобок: то ли это Python версии 2, то ли это какой-то непонятный мне прикол;
- Именование сущностей в стиле "гуляй вася": и по PEP8 и вопреки ему;
- Ну и т.д.
Они просто перевели как есть на русский язык и приложили файл с замеченными ошибками англоязычной версии
Это не они, это я приложил, перегнав erratum по ссылке в пдф Ну и архив с двумя с половиной строками кода тоже. (Кстати, неплохо бы другим релизерам перенять такой опыт! Сайты издательств имеют свойство дохнуть, а сами издательства - закрываться со временем.)
Издательству "Питер" же абсолютно пофиг на качество продукта. Они перепечатывают книгу уже лет 5, этот вариант куплен в ноябре 2022, а список ошибок обновлялся аж в 2020 году. Возможно, меняется лишь год выпуска на титульнике, и больше ничего. Ну и что касается несовпадения страниц - живя в Канаде, вы должны были знать, что в англоязычной литературе всякие там предисловия, благодарности и прочие мысли, не относящиеся к основному тексту книги, нумеруются римскими цифрами. А собственно текст книги - арабскими. Таким образом несложно вычислить смещение (ведь макет на русском обычно не ломают).
Ну и что касается несовпадения страниц - живя в Канаде, вы должны были знать, что в англоязычной литературе всякие там предисловия, благодарности и прочие мысли, не относящиеся к основному тексту книги, нумеруются римскими цифрами. А собственно текст книги - арабскими. Таким образом несложно вычислить смещение (ведь макет на русском обычно не ломают).
Прежде чем писать, что я кому должен, вы бы сначала проверили, есть ли смысл писать то, что вы написали. Например:
- Ошибка из восьмой страницы в "Замеченные ошибки и опечатки"(Page 8" - "mid = (low + high) // 2), в русскоязычном переводе находится на девятой странице. - То, что указано под Page 9, а в русскоязычной версии на десятой странице - неверно. В Page 9 написано, что должно быть "mid = (low + high) / 2", когда на самом деле должно быть - "mid = (low + high) // 2": вместо оператора деления должен быть оператор целочисленного деления. Даже в файле "Замеченные ошибки и опечатки" свои ошибки. Или же русскоязычный перевод и "Замеченные ошибки и опечатки" из разных версий книги и несовместимы друг с другом.
Недостающие слеши в пдфках и epub'e я вижу, смысл написанного касался лишь нумерации страниц.
Цитата:
в русскоязычном переводе находится на девятой странице
А у меня на этой странице отпечатан номер 26.
Оглавление в английской версии такое:
Цитата:
contents
preface xiii
acknowledgments xiv
about this book xv
1 Introduction to algorithms 1
Introduction 1
What you’ll learn about performance 2
What you’ll learn about solving problems 2
Binary search 3
A better way to search 5
Running time 10
Посмотрим. Но то, что автор индус, хорошо так напрягает. И говнокода от них много видел, и даже книжки переводил - впечатления не из приятных.
Интересны примеры с гитхаба - куча разных языков. Например, про zig я впервые узнал оттуда)
Поверхностная книжонка, очень много смишных картинок не улучшающих понимание и в довесок дешевый маркетинговый прием -
использование скандального жаргонного словечка в названии - кажется из книги Хайнлайна "Чужой в чужой стране".
Разработчикам бесполезна, новичкам вредна - читайте Скиену, Левитина, Ахо, Кнута и что душе угодно, не засоряйте мозг.
84838764Поверхностная книжонка, очень много смишных картинок не улучшающих понимание и в довесок дешевый маркетинговый прием -
использование скандального жаргонного словечка в названии - кажется из книги Хайнлайна "Чужой в чужой стране".
Разработчикам бесполезна, новичкам вредна - читайте Скиену, Левитина, Ахо, Кнута и что душе угодно, не засоряйте мозг.
Затруднение(реальное) в том, что как обычно 95% всего есть поверхностное например ни в одной книги упоминающей приоритетные очереди( max-heap и min-heap) не указано о давно известно https://en.wikipedia.org/wiki/Min-max_heap
84838764Поверхностная книжонка, очень много смишных картинок не улучшающих понимание и в довесок дешевый маркетинговый прием -
использование скандального жаргонного словечка в названии - кажется из книги Хайнлайна "Чужой в чужой стране".
Разработчикам бесполезна, новичкам вредна - читайте Скиену, Левитина, Ахо, Кнута и что душе угодно, не засоряйте мозг.
84838764Поверхностная книжонка, очень много смишных картинок не улучшающих понимание и в довесок дешевый маркетинговый прием -
использование скандального жаргонного словечка в названии - кажется из книги Хайнлайна "Чужой в чужой стране".
Разработчикам бесполезна, новичкам вредна - читайте Скиену, Левитина, Ахо, Кнута и что душе угодно, не засоряйте мозг.
Ну и архив с двумя с половиной строками кода тоже. (Кстати, неплохо бы другим релизерам перенять такой опыт! Сайты издательств имеют свойство дохнуть, а сами издательства - закрываться со временем.)
