Алгоритмы на Java

Роберт Седжвик, Кевин Уэйн

Книга Седжвика и Уэйна «Алгоритмы на Java» является классическим справочным руководством в котором содержится необходимый объем знаний для программиста в области алгоритмов, накопленных за последние несколько десятилетий

В книге «Алгоритмы на Java» представлен широкий спектр рассматриваемых тем: исчерпывающее толкование структур данных и алгоритмов сортировки, поиска, обработки графов и строк, включая пятьдесят алгоритмов, которые должен знать каждый программист. Описываются новые реализации алгоритмов на Java, написанные в ясном модульном стиле, при котором весь код доступен читателю и полностью готов к использованию. В книге изучение алгоритмов на Java ведется в контексте важнейших научных, инженерных и коммерческих приложений. Клиенты и алгоритмы выражены с помощью реального кода, а не псевдокода, как во многих других книгах.

Книга «Алгоритмы на Java» отличается от множества других ясным и кратким текстом, детальными примерами с иллюстрациями, тщательно подобранным кодом, историческим и научным контекстом, а также упражнениями для самостоятельной проработки на всех уровнях. В книге представлены точные соображения относительно производительности, поддерживаемые соответствующими математическими моделями и эмпирическими исследованиями, которые подтверждают достоверность этих моделей

Издательство: Вильямс, 2012 г.

ISBN 978-5-8459-1781-2

Количество страниц: 848.

Содержание книги «Алгоритмы на Java»:

13 Об авторах
14 Предисловие
- 14 Отличительные черты
- 15 Сайт книги
- 16 Использование в учебном плане
- 17 Контекст
- 17 Благодарности
- 18 От издательства
19 Глава 1. Основные понятия
- 20 Алгоритмы
- 22 Краткий обзор тем
- 24 1.1. Базовая модель программирования
  - 26 Базовая структура Java-программы
  - 27 Примитивные типы данных и выражения
  - 29 Операторы
  - 31 Сокращенные обозначения
  - 33 Массивы
  - 36 Статические методы
  - 42 API-иитерфейсы
  - 46 Строки
  - 48 Ввод и вывод
  - 58 Бинарный поиск
  - 62 Перспектива
  - 63 Вопросы и ответы
  - 65 Упражнения
  - 69 Творческие задачи
  - 70 Эксперименты
- 72 1.2. Абстракция данных
  - 72 Использование абстрактных типов данных
  - 82 Примеры абстрактных типов данных
  - 91 Реализация абстрактного типа данных
  - 97 Другие реализации АТД
  - 101 Проектирование типа данных
  - 115 Вопросы и ответы
  - 118 Упражнения
  - 119 Творческие задачи
- 122 1.3. Контейнеры, очереди и стеки
  - 122 API-интерфейсы
  - 132 Реализация коллекций
  - 142 Связные списки
  - 153 Обзор
  - 155 Вопросы и ответы
  - 157 Упражнения
  - 159 Упражнения со связными списками
  - 161 Творческие задачи
- 165 1.4. Анализ алгоритмов
  - 165 Научный метод
  - 166 Наблюдения
  - 171 Математические модели
  - 177 Классификация порядков роста
  - 180 Проектирование быстрых алгоритмов
  - 184 Эксперименты с удвоением
  - 186 Предостережения
  - 188 Учет зависимости от входных данных
  - 191 Память
  - 197 Перспектива
  - 198 Вопросы и ответы
  - 200 Упражнения
  - 201 Творческие задачи
  - 204 Эксперименты
- 206 1.5. Учебный пример: объединение-сортировка
  - 206 Динамическая связность
  - 211 Реализации
  - 221 Перспектива
  - 223 Вопросы и ответы
  - 223 Упражнения
  - 224 Творческие задачи
  - 226 Эксперименты
227 Глава 2. Сортировка
- 229 2.1. Элементарные алгоритмы сортировки
  - 229 Правила игры
  - 233 Сортировка выбором
  - 235 Сортировка вставками
  - 237 Визуализация алгоритмов сортировки
  - 238 Сравнение двух алгоритмов сортировки
  - 241 Сортировка Шелла
  - 246 Вопросы и ответы
  - 246 Упражнения
  - 247 Творческие задачи
  - 249 Эксперименты
