К вопросу об алгоритмах распознавания предфрактального графа

туальную модель энергосберегающих вычислительных процессов, представленную на рис. 3.

Обозначения, используемые на рисунке: Е -энергия, потребляемая БВС; X- множество вариантов архитектур ВС; О - множество вариантов алгоритмов целевых задач; 0 - множество требований к показателям качества ВС; X' - применяемая архитектура ВС; О' - используемые алгоритмы целевых задач; Рд - директивная вероятность безотказной работы ВС на заданном интервале функционирования ВС; Тд - директивная производительность ВС на заданном интервале функционирования ВС.

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

1) на этапе проектирования ВС - разработка алгоритмов целевых задач, эффективно решаемых на заданных структурах ВС, и выбор или разработка структур ВС, адекватных алгоритмам и программам целевых задач. Энергозатраты ВС в дальнейшем при реализации вычислений будут определяться показателями времени выполнения программ целевых задач и потребляемой мощностью ВС;

2) на этапе эксплуатации ВС - определение конфигурации ВС для энергосберегающего решения целевых задач на основе планирования параллельной обработки информации и оценивания времени вычислительных процессов. Энергозатраты ВС будут определяться количеством вычислительных модулей, выделенных на решение целевых задач, и временем выполнения программ целевых задач в соответствии с конфигурацией БВС и расписанием ПВП.

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Воеводин, В.В. Параллельные вычисления. [Текст]/В.В. Воеводин, Вл.В. Воеводин.-СПб.: БХВ-Петербург, 2004.-608 с.

2. Барский, А.Б. Параллельные информационные технологии: учеб. пособ. [Текст]/А.Б. Барский.-М.: Интернет-Университет информационных технологий; БИНОМ. Лаборатория знаний, 2007.-503 с.

УДК 519.1

И.Х. Утакаева, А.А.Кочкаров

К ВОПРОСУ ОБ АЛГОРИТМАХ РАСПОЗНАВАНИЯ ПРЕДФРАКТАЛЬНОГО ГРАФА

Способность «распознавать» считается основным свойством человеческих существ, как, впрочем, и других живых организмов. Образ представляет собой описание объекта. В каждое мгновение нашего бодрствования совершаются акты распознавания. Мы опознаем окружающие нас объекты и в соответствии с этим перемещаем-

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

развитыми у человека способностями распознавать образы [1].

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

Математической моделью многих задач распознавания является задача распознавания пред-фрактального графа [2].

Термином «затравка» условимся называть какой-либо связный и-вершинный граф Н = (Ж, О), с непомеченными, т. е. ненумерованными вершинами ие Ж. В качестве обобщения известной операции «расщепления вершины», определим операцию «замещения вершины затравкой» (ЗВЗ). Суть операции ЗВЗ состоит в замещении на каждом шаге каждой вершины ук(к = 1..и)е V графа О = (V, Е) и-вершинной затравкой Н, при этом для каждого ребра, инцидентного с ук, указанная вершина заменяется на некоторую вершину и из Ж.

Определим поэтапный процесс выполнения ЗВЗ. На этапе 5 = 1 в данной затравке Н = (Ж, О) нумеруем вершины и ребра; полученный граф обозначим через О1 = Е1).

Пусть выполнены этапы 5 = 1, 2, ..., I, и по завершению этапа I получен граф О 1 = (V Е {), который назовем предфрактальным (если I ^ да, то речь пойдет о фрактальном графе).

В дальнейшем будем использовать некоторые необходимые признаки предфрактальности графа О = (V, Е):

для мощности множества вершин IV| = N существует непустое множество пар и, Ь таких, что N = Щ(и, Ь);

для мощности множества ребер | Е| существует хотя бы одна пара и, Ь, удовлетворяющая равенству |ЕЬ| = д(и, Ь);

множество ребер ранга Ь состоит из объединения множеств ребер затравок, появившихся в результате того, что каждая вершина ранга Ь — 1 графа была замещена затравкой.

Пусть представлен в явном виде некоторый граф, обладающий признаками предфрактально-го графа. Задача распознавания предфрактально-го графа заключается в ответе на вопросы:

1) является ли данный граф предфрактальным с определенной затравкой;

2) можно ли построить эффективный алгоритм, который гарантированно построит процесс порождения предфрактального графа с определенной затравкой.

В данной статье исследуется следующая задача. Рассмотрим некоторый граф О = (V, Е) обладающий необходимыми признаками предфрак-тального графа:

