Фундаментальные алгоритмы на C. Части 1 - 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах

Роберт Седжвик

Эта книга посвящена глубокому исследованию всех основополагающих концепций и алгоритмов, которые, несомненно, относятся к категории «вечных». Тщательным образом проштудировав их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда.

Краткость, точность, выверенность, актуальность, изобилие примеров и учебных заданий - вот лишь небольшой перечень очевидных достоинств книги. Иллюстрация алгоритмов на одном из наиболее эффективных языков программирования С лишний раз подчеркивает их популярность и «вечность». Подробно рассматривается широчайший спектр фундаментальных алгоритмов на графах, в числе которых: поиск в орграфах, неорграфах и сетях; построение минимальных остовных деревьев и кратчайших путей; вычисление потоков в сетях с различными характеристиками. Большое внимание уделяется рабочим характеристикам алгоритмов, а также их математическому выводу.

Книгу можно использовать в качестве курса лекций (как студентами, так и преподавателями), справочного пособия или просто «романа», получая при этом ни с чем не сравнимое удовольствие.

Издательство: ДиаСофтЮП, 2003 г.

Рекомендуем обратить внимания на книги Роберта Седжвика:

Фундаментальные алгоритмы на C. Части 1 - 4. Анализ. Структуры данных. Сортировка. Поиск

Фундаментальные алгоритмы на C. Часть 5. Алгоритмы на графах

Алгоритмы на C++

ISBN 5-93772-083-0, 0-201-31452-5, 0-201-31663-3

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

