CПб.: Питер, 2017. — 288 с. — ISBN 978-5-496-02541-6.
Алгоритмы - это всего лишь пошаговые алгоритмы решения задач, и
большинство таких задач уже были кем-то решены, протестированы и
проверены. Можно, конечно, погрузится в глубокую философию
гениального Кнута, изучить многостраничные фолианты с
доказательствами и обоснованиями, но хотите ли вы тратить на это
свое время? Откройте великолепно иллюстрированную книгу и вы сразу
поймете, что алгоритмы - это просто. А грокать алгоритмы - это
веселое и увлекательное занятие.
Внутри ...
Знакомство с алгоритмами:
Введение, Что вы узнаете об эффективности алгоритмов, Что вы узнаете о решении задач, Бинарный поиск, Более эффективный поиск, Упражнения, Время выполнения, «O-большое», Время выполнения алгоритмов растет с разной скоростью,
Наглядное представление «O-большое», «O-большое» определяет время выполнения в худшем случае, Типичные примеры «O-большого», Упражнения, Задача о коммивояжере,Шпаргалка.
Сортировка выбором:
Как работает память, Массивы и связанные списки, Связанные списки, Массивы, Терминология, Упражнения, Вставка в середину списка, Удаление, Упражнения, Сортировка выбором, Пример кода, Шпаргалка.
Рекурсия:
Рекурсия, Базовый случай и рекурсивный случай, Стек, Стек вызовов, Упражнения, Стек вызовов с рекурсией, Упражнения, Шпаргалка.
Быстрая сортировка:
«Разделяй и властвуй», Упражнения, Быстрая сортировка, Снова об «O-большом», Сортировка слиянием и быстрая сортировка, Средний и худший случай, Упражнения, Шпаргалка.
Хеш-таблицы:
Хеш-функции, Упражнения, Примеры использования, Использование хеш-таблиц для поиска, Исключение дубликатов, Использование хеш-таблицы как кэша, Шпаргалка, Коллизии, Быстродействие Коэффициент заполнения, Хорошая хеш-функция, Упражнения,Шпаргалка.
Поиск в ширину:
Знакомство с графами, Что такое граф? Поиск в ширину, Поиск кратчайшего пути, Очереди, Упражнения, Реализация графа, Реализация алгоритма, Время выполнения, Упражнения,Шпаргалка.
Алгоритм Дейкстры:
Работа с алгоритмом Дейкстры, Терминология, История одного обмена, Ребра с отрицательным весом, Реализация, Упражнения, Шпаргалка.
Жадные алгоритмы:
Задача составления расписания, Задача о рюкзаке, Упражнения, Задача о покрытии множества, Приближенные алгоритмы, Упражнения, NP-полные задачи, Задача о коммивояжере — шаг за шагом, Как определить, что задача является NP-полной? Упражнения, Шпаргалка.
Динамическое программирование:
Задача о рюкзаке, Простое решение, Динамическое программирование, Задача о рюкзаке: вопросы, Что произойдет при добавлении элемента? Упражнения, Что произойдет при изменении порядка строк? Можно ли заполнять таблицу по столбцам, а не по строкам? Что произойдет при добавлении меньшего элемента? Можно ли взять часть предмета? Оптимизация туристического маршрута, Взаимозависимые элементы, Может ли оказаться, что решение требует более двух «подрюкзаков»? Возможно ли, что при лучшем решении в рюкзаке остается пустое место? Упражнения, Самая длинная общая подстрока, Построение таблицы, Заполнение таблицы, Решение, Самая длинная общая подпоследовательность Самая длинная общая подпоследовательность — решение, Упражнения, Шпаргалка.
Алгоритм k ближайших соседей:
Апельсины и грейпфруты, Построение рекомендательной системы, Извлечение признаков, Упражнения, Регрессия, Выбор признаков, Упражнения, Знакомство с машинным обучением OCR, Построение спам-фильтра, Прогнозы на биржевых торгах, Шпаргалка.
Что дальше?
Деревья, Инвертированные индексы, Преобразование Фурье, Параллельные алгоритмы , MapReduce, Для чего нужны распределенные алгоритмы? Функция map, Функция reduce, Фильтры Блума и HyperLogLog, Фильтры Блума, HyperLogLog, Алгоритмы SHA, Сравнение файлов, Проверка паролей, Локально-чувствительное хеширование, Обмен ключами Диффи—Хеллмана, Линейное программирование, Эпилог, Ответы к упражнениям.
Знакомство с алгоритмами:
Введение, Что вы узнаете об эффективности алгоритмов, Что вы узнаете о решении задач, Бинарный поиск, Более эффективный поиск, Упражнения, Время выполнения, «O-большое», Время выполнения алгоритмов растет с разной скоростью,
Наглядное представление «O-большое», «O-большое» определяет время выполнения в худшем случае, Типичные примеры «O-большого», Упражнения, Задача о коммивояжере,Шпаргалка.
Сортировка выбором:
Как работает память, Массивы и связанные списки, Связанные списки, Массивы, Терминология, Упражнения, Вставка в середину списка, Удаление, Упражнения, Сортировка выбором, Пример кода, Шпаргалка.
Рекурсия:
Рекурсия, Базовый случай и рекурсивный случай, Стек, Стек вызовов, Упражнения, Стек вызовов с рекурсией, Упражнения, Шпаргалка.
Быстрая сортировка:
«Разделяй и властвуй», Упражнения, Быстрая сортировка, Снова об «O-большом», Сортировка слиянием и быстрая сортировка, Средний и худший случай, Упражнения, Шпаргалка.
Хеш-таблицы:
Хеш-функции, Упражнения, Примеры использования, Использование хеш-таблиц для поиска, Исключение дубликатов, Использование хеш-таблицы как кэша, Шпаргалка, Коллизии, Быстродействие Коэффициент заполнения, Хорошая хеш-функция, Упражнения,Шпаргалка.
Поиск в ширину:
Знакомство с графами, Что такое граф? Поиск в ширину, Поиск кратчайшего пути, Очереди, Упражнения, Реализация графа, Реализация алгоритма, Время выполнения, Упражнения,Шпаргалка.
Алгоритм Дейкстры:
Работа с алгоритмом Дейкстры, Терминология, История одного обмена, Ребра с отрицательным весом, Реализация, Упражнения, Шпаргалка.
Жадные алгоритмы:
Задача составления расписания, Задача о рюкзаке, Упражнения, Задача о покрытии множества, Приближенные алгоритмы, Упражнения, NP-полные задачи, Задача о коммивояжере — шаг за шагом, Как определить, что задача является NP-полной? Упражнения, Шпаргалка.
Динамическое программирование:
Задача о рюкзаке, Простое решение, Динамическое программирование, Задача о рюкзаке: вопросы, Что произойдет при добавлении элемента? Упражнения, Что произойдет при изменении порядка строк? Можно ли заполнять таблицу по столбцам, а не по строкам? Что произойдет при добавлении меньшего элемента? Можно ли взять часть предмета? Оптимизация туристического маршрута, Взаимозависимые элементы, Может ли оказаться, что решение требует более двух «подрюкзаков»? Возможно ли, что при лучшем решении в рюкзаке остается пустое место? Упражнения, Самая длинная общая подстрока, Построение таблицы, Заполнение таблицы, Решение, Самая длинная общая подпоследовательность Самая длинная общая подпоследовательность — решение, Упражнения, Шпаргалка.
Алгоритм k ближайших соседей:
Апельсины и грейпфруты, Построение рекомендательной системы, Извлечение признаков, Упражнения, Регрессия, Выбор признаков, Упражнения, Знакомство с машинным обучением OCR, Построение спам-фильтра, Прогнозы на биржевых торгах, Шпаргалка.
Что дальше?
Деревья, Инвертированные индексы, Преобразование Фурье, Параллельные алгоритмы , MapReduce, Для чего нужны распределенные алгоритмы? Функция map, Функция reduce, Фильтры Блума и HyperLogLog, Фильтры Блума, HyperLogLog, Алгоритмы SHA, Сравнение файлов, Проверка паролей, Локально-чувствительное хеширование, Обмен ключами Диффи—Хеллмана, Линейное программирование, Эпилог, Ответы к упражнениям.