Грокаем алгоритмы. Бхаргава А.

СПб.: 2017. — 288 с.

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

Формат: pdf

Размер: 10,2 Мб

Смотреть, скачать: google.drive

Оригинал на английском языке: Modern JavaScript for the Impatient. Horstmann C.S. (2020, 343p.)

Оглавление
Предисловие 11
Благодарности 12
О книге 14
Структура книги 15
Как работать с этой книгой 16
Для кого предназначена эта книга 16
Условные обозначения и загружаемые материалы 17
Об авторе 17
От издательства 17
Глава 1. Знакомство с алгоритмами 18
Введение 18
Что вы узнаете об эффективности алгоритмов 19
Что вы узнаете о решении задач 19
Бинарный поиск 20
Более эффективный поиск 23
Упражнения 27
Время выполнения 28
«О-большое» 29
Время выполнения алгоритмов растет с разной скоростью 29
Наглядное представление «О-большое» 32
«О-большое» определяет время выполнения в худшем случае 34
Типичные примеры «О-большого» 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
Снова об «О-большом» 92
Сортировка слиянием и быстрая сортировка 93
Средний и худший случай 95
Упражнения 99
Шпаргалка 99
Глава 5. Хеш-таблицы 100
Хеш-функции 103
Упражнения 107
Примеры использования 107
Использование хеш-таблиц для поиска 108
Исключение дубликатов ПО
Использование хеш-таблицы как кэша 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. Алгоритм к ближайших соседей 236
Апельсины и грейпфруты 236
Построение рекомендательной системы 239
Извлечение признаков 240
Упражнения 245
Регрессия 245
Выбор признаков 248
Упражнения 249
Знакомство с машинным обучением 249
OCR 250
Построение спам-фильтра 251
Прогнозы на биржевых торгах 252
Шпаргалка 252
Глава 11. Что дальше? 254
Деревья 254
Инвертированные индексы 258
Преобразование Фурье 259
Параллельные алгоритмы 260
MapReduce 261
Для чего нужны распределенные алгоритмы? 261
Функция тар 261
Функция reduce 262
Фильтры Блума и HyperLogLog 263
Фильтры Блума 265
HyperLogLog 265
Алгоритмы SHA 266
Сравнение файлов 267
Проверка паролей 268
Локально-чувствительное хеширование 269
Обмен ключами Диффи—Хеллмана 270
Линейное программирование 272
Эпилог 273
Ответы к упражнениям 274