Введение
ГЛАВА I. Дескриптивная теория локальных алгоритмов 32
1.1. О локальных алгоритмах вычисления информации . 32
1.2. Локальные алгоритмы решения задач дискретной оптимизации 37
1.3. Локальный декомпозиционный алгоритм ABT решения задач дискретной оптимизации с блочно-древовидной структурой . 45
1.4. Локальный алгоритм ABT для задач дискретной оптимизации, характеризующихся блочно-древовидной структурой с дополнительными ограничениями . 51
1.5. О связи локальных алгоритмов с другими алгоритмами дискретной оптимизации . 54
1.6. Распространение локального алгоритма на другие блочные структуры 58
Выводы по главе I 59
ГЛАВА II. Локальные элиминационные алгоритмы 61
2.1. Основные определения . 61
2.2. Локальные элиминационные алгоритмы в задачах оптимизации . 62
2.3. Локальные элиминационные алгоритмы решения дискретных задач информатики 96
Выводы по главе II 114
ГЛАВА III. Разреженные матрицы и теоретико-графовые подходы к выделению блочных структур 116
3.1. Разреженные матрицы и выделение блочной структуры 116
3.2. Свойства матриц с блочно-древовидной структурой 121
3.3. Древовидная декомпозиция и древовидная ширина 126
Выводы по главе III 150
ГЛАВА IV. Оценки эффективности и условия целесообразности применения локальных алгоритмов 152
4.1. О сложности алгоритмов решения задач дискретной оптимизации, общие понятия о сложности алгоритмов 152
4.2. Оценки сложности алгоритмов дискретной оптимизации 155
4.3. Оценки эффективности локального алгоритма решения блочно-древовидных задач дискретной оптимизации 157
4.4. О целесообразности использования локального алгоритма для решения задач дискретной оптимизации с блочно-древовидной структурой 164
4.5. Случай блочно-древовидной структуры с дополнительными ограничениями 171
Выводы по главе IV 182
ГЛАВА V. Средние значения оценки эффективности локального алгоритма 184
5.1. Средние оценки эффективности локального алгоритма для блочно-древовидных задач дискретной оптимизации 184
5.2. Асимптотическая средняя оценка эффективности локального алгоритма для задач с блочно-древовидной структурой и ограниченной связностью 199
5.3. Средняя оценка эффективности локального алгоритма для небулева случая 206
5.4. Оценка эффективности локального алгоритма в блочном случае с дополнительными ограничениями одновариантного типа 208
5.5. Средняя оценка эффективности локального алгоритма на классе блочных задач в более общем случае 212
5.6. Асимптотические средние оценки эффективности локального алгоритма для блочно-древовидной структуры с дополнительными ограничениями многовариантного типа 215
5.7. Асимптотические средние оценки эффективности локального алгоритма для блочно-древовидной структуры с дополнительными ограниченими одновариантного типа 225
5.8. Средняя оценка эффективности локального алгоритма на классе всех блочно-древовидных структур с дополнительными ограничениями одновариантного типа 231
5.9. Средние оценки эффективности локального алгоритма при решении G-блочных задач дискретной оптимизации 234
Выводы по главе V 236
ГЛАВА VI. Анализ блочных структур в случаях наилучшего и наихудшего поведения локального алгоритма 239
6.1. Оценка максимального и минимального значений оценки эффективности локального алгоритма для задач дискретной оптимизации с блочно-древовидной структурой без дополнительных ограничений 239
6.2. «Наихудшее» и «наилучшее» поведение локального алгоритма на
классе блочно-древовидных структур с дополнительными ограниче-
ниями многократного выбора 250
Выводы по главе VI 269
ГЛАВА VII. Вычислительные аспекты реализации локального алгоритма 271
7.1. «Оценочный» эксперимент для локального алгоритма 271
7.2. Эксперимент для локального алгоритма в сочетании с алгоритмами пакета «Диспро» 280
7.3. Приближенные версии локального алгоритма 286
7.4. Локальный элиминационный алгоритм и параллельные вычисления 287
Выводы по главе VII 295
Заключение 297
Литература 307
Приложение
