Книга Седжвика и Уэйна "Алгоритмы на Java" является классическим справочным руководством в котором содержится необходимый объем знаний для программиста в области алгоритмов, накопленных за последние несколько десятилетий. В книге "Алгоритмы на Java" представлен широкий спектр рассматриваемых тем: исчерпывающее толкование структур данных и алгоритмов сортировки, поиска, обработки графов и строк, включая пятьдесят алгоритмов, которые должен знать каждый программист. Описываются новые реализации алгоритмов на Java, написанные в ясном модульном стиле, при котором весь код доступен читателю и полностью готов к использованию. В книге изучение алгоритмов на Java ведется в контексте важнейших научных, инженерных и коммерческих приложений. Клиенты и алгоритмы выражены с помощью реального кода, а не псевдокода, как во многих других книгах. Книга "Алгоритмы на Java" отличается от множества других ясным и кратким текстом, детальными примерами с иллюстрациями, тщательно подобранным кодом, историческим и научным контекстом, а также упражнениями для самостоятельной проработки на всех уровнях. В книге представлены точные соображения относительно производительности, поддерживаемые соответствующими математическими моделями и эмпирическими исследованиями, которые подтверждают достоверность этих моделей.
Об авторах Предисловие Отличительные черты Сайт книги Использование в учебном плане Контекст Благодарности От издательства Глава 1. Основные понятия Алгоритмы Краткий обзор тем 1.1. Базовая модель программирования Базовая структура Java-программы Примитивные типы данных и выражения Операторы Сокращенные обозначения Массивы Статические методы API-иитерфейсы Строки Ввод и вывод Бинарный поиск Перспектива Вопросы и ответы Упражнения Творческие задачи Эксперименты 1.2. Абстракция данных Использование абстрактных типов данных Примеры абстрактных типов данных Реализация абстрактного типа данных Другие реализации АТД Проектирование типа данных Вопросы и ответы Упражнения Творческие задачи 1.3. Контейнеры, очереди и стеки API-интерфейсы Реализация коллекций Связные списки Обзор Вопросы и ответы Упражнения Упражнения со связными списками Творческие задачи 1.4. Анализ алгоритмов Научный метод Наблюдения Математические модели Классификация порядков роста Проектирование быстрых алгоритмов Эксперименты с удвоением Предостережения Учет зависимости от входных данных Память Перспектива Вопросы и ответы Упражнения Творческие задачи Эксперименты 1.5. Учебный пример: объединение-сортировка Динамическая связность Реализации Перспектива Вопросы и ответы Упражнения Творческие задачи Эксперименты Глава 2. Сортировка 2.1. Элементарные алгоритмы сортировки Правила игры Сортировка выбором Сортировка вставками Визуализация алгоритмов сортировки Сравнение двух алгоритмов сортировки Сортировка Шелла Вопросы и ответы Упражнения Творческие задачи Эксперименты 2.2. Сортировка слиянием Абстрактное слияние на месте Нисходящая сортировка слиянием Восходящая сортировка слиянием Сложность сортировки Вопросы и ответы Упражнения Творческие задачи Эксперименты 2.3. Быстрая сортировка Базовый алгоритм Характеристики производительности Алгоритмические усовершенствования Вопросы и ответы Упражнения Творческие задачи Эксперименты 2.4. Очереди с приоритетами API-интерфейс Элементарные реализации Определения пирамиды Пирамидальная сортировка Вопросы и ответы Упражнения Творческие задачи Эксперименты 2.5. Применения Сортировка различных видов данных Какой же алгоритм сортировки лучше использовать? Сведения Краткий обзор применений сортировки Вопросы и ответы Упражнения Творческие задачи Эксперименты Глава 3. Поиск 3.1. Таблицы имен API Упорядоченные таблицы имен Примеры клиентов Последовательный поиск в неупорядоченном связном списке Бинарный поиск в упорядоченном массиве Анализ бинарного поиска Предварительные выводы Вопросы и ответы Упражнения Творческие задачи Эксперименты 3.2. Деревья бинарного поиска Базовая реализация Анализ Методы, основанные на упорядоченности, и удаление Вопросы и ответы Упражнения Творческие задачи Эксперименты 3.3. Сбалансированные деревья поиска 2-3-деревья поиска Красно-черные ДБП Реализация Удаление Свойства красно-черных деревьев Вопросы и ответы Упражнения Творческие задачи Эксперименты 3.4. Хеш-таблицы Хеш-функции Хеширование с раздельными цепочками Хеширование с линейным опробованием Изменение размера массива Память Вопросы и ответы Упражнения Творческие задачи Эксперименты 3.5. Применения Так какую же реализацию таблицы имен лучше использовать? API множеств Клиенты словарей Клиенты индексации Разреженные векторы Вопросы и ответы Упражнения Творческие задачи Эксперименты Глава 4. Графы 4.1. Неориентированные графы Термины Тип данных неориентированного графа Поиск в глубину Нахождение путей Поиск в ширину Связные компоненты Символьные графы Резюме Вопросы и ответы Упражнения Творческие задачи Эксперименты 4.2. Ориентированные графы Термины Тип данных орграфа Достижимость в орграфах Циклы и ориентированные ациклические графы Сильная связность в орграфах Резюме Вопросы и ответы Упражнения Творческие задачи Эксперименты 4.3. Минимальные остовные деревья Базовые принципы Тип данных для графа с взвешенными ребрами API МОД и клиент тестирования Алгоритм Прима «Энергичный» вариант алгоритма Прима Алгоритм Крускала Перспектива Вопросы и ответы Упражнения Творческие задачи Эксперименты 4.4. Кратчайшие пути Свойства кратчайших путей Типы данных орграфа с взвешенными ребрами Теоретические основы разработки алгоритмов поиска кратчайших путей Алгоритм Дейкстры Ациклические орграфы с взвешенными ребрами Кратчайшие пути в орграфах с взвешенными ребрами общего вида Перспектива Вопросы и ответы Упражнения Творческие задачи Эксперименты Глава 5. Строки Правила игры Алфавиты 5.1. Сортировка строк Распределяющий подсчет LSD-сортировка строк MSD-сортировка строк Трехчастная быстрая сортировка строк Каким алгоритмом сортировки строк воспользоваться? Вопросы и ответы Упражнения Творческие задачи Эксперименты 5.2. Trie-деревья Trie-деревья Свойства trie-деревьев Trie-деревья тернарного поиска (ТТП) Свойства ТТП Какую реализацию таблицы символьных имен следует использовать? Вопросы и ответы Упражнения Творческие задачи Эксперименты 5.3. Поиск подстрок Краткая история вопроса Примитивный поиск подстроки Алгоритм поиска подстроки Кнута-Морриса-Пратта Поиск подстроки методом Бойера-Мура Дактилоскопический поиск Рабина-Карпа Резюме Вопросы и ответы Упражнения Творческие задачи Эксперименты 5.4. Регулярные выражения Описание образцов с помощью регулярных выражений Сокращения Регулярные выражения в приложениях Недетерминированные конечные автоматы Моделирование НКА Построение НКА, соответствующего РВ Вопросы и ответы Упражнения Творческие задачи 5.5. Сжатие данных Правила игры Чтение и запись двоичных данных Ограничения Разминка: геномика Кодирование по длинам серий Сжатие Хаффмана Вопросы и ответы Упражнения Творческие задачи Глава 6. Контекст 6.1. Событийное моделирование Модель жестких дисков Временное моделирование Событийное моделирование Предсказание столкновений Выполнение столкновений Отмена событий Частицы События Код моделирования Производительность Упражнения 6.2. B-деревья Модель стоимости B-деревья Соглашения Поиск и вставка Представление Производительность Память Упражнения 6.3. Суффиксные массивы Максимальная повторяющаяся подстрока Примитивное решение Решение с сортировкой суффиксов Индексация строки API и код клиента Реализация Производительность Усовершенствованные реализации Упражнения 6.4. Алгоритмы для сетевых потоков Физическая модель Определения API Алгоритм Форда-Фалкерсона Теорема о максимальном потоке и минимальном сечении Остаточная сеть Метод кратчайшего расширяющего пути Производительность Другие реализации Упражнения 6.5. Сведение и неразрешимость Сведение Неразрешимость Упражнения Предметный указатель
