WWW.KNIGI.KONFLIB.RU

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

 
<< HOME
Научная библиотека
CONTACTS

Pages:     | 1 |   ...   | 5 | 6 || 8 |

«САМАРСКИЙ ИНСТИТУТ ИНЖЕНЕРОВ ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Кафедра телекоммуникаций на железнодорожном транспорте СОВРЕМЕННЫЕ ТЕХНОЛОГИИ РАЗРАБОТКИ И ТЕСТИРОВАНИЯ ...»

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

A1A2A3··· параметр D2 встречается в двух модулях: A2 и A3, в модуле A2 этот параметр является вычисляемым и не требует предварительной инициализации, а в модуле A3 - инициируемым и должен принять значение заранее. Но, так как модуль A2 в этой цепочке встречается раньше, то D2 не нужно заранее инициализировать. Таким образом, на этом маршруте параметр D2 необходимо отнести к классу вычисляемых. С другой стороны, если данное встречается впервые как инициируемое (внешнее), то его следует отнести к классу внешних данных.

Введем операцию конкретизации классификационных признаков для линейных маршрутов, применение ее к объектам маршрута при построении паспорта маршрута представим следующим образом:

где P( ) - паспорт соответствующего объекта.

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

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

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

Классификация параметров граф-агрегата P(G) будет определяться полученными паспортами всех маршрутов:

где - операция над данными объектов, реализующая объединение паспортов маршрутов.

Определим семантику для введенных операций. Пусть заданы два объекта A и B с соответствующими паспортами:

Обозначим классификационные признаки данных следующим образом:

“0” - d P(A) - данное не принадлежит модулю A;

“1” - d D in - данное принадлежит модулю A и является входным (инициируемым);

“2” - d D out - данное принадлежит модулю A и является вычисляемым.

Тогда таблица истинности операций следования и объединения имеет вид (см.

табл. 3.2):

Формально операции следования и объединения описываются следующим образом:

а) классификация данных в граф-агрегате на основании выполнения операции следования:

б) классификация данных в граф-агрегате на основании объединения паспортов цепочек A и B (операция объединения):

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

1. Ассоциативность операций следования и объединения:

2. Коммутативность для операции объединения:

3. Операция следования дистрибутивна слева относительно операции объединения:

4. Идемпотентность операций следования и объединения:

5. Поглощение для операции следования относительно операции объединения:

6. Отбрасывание общего окончания для операции следования:

7. Свойство симметричного поглощения для операции следования:

(AC)(BC)(AB) = (AC)(BC)(BA) = (AC)(BC) Представленные свойства операций следования и объединения позволяют оптимизировать алгоритм классификации данных за счет сокращения количества маршрутов и уменьшения их длины. Рассмотрим возможный способ применения этих свойств на примере графа G1 (рис. 3.5). На первом этапе для каждого из четырех маршрутов графа (см. рис.3.6) строятся паспорта, при этом используется операция следования:

На втором этапе, полученные паспорта цепочек объединяются, образуя паспорт данных граф-агрегата:

P(G1) = P(R1) P(R2) P(R3) P(R4) = Полученное выражение можно существенно сократить, если применить к нему преобразования, основанные на свойствах операций, в частности, свойство 6 отбрасывание общего окончания для операции следования. Очевидно, что выражения для цепочек R1 и R2:

имеют общее начало ( A1 A2 ) и общее окончание ( A3 A6 ). На основании свойств и 6 можно преобразовать к виду:

Таким образом, применяя последовательно свойства 1, 6 и 4 (поглощение следования относительно объединения), имеем:

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

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

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

Для реализации алгоритма сжатия количества операций предлагается использовать аксиомы 4, 5 и 6, которые сформулируем как правила вывода в форме метаформул:

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

Алгоритм упрощения формулы классификации данных состоит из следующих шагов:

1. Все дизъюнкты упорядочиваются, в первую очередь, по длине и лексикографически, в случае одинаковой длины. Более длинные дизъюнкты ставятся на первое место.

2. К каждому дизъюнкту применяется правило П1 до тех пор, пока это возможно.

3. К каждому дизъюнкту, начиная с первого, применяется правило П3. Причем, контактный “партнер” ищется на множестве дизъюнктов меньшей длины. Если правило П3 реализуется, то множество дизъюнктов переупорядочивается.

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