- 252 2.2. Сортировка слиянием
  - 252 Абстрактное слияние на месте
  - 253 Нисходящая сортировка слиянием
  - 258 Восходящая сортировка слиянием
  - 260 Сложность сортировки
  - 264 Вопросы и ответы
  - 264 Упражнения
  - 265 Творческие задачи
  - 266 Эксперименты
- 268 2.3. Быстрая сортировка
  - 268 Базовый алгоритм
  - 272 Характеристики производительности
  - 274 Алгоритмические усовершенствования
  - 280 Вопросы и ответы
  - 281 Упражнения
  - 282 Творческие задачи
  - 284 Эксперименты
- 285 2.4. Очереди с приоритетами
  - 286 API-интерфейс
  - 288 Элементарные реализации
  - 290 Определения пирамиды
  - 300 Пирамидальная сортировка
  - 304 Вопросы и ответы
  - 305 Упражнения
  - 307 Творческие задачи
  - 310 Эксперименты
- 312 2.5. Применения
  - 312 Сортировка различных видов данных
  - 316 Какой же алгоритм сортировки лучше использовать?
  - 320 Сведения
  - 323 Краткий обзор применений сортировки
  - 326 Вопросы и ответы
  - 326 Упражнения
  - 328 Творческие задачи
  - 330 Эксперименты
331 Глава 3. Поиск
- 333 3.1. Таблицы имен
  - 333 API
  - 336 Упорядоченные таблицы имен
  - 340 Примеры клиентов
  - 343 Последовательный поиск в неупорядоченном связном списке
  - 346 Бинарный поиск в упорядоченном массиве
  - 350 Анализ бинарного поиска
  - 352 Предварительные выводы
  - 355 Вопросы и ответы
  - 356 Упражнения
  - 357 Творческие задачи
  - 359 Эксперименты
- 361 3.2. Деревья бинарного поиска
  - 362 Базовая реализация
  - 366 Анализ
  - 369 Методы, основанные на упорядоченности, и удаление
  - 377 Вопросы и ответы
  - 377 Упражнения
  - 380 Творческие задачи
  - 381 Эксперименты
- 383 3.3. Сбалансированные деревья поиска
  - 383 2-3-деревья поиска
  - 389 Красно-черные ДБП
  - 396 Реализация
  - 398 Удаление
  - 401 Свойства красно-черных деревьев
  - 405 Вопросы и ответы
  - 405 Упражнения
  - 407 Творческие задачи
  - 411 Эксперименты
- 412 3.4. Хеш-таблицы
  - 413 Хеш-функции
  - 418 Хеширование с раздельными цепочками
  - 422 Хеширование с линейным опробованием
  - 428 Изменение размера массива
  - 429 Память
  - 431 Вопросы и ответы
  - 433 Упражнения
  - 435 Творческие задачи
  - 437 Эксперименты
- 438 3.5. Применения
  - 438 Так какую же реализацию таблицы имен лучше использовать?
  - 440 API множеств
  - 443 Клиенты словарей
  - 448 Клиенты индексации
  - 453 Разреженные векторы
  - 457 Вопросы и ответы
  - 458 Упражнения
  - 459 Творческие задачи
  - 461 Эксперименты
463 Глава 4. Графы
- 467 4.1. Неориентированные графы
  - 468 Термины
  - 470 Тип данных неориентированного графа
  - 477 Поиск в глубину
  - 482 Нахождение путей
  - 486 Поиск в ширину
  - 490 Связные компоненты
  - 496 Символьные графы
  - 504 Резюме
  - 504 Вопросы и ответы
  - 505 Упражнения
  - 508 Творческие задачи
  - 509 Эксперименты
- 511 4.2. Ориентированные графы
  - 511 Термины
  - 512 Тип данных орграфа
  - 516 Достижимость в орграфах
  - 519 Циклы и ориентированные ациклические графы
  - 530 Сильная связность в орграфах
  - 539 Резюме
  - 539 Вопросы и ответы
  - 540 Упражнения
  - 541 Творческие задачи
  - 543 Эксперименты
- 545 4.3. Минимальные остовные деревья
  - 548 Базовые принципы
  - 549 Тип данных для графа с взвешенными ребрами
  - 554 API МОД и клиент тестирования
  - 557 Алгоритм Прима
  - 561 «Энергичный» вариант алгоритма Прима
  - 565 Алгоритм Крускала
  - 568 Перспектива
  - 570 Вопросы и ответы
  - 570 Упражнения
  - 572 Творческие задачи
  - 573 Эксперименты
