|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[33] Эта лемма означает, что дуги нейтральных и парных циклов являются дугами некоторых итерантов. Другими словами, верно утверждение, обратное лемме 18. Пусть (ni,n2) G P. Пусть для i = 1,2 дуга щ является дугой итеранта C (допускается равенство C1 = C2). Тогда будем говорить, что итеранты 1 и 2 сцеплены. Итерант C, сцепленный с C1 (или C2), считаем сцепленным с C2 (с C1 соответственно). Таким образом, на множестве итерантов Dграфа определяется рефлексивное, симметричное и транзитивное отношение сцепленности. Пример 8. Пусть для Dграфа, представленного следующим рисунком, P = {(1, 4), (2, 3), (5, 6), (5,10), (1, 7), (9, 8)}. 146 10 8 -о- о-о-о- Тогда его три сильно связные компоненты сцеплены друг с другом. Здесь дуги 1, 5 парны соответственно линейным дугам 7,10. Однако они являются дугами итерантов, так как парны соответственно дугам 4, 6 сильно связной компоненты, не имеющей линейных в данном D графе дуг. Правда маршрутов, в которых дуги 1 и 4 образуют гнезда, не существует. В самом деле, единственный путь из end(1) в beg(4) состоит из дуги 2, т.е. не является нейтральным маршрутом. 3.2.3. Расширение понятия форманта Рассматриваемое расширение позволит при обработке Dграфа обходиться более короткими маршрутами на итерантах. В число формантов будут включены и некоторые нейтральные маршруты. Для построения ненейтрального форманта, достижимого из некоторой фиксированной вершины итеранта, требуется "прой ти", вообще говоря, более короткий маршрут, чем в случае, когда нейтральность форманта была обязательна. 3.2.3.1. Вставки и схемы. В определении вставки фиксируется наблюдение о том, что для разрастания маршрутов можно использовать и некоторые неней тральные циклы. Схемы определяются в терминах вставок. Они родственны канонам весьма частного вида. Пусть T - цикл, p(T) = T1T2, T1 G Right(V)*, T2 G Left(P)*, MT2T1) = Л. Тогда назовем цикл T Rbctsbkou . Заметим, что Tk,k > 1, является циклическим маршрутом и ц(Тk) = (T). Является маршрутом и путь T3T4, если T3TT4 - маршрут, в котором T есть R-вставка. Таким образом, замена R вставки любой ее степенью (в том числе и нулевой) оставляет маршрут маршрутом. Это оправдывает употребление в тер мине слова "вставка". Указанный класс маршрутов напоминает о регулярных языках, чем и объясня -ется приставка "R". Нейтральный цикл есть частный случай Rвставки. Пусть тройка (Ti,T2,T3) такова, что TiT2T3 - маршрут, Ti и T3 - циклы, \i{Tx) = TnTi2Ti3, ц(Т2) = TnT33, р(Тз) = T3iT32T33, T2 и T32 не пусты, ц(Т12Тз2) = Л, p.(Ti3Tii) = ii,(T33T3i) = Л. Тогда будем говорить, что данная тройка указывает повторяемые (точнее, согласованно повторяемые) циклы Ti и T3. Маршрут TiT2T3 назовем S-вставкой. Заметим, что Tf T2T3k, k > 0, является маршрутом с зарядом TiiT33. Парные циклы - частный случай повторяемых циклов. Понятие Sвставки вызывает ассоциации с понятием самовставляющегося символа грамматики, отсюда приставка "S". Пример 9. Dc}) -0-0 о- с Dмножеством {(1, 2), (3, 2)} определяет Рвставку 23, которая удовлетворяет определению элементарной схемы (см. ниже). Элементарной схемой является и предложение 1232. Пример 10. DcC -0-0-о 0 0 0 с D множеством {(1,10), (2, 3), (4, 8), (5, 3), (6, 7), (9, 7)} определяет S вставку T = 34536789, которая является участком элементарной схемы предложения (1, 2,T, 7,10). Здесь повторяемы ненейтральные циклы 345 и 789. Примеры показывают, что сформулированные в настоящей работе определе -ния Р и S вставок позволяют обнаружить явления итерации и согласованной итерации подцепочек в цепочках заданного Dграфом языка, минимально "прокручиваясь" по сильно связным компонентам. Маршрут, который является Р вставкой или S вставкой, будем называть вставкой. Формант - это вставка, любой собственный участок которой не является встав -кой. Схема - маршрут, все вставки которого являются формантами. Собственный участок вставки T, входящей в некоторую схему, не может сам быть вставкой: иначе T не была бы формантом. Однако различные вставки одной схемы могут иметь общий участок. Пусть в схеме T любые две вставки имеют непустой общий участок. Тогда назовем T элементарной схемой. Итак, понятие элементарной схемы расширено по сравнению с [Вылиток 98] не только за счет более емкого понятия вставки, но и за счет разрешения нескольких определенным образом "пересекающихся"вставок. Действительно, чтобы попасть из одной заданной вершины итеранта в другую заданную вершину, используя некоторую вставку, но не используя одновременно вставок, не имеющих непустых общих участков, может потребоваться обойти все циклы пучка циклов, похожего на демонстрируемый следующим примером маршрута. Поэтому кажется естественным считать элементарной схему T1T2T3T4T5T6T7, где Tj - нейтральный маршрут для 1 < i < 7, начальные вершины маршрутов T1, T2, T3 и T4 попарно различны, T1T2T3T4, T2T3T4T5, T3T4T5T и T4T5T3T7 являются Rвставками. Лемма 21. Пусть T - нейтральный участок элементарной схемы. Тогда справедливы неравенства width(T) < mm(\V + 1, depth(T) < mm(\V2, P + 1). Доказательство. Первое из неравенств доказывается аналогично лемме 2 из [Вылиток 98], а второе - аналогично лемме 3, оттуда же □ Лемма 22. Пусть T - нейтральный участок элементарной схемы T, m = V, pn gmjn(m+1,p),mjn(m2,p+1). Тогда T < n, \T < n((T) + 1). Доказательство. Доказательство первого неравенства аналогично доказатель ству леммы 4 из [Вылиток 98]. Второе неравенство следует из представления элементарной схемы T последовательностью Ton1T1...nKT )TKT )> где p(T) = п1...пм(т), Tj - нейтральный участок для 0 < i < p(T) □ Из леммы 22 следует Теорема 9. Множество элементарных схем, имеющих одни и те же заряд и пару концов, конечно □ 3.2.3.2. Отношение развития маршрутов. Развитие (по другому можно сказать "разрастание") сводится к последовательности замен так называемых атомов формантами. Как видно из следующих определений, атом всегда присутствует во вставке, в частности, в форманте, и может встречаться в маршрутах, которые не содержат вставок. Пусть T - это Rвставка. Тогда назовем R-атомом (вставки T) пустой маршрут с вершиной beg(T). Пусть тройка (T1, T2, T3) указывает согласованно повторяемые циклы T1 и T3. Тогда назовем T2 S - атомом (вставки T1T2T3). Маршрут, который является R атомом или S атомом, будем называть атомом. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||