Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 13
Текст из файла (страница 13)
а) Докажите, что свойству последовательности степеней леса в прямом порядке обхода из упражнения 20 удовлетворяют ровно ) циклических сдвигов Ь +~... Ь Ь,...ьзз)<) <Х Ь) Разработайте эффективный алгоритм для определения всех таких ) для данной строки 616э... Ьн. с) Поясните, как сгенерировать случайный лес с Ж = ио+ ° +и~ узлами, в кагором степень,у имеют ровно и, узлов. (Например, в качестве частного случая этой процедуры при Ф = ви + 1, ио = (1 — 1) и + 1, и1 = = ис-) = 0 н ис = и мы получаем случайное и-узловое 1-арное дерено.) 62.
[22[ Бинарное дерево может быть представлено также битовыми строками (11... („,г1 ... г„), где 11 и г, указывают, пусты или нет левое и правое поддеревья узла ) в прямом порядке обхода (см. теорему 2.3.1А). Докажите, что если 1г... 1„ и г1... г„— произвольные битовые строки, такие, что 11+ " + 1„+ г1 + ° + г„= = и — 1, то только один циклический сдвиг (11+1... 1„1~... 11, ту+1... г„г1... г)) двег корректное представление бинарного дерева, и поясните, как его найти. 63.
[16[ Если первые две итерации алгоритма Реми дают, то какие декори- рованные бинарные деревья возможны после очередной итерации? 64. [30[ Какая последовательность значений Х в алгоритме Н соответствует декорированным деревьям из (34) и каковы конечные значения ХоЬ1...
Ь|о? 63. [38[ Обобщите алгоритм Реми (алгорнтм Н) для 1-арных деревьев. сделано для ивуидп$апаса.огя 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОВ'ЬЕКТОВ 57 66. [81[ Деревом Шредере (Яс)гго()ег) иазывается бинарное дерево, в котором каждая ненулевая правая связь окрашена либо в белый, либо в черный цвет, Вот количества Я„деревьев Шредера для небольших и: и = 0 1 2 3 4 5 6 7 8 9 10 11 12 Я„= 1 1 3 11 45 197 903 4279 20793 103049 518859 2646723 13648869 Например, Яз = 11, как видно из приведеииых вариаитов (Белые связи "пустотелые'"; иа рисунке показаны также внешние узлы.) а) Найдите простое соответствие между деревьями Шредера с и внутренними узлами и обычными деревьями с и + 1 листьями и без узлов со степенью, равной 1, Ь) Разработайте код Грея для деревьев Шредера. 67. [Мйй[ Какова производящая функция Я (с) = 1 „Я с" для чисел Шредерау 68.
[10[ Какой вид имеет шаблон рождественской елки порядка 07 69. [30[ Содержатся ли в табл. 4 шаблоиы рождественской елки порядка 6 и 7, возможно, в замаскироваииом виде? в 70. [80[ Найдите простое правило, которое определяет для ка)идой битовой строки и другую битовую строку п', которая называется иапармикам (шасе) первой строки и обладает следующими свойствами: (1) ил = а; (В) [гг'[ = [о [; (ш) либо а С а', либо гг' С а; ((т) и (и) + в (гг') = [гг[. '71.
[М31[ Пусть Мг„— размер наибольшего возможного множества Я и-битовых строк, обладающих тем свойством, что если ~т и т — члены Я, такие, что а С т, то л (гг) < и (т) + С (Таким образом, например, М(„= М„согласио теореме Спериера.) Найдите формулу для М»„. > 72. [МЗЗ[ Если качать с едииствеияой строки ог <тз ... т, длиной э и примеиить к яей правило роста (36) и раз подряд, то сколько строк мы получим? 73.
[1$] Каковы первый и последний элементы строки шаблона рождественского дерева порядка 30, содержащей битовую строку 0110010010000111111011010Ш007 74. [Мйб[ Продолжая предыдущее упражнение, ответьте, сколько строк предшествует указанной в иему )ь 7$. [НМЗУ[ Пусть ~г(, гт,..., г„,) — номера строк, в которых шаблон рожде((ч) (в) () \ ствеиской елки порядка и содержит и — 1 элементов; например, из табл. 4 видно, что (г) ),...,гг~ ~) = (20,40, 54, 62,66,68,69). Найдите формулы для г(+, — г(") и для !пп„г /М„. (ч) сделано для ы(ькичп$апа1а.огя 58 КОМВИНАТОРНЫЙ ПОИСК Тб.
[НМ46] Рассмотрите предельный вид шаблона рождественской елки при п — оо. Имеет ли он, например, фрактальную размерность при выборе некоторого подходящего масштабирования? ТТ. [21 ] Разработайте алгоритм для генерации последовательности крайних справа элементов а1 ...а„строк шаблона рождественской елки для данного п. Указание: эти битовые строки характеризуются тем свойством, что аг + .
+ аь > й/2 при 0 < й < и. ?8. [20] Истинно или ложно утверждение: если «г1 ... «г, — строка шаблона рождественской елки, то ею же является и строка «Ун ... сг," (обршцеиная последовательность обращенных дополнений)? 79. [М36] Количество перестановок р1... р„, у которых имеется ровно один "спуск" рь > рь+м равно, согласно 5.1.3-(12), числу Эйлера (",) = 2" — и — 1. Количество элементов в шаблоне рождествекской елки выше нижней строка такое же.
а) Найдите комбннаторное поиснение этого совпадения, приведя взаимнооднозначное соответствие между перестановками с одним спуском и неотсортированными битовыми строками. Ь) Покажите, что две неотсортированные битовые строки принадлежат одной и той же строке шаблона рождественской елки тогда и только тогда, когда они соответствуют перестановкам, которые определяют одну и ту же диаграмму Р при соответствии Робинсона-Шенстеда (теорема 5.1.4А).
80. [60] Будем говорить, что две битовые строки сэ«ьиесшимм (сопсог«)ап~), если одну нз них можно получить из другой путем преобразования подстрок 010 «100 нли 101 110. Например, строки 011100 011010 ~ 010110 « 010101 « 011001 1 1 100110 «-«100101 «-«101001 ~-«110001 взаимно совместимы, но ни одна другая строка не совместима ни с одной из приведенных. Докажите, что строки взаимно совместимы тогда и только тогда, когда они принадлежат одному и тому же столбцу шаблона рождественской елки и строкам одинаковой длины в этом шаблоне.
81, [МЗО] Биклаштерам (Ыс!ппег) порядка (п,п') называется семейство Я пар битовых строк (щи'), где [о] = и и ]о«[ = и', обладающих тем свойством, что для различных членов (а, «т') и (г, г«) семейства Я условия и С т и с««С т' выполняются, только если и ~ т и «г' ф т'. Воспользуйтесь шаблонамн рождественской елки, чтобы доказать, что Я содержи г не более М„+„пар строк.
~ь 82. [М26] Пусть Е(У) — количество вычислений функции У алгоритмом Н. а) Покажите, что М„< Е(у) < М„+м причем равенство достигается, когда у— константа. сделано для ьуэуилпГапаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОВЪЕКТОВ 59 Ъ) Какая из всех функций у, таких, что Е (7) = М„, минимизирует ~,7 (о)? с) Какая из всех функций 7, таких, что Е(у) = М„+1„минимизирует ~; 7(о)? 83. [Мйй] (Д. Хансель (С. Напэе1).) Покажите, что существует не более Зм" монотонных булевых функций у (хм..., х„) от и булевых переменных.
1ь 84. [НМ37] (Д. Кляйтман (П. К!ейшап).) Пусть А — матрица действительных чисел размером ги х и, в которой каждый столбец о имеет длину ]]о]] > 1, и пусть Ь вЂ” ги-мерный вектор-столбец. Докажите, что не более М„векторов-столбцов х = т = (ам,а„) с компонентами ау = 0 или 1, удовлетворяют условию ]]Ах — Ь]] < < 1/2. Указание: воспользуйтесь конструкцией, аналогичной шаблону рождественской елки. 85. [НМ35] (Филипп Голль (РЪйрре Оойе).) Пусть Ъ" — произвольное векторное пространство, содержащееся во множестве всех действительных и-мерных векторов, но не содержащее ни одного из единичных векторов (1,0,...,0), (0,1,0,...,0), ..., (О,..., О, 1).
Докажите, что Р содержит не более М„векторов, все компоненты которых равны 0 или 1; более того, верхняя граница М„достижима. 86. [15] Если (2) рассматривать как ориеиширооаиимй лес, а не как упорядоченный, то какой канонический лес ему соответствует? Укажите этот лес как с использованием кодов уровней с1...снь так и при помощи указателей на родительские узлы р1...Рць 87. [Мйр] Пусть Р— упорядоченный лес, в котором Ь-й в прямом порядке обхода узел находится на уровне сы а его родительский узел — ры причем рь = О, если узел является корнем, а) Сколько лесов удовлетворяет условию сь = рь для 1 < Й < и? Ъ) Предположим, что Г и г' имеют коды уровней с1...
с„и с] ... с„и родительские связи р1... р„и р',... р'„соответственно. Докажите, что лексикографически с1... с„< с',... с'„тогда и только тогда, когда р1... и„< р',... р'„. 88. [Мйд] Проанализируйте алгоритм 0: как часто выполняется шаг 04? Чему равно общее количество изменений рь на шаге 05? 89. [М46] Как часто на шаге 05 выполняется присваивание рь — р ? м 90.
[М37] Если р1... р„— каноническая последовательность указателей на родительские узлы для ориентированного леса, то граф с вершинами (О, 1,..., и) и ребрами (Й вЂ” рь ] 1 < Й < и) является соободнмм деревом, т.е. связным графом без циклов (см. теорему 2.3.4.1А). И наоборот: каждое свободное дерево соответствует таким способом, как минимум, одному ориентированному лесу.
Однако указатели на родительские узлы 011 и 000 соответствуют одному и тому же свободному дереву >-' ; аналогично: последовательности 012 и 010 также дают одно дерево Цель этого упражнения — наложить на последовательности р1... р„ограничения с тем, чтобы каждое свободное дерево получалось только один раз. В 2.3.4.4-(9) мы доказали, что количество структурно различных свободных деревьев с и + 1 узлами имеет очень простую производящую функцию, показав, что свободное дерево всегда имеет, как минимум, один ценшропо (сепсгоЫ). сделано для ькиилпГапаса.ого бО КОМБИНАТОРНЫЙ ПОИСК а) Покажите, что канонический и-узловой лес соответствует свободному дереву с одним центроидом тогда и только тогда, когда в лесу ни одно дерево не имеет больше [и/2) узлов.
Ь) Модифицируйте алгоритм О таким образом, чтобы он генерировал все последовательности р1 ...р„, удовлетворяющие пункту (а). с) Поясните, как найти все р1 ...р„для свободных деревьев, имеющих два центроида. 91. [Мз?[ (А. Ньенхуис (А. Х11епЬшз) и Г. Вильф (Н. %111).) Покажите, что случайное ориентированное дерево может быть сгенерировано при помощи процедуры, аналогичной алгоритму случайного разбиения из упражнения 7.2.1.4-47, 92. [16[ Являются ли первое и последнее остовные деревья, посещенные алгорит- мом 8, смежными, в том смысле что они имеют и — 2 общих ребер? 93. [36[ Восстанавливает ли алгоритм 8 граф в первоначальное состояние по за- вершении работы? 94.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
