Отправить другу/подруге по почте ссылку на эту страницуВариант этой страницы для печатиНапишите нам!Карта сайта!Помощь. Как совершить покупку…
московское время09.12.24 13:46:31
На обложку
Волны в анизотропной плазмеавторы — Эллис В., Буксбаум С., Берс А.
ЕГЭ 2008—2009. Физика. Справочникавторы — Бальва О. П., сост.
Мировой нефтегазовый комплексавторы — Брагинский О. Б.
б у к и н и с т и ч е с к и й   с а й т
Новинки«Лучшие»Доставка и ОплатаМой КнигоПроводО сайте
Книжная Труба   поиск по словам из названия
Авторский каталог
Каталог издательств
Каталог серий
Моя Корзина
Только цены
Рыбалка
Наука и Техника
Математика
Физика
Радиоэлектроника. Электротехника
Инженерное дело
Химия
Геология
Экология
Биология
Зоология
Ботаника
Медицина
Промышленность
Металлургия
Горное дело
Сельское хозяйство
Транспорт
Архитектура. Строительство
Военная мысль
История
Персоны
Археология
Археография
Восток
Политика
Геополитика
Экономика
Реклама. Маркетинг
Философия
Религия
Социология
Психология. Педагогика
Законодательство. Право
Филология. Словари
Этнология
ИТ-книги
O'REILLY
Дизайнеру
Дом, семья, быт
Детям!
Здоровье
Искусство. Культурология
Синематограф
Альбомы
Литературоведение
Театр
Музыка
КнигоВедение
Литературные памятники
Современные тексты
Худ. литература
NoN Fiction
Природа
Путешествия
Эзотерика
Пурга
Спорт

/Наука и Техника/Математика

Параллельные алгоритмы целочисленной оптимизации — Хохлюк В. И.
Параллельные алгоритмы целочисленной оптимизации
Хохлюк В. И.
год издания — 1987, кол-во страниц — 224, тираж — 7100, язык — русский, тип обложки — мягк., масса книги — 200 гр., издательство — Радио и связь
цена: 299.00 рубПоложить эту книгу в корзину
Сохранность книги — хорошая

Р е ц е н з е н т ы:
д-р техн. наук, проф. Б. А. Головкин
д-р техн. наук, проф. Д. Б. Юдин

Формат 84x108 1/32. Бумага писчая №1. Печать высокая
ключевые слова — параллельн, численн, целочислен, оптимизац, алгоритм, распараллел, комбинаторн, оптимальн, алгол, сложност, неделим, маршрут, ветв, графов, перебор, евклид

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

В книге рассматриваются следующие вопросы: математические постановки прикладных задач; параллельные алгоритмы решения сформулированных задач; машинная реализация алгоритмов. Излагаемые вычислительные методы, реализованные с помощью средств параллельного программирования на реальной параллельной вычислительной системе, позволяют ускорить счёт в десятки и сотни раз. Это открывает путь к решению многих ранее недоступных важных практических задач, таких как обработка огромных массивов данных, выбор оптимального маршрута в различных случаях, оптимизация параметров сети ЭВМ и систем передачи данных, составление расписаний и др.

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

Табл. 6. Ил. 34. Библиогр. 82 назв.


Задачи целочисленной оптимизации возникают в различных приложениях и теоретических исследованиях. Настоящая монография посвящена изучению численных методов целочисленной оптимизации с точки зрения их распараллеливания. Интерес к параллельным вычислениям обусловлен следующими тремя основными причинами:
параллельные алгоритмы необходимы параллельным вычислительным системам, уже созданным и проектируемым;
переход от привычных последовательных вычислений к параллельным открывает новые возможности для построения алгоритмов;
распараллеливание вычислений позволяет во много раз увеличить скорость счёта.

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

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

Далее рассматриваются основные принципы построения параллельных алгоритмов (гл. 4), параллельные алгоритмы метода ветвей и границ для решения задач комбинаторной и целочисленной оптимизации (гл. 5) и параллельные алгоритмы метода секущих плоскостей для нахождения оптимального решения целочисленной и смешанной целочисленной линейных задач (гл. 6).

В последних главах анализируются и сравниваются различные вычислительные схемы для приведения целочисленной матрицы к специальному виду (гл. 7) и приводятся краткие сведения о десяти вспомогательных Алгол-процедурах для решения семи математических задач, встречающихся в качестве подзадач в методах целочисленной оптимизации.

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

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

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

В заключение автор выражает глубокую благодарность рецензентам книги профессорам Б. А. Головкину и Д. Б. Юдину за содержательные критические замечания, а также всем, кто помогал ему в работе над книгой.

ПРЕДИСЛОВИЕ

ОГЛАВЛЕНИЕ

Предисловие3
 
Г л а в а   1.  Задачи и методы целочисленной оптимизации5
 
1.1. Постановка задач5
1.2. Численные методы12
1.3. Вычислительная сложность задач целочисленной
оптимизации17
1.4. Элементы теории секущих плоскостей21
1.5. Параллельные вычисления25
1.6. Машинная реализация28
 
Г л а в а   2.  Целочисленные формулировки прикладных задач29
 
