БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

НАУЧНО-ПРАКТИЧЕСКИЕ КОНФЕРЕНЦИИ

<< ГЛАВНАЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     || 2 | 3 | 4 | 5 |   ...   | 19 |

«СОВРЕМЕННЫЕ ПРОБЛЕМЫ ИНФОРМАТИЗАЦИИ В АНАЛИЗЕ И СИНТЕЗЕ ТЕХНОЛОГИЧЕСКИХ И ПРОГРАММНО- ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ Сборник трудов Выпуск 16 (по итогам XVI международной открытой ...»

-- [ Страница 1 ] --

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

ВОЛОГОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

БАКИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АКАДЕМИЯ ФСО РОССИИ (г. ОРЕЛ)

ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

СОВРЕМЕННЫЕ ПРОБЛЕМЫ

ИНФОРМАТИЗАЦИИ

В АНАЛИЗЕ И СИНТЕЗЕ

ТЕХНОЛОГИЧЕСКИХ И ПРОГРАММНОh2>

ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

Сборник трудов Выпуск 16 (по итогам XVI международной открытой научной конференции) Научная книга Воронеж - 2011 СПИ-АС- ББК 32. С Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем: Сб. трудов. Вып. 16/ Под ред. д.т.н., проф.

О.Я.Кравца. - Воронеж: "Научная книга", 2011. - 151 с. (301ISBN 978-5-98222-714- Сборник трудов по итогам XVI Международной открытой научной конференции “Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем”, проводившейся в ноябре 2010 - январе 2011 гг., содержит материалы по следующим основным направлениям: анализ и синтез сложных систем;

проектирование энергетических, электромеханических и технологических систем;

программные и телекоммуникационные системы и приложения.

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

Редколлегия сборника:

Кравец О.Я., д-р техн. наук

, проф., руководитель Центра дистанционного образования ВорГТУ (главный редактор);

Алиев А.А., д-р техн. наук, проф., зав. кафедрой ИТиП БГУ;

Блюмин С.Л., заслуженный деятель науки РФ, д-р физ.-мат. наук, проф., кафедра ПМ ЛГТУ, Водовозов А.М., канд. техн. наук, доц., зав. кафедрой УВС ВолГТУ;

Лебеденко Е.В., канд. техн. наук, кафедра ИВТ Академии ФСО России;

Лукьянов А.Д., канд. техн. наук, доц., кафедра АПП ДонГТУ;

Подвальный С.Л., заслуженный деятель науки РФ, д-р техн. наук, проф., зав. кафедрой АВС ВорГТУ.

ББК 32. С Коллектив авторов, ISBN 978-5-98222-714- СПИ-АС- Введение Уважаемые коллеги!

Перед Вами сборник трудов, опубликованный по итогам шестнадцатой Международной открытой научной конференции “Современные проблемы информатизации”. Конференция проводилась в рамках плана Федерального агентства по образованию Воронежским государственным техническим университетом, Бакинским государственным университетом, Вологодским государственным техническим университетом, Липецким государственным техническим университетом, Академией ФСО России (г.Орел), Донским государственным техническим университетом (г.Ростов-на-Дону) в ноябре 2010 январе 2011 гг.

Было решено провести в рамках настоящей конференции три тематически дифференцированные – «Современные проблемы информатизации в экономике и обеспечении безопасности», «Современные проблемы информатизации в моделировании и социальных технологиях», «Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем».

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

Представители ведущих научных центров и учебных заведений России, Украины, Беларуси, Азербайджана представили результаты своих исследований, с которыми можно ознакомиться не только в настоящем сборнике, но и на http://www.sbook.ru/spi.

Настоящий сборник содержит труды участников конференции по следующим основным направлениям:

· анализ и синтез сложных систем;

· проектирование энергетических, электромеханических и технологических систем;

· программные и телекоммуникационные системы и приложения.

Председатель Оргкомитета, руководитель Центра дистанционного образования Воронежского государственного технического университета, Аль-хулайди Абдулмаджид Ахмед Галеб

РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА ДЛЯ

НАХОЖДЕНИЯ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА

Рассматриваемая задача может найти применение в различных областях:

· Разработка сетей. В данном случае решается задача о соединении n городов с минимальной суммарной стоимостью соединений.

· Производство печатных плат. По аналогии с сетью: мы хотим соединить n контактов проводами с минимальной суммарной стоимостью.

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

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

Постановка задачи: разработка параллельного алгоритма нахождения минимального покрывающего дерева.

Алгоритм Борувки Этот алгоритм, также известный как алгоритм Соллина, строит минимальное покрывающее дерево взвешенного графа (рис. 1) в итерациях, состоящих из следующих шагов [1].

Рис. 1. Взвешенный граф, содержащий 8 вершин и 12 ребер. После точки следует целочисленный вес ребра Шаг 1 (выбор самого лёгкого): Каждая вершина выбирает самое легкое инцидентное себе ребро. Каждый из соединительных компонентов, созданных таким образом, имеет один цикл двойного размера между двумя вершинами, каждая из которых выбирает одно и то же ребро. Вершина, имеющая меньший номер в этой паре, назначается корнем компонента и цикл удаляется. Компонент становится деревом.

Шаг 2 (поиск корня): Каждая вершина устанавливает корень дерева, которому она принадлежит.

Шаг 3 (переименование вершин): В списке ребер каждая вершина переименовывается именем корня компонента, которому она принадлежит.

Шаг 4 (слияние списка ребер): Списки ребер, принадлежащих одному и тому же компоненту, сливаются в список ребер корня. Другими словами, каждый соединительный компонент уменьшается до одной вершины.

Шаг 5 (очистка): В этот момент список ребер может иметь петли и множественные ребра. Все петли удаляются. Множественные ребра удаляются таким образом, что только самое лёгкое ребро остаётся между парой вершин.

Граф, остающийся после i-й итерации, является исходным для (i+1)й итерации до тех пор, пока все вершины не будут исчерпаны. Выходное остовное дерево является объединением набора ребер, выбранных на первом шаге, взятом на всех итерациях (с первоначальными именами вершин, такими, которые были при старте алгоритма). Алгоритм может быть выполнен таким образом, что итерация, на которой граф имеет n вершин и m ребер, будет выполняться время O(n+m). К тому же, число вершин графа на (i+1)-й итерации больше половины числа вершин на i-й итерации. Поэтому число итераций получается не более log(n) при общем времени работы O(m*log(n)).

Разработка алгоритма Борувки для параллельных систем Шаг 1 (выбор самого лёгкого): В списке ребер каждой вершины производится поиск самого легковесного ребра. На рис. 2 показан результат выполнения шага 1 при первой итерации для графа рис. 1. Связные списки выглядят, как показано на рис. 3.

Шаг 2 (поиск корня): Каждая вершина ищет корень дерева, которому она принадлежит, используя алгоритм подмены указателя. Сначала корень каждого компонента устанавливает свой указатель на себя. Каждая прочая вершина первоначально указывает на другую конечную точку самого легкого инцидентного ему ребра. Указатели вершин далее обновляются повторяющимися подменами указателя так, что за одну замену указателя вершина обновляет свой указатель на равный своего родителя.

Шаг 3 (переименование вершин): Каждый процессор находит новое имя для всех вершин, находящихся в его списке ребер. Два сообщения – для запроса и ответа – требуются для получения информации от другого процессора, который ей обладает.

Рис. 2. Результат поиска для каждой вершины самого легкого инцидентного ей ребра. Получено 3 дерева с корнями 0, 3 и 4 соответственно.

Рис. 3. Связный список графа Шаг 4 (слияние): Ребра всех вершин компонента посылаются процессору, который имеет список ребер корня. Список ребер далее сливается процессором.

Шаг 5 (очистка): Каждый процессор выполняет последовательный алгоритм на своем собственном списке ребер.

В нашей реализации алгоритма подмены указателя на шаге 2 процессоры синхронизируются на каждой итерации цикла.

Рассмотрим шаг 2 более подробно.

Время выполнения параллельного алгоритма на шаге 2 значительно больше, чем в последовательной версии.

1) Предлагается при каждой синхронизации на шаге 2 использовать пакетную передачу, независимую от количества обновляемых указателей. При условии (n/p) n, где n –число вершин, а p – количество процессоров, это значительно повысит производительность.

2) Новый рандомизированный алгоритм замены указателя.

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

Разработана новая схема замены указателей, которая далее будет называться “алгоритмом особых вершин”. Эта рандомизированная схема может быть применена к деревьям и спискам и требует только ожидаемой линейной работы.

В первом приближении, в нашем алгоритме каждый компонент обрабатывается следующим образом. Случайным образом выбирается подмножество вершин, называемых “особыми”. Назовем это подмножество SV. Каждая вершина в S-SV выполняет простой алгоритм замены указателя, пока она не укажет на “особую” вершину. В этой точке все вершины, кроме особых, отбрасываются и “особые” вершины повторяют тот же алгоритм рекурсивно (ещё раз с каждой вершиной, случайно выбираемой как “особая” на следующей итерации). Как только все “особые” вершины указывают на корень, оставшиеся вершины обновляют свои указатели за один шаг так, что они тоже указывают на корень.

Выводы: В ходе работы разработан параллельный алгоритм для нахождения минимального покрывающего дерева. Данный алгоритм подходит для разработки параллельной программы для кластера локальной сети, либо многопроцессорной системы. Отдельно рассмотрен вопрос синхронизации процессов.

Список использованных источников 1. http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-

АЛГОРИТМ РЕВЕРСИВНОГО ПОЗИЦИОНИРОВАНИЯ

ВЫСОКОИНЕРЦИОННЫХ ЗАГОТОВОК

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

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

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

