Грокаем алгоритмы. 2 изд

Отзывы о первом издании
Предисловие
Введение
Благодарности
О книге
Как работать с этой книгой
Для кого предназначена эта книга
Структура книги
О коде в книге
Об авторе
О научном редакторе
От издательства
Глава 1. Знакомство с алгоритмами
Введение
Что вы узнаете об эффективности алгоритмов
Что вы узнаете о решении задач
Бинарный поиск
Более эффективный поиск
Упражнения
Время выполнения
«O-большое»
Время выполнения алгоритмов растет с разной скоростью
Наглядное представление «O-большое»
«O-большое» определяет время выполнения в худшем случае
Типичные примеры «O-большого»
Упражнения
Задача о коммивояжере
Шпаргалка
Глава 2. Сортировка выбором
Как работает память
Массивы и связанные списки
Связанные списки
Массивы
Терминология
Упражнения
Вставка в середину списка
Удаление
Какая структура данных используется чаще: массивы или списки?
Упражнения
Сортировка выбором
Пример кода
Шпаргалка
Глава 3. Рекурсия
Рекурсия
Базовый случай и рекурсивный случай
Стек
Стек вызовов
Упражнения
Стек вызовов с рекурсией
Упражнения
Шпаргалка
Глава 4. Быстрая сортировка
«Разделяй и властвуй»
Упражнения
Быстрая сортировка
Снова об «O-большом»
Сортировка слиянием и быстрая сортировка
Средний и худший случай
Упражнения
Шпаргалка
Глава 5. Хеш-таблицы
Хеш-функции
Упражнения
Примеры использования
Использование хеш-таблиц для поиска
Исключение дубликатов
Использование хеш-таблицы как кэша
Шпаргалка
Коллизии
Быстродействие
Коэффициент заполнения
Хорошая хеш-функция
Упражнения
Шпаргалка
Глава 6. Поиск в ширину
Знакомство с графами
Что такое граф?
Поиск в ширину
Поиск кратчайшего пути
Очереди
Упражнения
Реализация графа
Реализация алгоритма
Время выполнения
Упражнения
Шпаргалка
Глава 7. Деревья
Ваше первое дерево
Каталоги файлов
Космическая одиссея: поиск в глубину
Правильное определение дерева
Бинарные деревья
Код Хаффмана
Шпаргалка
Глава 8. Сбалансированные деревья
Балансировка
Деревья повышают скорость вставки
Короткие деревья работают быстрее
АВЛ-деревья: разновидность сбалансированных деревьев
Повороты
Как АВЛ-дерево узнает, что требуется поворот?
Косые деревья
B-деревья
Какие преимущества есть у B-деревьев?
Шпаргалка
Глава 9. Алгоритм Дейкстры
Работа с алгоритмом Дейкстры
Терминология
История одного обмена
Ребра с отрицательным весом
Реализация
Упражнения
Шпаргалка
Глава 10. Жадные алгоритмы
Задача составления расписания
Задача о рюкзаке
Упражнения
Задача о покрытии множества
Приближенные алгоритмы
Шпаргалка
Глава 11. Динамическое программирование
И снова задача о рюкзаке
Простое решение
Динамическое программирование
Задача о рюкзаке: вопросы
Что произойдет при добавлении элемента?
Упражнения
Что произойдет при изменении порядка строк?
Можно ли заполнять таблицу по столбцам, а не по строкам?
Что произойдет при добавлении меньшего элемента?
Можно ли взять часть предмета?
Оптимизация туристического маршрута
Взаимозависимые элементы
Может ли оказаться, что решение требует более двух «подрюкзаков»?
Возможно ли, что при лучшем решении в рюкзаке остается пустое место?
Упражнения
Самая длинная общая подстрока
Построение таблицы
Заполнение таблицы
Решение
Самая длинная общая подпоследовательность
Самая длинная общая подпоследовательность — решение
Упражнения
Шпаргалка
Глава 12. Алгоритм k ближайших соседей
Апельсины и грейпфруты
Построение рекомендательной системы
Извлечение признаков
Упражнения
Регрессия
Выбор признаков
Упражнения
Знакомство с машинным обучением
OCR
Построение спам-фильтра
Прогнозы на биржевых торгах
Тренировка модели МО: общий обзор
Шпаргалка
Глава 13. Что дальше?
Линейная регрессия
Инвертированные индексы
Преобразование Фурье
Параллельные алгоритмы
map/reduce
Фильтры Блума и HyperLogLog
Фильтры Блума
HyperLogLog
HTTPS и обмен ключами Диффи — Хеллмана
Локально-чувствительное хеширование
Минимальные кучи и приоритетные очереди
Линейное программирование
Эпилог
Приложение А. Производительность АВЛ-деревьев
Приложение Б. NP-трудные задачи
Задачи разрешимости
Задачи выполнимости
Трудно решить, легко проверить
Сведе́ние
NP-трудность
NP-полнота
Шпаргалка
Приложение В. Ответы к упражнениям

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

Пора грокать алгоритмы по-новому!