2.1. Запись условий в бинарных переменных30
2.2. Выбор оптимального варианта37
2.3. Неделимые величины38
2.4. Задачи о покрытии, разбиении и упаковке множества40
2.5. Две задачи о назначениях45
2.6. Задача о расписании работ на машинах46
2.7. Учёт фиксированных доплат47
2.8. Задачи о размещении предприятий49
2.9. Задача о перевозке продукта53
2.10. Сетевой график54
2.11. Выбор оптимального маршрута56
 
Упражнения60
 
Г л а в а   3.  Преобразования задач целочисленной оптимизации66
 
3.1. Общие замечания66
3.2. Уменьшение размеров задачи70
3.3. Преобразование бинарной линейной задачи в задачи
о покрытии, разбиении и упаковке75
3.4. Линейная релаксация задач о покрытии и разбиении79
3.5. Задача о потоке минимальной стоимости83
3.6. Преобразование задачи о ранце в задачу о кратчайшем
пути88
3.7. Преобразования целочисленной линейной задачи над
конусом89
3.8. Эквивалентность целочисленных линейных задач93
3.9. Преобразование смешанной целочисленной линейной
задачи в целочисленную97
3.10. Преобразование целочисленной линейной задачи в
линейную99
3.11. Линеаризация нелинейной задачи100
 
Упражнения102
 
Г л а в а   4.  Методы распараллеливания вычислений106
 
4.1. Принцип распараллеливания данного
последовательного алгоритма106
4.2. Метод сдваивания111
4.3. Распараллеливание рекурсий114
4.4. Умножение матрицы на вектор118
4.5. Характеристика некоторых параллельных процессов120
 
Упражнения122
 
Г л а в а   5.  Параллельные алгоритмы ветвей и границ123
 
5.1. Выполнение p-ветвевого обхода дерева перебора123
5.2. Общий p-алгоритм ветвей и границ125
5.3. Линейная релаксация .128
5.4. Неявный перебор131
5.5. Коническая релаксация140
5.6. Распараллеливание алгоритмов динамического
программирования141
5.7. Приближенные p-алгоритмы144
 
Упражнения145
 
Г л а в а   6.  Параллельные алгоритмы секущих плоскостей147
 
6.1. Выполнение p-умножения двух матриц147
6.2. Секущие плоскости148
6.3. Прямые и двойственные алгоритмы152
6.4. Алгоритм нахождения всех крайних лучей
заострённого конуса155
6.5. Прямой алгоритм решения целочисленной линейной158
6.6. Прямой алгоритм решения целочисленной линейной
задачи оптимизации160
6.7. Обоснование алгоритмов167
 
Упражнения173
 
Г л а в а   7.  Приведение целочисленной матрицы к
специальному виду175
 
7.1. Оценка числа итераций алгоритма Евклида176
7.2. Множители в представлении наибольшего общего
делителя181
7.3. Элементарные преобразования целочисленной
матрицы185
7.4. Алгоритмы приведения целочисленной матрицы к
трапецеидальному виду188
7.5. Алгоритмы приведения целочисленной матрицы к
нормальному виду192
7.6. Алгоритмы нахождения общего целочисленного
решения системы линейных уравнений195
7.7. Машинная реализация и схемы распараллеливания198
 
Упражнения199
 
Г л а в а   8.  Краткие сведения о вспомогательных
АЛГОЛ-процедурах203
 
8.1. Общие замечания203
8.2. Процедура нахождения множителей в представлении
наибольшего общего делителя204
8.3. Процедуры приведения целочисленной матрицы к
трапецеидальному виду205
8.4. Процедуры приведения целочисленной матрицы к
нормальному виду205
8.5. Процедуры нахождения общего целочисленного решения
системы линейных уравнений206
8.6. Процедура нахождения всех крайних лучей заострённого
конуса207
8.7. Процедура нахождения всех вершин многогранника208
8.8. Процедура решения линейной задачи оптимизации209
 
Приложение. Основные обозначения и сокращения211
Список литературы218

Книги на ту же тему

  1. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
  2. Численные методы, алгоритмы и программы. Введение в распараллеливание: Учебное пособие для вузов, Карпов В. Е., Лобанов А. И., 2014
  3. Введение в параллельные методы решения задач: Учебное пособие, Якобовский М. В., 2013
  4. Параллельное программирование в среде MATLAB для многоядерных и многоузловых вычислительных машин: Учебное пособие, Кепнер Д., 2013
  5. Современные языки и технологии параллельного программирования: Учебник, Гергель В. П., 2012
  6. Итерационные методы для разреженных линейных систем: Учебное пособие. — В 2-х томах. Том 1, Саад Ю., 2013
  7. Параллельные вычислительные системы, Головкин Б. А., 1980
  8. Многоядерное программирование, Эхтер Ш., Робертс Д., 2010
  9. Принципы работы и система программного обеспечения МП ЕС 2700, Семерджян М. А., Налбандян Ж. С., Гаспарян Л. X., 1988

Напишите нам!© 1913—2013
КнигоПровод.Ru
Рейтинг@Mail.ru работаем на движке KINETIX :)
elapsed time 0.023 secработаем на движке KINETIX :)