|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[19] является срезом гнезда £, имеющим статус 1 + max{sj\1 < i < l}. Заметим, что при работе шагов 2-3 алгоритма 3 цепочка Sqz представляет срезы 0гнезда КСвыражения (0Squeeze(())0. Заметим, что для s > 1 срез со статусом s гнезда получается подстановкой в (1 ground(u))1 вместо заглушек некоторых срезов со статусом, не превышающим s - 1. В частности, (i ground(u))i является срезом гнезда (1u)1, имеющим статус 1. Пусть для любого КСвыражения £ Nests(£) есть обозначение множества всех гнезд, встречающихся во фракциях из Clan(£). Пусть £ есть КСвыражение, s - неотрицательное целое. Обозначим через Sections(£, s) множество всех срезов со статусом s гнезд, участвующих в Nests(£). Вернемся к алгоритму 3. В следующей теореме, как и раньше, предполагаем, что 0 G Names(Z). Теорема 10. Для любого неотрицательного целого s справедливо равенство Sections((0Z)0, s) = Sections((0Squeeze(Z))0, s). Доказательство. Индукцией по s. При s = 0 рассматриваемое множество срезов является множеством заглушек. По определению клана множество Clan((0()0) определяется через Trim((0 Z)0) = ATrim((). Из конструкции шагов 1, 2 алгоритма 3 следует, что КС выражение (0Squeeze(())0 и его клан представляют все заглушки, представленные в ATrim((), и только их. Следовательно, теорема в данном случае верна. Пусть теперь s > 0. Тогда каждый рассматриваемый срез представлен для некоторого целого l > 0 цепочкой вида (iu)i = (iV0)(nui)nvi... (Hui)HVl)i, ground(u) = V0(n)цVi... (M)4vh Из конструкции алгоритма (см. процедуру Replacement) следует, что для лю -бого имени 1 G ANames(() множества {ground(£)\(i£)i G Nests((0()0)} {ground(0\(iOi G Nests((oSqueeze(())o)} совпадают каждое с Embeddings(i), т.е. равны между собой. Таким образом, каждое из множеств Sections((0Z)0, s) и Sections((0Squeeze(Z))0, s) получается (ср. замечание к определению среза) из одного и того же множества Ut6AWames(c) [{(i} Embeddingt}] всевозможными подстановками вместо заглушек цепочек, входящих соответственно в U0<j<sSections((0C )0, j) U0<j<sSections((0Squeeze(Z ))0,j). По предположению индукции Sections((0Z )0,j) = Sections((0Squeeze(Z ))0,j) для 0 < j < s. Значит, верно и равенство Sections((0Z)0, s) = Sections((0Squeeze(Z))0, s) □ Следствие 4. Nests((0()0) = Nests((0Squeeze(())0). Доказательство. Заметим, что каждое гнездо С является своим срезом, т.е. принадлежит множеству Sections(C, s) для некоторого целого s > 1. Так как каждый элемент кланов интересующих нас КСвыражений является 0гнездом, неравенство Nests((0()0) = Nests((0Squeeze(Z))0) противоречило бы теореме 10 □ Следствие 5. L((0()0) = L((0Squeeze(Z))0). Доказательство. Согласно следствию 4 верно равенство Clan((0Z)0) = Clan((0S queeze(Z))0). Значит, по определению задаваемого КС выражением языка имеем равенство рас сматриваемых языков □ Теорема 11. \Squeeze(()\ < \(\. Доказательство. Положим nZ = Ы )0\ и убедимся, что в каждый момент работы алгоритма 3 выполняется неравенство \Sqz\ < щ. Оно очевидно для шага 1. Действительно, запись выражения ( представляет собой непустую цепочку, поэтому на шаге 1 имеем \Sqz\ = \(0)0\ < \(0Z)0\ = nz. На шаге 2 значение величины Sqz изменяется процедурой Replacement. Процедура заменяет заглушки одноименными срезами статуса 1 гнезд КСвыражения (сС )о. Из определения среза видно, что срез образован сцеплением некоторых участков (возможно, разъединенных) соответствующего гнезда. Будем говорить, что срез покрывает этот набор участков гнезда (или КСвыражения, объемлющего гнездо). Теперь отметим очень важное в доказательстве данной теоремы обстоятельство, вытекающее из закона взаиморасположения гнезд: различные срезы единичного статуса покрывают в КС выражении наборы участков, элементы ко торых попарно не перекрываются. (Это верно и для одинаковых на вид срезов статуса 1, относящихся к различным гнездам одного и того же КС выражения. Но нас интересуют различающиеся срезы, так как только они собираются в мно жествах Embeddings.) Таким образом, гнездо можно "выложить", как мозаику, всеми срезами единичного статуса, которые извлекаются из его записи. Процедура Replacement использует все текстуально различные срезы статуса 1. Каждый из них используется для замены заглушки ровно один раз. Следова тельно, вся совокупность цепочек, внедряемых в Sqz процедурой Replacement не может превзойти по длине КС выражения (оС)о. По завершении шага 2 в Sqz еще могут присутствовать заглушки. Ясно, что так может быть в том и только том случае, когда какие либо различные гнезда дают одинаковые срезы со статусом 1, т.е. когда в исходном выражении дублируется некоторая информация. Чтобы остаться в пределах рассматриваемого формализма - КСвыражения, необходимо заменить оставшиеся заглушки какиминибудь из одноименных с ними гнезд. В целях укорочения КСвыражения следует выбрать самые короткие из возможных замен. Что и делается. Шаг 4, исключающий из рассмотрения внешние скобки (с именем 0), не влияет на соотношение длин исходного и результирующего КСвыражений □ Выявим временные характеристики алгоритма 3, опираясь на соотношение (см. доказательство теоремы 11) Sqz < щ. Ясно, что время работы шагов 1 и 4 не зависит от входного выражения и прене брежимо мало, а время работы шагов 2 и 3 по меньшей мере линейно зависит от щ. Действительно, для построения всех используемых алгоритмом вспомогатель -ных объектов требуется линейный просмотр исходного выражения или не более длинной цепочки Sqz. Так как гнездо и заглушка обязательно имеют в своем составе два символа: левую и правую скобки, число гнезд и заглушек в цепочке Sqz не превышает ISqz 1 < Щ 2 < 2 . Текст шага 3 алгоритма 3 очень краток, и кажется, что время работы шага 3 сравнительно легко оценить. Начнем с него, подготавливая соображения, полез ные и в будущем. В случае простейшего представления цепочки Sqz шаг 3 должен затрачивать на поиск в ней последовательных вхождений заглушек время, пропорциональное ее длине. На обработку всех найденных заглушек потребуется не более половины этой длины (ср. замечание выше о числе заглушек в Sqz). |
Среды: 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 | ||