В основу алгоритма положены математические модели, описывающие статические крутильные деформации и динамические силы, возникающие в процессе позиционирования заготовки, а также 3D модели в пакете SolidWorks, что позволило спрогнозировать распределение крутильной деформации ротора вдоль оси.

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

Для дополнительной фиксации ротора в системе позиционирования используются управляемые тормозные стойки, фиксирующие отдельные диски ротора.

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

ВЗВЕШЕННЫЕ НЕОРИЕНТИРОВАННЫЕ ГИПЕРГРАФЫ В

МОДЕЛИРОВАНИИ МУЛЬТИАГЕНТНЫХ СИСТЕМ:

ПРОПОРЦИОНАЛЬНОЕ ПЕРЕРАСПРЕДЕЛЕНИЕ СОСТОЯНИЙ

АГЕНТОВ

Базовая модель достижения консенсуса в мультиагентной системе (МАС) с учетом групповых взаимодействий агентов (УГВА) представляется с использованием столбцов инцидентности гипердуг взвешенного ориентированного гиперграфа, ассоциированного с МАС [1].

Цель данной работы* – показать, как модель МАС с УГВА, направленных на достижение равной выгоды экономическими агентами путем пропорционального их активам перераспределения их прибылей [2], представляется с использованием столбцов инцидентности гиперребер взвешенного неориентированного гиперграфа, ассоциированного с МАС.

МАС состоит из конечного числа взаимодействующих между собой агентов, множество которых далее обозначается через V, |V|=m. Это множество некоторым, фиксированным на протяжении всего рассмотрения образом упорядочено, то есть агенты перенумерованы и всегда, в том числе и в их группах, представляются своими номерами i, 1im, в V.

Каждый агент характеризуется своим активом ai, 1im, а МАС в целом – вектором a=[ … ai … ]T. Рассматривается динамика МАС относительно дискретного времени tN={0,1, … }. Прибыль xi[t] каждого агента в каждый момент трактуется как его состояние, так что x[t]=[ … xi[t] … ]T – вектор состояния МАС, причем задан вектор ее начального состояния x[0]=[ … xi[0] … ]T. В каждый момент t1 взаимодействует группа V[t]V агентов в соответствии с алгоритмом пропорционального перераспределения состояний агентов (ППСА) [2], что приводит к модели данной МАС:

где веса w i[t] = a i /A[t], A[t] = jV[t] a j ;

для агентов, не входящих в группу, Модели сопоставляется взвешенный неориентированный гиперграф WН=(V,WНЕ), в основе которого лежит неориентированный гиперграф Н=(V,НЕ), вершины v которого отождествляются с агентами.

Через he[t] далее обозначается гиперребро, соответствующее группе V[t] взаимодействующих в момент t агентов. Столбец инцидентности I(he[t]) такого гиперребра содержит единицы на местах, отвечающих вхо

Работа поддержана РФФИ, проект № 09-07-00220-а дящим в группу агентам, а остальные его элементы – нули. Произведение такого транспонированного столбца I(he[t])T на вектор x[t-1] состояния МАС в предыдущий момент и на вектор активов а дает элементы модели:

Взвешенный столбец инцидентности WI(he[t]) получается заменой единиц в I(he[t]) соответствующими весами wi[t].

Агенты с номерами kV[t] не участвуют во взаимодействии, так что соответствующие им гиперребра одноэлементны. Столбец инцидентности I(k,[t]) каждого такого гиперребра содержит единственную единицу на месте, отвечающем агенту с номером kV[t].

С учетом всего вышесказанного модель данной МАС в векторноматричной форме представляется с использованием столбцов инцидентности гиперребер взвешенного неориентированного гиперграфа, ассоциированного с МАС:

P[t] = WI(he[t]) I(he[t])T + k V[t] I(k,[t]) I(k,[t])T.

Пример матрицы Р[t] модели МАС с УГВА и ППСА при m=5, некотором t (опущено) и V[t]={2,3,5}:

Матрицы P[t] являются марковскими [3]. Для достижения равной выгоды существенны наличие и единственность единичного собственного значения этих матриц.

Список использованных источников 1. Блюмин С.Л. Полные гиперграфы. Спектры лапласианов. Мультиагентные системы// Управление большими системами. – 2010. – № 30. – С.5-23.

2. Блюмин С.Л. Мультиагентные системы: проблемы и протоколы согласия, псевдообращение лапласианов графов // Системы управления и информационные технологии. – 2007. - № 2(28). – С. 4-9.



Pages:     || 2 | 3 | 4 | 5 |   ...   | 19 |
 


Похожие материалы:

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ ИМЕНИ Н.И. ВАВИЛОВА АГРАРНАЯ НАУКА В XXI ВЕКЕ: ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ Сборник статей VIII Всероссийской научно-практической конференции САРАТОВ 2014 1 УДК 378:001.891 ББК 4 Аграрная наука в XXI веке: проблемы и перспективы: Сборник ста- тей VIII Всероссийской научно-практической конференции. / Под ред. И.Л. Воротникова. – Саратов, 2014. – 580 с. ...»

«Введение О Болонском процессе, к сожалению, мало пишут в Рос- сийской академической прессе. Только по касательной привлекает он к себе внимание участников многочисленных научно-теоретических конференций и симпозиумов. Сужде- ния отдельных коллег о сущности Болонского процесса, его целях и характере, которые доводилось слышать в частных беседах и на собраниях различных академических сооб- ществ, нередко резко контрастировали друг с другом. Для одних – реформирование высшего образования России в ...»

«СБОРНИК СТАТЕЙ СДУДЕНЧЕСКИХ НАУЧНО- ПРАКТИЧЕСКИХ КОНФЕРЕНЦИЙ ФАКУЛЬТЕТА АГРОТЕХНИКИ И ЭНЕРГООБЕСПЕЧЕНИЯ КАФЕДРЫ ИНЖЕНЕРНОЙ ГРАФИКИ И МЕХАНИКИ 2012-2013Г Часть -1 ОРЕЛ-2013 Содержание Мир машин – 1 Бабенков А.И. Т-302 Руководитель: ст. преподаватель Дубинина О.И. РОТОРНО-ПОРШНЕВОЙ ДВИГАТЕЛЬ ВНУТРЕННЕГО СГОРАНИЯ………………………………. 8 Гайдук Е.В. АИБ-301 Руководитель: ст.преподаватель Дубинина О.И. ПЛАСТМАССЫ……………………………………………. 12 Германский М. Т-302 Руководитель: ст.преподаватель Дубинина О.И. ...»

«Лениногорский филиал X Всероссийская научно-практическая конференция ВЗАИМОДЕЙСТВИЕ НАУКИ И ПРАКТИКИ КАК МЕХАНИЗМ ЭФФЕКТИВНОГО РАЗВИТИЯ СОВРЕМЕННОГО ОБЩЕСТВА Рекомендовано Ученым советом ЛФ КНИТУ-КАИ Том II Казань 2014 УДК 378 ББК 74.58 В 40 Рекомендовано Учебным советом ЛФ КНИТУ-КАИ ОРГАНИЗАЦИОННЫЙ КОМИТЕТ Шафигуллин Н.Г. –директор ЛФ КНИТУ-КАИ, к. и. н. Данилова О.Л. – зам. директора по НР ЛФ КНИТУ-КАИ к. ф. н. Шамсутдинов Р.А. – зав. кафедрой ЕНГД, к. с. н. Горшенин Г.С. – зав. кафедрой ...»






 
© 2013 www.kon.libed.ru - «Бесплатная библиотека научно-практических конференций»