Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 90
Текст из файла (страница 90)
5.99 канале элемента В, . Кслн при эхом находился элемент В;, не обеспечивающий согласованное функционирование цепей (условия поведения злеменха В; противоречивы), то соахветсхвуюший интервал просхранства Рь,„являлся нереализуемым и в дальнейшем не рассматривался. Для оптимальнага по времени выявления всех аномалий динамических свойсхв введем граф связности !ясв — (дХ!д! 77) ! в котором каждая вершина взаимно однозначно соохветсхвует вектору Х; пространства Р„, ребро (Х;, ХУУ' Е 77 — критическому решетчатому интервалу,7(Х;, Х ), где Х;, Х вЂ” концы соохветсхвующей храссы. Для выявления всех аномалий при логическом моделировании нейронной сехи, не повторяя ни одну нз трасс, необходим однократный обход всех ребер графа связносхи С„, следовательно, граф С„должен быть эйлеровым. Гл.б.
П их«одни« тео ив алгоритмов 512 5 5.11. Оценка динамики логических структур 513 Для минимизации времени формирования входных векторов Х; необходимо отсутствие их повторения, следовательно, граф С, должен быть гамильтоновым. Используя характеризационный анализ, можно показать, что граф связности С„ эйлеров и гамилыонов тогда и талька тогда, когда его цикломатическое число а(С,В) равно нулю и его степень 5(С,В) не превышает двух: (и(Сев) = 0) 5ь(5(Сев) < 2). При этих условиях граф С,в является линейно упорядочнваемым.
Запрещенными фигурами исследуемого свойства графа связности являются циклы и вершины со степенью, превышающей 2. Если граф С„не является эйлеровым и гамилыоновым, та расширением носителя (ЬХ) устраняем циклы и вершины Х; со степенью 5(Х;) > 3 и линейно упорядочиваем граф С, . Линейно упорядоченный граф С„= ((Х; 0»5 Хь), Ц определяет входную сигнальную программу выявления аномалий динамических свойств нейронных сетей.
Анализ графов связности для реальных сетей показал их малую связность. Учитывая это свойство, предложим следующий эффективный олгория7м расширения носителя графа С, и его линейного упорядочивания: 1) Сев '= С7'~ 2) 5(С;) < 2 7 Если да, то переходим к п. 3), если нет — к и. 4); 3) Ъ'(С<) > 0 7 Если да, переходим к и.
4), если нет — к и. 6); 4) определяем цепь максимальной длины к„«(в пределе— остов, графа) СП 5) С; ~ 7г,„в„.— — С;, в РезУлыиРУющем гРафе штРихУем повторяющиеся векторы Х;. Переход,к п. 2); 6) линейно упорядочиваем граф ((Х; 11.»ьХ ), ь»"); 7) конец. Пусть граф связности С„= ((Х;), Ц (рис.
5.96, а) имеет вид (Х / В = а, Ь, с, Ы, е, Ь, яь), 77 = ((Х„Хь), (Х„Х,), (Х„Х»), (Хь, Х,), (Хь, Х,), (Х„Х„), (Х„Х,), (Х„Х,), (Х„Х,), (Х„Х,), (Х, Х ), (Х», Хь), (Х», Х ), (Хь, Х )). Имеем запрещенные фигуры графа связности Хь Х, Хь Х, Х» Х. Хь Х, 5Х») 3 4 5 4 4 4 4 и восемь базисных циклов (рис. 5.96, 6): о(Сев) =!(У! — ! (Х;)! + 1 = 14 — 7+ 1 = 8, и(С,В) — цикломатическое число графа.
«ь «» «Л «» о Л7 «С «» «» а Рис. ь.эб Выделяем остов 7гт, состоящий из шести ребер (рнс. 5.97, а): ктвв = ((Х»7 Хь)7 (Хь! ХВ7)7 (Хтэ Хс)7 (Х»7 Хс)7 (Х Хы) (ХА ХВН С, ~ 7г,„= ((Х,', Х,'), (Х,', Хь), (Хь, Х,'), (Х,', Хь), (Х', Х„') (Х„', Х') (Х' Х») (Х' Х,'Ц. Степень графа С„'1 7г,„равна 3: 5(С„~7г ~) = 3. Следовательно, выделяем остов и',„, (рис. 5.97, 6): и',«т ((Хьь., Х,'), (Х,', Хь), (Хь, Х,'), (Х,', Х,'), (Х.', Хл), (Х', Х')), !7 В.
Л. ГЮР»Л >В 514 а «1-- хе б ,х «ел ,х„ хе! Рис. 3.97 «е те х~о хр «е «7 «5 «е «3 13 15 16 Га ге 21 гг 13 17 1О Птг 3 9 31 37 51 х, Х,: «~«г«ехе«ехе«7«ехе«ц~хихл Рис. 3.98 Продел«гение рис. 5.98 Гл.б. Прикладки«таеорих алгоритмов и производим его удаление: (1«„'1 к,„) 1 к' „= ((Х', Хь), (Х~ь, ХоЦ. Линейно упорядочиваем граф связности с учетом расширения его носителя (рис. 5.97, в): д.. кх ((Х; 15 ЬХ;), 1У'), ~Х1 15 ЬХ1) = (Х„Х,', Х, Х', Х„Х,', Х,", ~Х111ЬХ;~ = 15.
3 5.11. Оцеика дииамики логических структур 515 При реализации линейно упорядоченного графа связности 1« = (1Х; 0 т«Х11, У') имеем 14 ребер, 15 вершин, 7 из которых соответствуют повторениям входных векторов. ФУикииоиалом качества 1Р„кт Решении этой задачи бУдем считать число, равное количеству повторений входных векторов, т. е.
1оке = ш1п ЯЬХ1)1 ~. Прн <рк„„= 0 граф связности является как эйлеровым, так и гамильтоновым. Если эйлеровость графа характеризуется наличием и распределением вершин с нечетными степенями, то эффективное определение гамильтоновости графа является открытой проблемой. Поэтому предложим приближенное, но с практической точки зрения оптимальное решение этой задачи. Линейно упорядоченный граф связности определяет как объем памяти ти, так и время выполнения Т„входной сигнальной программы при моделировании аномалий динамических свойств ИС: 1„= ЦХ;11ЛХ;! — 1) а.„, Т„= ((Х; ~1 21Х;! — 1) . Т„.„,, где Т„о«,1 — время моделирования одного переключения Х; -+ Х .
Линейное упорядочение графа связности является третьим (завершающим) этапом синтеза входной сигнальной программы (ВС-программы). Синтезированная ВС-программа для нейронной сети (см. рис. 5.89) и построенных решетчатых интервалов ,У' —,Узо представлена на рис. 5.98. Для оценки переходного процесса в ИС предложим числовую характеристику в виде соответствующего функционала 1о(Т,(Х;, Х )), учитывающего распределение трасс, функциональ- 516 Табдида 5.68 з=1,2, ..., еп. ии ври*, реш.
интервала ,7; 'ььь ьтх;,х1 а х таьь н(х;,хг) У(т(хнх,В .У. 1ь 20,0 20 О, 12 20,0 20 1,13 20,0 4,8 3 20,0 20 5,9 10,0 6,10 20 10,0 10,0 20 4,14 10,0 1,0 3, 10 0,0 10 0,0 8, 14 О,О 9, 15 11,0 3,6 1З 11,0 1,2 14 13,3 20 2,12 15 3,3 20 4,10 18 33 20 6,8 17 7,3 0,13 18 37 11, 12 7,3 22 3,8 4 15 23 з,т 5,14 7,3 22 3,4 25 8,15 З,Т 9,14 11,0 12 2 13 28 0,9 22 5,10 0,9 6,9 Гл.5. Прикладная теория алгоритмов ные и топологические свойства ИС и временной дебаланс пере- ключаемых цепей в ИС: ьЩх„х;Я = (~ь (~атеях„хЛ), Х (Н(Хь, ХУ)!) 1 ° беттах(У(Х;, Х )) ) ), (5.24) ь ьь Здесь: У(Т(Х;, Ху)) — частота (количество) цепей (Х;, Х ) решетчатого интервала,у = (Х;, Ху), для которого функция риска сбоя з-го выходного канала Нь(ХО Х ) = 1 — количество трасс; Н(Х;, Х-) — расстояние по Хеммингу между точками Х; н Хд в булевом Й „;мерном пространстве; Ьт,(У(Х;, Х )) — максимальный временной дебаланс цепей при переключении векторов Х; +р Х для з-го выходного элемента ИС, 2, (,У(Х;, Ху)) = ( (Т„(Х;, Ху)) —;„(Т,(Х;, Х,))), где т (Ть(Х;, Х )) — максимальное время задержки переключения 'входного канала т „= шахта д(га), сь = 1, 2,..., й,„; т „(х ) — время задержки канала хо з-го выходного элемента для к-й трассы решетчатого интервала У(Х;, Х ); т;„(Ть(Х;, Х )) — минимальное время задержки переключения входного канала т;„= пппт, (хд),,8 = 1, 2,..., Й,х„ Р з-го выходного элемента для к-й трассы решетчатого интервала ,У(Хч Ху); Тя — количество выходных каналов логической структуры.
В функционале (5.24) частота трасс и соответствуюшие им расстояния по Хеммингу определяют функциональные свойства выходных элементов, дебаланс цепей — топологические свойства всей логической структуры. Значение функционала (5.24) мажорирует относительную задержку на входных каналах выходных элементов ИС. Для нормального функционирования время смены входных векторов (реактивность ИС) не должно превышать шах(Ьт (.У(Х<, Х ))), ь' Ьь т. е. временную задержку для наихудшего случая переключений.
Предложенный функционал (5.24) позволяет оценить переходные процессы на этапе логического проектирования. З 5.11, Оценка динамики логических етрукту 517 Чем меньше значение функционала (5.24), тем меньше переходной процесс влияет на функционирование логической структуры. На основе предложенного функционала оценки качества логического проекта (5.24), оценим переходной процесс в нейронной сети (см. рис. 5.85, 5.89 — 5.92).
Сведем вычисление функционала (5.24) в табл. 5.88. За едиииит ввдериви ирииаха ваде ива иа одном вдирье. Гл.б. 17рикааднаа теа и.в ааеаритмав 518 519 15.12. Семантическое проектирование ско остноо Суммируем элементы последнего столбца и, логарифмируя сумму, получаем ~е) = -(ч(1;дцх;, х э.
~н~х,, хсе-', 0 и гьгпьак ' Т(Хс ~ Ху) = 15230, 7 ~~ 2, 2. Минимизация функционала (5.24) осушествцяется с помощью уменьшения дебаланса активизируемых цепей. Для нейронных сетей гексагональной структуры, работающих в условиях субмикронной технологии, нулевой дебаланс активизируемых цепей достигается совместным решением систем уравнений дпя разрешенных и запрещенных кваэипорогов всех нейронов сети путем соответствующего согласования весов синапсов: суммы весов сннапсов нейронов, образующих активизируемую цепь, должны быть равными для каждой цепи. 3 5.12.
Семантическое проектирование скоростной транспортной сети большого города Повышение пропускной способности, увеличение скорости сообщения и безопасности движения транспорта и пешеходов в больших городах является важной и острой проблемой в современном градостроительстве. Ее решение связано не только с большими капитальными затратами, но и с проблемой сохранения исторических памятников и памятников культуры.
При этом ввод магистралей с большой пропускной способностью ставит проблему разработки принципа оптимальной трассировки скоростных дорог. Дорога называется скарастноб, если мощность транспортного потока, который она реализует, не меньше одного экипажа в секунду в одном направлении. Такой поток называется скоростным. Идеальным принципом управления скоростными потоками является принцип непрерывного движения на магистралях типа скоростной дороги, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
