AOP_Tom2 (1021737), страница 215
Текст из файла (страница 215)
Законы ассоциативности: АЬ(ВОС) = (АЮВ)ЬС, А0(В0С) = (А0В) 0С, АП(ВПС) = (А ГЗ В) С С. Законы дистрибутивности: А 0 (В й С) = (А 0 В) й (А 0 С), А Гэ (В 0 С) = (АПВ)0(АПС), АЬ(В0С) = (АЭ1В)0(АСС), АЭ1(ВГЗС) = (АЮВ)Г)(Аз~С), Законы идемпотентности: А 0 А = А, А Г1 А = А. Законы поглощения. А 0 (А С В) = А, АГ1(А 0 В) = А, АП(АюВ) = А, А0(АЫВ) = АЮ В.
Законы единицы н нуля: ЭЬ А = А, й 0 А = А, 9 П А = й, где й обозначает пустое мультимножество. Закон перечисления: А Ы В = (А 0 В) ю (А Г3 В). Прочие свойства, аналогичные соответствующим свойствам множеств, вытекают из частичной упорядоченности, определенной правилом А С В тогда и только тогда, когда А Гз В = А (тогда н только тогда, когда А 0 В = В). Промечаннл. Другие общие применения мультимножеств — нули и полюсы мероморфных функций, инварианты матриц в канонической форме, инварианты конечных Абелевых групп и т. д.
Мультимножества могут быть полезны в комбинаторике и в теории мер. Терминальные строки нециркулярной контекстно-свободной грамматики образуют мультимножество, которое является множеством тогда и только тогда, когда грамматика свободна от неопределенностей. В статье автора в ТЬеогейса1 Яепйеэ ш Сошригег Яс1елсе, ефбеб Ьу 5. П. ЬЗ!швп (Асабеш1с Ргевэ, 1992), 1 — 13, обсуждаются дальнейшие применения к контекстно-свободным грамматикам и вводится операция А ГЗ В, где каждый элемент, который встречается а раз в А и Ь раз в В, встречается в А Щ В аЬ раз. Хотя мультимножества появляются в математике достаточно часто, во многих случаях они трактуются неуклюже, поскольку в настоящее время не существует стандартного пути рассмотрения множеств с повторяющимися элементами.
Некоторые математики выразили свое мнение о том, что отсутствие адекватной терминологии и обозначений для этой глобальной концеппли определенно затрудняет развитие математики. (5йультимножество, конечно, формально эквивалентно отображению множества на неотрицательные целые числа, ио эта эквивалентность имеет слишком малое значение,эля творческого математического мышления.) Автор обсуждал этот вопрос со многимн специалистами в 60-х годах, пытаясь найти приемлемое решение вопроса. Вот некоторые из предлагавшихся для этой концепции наэааний: список (1Ы), связка (ЬппсЬ), мешок (Ьаб), куча (Ьеар), проба (эашр!е), взвешенное множество (ие!б!»се»! эес), коллекция (со!!есНол*), комплект (во!Фе).
Однако все эти они конфликтуют с существующей терминологией, имеют неуместное дополнительное значение или слишком неудобны для произношения и написания. Наконец, стало ясно, что для такой важной концепции необходимо собственное имя, и оно— "мультимножество" (пш16эес) — было предложено Н. Г. де Брейном (В. С. бе Вгп!)в). Его предложение широко распространилось в 70-х годах и теперь является стандартным термином.
Зались "А Э! В" была выбрана автором, чтобы избежать конфликтов с существующил»и обозначенинми и усилить аналогию с обьедииением множеств. Для этого нежелательно использовать "А + В", поскольху специалисты в области алгебры приняли А + В как запись для мультимножества (а + )1 ! о б А и В.
б В). Пусть А является мульти- множеством неотрицательных целых чисел, а С(х) = ~ „л х" — производящая функция, соответствующая А. (Очевидно, что производящие функции с неотрицательными целыми коэффициентами находятся во взаимно однозначном соответствии с мультимножествамн неотрицательных чисел.) Если С(х) соответствует А, а Н(х) соответствует В, та С(х) + В(х) соответствует А е! В, а С(х)Н(х) соответствует А + В. Если построить пРоизводащие фУнкцин ДиРихле 9(х) = 4"„ел 1/и*, 5(х) = 2 „ев 1/и", то пРоизведение д(х)Ь(х) будет соответствовать произведению мультнмножеств АВ. 20. Тип 3: (Яо,...,Яг) = (Мое,,М«о) = ((О),, (А), (А — 1,А), (А — 1,А,А), (А — 1, А — 1,А,А,А), ..., (А+ С вЂ” 3,А+ С вЂ” 3,А+ С вЂ” 2,А+ С вЂ” 2, А+ С вЂ” 2)). Тип 5: (Моо,..., М,а) = ((О), ..., (А), (А — 1, А),, (А+С вЂ” 1., А+С), (А+С вЂ” 1, А+ С вЂ” 1,А+ С),..., (А+ С+ Р— 1, А+ С+ Р— 1,А+ С+ Р)); (Мам, М.») = (Э,...,б, 6,, 6, (А+С вЂ” 2),, (А+ С+Р— 2)), В* = МоШМп.
21. Пусть, например, и = 2~»+~, х = (20+'!" — 1)/(2" — 1) = 2»" + +2" +1, у = 20»'м+1. Тогда кр = (2цэ+и" — 1)/(2" — 1), Если и = 2цэ ьп" + хр, имеем !(и) < 4(д+ 1)и+ о+ 2 по теореме р, но Г(п) = 4(д+ 1)к+ 20+ 2 согласно теореме Н. 22. Подчеркните все, кроме и — 1 вставок, использованных при вычислении к. 23.
Теорема С (подчеркнуто все). 24. Используйте числа (В»ч — 1)/( — 1), 0 < ! < г,подчеркнутые, когда подчеркнуто оь и с»В' '(В»' — 1)/( — 1) для 0 < / < 1, 0 < ! < Ьз.ы — Ь;, 1 < й < !о(В), подчеркнутые, когда подчеркнуто с», где со, с»,... — ! -цепочка минимальной длины для В. Для доказательства е второго неравенства положите В = 2 и используйте (3).
(Второе неравенство редко приводит к улучшению теоремы С, если вообще приводит.) 25. Будем считать, что А» = 1. Используем правило К А»,... Ам где А, = "ХК", егли Ы = 1, и А = "К" в противном случае, и где "К" обозначает взятие квадратного корня, а "Х" — умножение на х. Например, если у = (.1101101)э, правило выглядит следующим образом: К К ХК ХК К ХК ХК. (Существуют бинарные алгоритмы для извлечении квадратного корня, пригодные для использования на аппаратном уровне, врел»я работы которых сравнимо со временем выполнения деления; компьютеры с таким аппаратным обеспечением могли бы таким образом вычислять более общие дробные степени с помощью технологии, описанной в этом упражнении.) 26.
Если известна пара (Г»,Г»»), то имеем (Г»ем Г») = (Г» + Г»-и Г») и (Гэ»,Гы ~) = (Г» + 2ûû»мГ» + Г»,), поэтому для вычисления (Г„,Г ~) может быть применен э г э бинарный метод с О(!обо) арифметическими операциями. Возможно, лучше применить пары значений (Г», б»), где б» = Г» — г+Г»»» (см. упр. 4.5.4 — 15); тогда имеем (Г»т н Л»т») = (э(Г» + б»), ~ (5Г» + Л»)), (Гг», Лг») = (Г»б», Л» — 2( — 1)"). * Заметим, что этот терман, хотя н не прижился в математике, ~вкроко распространен в программировании, особенно — э абьектно-оряентироэанном. — Прим.
нерее. В случае обобщенной линейной рекуррентности х = а>хв > + +агх э х, можно найти за 0(>С !об и) арифметических операций, вычислив и-ю степень соответствующей з матрицы размера >С х >С. [Это наблюдение было сделано в работе 3. С. Р. М11!ег аш1 П. 3. Врепсег Вго>гп, Сошр. Х 9 (1966), 188-190.[ На самом деле, как заметил Ричард Брент (В!сЬагсС Вгепс), количество операций может быть сведено до 0(>С~ 1об и) или даже до 0(>С!об>С!о8 и) с помощью упр. 4.7-6, если сначала вычислить х" шог) (х~ — а>х~ ' — .
— аэ)> а затем заменить х' на х . 27. Наименьшее и, требующее з малых шагов, должно быть равным с(г) для некоторого г. Если сЯ < п < с(г+ 1), то 1(п) — Л(п) < г — Л(с(г)) = 1(с(г) — Л(с(г))). Поэтому ответ для 1 < л < 6 — 3, 7, 29. 127, 1903, 65131; вероятно, с(28) потребует 7. 28.
(а) х5?у = хууЧ(х+у), где "Ч" означает побитовое "или" (см. упр. 4.6.2-26). Ясно, что и(хэуУ) < и(х ЧУ)+ и(х>>У) = и(х)+ и(У). (Ь) Заметим, во-пеРвых, что А,,/2Ш-' С Ас/2гб для 1 < > < г, и, во-вторых, что в неудвоеннн >С» = С, >, в противном случае а; > > 2а» а> + аь = аь Следовательно, А, С А, > н Аь С А, >/2 > ~'. (с) Простая инлукция по Ь но близкие шаги требуют более пристального внимания. Будем говорить, что т обладает свойством Р(а), если все единицы в его бинарном представлении располагаются в последовательных блоках > а в строке.
Если т и т' обладают свойством Р(а), то нм обладает и т>>ут'; если т обладает свойством Р(о), то р(т) обладает свойством Р(а + 5). Следовательно, В; обладает свойством Р(1 + дс,). И наконец, если т обладает свойством Р(а), то и(р(т)) < (о+5) и(т)/о, для и(гл) = и>+ +ию где каждый размер блока и» а.
Следовательно, и(р(т)) < (и>+5)+ +(из+ 5) < (1+5/а)и>+ . +(1+5/а)ию (4) Пусть / = 6, + с„— чисво неудвоений, а з — число малых шагов Если / > 3.271 18 и(п), то з > !8 и(п), квк и требовалось, в соответствии с (16). В противном случае а, < (1+ 2 ~)~ 2" т~' для 0 < > < г. Значит, и < ((1+ 2 ~)/2) "2" и г > !8 и+ 6„— 6, 18(1+ 2 ~) > 18п+ 18 и(п)— 18(1 + бс>) — 6„!8(1+ 2 ~).
ПУсть 5 = [!8(/+ 1)); тогда !п(1 + 2 ) < 1п(1 + 1/(/+ 1)) < 1/(/+ 1) < б/(1+5/). Отсюда следует, что !8(1+бх)+(/-х) !8(1+ 2 ~) < !8(1+5/) для 0 < х < /. Поэтому окончательно !(и) >!8 и+!8 и(п) — 18(1+(3.271 18 и(п)) [!8(1+3.271 18 г (гс)))). [ТЬеогеС!св) Соп>р. Всб 1 (1975), 1-12.[ 29. В только что процитированной работе Шенхвге усовершенствовал метод из упр. 28 для доказательства того, что !(и) > !8 п+ !8 и(п) — 2.13 для всех и.
Может ли оставшийся пробел быть закрытым? 30. и = 31 представляет собой наименьший пример; !(31) = 7, но цепочка со сложением и вычитанием 1, 2, 4, В, 16, 32, 31 имеет длину 6. [После доказательства теоремы Е Эрдеш (Егдоз) указал, что тот же результат справедлив и для вддитивно-вычитательных цепочек. Шенхаге распространил нижнюю границу из упр. 28 на цепочки со сложением н вычитанием с и(п), замененные й(п), как определено в упр. 4.1 — 34. Обобщенный бинарный метод возведения в степень справа налево, в котором используется Л(п)+й(п) — 1 ул>ножений, когда заданы и х, и х ', может основываться иа представлении а„из этого упражнения.] 32.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
