Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 107
Текст из файла (страница 107)
(в(п) = Л(п) + и(н) — 1, так что, если и = 2", (в(и)/Л(п) = 1, но если п = 2«е' — 1, (в(п)/Л(п) = 2. 17. Пусть ц «. з,. Удалим все интервалы 1«, которые можно удалить без изменении объединения 1~ О 0 Хь (Интервал (Л« ..з«] может быть удален, если 1«+з < 2« либо 20 < уз < и 1«тз < з««о) Теперь объединим перекрывающиеся интервалы (10 .. «Ь],..., (1Ь .. «Ь] э интервал (1'., з ] = (11, . зл] и заметим, что ас < а (1+5)" д+"'+'з зз < а~ (1+ 6)зп поскольку каждая точка (у' ..1) покрывается объедянением (/и гЬ)ц 0(/э.
1а) не более двух раз. 16. Назовем /(та) "хорошей" функцией, если ((об/(та))/ш -ь 0 при ш -э оо. Произвольный полипом от оз является "хорошим'! Произведение хороших функций — хорошая функция. Если 9(ш) -+ 0 и с — положителъная константа, то с Ы 1 — хорошая функция; хороша также и ( ~ ), так как с учетом аппроксимации Стирлинга это эквивалентно утверждению д(т) 1об(1/д(ш)) -э О. Теперь заменим каждый член суммы максимальным по в, 1, е членом. Общее число членов — хорошее, так же как и (~+'), ('+") < 2'+" и ф', потому что (Ф+ е)/ш -Ф О.
и наконец (~ +ю ) < (2т)ы/В < (4ешз/1)', где (4е)~ — хорошая функция. замещая Ф его верхней границей (1 — е/2)гл/Цт), показываем, что (шз/1)' < 2 О '7Ю/(т), где /(ш)— хорошая функция. Следояателъно, вся сумма меньше, чем а'" для больших ш, если а = 2~ ", где О < О < -'е. 19. (а) МПХ, МОЛ, МЮ)1':соответственно; см. 4.5.2 — (б), 4.5,2-(7). (Ь) /(г)у(х), )сгп(/(е),9(х)), бед(/(е)ьй(з)). (По тем же причинам, что и в п. (а), потому что нормированные неприводимые полиномы над полем комплексных чисел в точности представляют собой полиномы з — ъ.) (с) Законы коммутативности: АыВ = ВША, А с1В = ВОА, АпВ = ВпА.
Законы ассоциативности: Ай (Вы С) = (А ы В) эгС, А 0(В ОС) = (А 0 В) гзС., А П (В П С) = (АПВ) ПС. Законы дистрибутивности: А О(В ПС) = (А 0 В) П(А ЦС)., А П (В11 С) = (АП В) 0(АП С), АЮ(В и С) = (АЫВ) О (А ЫС), АЮ (В ПС) = (АЫ В) П (А Щ С).
Законы идемпотентности: А 0 А = А, А ПА = А. Законы поглощении: А О(АП В) = А, АП(АОВ) = А, АП(АыВ) = А, А11(АыВ) = АщВ. Законы единицы и пуля: ЭыА = А, Э 0 А = А, Э П А = Э, где Э обозначает пустое мультимножество. Закон перечисления: А Ы В = (А 0 В) Ы (А П В), Прочие свойства, аналогичные соответствующим свойствам множеств, вмтекыот из частичной упорядоченности, определенной правилом А С В тогда и толъко тогда, когда А П В = А (тогда и только тогда, когда А 0 В = В). Примечания. Другие общие применения мультимножеств — нули и полюсы мероморфных функций, инварианты матриц в канонической форме, инварианты конечных Абелевых групп и т. д.
Мулътимножества могут быть полезны в комбннаторике и в теории мер. Терминальные строки нециркулярной контекстно-свободной грамматики образуют мультимножество, которое является множеством тогда и только тогда, когда грамматика свободна от неопределенностей. В статье автора в 2Ъеогег(са( Ягис(йн (л Сошригег Яс1елсе, ео(1ео Ьу Я. 12.
анап (Асабеш(с Ргеш, 1992), 1-13, обсуждаются дальнейшие применения к контекстно-свободным грамматикам н вводится операция А П В, где каждый элемент, который встречается а раз в А и Ь раз в В, встречается в А П В аЬ раз. Хотя мультимножества появляются в математике достаточно часто, во многих случаях они трактуются неуклюже, поскольку в настоящее время не существует стандартного пути рассмотрения множеств с повторяющимися элементами. Некоторые математики выразили свое мнение о том, что отсутствие адекватной терминологии и обозначений для этой глобальной концепции определенно затрудняет развитие математики. (Мультимножество, конечно, формально эквивалентно отображению множества на неотрицательные целые числа, но эта эквивалентность имеет слишком малое значение для творческого математического мышления.) Автор обсуждал этот вопрос со многими специалистами в 00-х годах, пытаясь найти приемлемое решение вопроса.
Вот некоторые из предлагавшихся для этой концепции названий: список ((пй), связка (ЬцпсЬ), мешок (Ьаб), куча (Ьеар), проба (вашу!е), взвешенное множество (гое1я)ггеб вес), коллекция (соПесч(алэ), комплект (вп)ге). Однако все эти они конфликтуют с существующей термияологией, имеют неуместное дополнительное значение или слишком неудобны для произношения и написания. Наконец, стало ясно, что для такой важной концепции необходимо собственное нмя, и оно— "мулътимножество" (ши)слег) — было предложено Н.
Г, де Брейном (1э". О, бе Вгпцп). Его предложение широка распространилось в 70-х годах и теперь является стандартным термином. Зались "АзгВ" была выбрана автором, чтобы избежать нонфликтов с сущее:гвующими обозначениями и усилить аналогию с объединением множеств.
Для этого нежелательно использовать "А + В", поскольку специалисты в области алгебры приняли А + В как запись для мультимножества (а + р' ! а б А и В б В). Пусть А являетсв мулъти- множестном неотрицательных целых чисел, а С(к) = ~„ел э" — производящая функции, соответствующая А. (Очевидно, что производящие функции с неотрицательными целыми коэффициентами находится во взаимно однозначном соответствии с мулътимножествами неотрицательных чисел.) Если С(г) соответствует А, а Н(г) соответствует В, то С(э) + Н(г) соответствует А Эг В, а С(к)Н(в) соответствует А + В.
Если построить производящие функции Дирихле д(г) = 2 „е» 1/и*, Ь(э) = 2 „, 1/и', то произведение д(в) Ь(э) будет соответствовать произведению мультимножеств АВ, 20. Тип 3: (Яо,...,5~) = (Моо,,Мю) = ((О), ..., (А), (А — 1,А), (.4 — 1,А,А), (А — 1,А — 1,А,А,А), ..., (А+ С вЂ” З,А+ С вЂ” З.А+ С вЂ” 2,А+С вЂ” 2,А+ С вЂ” 2)). Тип б: (Мое,...,М о) = ((О), ..., (А), (А-1, А),..., (А+С-1,А+С), (А+С-1,А+ С вЂ” 1 А+ С), ..., (А+ С + Р— 1 А+ С+ Р— 1 А+ С+ Р)); (Мол,Мг) = (6, ...,6, 6,, 6, (А+ С вЂ” 2), ..., (А+ С+ Р— 2)): Я = Мозг Мь 21. Пусть, например, и = 2»о+э, я = (2~»оп" — 1)/(2" — 1) = 2""+ +2" +1, у = 20+гы+1.
Тогда ку = (Зги+0" — 1)/(2" — 1), Если л = 2ло+гы + яу, имеем 1(и) < 4(д+ 1)и+ д+ 2 по теореме р, но Г(л) = 4(д + 1)п + 22 + 2 согласно теореме Н. 22. Подчеркните все, кроме н — 1 вставок, исполъзованных при вычислении к. 23. Теорема О (подчеркнуто все). 24. Используйте числа (В ' — 1)/( — 1), 0 < э < г, подчеркнутые, когда подчеркнуто а„ и с»В' '(Вч -1)/(В-1) для 0 < у < г, 0 < г < Ьг ы-Ьз, 1 < Ь < 1о(В), подчеркнутые, когда подчеркнуто с», где со, см, .. — 1 -цепочка минимальной длины для В.
Для доказательства о второго неравенства положите В = 2 н используйте (3). (Второе неравенство редко приаодит к улучшению теоремы О, если вообще приводит,) 20. Будем считать, что э(» = 1. Используем правило К А» г ... Ам где А; = кХК", если 41 = 1, и А; = кК" в противном случае, и где "К" обозначает взятие квадратного корня, а "Хэ — умножение на к. Например, если у = (.110110Цг, правило выглндит следуюшдм образом: К К ХК ХК К ХВ. ХК, (Существуют бинарные алгоритмы для извлечения квадратного корня, пригодные для использования на аппаратном уровне, время работы которых сравнимо со временем выполнения деления; компьютеры с таким аппаратным обеспечением могли бы таким образом вычислять более общие дробные степени с помошъю технологии, описанной в этом упражнении.) 20.
Если известна пара (В», В»-г ), то имеем (В»+и 1») = (В» + г»-» г») и (гг» гэ»-г) = (В»г + 2Ь»Ь» ц г»г + В»г,), поэтому для вычисления (г, Е„-г) может быть применен бинарный метод с 0()обл) арифметическими операциями. Возможно, лучше применить пары значений (г»,7»), где Г» = Ь»-г+В»+г (см. упр. 454-1$); тогда имеем (Ь»»д, Е»+г ) = (1(Р»+ У»), 1г(ЬВ»+ 1»)), (Ьг», Уг») = (Е»/»:В㻠— 2(-1) ) э Заметим, чта этот термин, хотя и не прижился в математике, широко рвспрастрэнен в программировании, особенно — в объектно-ориентированном, — Прим, перов, В случае обобщенной лияейной рекуррентности х„= а»х„» + ° + аах е х„можно найти за 0(а !оба) арифметических операций, вычислив и-ю степень соответствующей матрицы размера б х»(.
(Это наблюдение было сделано в работе б. С. Р. Мй!ег апд 11. б. Зревсег Вгони, Совр. Х 9 (1966), 188-190.) На самом деле, как заметил Ричард Врент (ВбсЬэгб Вгелг)., количество операций может быть сведено до О(а» 1об и) или даже до 0(И!обд!оби) с помощъв упр.4 7-6, если сначала вычислить х" шоб(х~-а»х~ '- . -аз), а затем заменить хз на х . 27. Наименьшее и, требующее э малых шагов, должно быть равным с(г) лля некоторого г.
Если с(г) < и < с(г+ 1), то Е(и) — Л(и) < г — Л(с(г)) = !(с(г) — Л(с(г))). Поэтому ответ для 1 < э < 6 — 3, 7, 29, 127, 1903, 65131; вероятно, с(28) потребует 7. 28. (а) хзур = хЧрЧ(х+р), где "ч" означает побитовое "или" (см. упр. 4.6.2-26). ясно, что л(хчр) < и(хм 3)+и(х Л 9) = и(х)+и(у). (Ь) Замет»п», во-первых, что А;,/2"-' С А,/2гч для 1 < 1 < г, и, во-вторых, что в неудвоенни Из = И, и в противном случае а» ~ > 2а! > а, + а» = а;. Следовательно, А, С А, » и А» С А, »/2»» ~».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