Содержание книги «Фундаментальные алгоритмы на C. Части 1 - 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах»:

  • 17 Часть 1. Анализ
  • 18 Глава 1. Введение
    • 19 1.1. Алгоритмы
    • 21 1.2. Пример задачи связности
    • 25 1.3. Алгоритмы объединения-поиска
    • 36 1.4. Перспективы
    • 38 1.5. Обзор тем
  • 40 Глава 2. Принципы анализа алгоритмов
    • 41 2.1. Реализация и эмпирический анализ
    • 45 2.2. Анализ алгоритмов
    • 48 2.3. Возрастание функций
    • 54 2.4. O-нотация
    • 59 2.5. Простейшие рекурсии
    • 63 2.6. Примеры анализа алгоритмов
    • 68 2.7. Гарантии, предсказания и ограничения
    • 72 Ссылки к части 1
  • 74 Часть 2. Структуры данных
  • 75 Глава 3. Элементарные структуры данных
    • 76 3.1. Строительные блоки
    • 86 3.2. Массивы
    • 92 3.3. Связные списки
    • 98 3.4. Обработка простых списков
    • 106 3.5. Распределение памяти под списки
    • 109 3.6. Строки
    • 114 3.7. Составные структуры данных
  • 124 Глава 4. Абстрактные типы данных
    • 128 4.1. Абстрактные объекты и коллекции объектов
    • 131 4.2. АТД для стека магазинного типа
    • 134 4.3. Примеры клиентов, использующих ATД стека
    • 140 4.4. Реализации АТД стека
    • 144 4.5. Создание нового АТД
    • 147 4.6. Очереди FIFO и обобщенные очереди
    • 155 4.7. Повторяющиеся и индексные элементы
    • 160 4.8. АТД первого класса
    • 170 4.9. Пример использования АТД в приложениях
    • 175 4.10. Перспективы
  • 177 Глава 5. Рекурсия и деревья
    • 178 5.1. Рекурсивные алгоритмы
    • 185 5.2. Разделяй и властвуй
    • 199 5.3. Динамическое программирование
    • 206 5.4. Деревья
    • 215 5.5. Математические свойства бинарных деревьев
    • 218 5.6. Обход дерева
    • 224 5.7. Рекурсивные алгоритмы для бинарных деревьев
    • 229 5.8. Обход графа
    • 235 5.9. Перспективы
    • 236 Ссылки для части 2
  • 237 Часть 3. Сортировка
  • 238 Глава 6. Элементарные методы сортировки
    • 240 6.1. Правила игры
    • 246 6.2. Сортировка выбором
    • 247 6.3. Сортировка вставками
    • 250 6.4. Пузырьковая сортировка
    • 252 6.5. Характеристики производительности элементарных методов сортировки
    • 258 6.6. Сортировка Шелла
    • 267 6.7. Сортировка других типов данных
    • 271 6.8. Сортировка по индексам и указателям
    • 278 6.9. Сортировка связных списков
    • 282 6.10. Метод распределяющего подсчета
  • 285 Глава 7. Быстрая сортировка
    • 286 7.1. Базовый алгоритм
    • 291 7.2. Характеристики производительности быстрой сортировки
    • 295 7.3. Размер стека
    • 299 7.4. Подфайлы небольшого размера
    • 302 7.5. Метод разделения с вычислением медианы из трех элементов
    • 307 7.6. Дублированные
    • 310 7.7. Строки и векторы
    • 312 7.8. Выборка
  • 316 Глава 8. Слияние и сортировка слиянием
    • 318 8.1. Двухпутевое слияние
    • 320 8.2. Абстрактное обменное слияние
    • 322 8.3. Нисходящая сортировка слиянием
    • 325 8.4. Усовершенствования базового алгоритма
    • 328 8.5. Восходящая сортировка слиянием
    • 331 8.6. Производительность сортировки слиянием
    • 335 8.7. Реализации сортировки слиянием для связных списков
    • 338 8.8. Возврат к рекурсии
  • 340 Глава 9. Очереди с приоритетами и пирамидальная сортировка
    • 344 9.1. Элементарные реализации
    • 347 9.2. Пирамидальная структура данных
    • 349 9.3. Алгоритмы на пирамидальных деревьях
    • 356 9.4. Пирамидальная сортировка
    • 363 9.5. Абстрактный тип данных очереди с приоритетами
    • 368 9.6. Очереди с приоритетами для индексных элементов
    • 372 9.7. Биномиальные очереди
  • 383 Глава 10. Поразрядная сортировка
    • 385 10.1. Биты, байты и слова
    • 388 10.2. Бинарная быстрая сортировка
    • 394 10.3. Поразрядная сортировка MSD
    • 402 10.4. Трехпутевая поразрядная быстрая сортировка
    • 406 10.5. Поразрядная сортировка LSD
    • 410 10.6. Характеристики производительности поразрядных сортировок
    • 414 10.7. Сортировки с сублинейным временем выполнения
  • 419 Глава 11. Специальные методы сортировки
    • 421 11.1. Нечетно-четная сортировка слиянием Бэтчера
    • 426 11.2. Сети сортировки
    • 434 11.3. Внешняя сортировка
    • 441 11.4. Реализации сортировки-слияния
    • 448 11.5. Параллельная сортировка-слияние
    • 453 Ссылки для части 3
  • 455 Часть 4. Поиск
  • 456 Глава 12. Таблицы символов и деревья бинарного поиска
    • 458 12.1. Абстрактный тип данных таблицы символов
    • 463 12.2. Распределяющий поиск
    • 466 12.3. Последовательный поиск
    • 472 12.4. Бинарный поиск
    • 477 12.5. Деревья бинарного поиска
    • 483 12.6. Характеристики производительности деревьев бинарного поиска
    • 486 12.7. Индексные реализации таблиц символов
    • 490 12.8. Вставка в корень в деревьях бинарного поиска
    • 495 12.9. Реализации других функций АТД с помощью BST-дерева
  • 504 Глава 13. Сбалансированные деревья
    • 508 13.1. Рандомизированные BST-деревья
    • 514 13.2. Скошенные деревья бинарного поиска
    • 520 13.3. Нисходящие 2-3-4-деревья
    • 525 13.4. Красно-черные, или RB-деревья
    • 535 13.5. Списки пропусков
    • 543 13.6. Характеристики производительности
  • 547 Глава 14. Хеширование
    • 548 14.1. Хеш-функции
    • 558 14.2. Раздельное связывание
    • 562 14.3. Линейное зондирование
    • 567 14.4. Двойное хеширование
    • 573 14.5. Динамические хеш-таблицы
    • 577 14.6. Перспективы
  • 582 Глава 15. Поразрядный поиск
    • 583 15.1. Деревья цифрового поиска
    • 588 15.2. Trie-деревья
    • 597 15.3. Patricia-деревья
    • 605 15.4. Многопутевые trie-деревья и TST-деревья
    • 622 15.5. Алгоритмы индексирования текстовых строк
  • 627 Глава 16. Внешний поиск
    • 629 16.1. Правила игры
    • 631 16.2. Индексно-последовательный доступ
    • 634 16.3. B-деревья
    • 646 16.4. Расширяемое хеширование
    • 657 16.5. Перспективы
    • 660 Ссылки для части 4
  • 663 Предметный указатель к частям 1-4
  • 673 Часть 5. Алгоритмы на графах
  • 674 Глава 17. Виды графов и их свойства
    • 678 17.1. Глоссарий
    • 687 17.2. АТД графа
    • 691 17.3. Представление графа в виде матрицы смежности
    • 697 17.4. Представление графа в виде списков смежности
    • 700 17.5. Вариации, расширения и затраты
    • 709 17.6. Генераторы графов
    • 720 17.7. Простые, эйлеровы и гамильтоновы пути
    • 734 17.8. Задачи обработки графов
  • 744 Глава 18. Поиск на графе
    • 745 18.1. Исследование лабиринта
    • 750 18.2. Поиск в глубину
    • 755 18.3. Функции АТД поиска на графе
    • 760 18.4. Свойства лесов DFS
    • 767 18.5. Алгоритмы DFS
    • 774 18.6. Разделимость и двусвязность
    • 782 18.7. Поиск в ширину
    • 792 18.8. Обобщенный поиск на графах
    • 800 18.9. Анализ алгоритмов на графах
  • 807 Глава 19. Орграфы и ориентированные ациклические графы
    • 810 19.1. Глоссарий и правила игры
    • 819 19.2. Анатомия DFS в орграфах
    • 828 19.3. Достижимость и транзитивное замыкание
    • 840 19.4. Отношения эквивалентности и частичные порядки
    • 844 19.5. DAG-графы
    • 849 19.6. Топологическая сортировка
    • 859 19.7. Достижимость в DAG-графах
    • 862 19.8. Сильные компоненты в орграфах
    • 872 19.9. Еще раз о транзитивном замыкании
    • 876 19.10. Перспективы
  • 880 Глава 20. Минимальные остовные деревья
    • 883 20.1. Представления
    • 889 20.2. Основные принципы алгоритмов построения дерева MST
    • 896 20.3. Алгоритм Прима и поиск по приоритету
    • 907 20.4. Алгоритм Крускала
    • 913 20.5. Алгоритм Борувки
    • 916 20.6. Сравнения и усовершенствования
    • 922 20.7. Евклидово MST-дерево
  • 925 Глава 21. Кратчайшие пути
    • 933 21.1. Основные принципы
    • 938 21.2. Алгоритм Дейкстры
    • 948 21.3. Кратчайшие пути между всеми парами вершин
    • 956 21.4. Кратчайшие пути в ациклических сетях
    • 964 21.5. Евклидовы сети
    • 969 21.6. Сведение
    • 984 21.7. Отрицательные веса
    • 1001 21.8. Перспективы
  • 1003 Глава 22. Потоки в сетях
    • 1010 22.1. Транспортные сети
    • 1022 22.2. Алгоритмы поиска максимального потока методом аугментального пути
    • 1047 22.3. Алгоритмы определения максимальных потоков методом выталкивания превосходящего потока
    • 1061 22.4. Сведения к максимальному потоку
    • 1076 22.5. Потоки минимальной стоимости
    • 1089 22.6. Сетевой симплексный алгоритм
    • 1108 22.7. Сведения к задаче о потоке минимальной стоимости
    • 1117 22.8. Перспективы
    • 1121 Ссылки, использованные в пятой части
  • 1123 Предметный указатель к части 5

Инструкция как скачать книгу Роберт Седжвик: Фундаментальные алгоритмы на C. Части 1 - 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
Фундаментальные алгоритмы на C. Части 1 - 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах
Рейтинг книги:
0 голосов
1141

Поиск книг:




При поиске учитываются только слова, длина которых больше 3-х символов.

Статистика: