Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 39
Текст из файла (страница 39)
Пусть Т п У такие же, как и в предыдущем примере. Тогда постпорядок на У будет иметь вид е <г( <г6 <г с <г~ <гд <гЬ <гд <г а с всходом е,1,Ь,е,1,б,й,с1,а. т" Определение. Пусть Т (т', Е) — полное бинар- ное дерево. Определим симметричный порядок (, на следующим образом: для каждой вершины, на являющей- ся листом и имеющей прямые спуски ш~ и шз (ш~ ( шз), положим т + ш,<,и длявсехш,енГ (шт) Ц(шД, и(,ш, для всех шт ен Г (шз) Ц (из). т" Порядок <, также является расширением (,. Пример 6.11. Пусть Т вЂ” дерево, изображенное на рпс, 7.31. Тогда (, определено, как показано на рпс 7.31.
Рас. 7.31 Обход по предпорядку упорядоченного ориентирован- ного дерева соответствует обходу по глубине с корнем в качестве начальной вершины. Если Т (У, Е) — упорядоченное ориентированное де- рево, то вершины Т могут быть расположены в предпо- рядок с применением следующего алгоритма, начинаю- щегося с карня: ргосебнге рте (и) ртосезз и И Ь, ть Ю йо рте (ш) 1от еасЬ ш се Ь, епдртос Соответствующий алгоритм для постпорядка имеет вид ртосебнге роз1(и) 0 Е. И 1Ьеп ртоеевз и е(зе Ьей1п роз1(ш) 1от еасЬ шж Ь, ртосезз и епб У п р з ж н е н п е 7.6.
1. Пусть А ж.й>(я, В) — матрица смежности оргрзфз. Выписать выражения для функций 6+ н 6- в терминзх А. 2. Сколько рзэличных оргрэфов может существовать нз вершинах? 3. Пусть С ()г, Е) — оргрзф. Какое мзкспмзльпо возможное значение величины !Е! ? 4. Пусть С ()г, Е)- оргрзф, где Р (уь уз, из, иь уз) и Е ((иь уз), (уз, уз), (из, уз), (и>ь уа), (у>ы уз)). Определить ызтрицы В(Е') и П(Ее) 5. Дать мэтричные характеристики слабой, односторонней и сильной связности в орграфе. 6.
Пусть С (г', Е) — вцпкличный оргрзф. Какое максимзльно возможное знзченке величины !Е! ? 7. Докзэзть двв последних предложения в п. 6.2. 8. Показать, что если Т (Р, Е) — полное бинзрное дерево н Рт обозначает множество уходов пз Т, то 1 г>! !У~И+1. О. Поддеревом Т' *(>г', Е') орпентпровзнного дерева Т (г', Е) нзэывзется такое орнентнровзнное дерево, что: е) Ичь р'ж р; б) Е' )г'Х7" 0Е; в) нп одна пз вершин УЮ' не является спуском вершины в Г'.
Нарисовать все поддеревья Г ((У!> Уз», Уа)> ((Р1> Уз)> (У!> Рз)> (Рз> Уа)> (Уз, Уз), (из> Уз))) 10. Определение. Если Т вЂ” орпентпровзнное дерево, то уровень вершины определяют кзк максимальную длину маршрута от этой верпшны до листа. Глубина вершины — это длине пути от корня до этой вершины. Глубиной Т нззывзют длину сэмого длинного маршрута в Т.
Высотой вершины Т называют глубину Т зз вычетом глубины вершины. Высота Т является высотой корня. Т Пусть Т вЂ” орнентпровзнное дерево ((УЬ ..., Уа)> ((РЬ Уа), (У>, УЗ), (УЬ У<) > (Ра, РЗ), (Уз, Уа), (Уз, У>), (Уз, Уз), (Уз, Уа))), в) нарисовать Т со значениями уровней в качестве меток вершины; б) нзрксовзть Т со знзченпямп глубин в качестве меток вершины; зоб в) нарисовать Т со значеняямн высот в качестве меток вершин; г) чему равна глубина Т? д) чему равна высота Т? 11. Пусть Т вЂ” ориентированное дерево. Раарезом С дерева Т нааывается подмножество вершин Т таких, что а) не существует двух верпшн С на маршруте в Т; б) пи одна вершина не может быть добавлена к С без нарушения а). Определить все разрезы ориептпрованного дерева, пзображенного па рнс.
7.32. У5 Рос. 7.32 12. Пусть Т (Р, Е) — полное бпнарное дерево и )И л. Покааать, что существует и!/2'" '"' полных порядков на У, которые расширяют трапсверсальный порядок <. 13. Пропнтерпретпровать <и <т и <, для бинарных деревьев, связанных со структурой арнфиетическпх выраженнй, как в у 6 гл.
3, ГЛАВА 8 ЯЗЫКИ И ГРАММАТИКИ Все средства общения включают язык. Обычно мы «общаемся» с компьютером при помощи языка, который каким-либо обраеом эапнсывается (перфокарты, телетайп, экран дисплея и т, п.), и, следовательно, предложения явыка состоят иэ строк символов. Действительно, весь вычислительный процесс может рассматриваться как преобраэование одного множества строк в другое. Такие процессы ведут себя совершенно определенным образом, и, следовательно, с ними можно обращаться как с математическими объектами — по крайней мерв строки могут рассматриваться как алемепты коканда.
В втой главе мы будем подходить к изучению языка скорее с математиче ской точки ерения, чем с литературной. В 3 ( будет введено понятие строки и будут рассмотрены некоторые проблемы, относящиеся к этому вопросу; в $2 будут введены яэыковые структуры. Далее будут более детально исследованы некоторые важные классы языков и рассмотрено введение в грамматический разбор, в !.
Основные покатив (Л. Строки. Буква (или символ)-это простой неде- лимый знак, или символ; множество букв образует ал- фавитт. Пример (.(. 4 (а,Ь,с),В (0,(), С (РЕВРОВМ, АВП, 6171ЫО, ТО, ...), Е (а,Ь,с,...,к,р,в). Здесь мы можем рассматривать В как бинарный алфавит, С-кек алфавит яэыка Кобол (в котором слова типа РЕВГОВМ не могут быть раэделены), а Ь' — как анг- лийский алфавит. (7 д. к»к, г. в»а» 257 Алфавиты являются множествамн, п поэтому к пим можно применять теоретико-множественные обозначения. В частности, если А и В такие алфавиты, что А ы В, то будем говорить, что А является подальравитом В, или что В является расширением А.
Строки являются упорядоченными совокупностями букв алфавита (капример, алфавита А) н, следовательно, выглядят подобно элементам А" А ХА Х ... Х А. Од- нако будет более естественным записывать кх в виде аьаз...а, а не (аь, аи ..., а.). Буквы сами по себе также являются строками для случая и = ь. Мы будем допускать случай, ъогда строка не имеет букв (пустая строка), и обозначать эту строку через Л. Заметим, что Л не являет- ся символом, т. е.
Л ФА для любого алфавита А. По аналогии с лингвистикой будем строки также назы- вать словами. Мнонсество всех строк (слов) вад алфа- витом А называют вамьвканием А и обозначают А', так что А' А» Ц Аь () А' () ... () А", где А' (Л). »-» Для удобства определим также множество непустых строк над А следующим образом: А+ = А»~(Л) () А", П 1 Как уже упоминалось в примере 2Аь гл. 5, основная операция над строками называется конкатенацией; фор- мально она может быть определена как бинарная опера- ция О на А" следующпм образом: о:(.,И- (). Аналогично зта же операция определяется для А+. Опе- рация О ассоциативна, но пе коммутатпвна; Л является единицей в А" по отношению к О. Сформулируем ниньо основные свойства операции О па А» и А+.
Предложение. По отношению к операции О а) А» является моноидом; б) А+ — полугоуппа. Р результат слияния строк а и р, т. е. сьр, заключается в следующем: строка 5 записывается сразу же за стро- кой а. Другой способ определения строка — рекурсивный: сь является строкой вад алфавитом А, если или а Л, или и аб, где аы А, а () — строка над А. Здесь аб означает, что буква а стоит непосредственно перед строкой р. $58 Все слова в А" (и «в(0) ОХ) состоят точно иэ я букв; в этом случае говорят, что строка имеет длину и. Длина а «эА* обозначается как )а! н !и! и тогда и только тогда, когда а <и А".
Очевидно, что )Л! 0 и !а! 1 тогда и только тогда, когда аж А. Если строки состоят пз повторнгощихся букв, то обычно принимают сокращенные обозначения, чтобы показать, что строку следует рассматривать как произведение (по отношеип«о к операцпп конкатенации). Поэтому для а «в А будем писать Л а", аа а«, аа" ' а", п«вХ.
Будем использовать следующее обозначение для повторяющихся строк: строку аЬаЬа будем аапнсывать как (аЬ)«а нлн н«э как я(Ьа)«. Этот пример иллюстрирует одну нз основных трудностей при рассмотрении строк. Ь(ы используем строки для описания строк, и, следовательно, мы должны иметь возможность различать используемые алфавиты, Если приведенные выше вырансения рассматрквалнсь над алфавитом А, а символов «(» и «)«в А пег, тогда смысл понятен; с другой стороны, если круглые скобки есть в А, то выражение (аЬ)«а мо«кет быть понято как (аЬ) )а. При условии что мы осознаем воэможность таких проблем и знаем, какие алфавиты используются, зтпх ошибок можно избе«кать, используя различные алфавиты и биекцию между двумя алфавитамп.
В некоторых случаях может быть более удобно построить мономорфиэм между мнол~ествамн строк, так что одно множество рассматривается над существенно более простым алфавитом. Пример 1.2. Пусть В (О, 1) и А (а, Ь, с). Тогда ф: А« - В«, определенное соотношением ф(ху) ф(х)ф(у), где х, у«вА«и ф(а) О, ф(Ъ) 10, ф(с) ИО, является гомоморфпэмом моновда (пам надо сохранять комбинации) из А«в (О, 10, ИО)*жВ«. Например, ф: аЬЬса- 01010ИОО, ф '. 010И010ИО- аЬсЬс. В действительности этот метод построения может исполь- зоваться для отображения произвольного конечного ал- фавита в (О, 1)».
Х !«« 259 Иа определения длины строки следует, что если и, 1) ««А», то 1и()1 !и!+ !Ь1, 1и" 1 = я!и!. Более того, если а юА, то 1а" ', к. При преобразовании одной строки в другую нежелательно, чтобы вся входная строка изменялась под действием одной операции; в противном случае процесс можно было бы определить только с помощью множества входных-выходных пар. В дальнейшем нам понадобится понятие подстроки.
Пусть ааданы строки и и 11 над алфавитом А. Строка !) называется подстрокой и, если и тбб, Т бшА*. Пример $.3. Пусть А (а, Ь, с) и и=аЬас. Тогда подстроками и являются следующие строки: Л, а, Ь, с, оЬ, Ьа, ас, оЬа, Ьас, аЬас. В частности, заметим, что и является подстрокой самой себя, а Л-подстрокой и (и любой другой строки), поскольку и ЛаЬас ЛаЛЬас ЛаЛЪЛао ЛаЛЬЛаЛс ЛаЛЬЛаЛсЛ аЛЬас оЛЛЬас ... Х Выделение подстроки естественно приводит к замене подстроки другой строкой. Однако пока еще мы не достиглн уровня, достаточного для корректного выполнения этой операции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
