Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Седжвик Р. — Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах
Седжвик Р. — Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


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

Автор: Седжвик Р.

Аннотация:

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


Язык: ru

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2002

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

Добавлена в каталог: 23.04.2011

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Абстрактный тип данных (АТД)      21 31
Алгоритм      36 93 334 376
Алгоритм BFS (breadth-first search - поиск в ширину)      94
Алгоритм DFS (depth-first search - поиск в глубину)      69 93 117
Алгоритм DFS по матрице смежности      108
Алгоритм DFS по спискам смежных вершин      108
Алгоритм DFS рекурсивный      93
Алгоритм Беллмана — Форда      347
Алгоритм Борувки      247 266
Алгоритм быстрого объединения      см. "Метод быстрого объединения"
Алгоритм быстрого поиска      см. "Метод быстрого поиска"
Алгоритм выталкивания избыточного потока      411
Алгоритм выталкивания избыточного потока, худший случай      411
Алгоритм выталкивания превосходящего потока      412
Алгоритм вычеркивания циклов      438 442
Алгоритм вычисления максимального потока      386 387
Алгоритм Габова      219
Алгоритм Дейкстры      294
Алгоритм динамический      36
Алгоритм интерактивный      36
Алгоритм Косарайю      214
Алгоритм Крускала      246 260
Алгоритм определения максимальных потоков      402
Алгоритм определения самого длинного аугментального пути      389
Алгоритм поиска кратчайшего маршрута      86
Алгоритм поиска максимального потока      376
Алгоритм поиска на графе      93
Алгоритм Прима      246 250 259
Алгоритм сетевой симплексный      86 444 449
Алгоритм сжатия пути      см. "Метод сжатия пути"
Алгоритм Тарьяна      213 217
Алгоритм топологической сортировки      205
Алгоритм Уоршалла      180
Алгоритм Флойда      184 304 345
Алгоритм Форда — Фалкерсона      377 см.
Алгоритм Форда — Фалкерсона, худший случай      404
Алгоритм эффективный      334
Алгоритм Ярника      258
Арбитражная операция      343
Бахрома (fringe)      141 254 298 см.
Библиотечное программирование      332
Бисвязность      124
Вектор ребер      37
Вершина (vertex)      23 128 162 255
Вершина краевая      255
Вершина отделимости (separation vertices)      128 см.
Вершина полустепени захода (indegree)      29
Вершина полустепени исхода (outdegree)      29
Вершина, исток (source)      162
Вершина, сток (sink)      162
Вершинная связность (vertex connectivity)      129
Вершины смежные (adjacent)      23
Вес      279
Вес пути      279
Вес ребра      340
Вес ребра отрицательный      340
Гамильтонов путь      72
Генератор случайных графов      59
Граф      18 22 124 157 160 244 379
Граф k-реберно-связный      130
Граф k-связный      129
Граф ациклический связный      26 см.
Граф взвешенный      30
Граф вызовов функций      63
Граф двусвязный      128
Граф двухдольный      28
Граф Де-Бруйна      66
Граф изоморфный      24
Граф индуцированный подграф      23
Граф интервальный      65
Граф неориентированный      28
Граф неориентированный базовый      30
Граф ориентированный      28 157 160
Граф ориентированный ациклический (DAG)      30 158 164 193
Граф ориентированный двоичный      196
Граф ориентированный сильно связный (strongly connected)      164
Граф ориентированный, направленный цикл      30
Граф ориентированный, обращение (reverse)      162
Граф планарный      24
Граф подграф      23
Граф подграф индуцированный      23
Граф подграф максимальный связный      26
Граф полный      27
Граф простой      22
Граф разреженный      28
Граф реберно-отделимый      124
Граф свойство локальности      60
Граф связный      26
Граф сепарабельный (separable)      128
Граф случайный      60
Граф со степенями разделения      65
Граф статический      35
Граф транзакций      62
Граф Эвклидов      24
Граф Эвклидов с близкими связями      61
Граф, генератор случайных графов      59
Граф, дополнение графа      27
Граф, матрица смежности      38
Граф, насыщенность графа      27
Граф, объединение двух графов      27
Граф, сечение (cut) графа      244 379
Граф, сечение (cut) графа, st-сечение      379
Граф, сечение (cut) графа, минимальное      379
Граф, список смежных вершин      38
Граф, точка сочленения (articulation point)      128
Граф, триангуляция Делони      276
Дерево (tree)      26 231 289
Дерево кратчайших путей (SPT)      289
Дерево минимальное остовное (MST)      231 232
Дерево минимальное остовное Эвклидово      276
Дерево остовное      26
Дерево Фибоначчи      270
Диаграмма PERT      158 340
Длина пути      25
Дополнение графа      27
Дуга (arc)      29
Задача      314 360
Задача двудольного взвешенного сочетания      86
Задача двудольного сочетания      86 425
Задача динамической достижимости      228
Задача календарного планирования      474
Задача коммивояжера      88
Задача о Кенигсбергских мостах      75
Задача о кратчайшем пути с единственным источником      464
Задача о максимальном потоке      364 369 420
Задача о максимальном сочетании      473
Задача о минимальном сечении      379
Задача о многопродуктовом потоке      473
Задача о потоке минимальной стоимости      364 435
Задача о почтальоне      87 468
Задача о трудоустройстве      362
Задача обнаружения циклов      159
Задача обработки графов      83
Задача окраски      87
Задача определения кратчайших путей для всех пар вершин      184
Задача поиска наиболее длинных путей с несколькими источниками      314
Задача распределения      86 361 467
Задача составления расписаний      158
Задача сочетания с минимальными расстояниями      362
Задача топологической сортировки      158 159
Задача транспортная      360
Запрос (query)      35
Изоморфные графы      24
Интерфейс      52
Интерфейс "толстый"      52
Интерфейс насыщенный      52
Исследование Тремо      95
Календарное планирование      329
Карта (шар)      162
Классы эквивалентности      191
Клика (clique)      27 см.
Контур (tour)      25
Коридор (passage)      94
Кратчайший путь (shortest path)      132
Лабиринт (maze)      94
Лес (forest)      26
Лес DFS      112
Лес остовный      26
Математическое программирование      338
Матрица      178 290
Матрица булева      178
Матрица путей      290
Матрица расстояний      290
Матрица смежности графа      21 38
Метод      99 376
Метод аугментального пути      376
Метод быстрого объединения      см. "Алгоритм быстрого объединения"
Метод быстрого поиска      см. "Алгоритм быстрого поиска"
Метод выталкивания превосходящего потока      402 413
Метод поиска в глубину      99
Метод Тремо      100
Метод Уоршалла      180
Метод Форда — Фалкерсона      376 см.
Минимальное остовное дерево (MST)      231 232
Модель линейного программирования (LP-модель)      364
Мост (bridge)      124
Мультиграф      22
Мультиграф с петлями      23
Набор соединений (connections)      18
Набор элементов (items)      18
Насыщенность графа      27
Номер предпорядка (preorder number)      110
Обращение орграфа      163
Объединение двух графов      27
Операция      47 146 254 321
Операция decrease key (уменьшить ключ)      270
Операция edge existence (проверка наличия ребра)      47
Операция find edge (найти ребро)      53
Операция find minimum (поиск минимального ребра)      254
Операция remove edge (удалить ребро)      47
Операция remove the minimum (удалить минимальное ребро)      254 270
Операция reweighting (повторное взвешивание)      321 350
Операция update (обновления )      146
Операция арбитражная      343
Орграф      29 157 160 279 см.
Орграф взвешенный      279
Орграф декомпозиция      175
Орграф сильно связный (strongly connected)      164
Орграф, обращение (reverse)      162
Ослабление      287 см.
Остаточная сеть (residual network)      382
Отделимость      123
Отношение (relation)      190
Отношение рефлексивное      190
Отношение симметричное      190
Отношение эквивалентности      191
ОЧЕРЕДЬ (QUEUE)      141
Очередь FIFO      132
Очередь LIFO      132
Очередь с приоритетами      146
Перекресток (intersection)      94
Петля (self-loop)      22
Планирование      329
Планирование календарное      329
Подграф      23
Подграф индуцированный подграф      23
Подграф максимальный связный      26
Подграф полный      27
Поиск в глубину (DFS)      69 93 99 169
Поиск в глубину на матрице смежности      169
Поиск в глубину на списках смежных вершин      169
Поиск в ширину (BFS)      94 132
Поиск на графе      93 104
Поиск простого пути      70
Порядок      192
Порядок полный      192
Порядок частичный      191
Потенциал (potential)      445
Потенциал, потенциалы вершин      448
Поток (flow)      368 417
Поток допустимый      423 436
Поток максимальный      369 419
Поток минимальной стоимости      435 437
Поток превосходящий (preflow)      403
Поток, допустимое остовное дерево      449
Поток, остаточная сеть (residual network)      437
Поток, остовное дерево максимального потока      446
Поток, стоимость потока (flow cost)      435
Приложение составления расписаний      194
Программирование      332
Программирование библиотечное      332
Программирование математическое      338
Путь (path)      25 69 132 161 165 231 384
Путь аугментальный      384
Путь аугментальный кратчайший      386 399
Путь аугментальный с максимальной пропускной способностью      388 397
Путь аугментальный самый длинный      389
Путь гамильтонов      72
Путь кратчайший      132 231 281
Путь кратчайший в ациклических сетях      311
Путь кратчайший из нескольких источников      312
Путь обходной      341
Путь ориентированный      161
Путь простой      69
Путь циклический      25 165
Путь эйлеров      74
Путь, вес пути      279
Путь, длина пути      25
Путь, непересекающиеся пути      26
Путь, непересекающиеся пути по вершинам      26
Путь, непересекающиеся пути по ребрам      26
Ребро      23 244 379
Ребро инцидентно (incident on)      23
Ребро случайное      59
Ребро, ориентированные ребра      29
Ребро, пересекающее ребро (crossing edge)      244 379
Ребро, реберная связность (edge connectivity)      130
Релаксация (relaxation)      287 см.
Сведение      325 334 336 338
Сведение эффективное      334
Свойство сечения      244
Свойство цикличности      245
Связность      129
Связность вершинная      129
Связность реберная      130
Сеть (network)      279 366 382 см.
Сеть ациклическая      312
Сеть транспортная      30 366
Сеть транспортная со случайными потоками      396
Сеть Эвклидова      319
Сеть, st-сеть      368
Сеть, диаметр сети      305
Сеть, остаточная сеть (residual network)      382 410 437
Сеть, управление потоками в сети      368
Сечение (cut) графа      244 379
Сечение минимальное      379
Сечение, st-сечение      379
Сильная связность (strong connectivity)      212
Сортировка      199
Сортировка топологическая      194 199
Сортировка топологическая обратная      200
Список смежных вершин графа      21 38 44
Стандартная библиотека шаблонов (STL)      33
Степень (degree) вершины      23
Стоимость потока (flow cost)      435
Схема BDD (binary decision diagram)      196
Теорема      378
Теорема декомпозиции потоков      371
Теорема Куратовского      85
Теорема Менгера      130 429
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте