URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации
Id: 103864
 
1199 руб.

Полиэдральные графы и сложность в комбинаторной оптимизации

1995. 126 с. Твердый переплет. ISBN 5-230-20441-9. Букинист. Состояние: 4+. Есть погашенная библиотечная печать.

 Аннотация

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

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


 Оглавление

. наук Ю.А. Жура-иза сложных систем

е графы и сложность. ун-т. --- Ярославль,

зафов многогранни-гимизации, которые Основное внимание эафов, которая слу-лгоритмов из широких комбинаторных гальна по размерно-юненциальна --- для

спирантов, научных числительной мате-

: Российского фонда 17).

Предисловие 4

Глава 1. Введение

1.1. Задачи и алгоритмы комбинаторной оптимизации 7

1.2. Элементы теории выпуклых многогранников 15

Глава 2. Алгоритмы, использующие линейные сравнения

2.1. Унифицированная постановка задач комбинаторной оптимизации 26

2.2. Многогранники задач. Конусное разбиение 30

2.3. Линейные разделяющие деревья 32

2.4. Алгоритмы прямого типа 38

Глава 3. Алгоритмы и многогранники конкретных задач

3.1. Предварительные замечания 44

3.2. Задачи сортировки, перестановочные многогранники 45

3.3. Матроиды и "жадный" алгоритм 62

3.4. Задача о кратчайшем пути 69

3.5. Задачи о паросочетаниях 74

3.6. Задача коммивояжера 77

3.7. Другие труднорешаемые задачи 88

Глава 4. Многогранники с высокой плотностью графа и полиномиальная разрешимость задач

4.1. Об одной гипотезе Д. Гейла 105

4.2. К вопросу о полиномиальной разрешимости задач 106

4.3. Специальные многогранники, связанные с задачей "трехмерное сочетание" 109

4.4. Специальные многогранники с полным описанием

вершин 111

Литература 120

 
© URSS 2016.

Информация о Продавце