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

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

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

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

Предложен алгоритм решения k-SAT-задачи в среднем за полиномиальное время и 3-SAT-задачи за полиномиальное время. Предлагаемый метод позволяет существенно сократить время решения SAT-задач.

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

Предложен субэкспоненциальный алгоритм решения SAT-задачи.

Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основании сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей O(mn<^>2), где в случае решения ЗНВП в произвольных графах n - число вершин, а m - число ребер в графе, а в случае решения ЗНП n - число столбцов, а m - число строк в матрице B. Показано, что погрешность решения этих задач предложенными процедурами A1 и A2 не превышает 5 % при плотности строк матрицы B, равной 0,5 и более. Предложенные алгоритмы можно использовать для эффективного планирования распределения ресурсов в GRID-системах в масштабе реального времени при достаточно жестких ограничениях на время решения задач, если допустимое время планирования находится в диапазоне от 5 до 100 мс.

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

Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, в среднем не превышающую О(2<^>0,4n), которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n - число вершин графа.

На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n<^>6), где n - число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125.

Дано обоснование машинного доказательства гипотезы о четырех красках, выполненного группой математиков, возглавляемой К. Аппелем и В. Хейкеном.

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

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

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

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

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

Запропоновано алгоритм поліноміальной складності для розв'язування задачі три-виконуваність.

Запропоновано стратегії відсікання безперспективних варіантів розв'язування задач лінійного програмування з булевими змінними на основі рангового підходу за рахунок введення песимістичного гарантованого прогнозу. Показано, що використання таких стратегій дозволяє істотно підвищити точність наближених алгоритмів розв'язування та зменшити часову складність точних алгоритмів розв'язування задач лінійного программування з булевими змінними.

Предложен метод на основе идей рангового подхода, позволяющий получить приближенные алгоритмы для решения любых задач линейного и нелинейного булевого программирования с полиномиальной временной сложностью и погрешностью, не превышающей 5 - 10 % при числе ограничений больше 50. При этом с увеличением числа ограничений погрешность асимптотически уменьшается.