Комбинаторная оптимизация, Алгоритмы и сложность, Пападимитриу X., Стайглиц К., 1984

Комбинаторная оптимизация, Алгоритмы и сложность, Пападимитриу X., Стайглиц К., 1984.
 
   В предлагаемой вниманию читателей книге удачно синтезированы вопросы, которые ранее в литературе освещались изолированно. Объединяющим все изложение лейтмотивом послужила задача линейного программирования, занимающая важное место в истории развития теории алгоритмов.
Материал книги удачно скомпонован. Каждая глава сопровождается соответствующей библиографией, небольшим историческим обзором и списком задач. Книга несомненно привлечет внимание широкого круга читателей, интересующихся вопросами построения эффективных алгоритмов для дискретных задач.




Задачи оптимизации.
Задачи оптимизации естественным образом разделяются на два класса: задачи с непрерывными переменными и задачи с дискретными переменными, которые будем называть комбинаторными. В непрерывных задачах обычно отыскивается множество действительных чисел или даже некоторая функция; в комбинаторных задачах — некоторый объект из конечного или возможно бесконечного счетного множества. Такими объектами обычно бывают целое число, множество, перестановка или граф. Эти два рода задач обычно совершенно различны по характеру, и методы их решения резко разделились. Комбинаторную оптимизацию мы начнем изучать (в некотором смысле) с пограничной зоны на стыке с непрерывной оптимизацией.

В теории оптимизации особая роль отводится линейному программированию: с одной стороны — это непрерывная оптимизационная задача, с другой, как упомянуто выше,— ее можно рассматривать также как комбинаторную по природе, и на самом деле она служит основой для изучения многих чисто комбинаторных задач. Поэтому дадим определение задачи оптимизации достаточно общим, чтобы охватить линейное программирование (и почти любую другую задачу оптимизации).

ОГЛАВЛЕНИЕ.
Предисловие переводчика.
Предисловие.
Глава 1. Задачи оптимизации.
1.1. Введение.
1.2. Задачи оптимизации.
1.3. Окрестности.
1.4. Локальные и глобальные оптимумы.
1.5. Выпуклые множества и функции.
1.6. Задачи выпуклого программирования.
Задачи.
Комментарии и ссылки.
Приложение. Терминология и обозначения.
П.1. Линейная алгебра.
П.2. Теория графов.
П.3. Упрощенный Алгол.
Глава 2. Симплекс-алгоритм.
2.1. Формы задачи линейного программирования.
2.2. Базисные допустимые решения.
2.3. Геометрия задач линейного программирования.
2.4. Переход от одного бдр к другому.
2.5. Организация таблицы.
2.6. Выбор выгодного столбца.
2.7. Выбор ведущего элемента и алгоритм Блэнда, устраняющий зацикливание.
2.8. Начало симплекс-алгоритма.
2.9. Геометрические аспекты замещения.
Задачи.
Комментарии и ссылки.
Глава 3. Двойственность.
3.1. Двойственная задача линейного программирования в общей форме.
3.2. Дополняющая нежесткость.
3.3. Лемма Фаркаша.
3.4. Задача о кратчайшем пути и двойственная к ней задача.
3.5. Двойственная информация в таблице.
3.6. Двойственный симплекс-алгоритм.
3.7. Интерпретация двойственного симплекс-алгоритма.
Задачи.
Комментарии и ссылки.
Глава 4. Вычислительные аспекты симплекс-алгоритма.
4.1. Модифицированный симплекс-алгоритм.
4.2. Вычислительные эффекты модифицированного симплекс-алгоритма.
4.3. Задача о максимальном потоке и ее решение модифицированным методом.
4.4. Метод декомпозиции Данцига — Вулфа.
Задачи.
Комментарии и ссылки.
Глава 5. Прямо-двойственный алгоритм.
5.1. Введение.
5.2. Прямо-двойственный алгоритм.
5.3. Комментарии к прямо-двойственному алгоритму.
5.4. Прямо-двойственный метод в применении к задаче о кратчайшем пути.
5.5. Замечания по методологии.
5.6. Прямо-двойственный метод в применении к задаче о максимальном потоке.
Задачи.
Комментарии и ссылки.
Глава 6. Примо-двойственные алгоритмы для задач о максимальном потоке и кратчайшем пути: алгоритмы Форда — Фалкерсона и Дейкстры.
6.1. Теорема о максимальном потоке и минимальном разрезе.
6.2. Алгоритм пометок Форда и Фалкерсона.
6.3. Проблема конечности алгоритма пометок.
6.4. Алгоритм Дейкстры.
6.5. Алгоритм Флойда — Уоршелла.
Задачи.
Комментарии и ссылки.
Глава 7. Прямо-двойственные алгоритмы для задачи о потоке минимальной стоимости.
7.1. Задача о потоке минимальной стоимости.
7.2. Комбинаториализация пропускных способностей. Алгоритм ЦИКЛ.
7.3. Комбинаториализация стоимости. Алгоритм ДОСТРОЙКА.
7.4. Явный прямо-двойственный алгоритм для задачи Хичкока. Алгоритм АЛЬФАБЕТА.
7.5. Преобразование задачи о потоке минимальной стоимости в задачу Хичкока.
7.6. Заключение.
Задачи.
Комментарии и ссылки.
Глав 8. Алгоритмы и сложность.
8.1. Вычислимость.
8.2. Временные оценки.
8.3. Размер индивидуальной задачи.
8.4. Анализ алгоритмов.
8.5. Полиномиальные алгоритмы.
8.6. Симплекс-алгоритм не является полиномиальным.
8.7. Алгоритм эллипсоидов.
Задачи.
Комментарии и ссылки.
Глава 9. Эффективные алгоритмы для задачи о максимальном потоке.
9.1. Поиск по графу.
9.2. Что нехорошо в алгоритме пометок?.
9.3. Расстановка пометок на сети и поиск по орграфу.
9.4. Алгоритм нахождения максимального потока со сложностью O(|V|3).
9.5. Случай единичных пропускных способностей.
Задачи.
Комментарии и ссылки.
Глава 10. Алгоритмы для задачи о паросочетании.
10.1. Задача о паросочетании.
10.2. Алгоритм построения паросочетания в двудольном графе.
10.3. Паросочетание в двудольном графе и поток в сети.
10.4. Паросочетание в произвольном графе. Цветки.
10.5. Паросочетание в произвольном графе. Алгоритм.
Задачи.
Комментарии и ссылки.
Глава 11. Взвешенное паросочетание.
11.1. Введение.
11.2. Венгерский метод для задачи о назначениях.
11.3. Задача о взвешенном паросочетании в произвольном графе.
11.4. Выводы.
Задачи.
Комментарии и ссылки.
Глава 12. Остовные деревья и матроиды.
12.1. Задача о минимальном остовном дереве.
12.2. Алгоритм со сложностью O(|E| log |V|) для задачи о минимальном остовном дереве.
12.3. Жадный алгоритм.
12.4. Матроиды.
12.5. Пересечение двух матроидов.
12.6. О некоторых расширениях задачи о пересечении матроидов.
Задачи.
Комментарии и ссылки.
Глава 13. Целочисленное линейное программирование.
13.1. Введение.
13.2. Вполне унимодулярность.
13.3. Верхние оценки решений задач ЦЛП.
Задачи.
Комментарии и ссылки.
Глава 14. Алгоритм отсекающей плоскости для задач целочисленного линейного программирования.
14.1. Отсечение Гомори.
14.2. Лексикографическое упорядочение.
14.3. Конечность дробного двойственного алгоритма.
14.4. Другие алгоритмы отсекающей плоскости.
Задачи.
Комментарии и ссылки.
Глава 15. NP-полные задачи.
15.1. Введение.
15.2. Задача оптимизации — это три задачи.
15.3. Классы Р и NP.
15.4. Полиномиальные сведения.
15.5. Теорема Кука.
15.6. Другие NP-полные задачи: КЛИКА и ЗК.
15J. Еще несколько NP-полных задач: сочетание, покрытие и разбиение.
Задачи.
Комментарии и ссылки.
Глава 16. Еще об NP-полноте.
16.1. Класс co-NP.
16.2. Псевдополиномиальные алгоритмы и «сильная» NР-полнота.
16.3. Частные случаи и обобщения NP-полных задач.
16.4. Словарь родственных понятий.
16.5. Эпилог.
Задачи.
Комментарии и ссылки.
Глава 17. Приближенные алгоритмы.
17.1. Эвристики-для задачи о вершинном покрытии. Пример.
17.2. Приближенные алгоритмы для задачи коммивояжера.
17.3. Приближенные схемы.
17.4. Отрицательные результаты.
Задачи.
Комментарии и ссылки.
Глава 18. Метод ветвей и границ и динамическое программирование.
18.1. Метод ветвей и границ для целочисленного линейного программирования.
18.2. Метод ветвей и границ в общем виде.
18.3. Отношения доминирования.
18.4. Стратегии метода ветвей и границ.
18.5. Применение к задаче о расписании для конвейера.
18.6. Динамическое программирование.
Задачи.
Комментарии и ссылки.
Глава 19. Локальный поиск.
19.1. Введение.
19.2. Задача 1: ЗК.
19.3. Задача 2: надежные сети минимальной стоимости.
19.4. Задача 3: топология прибрежной системы газопроводов.
19.5. Задача 4: равномерное разбиение графа.
19.6. Общие аспекты локального поиска.
19.7. Геометрия локального поиска.
19.8. Пример больших минимальных точных окрестностей.
19.9. Сложность точного локального поиска для ЗК.
Задачи.
Комментарии и ссылки.
Дополнительные комментарии и ссылки.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Комбинаторная оптимизация, Алгоритмы и сложность, Пападимитриу X., Стайглиц К., 1984 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - djvu - Яндекс.Диск.




Теги: учебник по высшей математике :: высшая математика :: Пападимитриу :: Стайглиц :: алгоритм :: комбинаторика