- 575 4.4. Кратчайшие пути
  - 576 Свойства кратчайших путей
  - 578 Типы данных орграфа с взвешенными ребрами
  - 585 Теоретические основы разработки алгоритмов поиска кратчайших путей
  - 587 Алгоритм Дейкстры
  - 592 Ациклические орграфы с взвешенными ребрами
  - 603 Кратчайшие пути в орграфах с взвешенными ребрами общего вида
  - 617 Перспектива
  - 618 Вопросы и ответы
  - 618 Упражнения
  - 620 Творческие задачи
  - 623 Эксперименты
625 Глава 5. Строки
- 626 Правила игры
- 628 Алфавиты
- 632 5.1. Сортировка строк
  - 632 Распределяющий подсчет
  - 636 LSD-сортировка строк
  - 639 MSD-сортировка строк
  - 648 Трехчастная быстрая сортировка строк
  - 652 Каким алгоритмом сортировки строк воспользоваться?
  - 653 Вопросы и ответы
  - 653 Упражнения
  - 654 Творческие задачи
  - 655 Эксперименты
- 656 5.2. Trie-деревья
  - 657 Trie-деревья
  - 668 Свойства trie-деревьев
  - 672 Trie-деревья тернарного поиска (ТТП)
  - 674 Свойства ТТП
  - 676 Какую реализацию таблицы символьных имен следует использовать?
  - 677 Вопросы и ответы
  - 677 Упражнения
  - 678 Творческие задачи
  - 680 Эксперименты
- 681 5.3. Поиск подстрок
  - 681 Краткая история вопроса
  - 682 Примитивный поиск подстроки
  - 684 Алгоритм поиска подстроки Кнута-Морриса-Пратта
  - 692 Поиск подстроки методом Бойера-Мура
  - 697 Дактилоскопический поиск Рабина-Карпа
  - 701 Резюме
  - 702 Вопросы и ответы
  - 703 Упражнения
  - 704 Творческие задачи
  - 706 Эксперименты
- 707 5.4. Регулярные выражения
  - 708 Описание образцов с помощью регулярных выражений
  - 710 Сокращения
  - 711 Регулярные выражения в приложениях
  - 713 Недетерминированные конечные автоматы
  - 716 Моделирование НКА
  - 718 Построение НКА, соответствующего РВ
  - 723 Вопросы и ответы
  - 723 Упражнения
  - 724 Творческие задачи
- 726 5.5. Сжатие данных
  - 726 Правила игры
  - 727 Чтение и запись двоичных данных
  - 731 Ограничения
  - 734 Разминка: геномика
  - 737 Кодирование по длинам серий
  - 740 Сжатие Хаффмана
  - 760 Вопросы и ответы
  - 761 Упражнения
  - 763 Творческие задачи
765 Глава 6. Контекст
- 769 6.1. Событийное моделирование
  - 769 Модель жестких дисков
  - 769 Временное моделирование
  - 770 Событийное моделирование
  - 770 Предсказание столкновений
  - 771 Выполнение столкновений
  - 772 Отмена событий
  - 772 Частицы
  - 773 События
  - 774 Код моделирования
  - 777 Производительность
  - 778 Упражнения
- 780 6.2. B-деревья
  - 780 Модель стоимости
  - 780 B-деревья
  - 781 Соглашения
  - 782 Поиск и вставка
  - 783 Представление
  - 786 Производительность
  - 786 Память
  - 788 Упражнения
- 790 6.3. Суффиксные массивы
  - 790 Максимальная повторяющаяся подстрока
  - 790 Примитивное решение
  - 791 Решение с сортировкой суффиксов
  - 792 Индексация строки
  - 794 API и код клиента
  - 796 Реализация
  - 797 Производительность
  - 798 Усовершенствованные реализации
  - 799 Упражнения
- 802 6.4. Алгоритмы для сетевых потоков
  - 802 Физическая модель
  - 804 Определения
  - 805 API
  - 807 Алгоритм Форда-Фалкерсона
  - 808 Теорема о максимальном потоке и минимальном сечении
  - 810 Остаточная сеть
  - 812 Метод кратчайшего расширяющего пути
  - 814 Производительность
  - 816 Другие реализации
  - 817 Упражнения
- 820 6.5. Сведение и неразрешимость
  - 820 Сведение
  - 826 Неразрешимость
  - 836 Упражнения
838 Предметный указатель