Локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации

СОДЕРЖАНИЕ
Обозначения, сокращения и определения.
ВВЕДЕНИЕ
ГЛАВА I. ДЕСКРИПТИВНАЯ ТЕОРИЯ ЛОКАЛЬНЫХ АЛГОРИТМОВ.
1.1.0 локальных алгоритмах вычисления информации
1.2. Локальные алгоритмы решения задач дискретной оптимизации
1.3. Локальный декомпозиционный алгоритм 2СВТ решения задач дискретной оптимизации е блочнодревовидной структурой.
1.4. Локачьный алгоритм для задач дискретной оптимизации,
характеризующихся блочнодревовидной структурой с дополнительными ограничениями.
1.5. О связи локальных алгоритмов с другими алгоритмами дискретной оптимизации
1.6. Распространение локального алгоритма на другие блочные структуры
Выводы по главе 1.
ГЛАВА II. ЛОКАЛЬНЫЕ ЭЛИМИНАЦИО 1НЫЕ АЛГОРИТМЫ
2.1. Основные определения.
2.2. Локальные элиминационные алгоритмы в задачах оптимизации
2.3. Локальные элиминационные алгоритмы решения дискретных задач информатики
Выводы по главе II
ГЛАВА III. РАЗРЕЖЕННЫЕ МАТРИЦЫ И ТЕОРЕТИКОГРАФОВЫЕ ПОДХОДЫ К ВЫДЕЛЕНИЮ БЛОЧНЫХ СТРУКТУР
3.1. Разреженные матрицы и выделение блочной структуры
3.2. Свойства матриц с блочнодревовидной структурой
3.3. Древовидная декомпозиция и древовидная ширина
Выводы по главе III.
ГЛАВА IV. ОЦЕНКИ ЭФФЕКТИВНОСТИ И УСЛОВИЯ ЦЕЛЕСООБРАЗНОСТИ ПРИМЕНЕНИЯ ЛОКАЛЬНЫХ АЛГОРИТМОВ
4.1. О сложности алгоритмов решения задач дискретной оптимизации, общие понятия о сложности алгоритмов.
4.2. Оценки сложности алгоритмов дискретной оптимизации.
4.3. Оценки эффективности локального алгоритма решения блочнодревовидных задач дискретной оптимизации.
4.4. О целесообразности использования локального алгоритма для решения задач дискретной оптимизации с блочнодревовидной структурой
4.5. Случай блочнодревовидной структуры с дополнительными ограничениями
Выводы по главе IV
ГЛАВА V. СРЕДНИЕ ЗНАЧЕНИЯ ОЦЕНКИ ЭФФЕКТИВНОСТИ
ЛОКАЛЬНОГО АЛГОРИТМА
5.1. Средние оценки эффективности локального алгоритма для блочнодревовидных задач дискретной оптимизации
5.2. Асимптотическая средняя оценка эффективности локального алгоритма для задач с блочнодревовидной структурой и ограниченной связностью.
5.3. Средняя оценка эффективности локального алгоритма для небулева случая
5.4. Оценка эффективности локального алгоритма в блочном случае с дополнительными ограничениями одновариантного типа
5.5. Средняя оценка эффективности локальною алгоритма на классе блочных задач в более общем случае
5.6. Асимптотические средние оценки эффективности локального алгоритма для блочнодревовидной структуры с дополнительными ограничениями многовариантного типа.
5.7. Асимптотические средние оценки эффективности локального алгоритма для блочнодревовидной структуры с дополнительными ограниченими одновариантного типа.
5.8. Средняя оценка эффективности локального алгоритма на классе всех блочно древовидных структур с дополнительными ограничениями одно вариантного типа
5.9. Средние оценки эффективности локального алгоритма при решении 7 блочных задач дискретной оптимизации
Выводы по главе V.
ГЛАВА VI. АНАЛИЗ БЛОЧНЫХ СТРУКТУР В СЛУЧАЯХ НАИЛУЧШЕГО И НАИХУДШЕГО ПОВЕДЕНИЯ ЛОКАЛЬНОГО АЛГОРИТМА.
6.1. Оценка максимального и минимального значений оценки эффективности локального алгоритма для задач дискретной оптимизации с блочнодревовидной структурой без дополнительных ограничений.
6.2. Наихудшее и наилучшее поведение локального алгоритма на классе блочнодревовидных структур с дополнительными ограничсниями многократного выбора
Выводы по главе VI
ГЛАВА VII. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ РЕАЛИЗАЦИИ ЛОКАЛЬНОГО АЛГОРИТМА
7.1. Оценочный эксперимент для локального алгоритма.
7.2. Эксперимент для локального алгоритма в сочетании с алгоритмами пакета Диспро.
7.3. Приближенные версии локального алгоритма.
7.4. Локальный элиминационный алгоритм и параллельные вычисления
Выводы но главе VII.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА