Книги по разным темам
Pages: | 1 | 2 | 3 | 4 | 5 | и величина сдвига tS (tS Z0 ), Предикатный символ описывает тогда бинарное отношение временного следоваT3 = ЗА(T1,T 2,tS ) =< T3,tT 3,T 3,lT 3 >.
ния на декартовом произведении U U.
Терм T3 содержит описания всех функДля термов циональных задач, входящих в T1 и T 2, T1 =< T1,tT1,T1,lT1 > при этом и tT 3 = tT1, T 3 = T1 + T 2 + tS.
T 2 =< T 2,tT 2,T 2,lT 2 > Логические векторы не изменяются.
предикат T1 T 2 истинен, если Функциональный символ @ описыtT1 + T1 = tT 2, и ложен в противном слувает операцию привязки начала выполнечае.
ния УА к абсолютному значению времеПредикатный символ < описывает ни. Пусть дан терм бинарное отношение предшествования на T =< T,tT,T,lТ > декартовом произведении U U. Для и значение момента времени термов t0 (t0 Z0 ), T1 =< T1,tT1,T1,lT1 > тогда и T1 =< T1,tT1,T1,lT1 >.
T 2 =< T 2,tT 2,T 2,lT 2 > Терм T1 содержит описания всех функпредикат T1 этом tT1 = t0, T1 = T и логические вектоПредикатный символ < описывает ры не изменяются. бинарное отношение сильного предшестПредикатные символы расширенного вования на декартовом произведении исчисления УА РВ U U. Для термов T1 =< T1,tT1,T1,lT1 > Предикатные символы, одноимённые с функциональными, будем обозна- и чать курсивом. Пусть U - множество T 2 =< T 2,tT 2,T 2,lT 2 > управляющих алгоритмов реального врепредикат T1 tT1 + T1 < tT 2, и ложен в противном слуПредикатный символ СН описывает чае. бинарное отношение совпадение по наПредикатный символ <> описывает чалу на декартовом произведении U U. отношение несовместности по времени. Для термов Это бинарное отношение на декартовом T1 =< T1,tT1,T1,lT1 > произведении U U, где U - множество и управляющих алгоритмов реального вреT 2 =< T 2,tT 2,T 2,lT 2 > мени. Для термов предикат T1СНT 2 истинен, если tT1 = tT 2, T1 =< T1,tT1,T1,lT1 > и ложен в противном случае. и Предикатный символ СК описывает T 2 =< T 2,tT 2,T 2,lT 2 > бинарное отношение совпадение по конпредикат T1<>T 2 истинен, если цу на декартовом произведении U U. (tT1 + T1 < tT 2 ) (tT 2 + T 2 < tT1), и ложен в Для термов противном случае. T1 =< T1,tT1,T1,lT1 > Предикатный символ описывает и бинарное отношение несовместности по Вестник Самарского государственного аэрокосмического университета № 2 (26) 2011 г. огике на декартовом произведении системы УА РВ следует, что любое отноU U. Для термов шение на множестве функциональных задач однозначно определяется отношенияT1 =< T1,tT1,T1,lT1 > ми <, >, = на декартовом произведении и N N {0,1}J, где J размерность логиT 2 =< T 2,tT 2,T 2,lT 2 > ческого вектора, обусловливающего выпредикат истинен, если несовместны полнение функциональных задач данного логические векторы, обусловливающие множества. Аналогично, любая операция выполнение T1 и T 2, и ложен в противна множестве функциональных задач одном случае. нозначно определяется стандартными Построение спецификации с помощью операциями умножения и сложения на формул исчисления УА РВ множестве целых чисел. Это позволяет проводить описание УА РВ с помощью Будем называть функциональную системы алгебраических уравнений отнозадачу вполне определённой, если для неё сительно времени начала и длительности известны время начала t, длительность частично определённых функциональных и обусловливающий её выполнение логизадач. ческий вектор. В противном случае буСодержательно алгоритм построедем называть функциональную задачу чания алгебраической модели по специфистично определённой. кации УА РВ состоит из следующих шаПусть требуется описать специфигов: кацию взаимодействия управляющих ал1) спецификация переводится в ПОгоритмов, состоящих из N функциональЛИЗ; ных задач: f1,..., fN, при этом K N за2) для каждого оператора в записи дач вполне или частично определены. Товыполняются следующие правила: гда спецификацию можно записать в виде - если оператор выражает отношение на множестве функциональных P1( f1,..., fN ), задач, то определяются время начала, P ( f1,..., fN ), длительность, координаты условного вектора операндов и формулируется уравнение или неравенство, соответ P ( f1,..., fN ), M ствующее данному отношению. Каж дая часть полученного соотношения f1 : = '1, t1 = t '1, = '1, 1 умножается на характеристическую f2 : = '2, t2 = t '2, = '2, функцию соответствующего логиче ского вектора; fK : = 'K, tK = t 'K, = 'K. - если оператор определяет опе K K рацию на множестве функциональных задач, то определяются время начала, Здесь Pi ( f1,..., fN ) представляет содлительность, координаты условного бой формулу, выражающую композицию вектора операндов и над ними выполопераций или отношений алгебраической няются преобразования, задаваемые системы УА РВ для функциональных заданной операцией. дач f1,..., fN. Оптимизация Моделирование операций и отношений Оптимизирующие преобразования алгебраической системы системой алгебраической модели заключаются в уравнений нахождении решения полученной систеИз приведённых выше определений мы уравнений относительно переменных, отношений и операций алгебраической соответствующих времени начала и дли Управление, вычислительная техника и информатика тельности частично определённых функ- 17) ( =1) (T1 СН T2) = (( =1) 1 циональных задач. При этом возможны T1)СН (( = 1) T2), три варианта: 18) ( =1) (T1 СК T2) = (( =1) 1 1) Система является определённой. В этом случае оптимизация может считаться T1)СК(( =1) T2), завершённой. Все функциональные задачи 19) T1 СН T1 = T1, являются вполне определёнными. В этом 20) T1 СК T1 = T1, случае спецификация не будет содержать 21) ( T ) + (м T ) = T, ни одной формулы. 2) Система несовместна. Специфика- 22) ( ( T )) = ( ) T. ция некорректна, то есть содержит услоС помощью этих тождеств можно вия, противоречивые с точки зрения логи- осуществить синтаксическую редукцию ки или по времени. (эквивалентные преобразования, сокра3) Система является неопределённой. щающие длину формулы) спецификации Решение представляет собой выражение УА РВ. значений логических и временных харакРассмотрим пример. Пусть в специтеристик одних функциональных задач фикации присутствует формула (свободные переменные системы) через (( f1 f2)СН( f1 f3)) СК( f4 ( f2 СН f3)). огические и временные характеристики других функциональных задач (базисные Применяя тождества 7, 8, эту форпеременные). При этом возможна оптимимулу можно преобразовать к виду зация, заключающаяся в минимизации ( f1 СК f4 ) ( f2 СН f3). выражений свободных переменных через При этом происходит уменьшение колибазисные. чества операций в два раза. Формальные преобразования специфи- В качестве внутреннего представлекации УА РВ ния оптимизируемых формул управляющего алгоритма будем рассматривать их Из приведённых выше определений двоичные деревья синтаксического разбоотношений алгебраической системы УА ра. Оптимизация двоичных деревьев проРВ следуют тождества: водится в два этапа: 1) T1 СН T2 = T2 СН T1, 1) идентификация двоичных поддеT1 СК T2 = T2 СК T1, 2) ревьев; T1 + T2 = T2 + T1, 3) 2) применение к поддеревьям аксиомы сжатия, если это возможно. (T1 T2 ) T3 = T1 (T2 T3), 4) Существует несколько способов (T1 СН T2 ) СН T3 = T1 СН (T2 СН T3), 5) идентификации одинаковых поддеревьев. (T1 СК T2 ) СК T3 = T1 СК (T2 СК T3 ), 6) Первый подход - метод прямого сравнения, то есть для каждого узла сравниваем (T1 T2 )СН (T1 T3) = T1 (T2 СН T3), 7) все поддеревья. Второй подход - метод 8) (T1 T2 )СК(T3 T2 ) = (T1 СК T3) T2, простых чисел. Все узлы двоичного дере9) (T1 T2 ) + (T1 T3 ) = T1 (T2 + T3 ), ва нумеруются простыми числами, опера10) (T1 T2 ) + (T3 T2 ) = (T1 + T3) T2, ции СН, СК,, + получают коды 2, 3, 5, 11) (T1 СН T2 ) + (T1 СН T3) = T1 СН (T2 + T3), 7. Узлы, соответствующие одной и той же операции или одной и той же функцио12) (T1 СН T2 ) + (T3 СН T2 ) = (T1 + T3) СН T2, нальной задаче, нумеруются одинаковыми 14) (T1 СК T2 ) + (T1 СК T3) = T1 СК (T2 + T3), числами. Для идентификации поддерева 15) (T1 СК T2 ) + (T3 СК T2 ) = (T1 + T3 ) СК T2, производится перемножение кодов всех узлов, входящих в него. Некоммутатив16) ( =1) (T1 T2) = (( =1) 1 ные операции и + для различения лево T1) (( =1) T2), го и правого поддеревьев в случае равен Вестник Самарского государственного аэрокосмического университета № 2 (26) 2011 г. ства произведений используют приписы- рующей управляющей программе, понивание знака минус (л). Недостатком жая тем самым её структурную сложность метода простых чисел является быстрое (сложность управляющего графа, связанпереполнение. Поэтому вместо него воз- ного с потоком управления). Кроме того, можно применение метода лцелых чисел, алгебраический метод синтаксической рев котором узлы-поддеревья кодируются дукции формул позволяет проверить корцелыми числами. Однако при этом необ- ректность задания временных и логичеходимо иметь в памяти таблицу, описы- ских условий управляющего алгоритма. вающую каждый подузел с информацией Данный подход приводит к квазиоптио его левом, правом поддереве и месте в мальному решению (как таковая, строго дереве. говоря, задача оптимизации в классичеРассмотрим алгоритм проведения ской постановке не ставится). эквивалентных преобразований на бинар- Таким образом, метод формальных ных деревьях. Этот алгоритм начинает преобразований обеспечивает квазиоптиобработку с самых нижних поддеревьев, а мальность построенного решения. затем, поднимаясь выше, охватывает все Библиографический список большее количество узлов. Поддеревья 1. Мальцев, А. И. Алгебраические соединяются с помощью узла-операции, системы [Текст] / А. И. Мальцев. - Москпричём в конструкции D1 f D2 (поддерева: Наука, 1970. - 400 с. во, над которым в текущий момент рабо2. Касьянов, В. Н. Графы в програмтает алгоритм) поддеревья D1 и D2 уже мировании: обработка, визуализация и отработаны, поэтому по ним надо спусприменение [Текст] / В. Н Касьянов, В. А. титься максимум на один - два уровня. Евстигнеев. - СПб.: БХВ - Петербург, Таким образом, процесс эквивалентных 2003. - 1104 с. преобразований носит индуктивный ха3. Калентьев, А. А. Автоматизирорактер. Базисом индукции является исванный синтез алгоритмов асинхронного ходное двоичное дерево представления управления техническими системами с алгоритма D0. Шаги индукции проводятмножеством дискретных состояний ся применением аксиом исчисления [Текст] / А. А Калентьев. - Самара: управляющих алгоритмов. На каждом шаСГАУ, 1998. - 204 с. ге индукции получаем эквивалентное пре4. Тюгашев, А. А. Синтез и верифидыдущему двоичное дерево Dj. Последо- кация управляющих алгоритмов реального времени для бортовых вычислительвательность D0, D1,..., Dk длины k +1 назоных систем космических аппаратов вём выводом D0 Dk. [Текст]: дис. Е д-ра техн. наук / А. А. Тюгашев. - Самара: Изд-во СГАУ, 2007. Заключение - 312 с. Необходимо заметить, что приведённые методы синтаксической редукции спецификации УА РВ уменьшают количество информационных связей в результи Управление, вычислительная техника и информатика CONSTRUCTING THE SPECIFICATION FOR THE ON-BOARD REALTIME CONTROL ALGORITHM й 2011 A. A. Tyugashev, A. Yu. Bogatov Samara State Aerospace University named after academician S. P. Korolyov (National Research University) An approach to solving the problem of the on-board algorithm specification is proposed. This approach is founded on the calculus of a realtime control algorithm. The possibility of the automation of syntax reduction for the specification is also considered. Mathematical model, specification, control algorithm, equivalent optimizing transformations, functional task, system of linear equations, binary tree, predicate. Информация об авторах Тюгашёв Андрей Александрович, доктор технических наук, профессор кафедры компьютерных систем. Самарский государственный аэрокосмический университет имени академика С. П. Королёва (национальный исследовательский университет). Область научных интересов: разработка ИПИ-технологий на проблемно- ориентированном уровне. E-mail: tau797@mail.ru. Богатов Артём Юрьевич, аспирант, ассистент кафедры компьютерных систем. Самарский государственный аэрокосмический университет имени академика С. П. Королёва (национальный исследовательский университет). Область научных интересов: теория алгоритмов, CALS-технологии. E-mail: artmbogatov@yandex.ru. Tyugashev Andrey Alexandrovitch, doctor of technical sciences, professor of the department of computer systems, Samara State Aerospace University named after academician S. P. Korolyov (National Research University), tau797@mail.ru. Area of research: informatics and CALS-technology. Bogatov Artyom Yurievitch, assistant of the department of computer systems, Samara State Aerospace University named after academician S. P. Korolyov (National Research University), artmbogatov@yandex.ru. Area of research: theory of algorithms and CALStechnology. Вестник Самарского государственного аэрокосмического университета № 2 (26) 2011 г. ББК 65.УДК 004.СОГЛАСОВАНИЕ МЕХАНИЗМОВ УПРАВЛЕНИЯ ПРОЦЕССАМИ КОНСРУКТОРСКО-ТЕХНОЛОГИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА НА УРОВНЕ СОТРУДНИКОВ ПОДРАЗДЕЛЕНИЙ й 2011 А. С. Кириченко 1, И. Н.Хаймович ФГУП ГНПРК - ЦСКБ-Прогресс Самарский государственный аэрокосмический университет имени академика С. П. Королёва (национальный исследовательский университет) Статья посвящена описанию автоматизации в конструкторско-технологической подготовке производства, выявлению проблем и их решению. Полученная математическая модель позволяет устранить противоречия между сотрудниками конструкторских и технологических подразделений. Конструкторско-технологическая подготовка производства, математическая модель, принятие решений, доход, автоматизация. В современном мире, когда начина- изделием, привести к типовому процессу. ют говорить об автоматизации конструк- И чем ближе новый технологический торско-технологической подготовки про- процесс к типовому, тем меньше времени изводства (КТПП), в основном рассматри- понадобится на его освоение и тем больвают интеграцию CAD/CAE/CAM/PDM- шее количество деталей сможет произвосистем в производство, с повышением их дить предприятие. Книги по разным темам