алгоритми оптимізації, алгоритмы оптимизации ; дискретні пристрої, ДП, дискретные устройства, ДУ ; теорія графів, теория графов, graphs theory

В диссертации исследованы схемы рекурсивногоразбора, определенные на основе относительных разбиений, как средства анализа графов. Введены и исследованы характеристики графа, выражающие его сложность по отношению к операциям разбора. Разработаны средства анализа двудольных графов ( D- разбиения), предназначенные для решения задачи поиска в графе структуры, вложимой в плоскую прямоугольную решетку. Исследованы основные свойства D-разбиений. Проведено экспериментальное исследование алгоритма поиска всех клик, которое показало его более высокую эффективность по сравнению с известным алгоритмом Брона-Кербоша и его модификацией. Предложены новые алгоритмы оптимизации размещения схем дискретных устройств на плоскости, основанные на поиске при помощи D- разбиений моделирующего двудольного графа, оптимальной структуры, вложимой в плоскую прямоугольную решетку. Эффективность разработанных в диссертации алгоритмов проилюстрирована на решении следующих прикладных задач: расчет низкоэнергетичных вторичных структур рибонуклеиновых кислот; нахождение родственных структур химических соединений; размещение элементов электронных схем на печатных платах с критерием минимума суммарной длины соединений.

• УДК // Комбінаторний аналіз. Теорія графів