Ю. А. Белов, В. А. Бондаренко, А. Н. Максименко
Геометрические вопросы
сложности
Дискретпых задач
Учебное: пособи.с
Реком<11+006тьо
НиущиотистОдттсншм (3009an yHuecpcmm-mm
dam, студентов но-праб.ж-‘-нгш
Прикладная. математика и информатика.
l
винищем яму J’
У‘ндгы-хый фонд
Ярославл ь 2006
уди 519.11/. <...> Уппинского
Белов, Ю.А. Геометрические вопросы сложности Дискретных задач: учеб. пособие _/ Ю. <...> Излагается единый подход к качественному исследованию задач
Дискретной оптимизации, основанный на их геометрической интернретации. <...> В первой части приводятся необходимые факты из комбинаторной теории многогранников, рассматриваются многогранники
основных комбинаторных задач. <...> В заключительной части устанавливаются нижние оценки
СЛО)КПОС'ГИ задач В НТИРОКОМ классе ЗЛЁ‘ОРИ’ГМОВ. <...> Предназначено для студентов, обучающихся по направлению
010500 Прикладная математика и информатика (дисциплина “Геометрические вопросы комбинаторной оптимизации”, блок СД), очной
формы обучения. <...> 1,2 Выпуклые множества
Выпуклые многогранники
2.1 Основные свойства выпуклых многогранников
22 Примеры многогранников „
Геометрическая интерпретация
задач дискретной оптимизации
3.1 Примеры задач дискретной оптимизации
3.2 Геометрическая постановка задач дискретной оптимизации . <...> Линейные разделяющие алгоритмы
4.1 Основное определение
4.2 Геометрическая интерпретация линейного алгоритма
4.3 Оценки линейных разделяющих алгоритмов
Многогранники задач дискретной оптимизации
5.1 Основные комбинаторные характеристики многогранников
5.2 Многогранник задачи сортировки
5.3 Многогранники, порождаемые матроидами
Многогранники задач на графах
6‚1 Многогранник задачи о назначениях . <...> 6.2 Многогранник задачи о минимальном
совершенном пароеочетании . <...> Задача сортировки и задача о назначениях
8,2.1 . <...> . .
Алгоритмы (т Оракулом И класс NP
Сравнение задач по сложности . <...> Эти
задачи хорошо известны: первая называется задачей о минимальном остовном дереве, вторая —- задачей коммивояжера <...>