• для мощности множества вершин IV | = N существуют и, т, Ь такие, что

т 2 п 2 , при Ь - нечетном,

(2 п2, при Ь - четном; • для мощности множества ребер |Е| существуют и, т, Ь, удовлетворяющие равенству:

ь-з

\ЕЛ =

т

+

2

т

к = 0

п{п — 1)

2

тк+1пк +

Ь-2 2

2

т

тк+1пк+1

, при Ь - нечетном,

к к т п +

п

тк+1пк

, при Ь - четном',

• множество вершин состоит из двух подмножеств V1 и V, где Vl(V2) - множество вершин уе V степени degv = и + 1 (степени degv = и).

Согласно полученным результатам проверки необходимых условий данный граф удовлетворяет условиям предфрактальности. Теперь рассмотрим вопрос, является ли представленный граф О = (V, Е) предфрактальным графом О / = (V ,, Е1) с двумя полными затравками Н1 = (Ж1, О1) и Н2 = (Ж2, О2), где мощности множеств вершин |Ж1| = т и |Ж2| = и, в случае, когда смежность старых ребер не нарушается. Причем, процедура ЗВЗ производена на нечетных этапах затравкой Н1 = (Ж1, О) и Н2 = (Ж2, О2) на четных, т. е. ответим на вопросы 1 и 2.

Для распознавания исследованного на необходимые условия предфрактальности графа О = (V, Е) предложен алгоритм а.

Алгоритм а

Процедура выделения затравки Н1 = (Ж О1) и Н2 = (Ж2, О2) обозначается у1(у2) в случае, если длина траектории О = (V, Е) Ь - нечетная(четная), то на последнем шаге было замещение затравкой Н1 = (Ж1, О1) (Н2 = (Ж2, О2)). Следовательно, для

предфрактального графа нечетного ранга Ь следует воспользоваться процедурой у в противном случае - процедурой у2. На последующих этапах процедуры будут чередоваться.

Описание процедуры у (выделение затравки Н1 = (Жр Q1У) Во множестве V выделяется очередная неотмеченная вершина V. Так как всякая «новая» затравка Н1 = (Ж Q1) имеет т - 1 вершину степени т - 1 и одну вершину, степень которой больше, чем т - 1, то Vv е V возможны два случая:

1. deg V = т -1; 2. deg V > т -1.

В первом случае исходная вершина и смежные с ней т - 1 вершин объединяют во множество Ж1. Далее окрашиваются все вершины Ж1, а

т

также -2- ребер, концы которых представляют собой вершины Ж

Во втором случае рассматриваемая вершина V имеет инцидентность не только с (т - 1) «новым» ребром, но и со «старыми» ребрами. Среди множества вершин смежных с V выделяются т - 1 вершин, степень которых т - 1. Исходная вершина V и выделенные т - 1 вершин степени т - 1 объединяются во множество Ж1. После чего

т

окрашиваются вершины Ж1, а также -2- ребер, концы которых представляют собой вершины множества Ж1.

Работа процедуры у1 завершается проверкой: образует ли множество выделенных таким образом вершин и ребер т-вершинный полный граф. Если да, то шаг, включающий в себя описанную процедуру у1, завершается результативно, и следует переход к следующему шагу первого этапа. В противном случае, шаг считается безрезультатным, и алгоритм прекращает свою работу с отрицательным ответом на поставленный вопрос распознавания: является ли представленный граф О = (V, Е) предфрактальным графом О = (V, Е) с двумя полными затравками Н1 = (Ж1, Q1) и Н2 = (Ж2, Q2), где мощности множеств вершин = т и |Ж21 = п, в случае, когда смежность старых ребер не нарушается, где процедура ЗВЗ произведена на нечетных номерах этапов затравкой Н1 = (Ж1, Q1) и затравкой Н2 = (Ж2, Q2) на четных.

Описание процедуры у2 (выделение затравки Н2 = (Ж2, Q2)) Во множестве V выделяется оче-

редная неотмеченная вершина V. Так как всякая «новая» затравка Н2 = (Ж2, Q2) имеет п - 1 вершину степени п - 1 и одну вершину, степень которой больше п - 1, то Vv е V возможны два случая:

1. deg V = п -1; 2. deg v> п -1.

В первом случае исходная вершина и смежные с ней п - 1 вершин объединяются во множество Ж2. Далее окрашиваются вершины Ж2, а так-

п(п - 1) ,.

же -2- ребер, концы которых представляют

собой вершины Ж

Во втором случае вершина V имеет инцидентность не только с п - 1 «новым» ребром, но и со «старыми» ребрами. Среди вершин, смежных с V, выделют п - 1 вершин со степенью п - 1. Исходную вершину V и выделенные п - 1 вершины степени п - 1 объединяют во множество Ж2. Далее

п

окрашиваются вершины Ж2, а также -2- ребер, концы которых представляют собой вершины множества Ж.

Работа процедуры у2 завершается проверкой: образует ли множество выделенных таким образом вершин и ребер п-вершинный полный граф. Если да, то шаг, включающий в себя описанную процедуру у2, завершается результативно, и следует переход к следующему шагу первого этапа. В противном случае, шаг считается безрезультатным, и алгоритм прекращает свою работу с отрицательным ответом на поставленный вопрос распознавания: является ли представленный граф О = (V, Е) предфрактальным графом О = (V, Е) с двумя полными затравками Н1 = (Ж1, Q1) и Н2 = (Ж2, Q2), где мощности множеств вершин = т и |Ж2| = п, в случае, когда смежность старых ребер не нарушается, где процедура ЗВЗ произведена на нечетных этапах затравкой Н1 = (Ж1, Q1), и Н2 = (Ж2, Q2) на четных.

По окончании первой части описанных выше алгоритмов, осуществляется проверка: все ли вершины исходного графа оказались отмеченными. Если да, то первый этап алгоритмов заканчивает свою работу следующей процедурой. Исходный граф обозначается через О'Ь и представляется в качестве первого члена последовательности О'Ь, О'Ь1, ..., О*1. Каждая выделенная затравка стягивается в вершину. Полученный в результате стягивания граф обозначается через О'Ь_г Далее, по отношению к нему реализуется очередной этап алгоритма.

В случае результативной работы каждого из Ь - 1 этапов, в качестве последнего члена последовательности получим т-вершинный полный граф. Этот результат означает получение положительного ответа на вопрос является ли представленный граф предфрактальным графом с непересекающимися «старыми» ребрами, образованным двумя полными затравками Н1 =

Принципиальная распознаваемость исследуемого предфрактального графа О = (V, Е) вытекает из конструктивного описания алгоритма а и однозначности результатов его работы.

Рассмотрим вопрос о вычислительной сложности алгоритма а. В процессе реализации этапов алгоритма осуществляются следующие операции: определение степени вершины, выявление окрестности радиуса 1 для этой вершины, просмотр всех пар вершин графа на предмет смежности, выделение и окрашивание ребер. Так как эти операции выполняются в пределах одной затравки, то верхняя оценка этапа не превосходит совокупного количества ребер, выделенных и отмеченных в процессе работы этапа. Отсюда, справедлива теорема: Всякий предфрактальный граф О = (V, Е) с двумя полными затравками распознается алгоритмом а, где смежность старых ребер не нарушается, с вычислительной трудоемкостью алгоритма т(а) < 0(|Е|Ь).

СПИСОК ЛИТЕРАТУРЫ

1. Горелик, А.Л. Методы распознавания [Текст]/ А.Л. Горелик, В.А. Скрипкин. -М.: 2004.

2. Емеличев, В.А. Лекции по теории графов [Текст]/В.А. Емеличев [и др.]. -М.: 1990.

3. Кочкаров, А.М. Распознавание фрактальных графов: Алгоритмический подход [Текст]/А.М. Кочкаров. -Нижний Архыз, 1998.

4. Мандельброт, Б. Фракталы, случай и финансы [Текст]/Б. Мандельброт. -М.: 2004.

5. Шредер, М. Фракталы, хаос, степенные законы [Текст]/М Шредер. -М.: 2005.

6. Мандельброт, Б. Фрактальная геометрия природы [Текст]/Б. Мандельброт. -М.: 2002.

УДК 669.5

А.Л. Рутковский, И.И. Болотаева, Т.А. Юрошева

алгоритм модифицированного симплексного поиска

В ЗАДАЧЕ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ПАРАМЕТРАМИ ПРОцЕССА ЭЛЕКТРОЛИЗА цИНКА

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

Задачи статистической оптимизации подобных процессов, возникающие при разработке и реализации АСУТП цветной металлургии, формально сводятся к параметрическому анализу

систем идентификации с антиинтуитивным поведением математической модели по данным измерений входных и выходных координат процесса [1] и последующего определения оптимальных значений входных переменных, обеспечивающих экстремум некоторого функционала. Такая постановка соответствует решению задачи математического программирования [2]:

F