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