Работу предложенного алгоритма рассмотрим на примере упрощения формулы классификации данных агрегата G1:

A1, A2, A4, A3, A6 применим правило A1, A2, A3, A6 применим правило В результате исходная формула (3.1) упростилась до вида (3.2), количество операций сократилось с 14 до 8. Вычислительные эксперименты показали, что сокращения числа операций на реальных объектах в среднем составляет 50%, причем, с ростом цикломатического числа, когда число маршрутов нарастает, производительность алгоритма сжатия операций увеличивается.

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

Главной проблемой этого метода является комбинаторный рост числа циклов с ростом цикломатического числа графа (см. табл.3.3) и ограниченность типов рассматриваемых циклов. Цикломатика обеспечивает перечисление простых и сложных циклов, не рассматривая составные циклы, когда одна или несколько дуг повторяются. На рис.3. показан граф, имеющий составной цикл R={a, b, c, a, d}.

В работах [26, 34] предлагается метод классификации типов данных, основанный на реализации частичного перебора маршрутов граф-агрегата.

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

Маршруты ориентированного графа будем описывать списками вершин. Данный подход менее удобен, чем при использовании списка дуг, поскольку часто содержит повторяющиеся вершины. Например, маршрут M={A, B, E, F, B, C, D, B, G} графа G2 (см.

рис. 3.8) повторяет вершину B три раза.

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

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

Свободными вершинами графа G относительно схемы маршрута S будем называть вершины графа, не содержащиеся в схеме маршрута S, т.е. L ( S ) = V ( G ) \ V ( S ), где V(G) и V(S) - соответственно вершины графа и схемы маршрута.

Алгоритм частичного перебора (АЧП) использует следующие правила:

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

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

3. Если переход возможен, то схема маршрута “расширяется” на один символ.

4. Если переход невозможен, то рассматривается следующая вершина списка свободных вершин и так до тех пор, пока не кончится список вершин.

5. Если переход из текущей вершины в любую из свободных вершин (не содержащихся в схеме маршрута) невозможен, то происходит “откат” по схеме маршрута на один символ назад.

6. При достижении концевой вершины алгоритм “откатывает” на один символ назад.

7. Алгоритм завершает свою работу, если список свободных вершин корневой вершины исчерпан.

Схема маршрута L = {v 0, v1,..., v m } реализует сжимающее кодирование маршрутов на орграфах, поскольку описывает путь из корневой вершины в концевую v 0 v m через любое количество повторений, предшествующих vm вершин. Схема маршрута позволяет закодировать любые маршруты орграфа: простые, сложные и составные.

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

Покажем, что алгоритм АЧП реализует частичный перебор схем маршрутов. В качестве примера рассмотрим граф G1, вершины которого пронумеруем так, как это показано на рисунке 3.9. Алгоритм АЧП формирует множество схем маршрутов, реализуя разбиение исходной задачи на взаимно независимые подзадачи в соответствии со стратегией И/ИЛИ-графов [4]. Построим мультиграф с двумя типами вершин.

Вершины типа “И” помечаются номерами вершин исходного графа, вершины типа “ИЛИ" помечаются списками вершин, достижимых (смежных) и недостижимых из соответствующей “И”-вершины графа. Правила алгоритма АЧП позволяют на каждом шаге алгоритма множество свободных вершин разбить на две части: достижимое и недостижимое подмножества. Причем достижимость понимается либо как непосредственный переход по дуге графа, либо, опосредованно, через вершины предшествующего уровня иерархии, т.е. в соответствии со схемой маршрута.

На рисунке 3.10 а) показан И/ИЛИ-граф алгоритма АЧП для графа G1. Решением задачи перечисления схем маршрутов является подграф И/ИЛИ-графа, из которого исключены ИЛИ вершины (см. рис. 3.10 б)).



Pages:     | 1 |   ...   | 5 | 6 || 8 |
 


Похожие работы:

«БАМ В. Б. ЛАВРЕНТЬЕВ ВОЖДЕНИЕ АВТОМОБИЛЕЙ ВЫСОКОЙ ПРОХОДИМОСТИ МОСКВА ТРАНСПОРТ 1974 УДК 656.13.052.56:629.113.028 ПРЕДИСЛОВИЕ Вождение автомобилей высокой проходимости. Лаврентьев В. Б. М., Транспорт, 1974. 96 г. В книге рассмотрены основные элементы конструкции полноприводных автомобилей с точки зрения влияния на их проходимость по профильным препятствиям и слабым грунтам. Процессы, происходящие при взаимодействии элементов ходовой части с грунтом автомобиля высокой проходимости при его...»

«А.И. КОРОБЧЕНКО, С.П. ПАРФЕНОВ Воспитание выносливости средствами лыжной подготовки Учебно-методическое пособие для студентов всех специальностей Иркутск 2009 УДК 796 ББК 75 В77 Рецензент Г.К. Хомяков, канд. мед. наук, директор спорткомплекса Изумруд Коробченко А.И., Парфенов С.П. В77 Воспитание выносливости средствами лыжной подготовки : учеб.методическое пособие / А.И. Коробченко, С.П. Парфенов. Иркутск : ИрГУПС, 2009. – 60 с. В данном пособии раскрывается смысл и польза занятий лыжными...»

«ПРИБОР ПРИЕМНО-КОНТРОЛЬНЫЙ ОХРАННО-ПОЖАРНЫЙ ППКОП 01059 - 56 - 4 “ДОЗОР - 4” РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ НН 2.406.002 РЭ. Руководство по эксплуатации 1. ОБЩИЕ СВЕДЕНИЯ 1.1. Основные возможности 2. ТЕХНИЧЕСКИЕ ДАННЫЕ 3. ПОРЯДОК УСТАНОВКИ ПРИБОРА И ПОДГОТОВКИ К РАБОТЕ 3.1. Монтаж 3.2. Установка напряжений нормы в шлейфах и режима работы 4. ИСПОЛЬЗОВАНИЕ ПРИБОРА 4.1. Режим 0 - технологический контроль 4.2. Режимы 1, 2, 3, 4, 5 - пожарная сигнализация 1.3. Режимы 6, 7, 8, 9 - пожарная и охранная...»

«ФИНЛЯНДИЯ ШВЕЦИЯ НОРВЕГИЯ ДАНИЯ ж/Д И АВИАТРАНСПОРТ 3 СхЕМА ж/Д ВОКзАЛА В САНКТ-ПЕТЕРБУРГЕ Посадка на автобусы в санкт-Петербурге Автобусы Вокзал ДЛЯ АВИАТУРОВ вылет из аэропорта Шереметьево, терминал 2 (SVO-2) Встреча в аэропорту. Регистрация на международные рейсы начинается за 2 часа. Мы назначаем время встречи за 2,5–3 часа до вылета и настоятельно рекомендуем прибыть не позднее указанного времени. как проехать в аэропорт Шереметьево: на экспрессе с Савёловского вокзала. Железнодорожный...»

«КАТАЛОГ ДЕТАЛЕЙ И СБОРОЧНЫХ ЕДИНИ Ц ЧАСТЬ ПЛАНЕР КНИГА 3 2 4 (включая раздел 24.43.00) Глава КАТАЛОГ ДЕТАЛЕЙ И СБОРОЧНЫХ ЕДИНИЦ ПЕРЕЧЕНЬ ГЛАВ КАТАЛОГА Номер Наименование главы ВВЕДЕНИЕ Часть I - УКАЗАНИЯ ПО ОБЩЕМУ ОБСЛУЖИВАНИЮ Хранение самолета (наземное оборудование) 12 Часть 2 - ПЛАНЕР. Книга I 20 Общие указания Фюзеляж 21 Часть 2 - ПЛАНЕР. Книга 2 Двери и люки 22 Окна 23 Оперение 25 Пилоны 26 Часть 2. - ПЛАНЕР. Книга 3 Крыло (включая раздел 24.43,00) 24 Часть 2 - ПЛАНЕР. Книга 4 Крыло (с...»

«ПЕРЕЧЕНЬ ДЕЙСТВУЮЩИХ НОТАМ Cледующие НОТАМ действуют по состоянию на 06 марта 2014 0500 UTC НОТАМ, не включенные в перечень, аннулированы, или срок их действия истек, или внесены в АИП книга 4 очередной Поправкой   СЕРИЯ Д  (Д0013/13 НОТАМН Щ)УЕЕЕ/ЩПИЬЬ/И/НБО/А/000/999/6022С13426В015 А)УЕМУ Б)1303070900 Ц)ПОСТ Е)ВМЕСТО КООРДИНАТ ТРЕТЬЕГО РАЗВОРОТА: N601205.3 E1341811.1 4ИТАТЬ N601252.9 E1342055.7. ВМЕСТО КООРДИНАТ 4ЕТВЕРТОГО РАЗВОРОТА: N601319.5 E1341258.8 4ИТАТЬ N601407.1 E1341543.3. ДЛЯ ВС СО...»

