Задачи о клике и невыпуклая оптимизация, Груздева Т.В., Стрекаловский А.С., 2014

Задачи о клике и невыпуклая оптимизация, Груздева Т.В., Стрекаловский А.С., 2014.

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




Задачи диагностики мультипроцессорных систем.
Основная задача в изучении надежности многопроцессорных систем состоит в определении всех неисправных процессоров (блоков) в данной системе. Классический подход к диагностике системы был разработан около 30 лет назад Ф. Препарата и др. [144]. Суть его заключается в следующем. Система разбивается на модули, каждый из которых может в одиночку проверить другой модуль. Далее контролирующий модуль по результатам выполнения проверки оценивает состояние проверяемого модуля двоично: исправен — 0, неисправен — 1. Результат теста всегда правилен (достоверен), если исправен контролирующий модуль и недостоверен в противном случае. Предполагается также, что неисправности модулей устойчивы, а тесты полные, т.е. обнаруживают всевозможные неисправности модулей. Суммарный результат проверки системы образует двоичный вектор, который называется реальным синдромом [144].

Модель Ф. Препарата имеет существенные недостатки, связанные с довольно сильными и редко выполнимыми на практике предположениями относительно устройств системы и взаимосвязей между элементами модели.

ОГЛАВЛЕНИЕ.
Список основных обозначений.
Введение.
Глава 1 Задачи о клике: базовые свойства, методы решения и приложения.
1.1. Основные определения и свойства.
1.2. Практические приложения.
1.2.1. Задачи диагностики мультипроцессорных систем.
1.2.2. Задачи теории кодирования.
1.2.3. Построение оценок в задаче размещения.
1.2.4. Шенноновская емкость графов.
1.2.5. Задача Рамсея.
1.2.6. Би лиотека DIMACS.
1.3. Целочисленные постановки задач о клике.
1.4. Задачи о клике и непрерывная оптимизация.
1.5. Методы решения.
Глава 2 D.с. максимизация и задачи о клике.
2.1. Задача поиска максимальной клики.
2.1.1. D.с. представление задачи и стратегия глобального поиска.
2.1.2. Решение линеаризованной задачи.
2.1.3. Локальный поиск.
2.1.4. Построение аппроксимации и аналитическое решение линеаризованной задачи.
2.1.5. Одномерная максимизация и алгоритм поиска максимальной клики.
2.1.6. Вычислительный эксперимент по поиску максимальной клики.
2.2. Непрерывная постановка задачи о максимальной взвешенной клике.
2.2.1. Метод поиска локально максимальной взвешенной клики.
2.2.2. Алгоритм глобального поиска.
2.2.3. Численное решение задачи о максимальной взвешенной клике.
2.2.4. Построение оценок на вес и мощность максимальных клик.
2.3. Заключительные замечания по второй главе.
Глава 3 Задачи с d.c. ограничением и задачи о клике.
3.1. Задача о максимальной клике.
3.1.1. Непрерывные постановки задачи поиска максимальной клики.
3.1.2. Локальный поиск.
3.1.3. Глобальный поиск.
3.1.4. Вычислительный эксперимент по поиску максимальной клики.
3.2. Задача о максимальной взвешенной клике.
3.2.1. Непрерывные постановки задачи.
3.2.2. Поиск локально максимальной взвешенной клики.
3.2.3. Алгоритм глобального поиска.
3.2.4. Численное решение задачи о максимальной взвешенной клике.
3.3. Заключительные замечания по третьей главе.
Приложение А Теоретические основы d.c. оптимизации.
А.1. Свойства d.c. функций.
А.2. Задачи d.c. максимизации.
А.2.1. Локальный поиск.
А.2.2. Условия глобальной оптимальности.
А.2.3. Максимизирующие последовательности.
А.2.4. Теоретический метод и стратегия глобального поиска.
А.2.5. Сходимость стратегии глобального поиска.
А.3. Задачи с d.c. ограничениями.
А.3.1. Локальный поиск.
А.3.2. Условия глобальной оптимальности.
А.3.3. Минимизирующие последовательности.
А.3.4. Стратегия глобального поиска.
А.3.5. Сходимость стратегии глобального поиска.
Библиографический список.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Задачи о клике и невыпуклая оптимизация, Груздева Т.В., Стрекаловский А.С., 2014 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Груздева :: Стрекаловский