«© Honda Motor Co., Ltd. 2006 ВАЖНАЯ ИНФОРМАЦИЯ КОНСТРУКЦИЕЙ ДАННОГО МОТОЦИКЛА ПРЕДУСМОТРЕНО ЕГО ИСПОЛЬЗОВАНИЕ ИСКЛЮЧИТЕЛЬНО В СПОРТИВНЫХ СОСТЯЗАНИЯХ, ВСЛЕДСТВИЕ ЧЕГО НА НЕГО НЕ РАСПРОСТРАНЯЕТСЯ ДЕЙСТВИЕ ГАРАНТИИ. ДАННЫЙ МОТОЦИКЛ НЕ СООТВЕТСТВУЕТ ТРЕБОВАНИЯМ СТАНДАРТОВ ПО БЕЗОПАСНОСТИ, ПРЕДЪЯВЛЯЕМЫМ К ТРАНСПОРТНЫМ СРЕДСТВАМ, КОТОРЫЕ ПРЕДНАЗНАЧЕНЫ ДЛЯ ЭКСПЛУАТАЦИИ НА ДОРОГАХ ОБЩЕГО ПОЛЬЗОВАНИЯ, ВСЛЕДСТВИЕ ЧЕГО ЭКСПЛУАТАЦИЯ ДАННОГО МОТОЦИКЛА НА ДОРОГАХ ОБЩЕГО ПОЛЬЗОВАНИЯ КАТЕГОРИЧЕСКИ ЗАПРЕЩЕНА....»

«rr.by СООБЩЕНИЯ. РАЗНОЕ Витебск 38 i КАК ПОДАТЬ ЧАСТНОЕ ОБЪЯВЛЕНИЕ В ГАЗЕТУ “ИЗ РУК В РУКИ”? ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ Условия приема на стр. 39 № 96(958) Витебск и Витебская область Рекламное издание СП “БЕЛПРОНТО”...»

«rr.by СООБЩЕНИЯ. РАЗНОЕ Витебск 37 i КАК ПОДАТЬ ЧАСТНОЕ ОБЪЯВЛЕНИЕ В ГАЗЕТУ “ИЗ РУК В РУКИ”? ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ Условия приема на стр. 38 № 35(997) Витебск и Витебская область Рекламное издание СП “БЕЛПРОНТО”...»

«ES-TEN-0407 РЕВЕРСИВНЫЕ ВИБРОПЛИТЫ TEN Руководство по эксплуатации 1 TEN2540- TEN2550-TEN3040- TEN3050 СОДЕРЖАНИЕ 1 ВВЕДЕНИЕ...4 2 ПРАВИЛА ТЕХНИКИ БЕЗОПАСНОСТИ..4 2.1 БЕЗОПАСНОСТЬ ПРИ РАБОТЕ С ОБОРУДОВАНИЕМ. 2.2 БЕЗОПАСНОСТЬ ПРИ РАБОТЕ С ДВИГАТЕЛЕМ. 2.3 БЕЗОПАСНОСТЬ ПРИ ТЕХНИЧЕСКОМ ОБСЛУЖИВАНИИ 2.4 МАРКИРОВКИ. 3 УТИЛИЗАЦИЯ...7 4 ТЕХНИЧЕСКИЕ ХАРАКТЕРИСТИКИ..7 4.1 ХАРАКТЕРИСТИКИ ДВИГАТЕЛЯ 4.2 ХАРАКТЕРИСТИКИ ВИБРОПЛИТЫ. 4.3 МАКСИМАЛЬНЫЙ НАКЛОН ПЛИТЫ В ПРОЦЕССЕ РАБОТЫ 4.4 АКУСТИЧЕСКИЕ И...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.