AOP_Tom3 (1021738), страница 212
Текст из файла (страница 212)
Е де Брейн (К. С. ь1е Вгпьзп), К. вшьЭббенхорст Тенгберген (С. кап ЕЬЬепЬогэг ТепбЬегбеп) и Д. Круйсвик (Р. Кгвуэкйй) (%епьг АгсйьеГ гоог угьэкипь1е (2) 23 (1951), 191 — 193) доказали обобщение леммы Спернера для мультимножеств: "Пусть М вЂ” мультимножество, содержащее гь элементов (считая повторения). Набор всех (ьь/2)-элементнььх мультиподмножеств М представляет собой наибояьший возможный набор, такой, что ни одно мультиподмножество не содержится в другом". Например, наибольший такой набор при М = (а,а,Ь,Ь,с,с) состоит из семи мультиподмножеств: (а,а,Ь), (а,а,с), (а,Ь,Ь), [а, Ь, с), (а, с, с), (Ь, Ь, с), (Ь, с, с). Этот набор соответствует семи перестановкам шести атрибутов (Ас, Вс, А«, Вг, Ав, Вэ) для случая, когда запрос, включающий Аи содержит также Вь Дополнительные комментарии по этому вопросу приводятся в статье С.
Сгеепе апб П. Ь К1ейшап, Ь Сотбслааогса1 ТЬеогу А20 (197б), 80-88. 2. Пусть ас«н — список всех ссылок на записи, имеющие значения трех атрибутов («,Ь Ь), и предположим, что список аасс — самый короткий среди списков аасс, а«ос, асса Тогда списком с минимальной длиной является аашаоссасссасосасооамоасссаоссаосо, Однако, если аасс пуст и пуст также любой из списков аеас, аосо и асан, длина может быть сокращена путем удаления одного из двух вхождений асс« ]САСМ 18 (1972), 802 — 808].
3. (а) Зерна аниса и/или мед, возможно, в комбинации с мускатным орехом и/или ванилином. (Ь) Никакие. 4. Пусть рс — вероятность того, что запрос включает в точности 1-битовые позиции, и пусть Рс — вероятность того, что 1 данных позиций в случайной записи равны 1. Тогда ответом 6Удет хт с РсРс минУс веРоитность того, что искомаа запись действительно найдена; последняя вероятность равна (~ »)/(„), где Ьс = ("„).
По принципу включения и исключения Р = Е(-1)1('.)/(.—,Ь, )//(.,Ь,г), «>о где /(и, /с, г) — количество возможных выборов т различных Ь-битовых кодов атрибутов в и-битовых полях, а именно У(., Ь, ) = ((,"") ) При д = г имеем согласно упр. 1.3.3-2б ~:( )(, )(„,) „, (,)~:( ) ()/(,, )//(,, ) с>а ,>о Примечание. Приведенные выше вычисления впервые были выполнены в более общей форме в С.
Огоэх апс1 1 . Тайасв, Ь оЬПосашепааасоп 12 (1936), 231-234. Легко показать, что среднее значение 2 грс равно п(1 — /(и — 1, 1с, 9)//(и, Ь, 9)). Предположение о том, что коды случайных атрибутов в записях и запросах необязательно должны быть различными, как в случаях использования технологий Харрисона и Блюма, может быть проанализировано таким же образом с /(п,д,г) = („")". Когда параметры находятся в соответствующих диапазонах, получаем Рс ж (1 — е "~")' и т рсРс -- Р 0, ас ы! Тг Ь(в) — 2 (мс)( «)Ь (д)Ь«(1 — «)/(~с+~«) (следовательно, если Ьс(Г) Ь1«п и Ь«(г) Ьс«о, то Ь(г) Асс «о ) 7 (а) Ь(1) — 3 Ь(2) — 1« (Ь) Ц1) — 3э Ь(2) = 2« Ь(3) = 1,«.
]ПРимнчание. Тривиальное проецирующее отображение типа 00»» — с О, 01»» -с 1, 10»» -» 2, 11»» -с 3 представляет собой отображение, наихудший случай которого хуже, но средний — лучше: Ь(1) = 3, Ь(2) = 2-', Ь(3) = 1-'.] 8. (а) При 5 = Яо01Э5«1 имеем /с(5) = /с(до 05«) +/с с(эо) +/с с(зс). Таким обРазом, /с(н, т) представляет собой минимум /с(во, сп — 1) + /с с (во, сл — 1) + /с с (в«, сл — 1) по всем во и нс, таким, что 2~ ' > но > вс > 0 и во + нс = н.
Чтобы доказать, что минимум достигается для ва — — Гв/21 вс = (в/2]с можно испольэовать индукцию по т с очевидным результатом при т = 1: дано т > 2. Пусть дс(в) = /с(в,т — 1) и Ьс(в) = /с(н,т — 2). Тогда по индукции дс(на) + дс-с(но) + дс — с(нс) = Ьс(Гва/21) +Ьс с(Гва/21) + Ьс-с((ва/2]) + Ьс-с(Гно/21) + Ьс-г(Гва/21) + Ьс «((но/2]) + Ьс-с(Гнс/21) + Ьс-«(Гнс/2!) + Ьс-х((вс/2]), что > дс((но/21+ Гнс/21)+дс с(Гва/21+ Гвс/21)+дс-с((во/2]+ (вс/2]) Если во > в«+1, имеем [за/2) + [з»/2) < ва, за исключением случая, когда ва = 26+ 1 и ⻠— — 26 — 1. В последнем случае, однако, дс(за) + дс — »(ва) + дс»(з») > 6»(26 + 1) + 26»-»(26) > Ь»(26) + 26»» (26).
(Ь) Заметьте, что множество Я, содержащее числа О, 1,, в — 1 в двоичной записи, имеет такое свойствос Яа О 5» = Яа и ла содержит [за/21 элементов. Отсюда следует, что /,(2 -", ) = [ '] (1+ г)" (1+2 )--". 10. (а) Должно существовать ао(о — 1) троек, и х„должно встречаться в -о из ннх. » » (Ь) Поскольку о нечетно, для каждого» имеется уникальная тройка (х„у», г), откуда легко показать, что Я~ — Штейнеровская система троек. Отсутствующие в К' пары— (г,хэ), (хг,уг)» (уг,хз), (хэ,уэ),, (х„»,у„»), (у„»,х,), (х„,г) (4) Начав со случая для о = 1 и применив операции ь э 2о — 2, о -э 2о+1, получим все неотрицателъные числа, которые не имеют внд 36 -»- 2, потому что случаи б(с + (О, 1, 3, 4) получаются из меньших чисел 36+ (1, О, 1,3) соответственно. Оказывается, "Штейнеровские системы троек"' не должны именоваться Штейнеровскими, хотя это имя глубоко укоренилось в литературе. Публикация Штейнера [Сгейе 45 (1853), 181-182[ появилась несколькими годами позже публикапни Киркмана.
Феликс Клейн (ге!!х К1е!о) заметил [)сот!евипдеп йЬег »4»е ЕлгайсИипд с!ег Магй. пп 19. дайгйвпс(ег1 1 (Врг!пйег, 1926), 128), что в последмие годы жизни Штейнер цитировал английских авторов без ссылок на них. Более того, концепция троек появилась еще раньше в двух хорошо известных книгах Ю. Плюкера (Л. Р!Осйег) [Яувсеш с(ег ала!усззсбеп Сеошесг»е (1835), 283-284; ТЬеопе с(ег а!деЬгювсйеп Сиггеп (1839), 245-247[. 11. Возьмем Штейнеровскую систему троек нзд 2е + 1 объектами. Назовем один из объектов х, а другие объекты переименуем таким образом, чтобы тройками, содержащими г, оказались (х, хп х,). Затем удалим эти тройки. 12.
[6, (6+1) шо414, (6+4) шо414, (6+б) п»о»114) при О < 6 < 14, где (6 + 7)»пой 14 представляет собой дополнение й (кол»плеь»ентарная система является частным случаем групп, разделяемых на блоки; см. Вове, БЬг!ЬЬапйе, апб ВЬассасЬагуа, Апл. Магй. Ясаивбсв 24 (1953), 167-195) 14. Самый простой вид удаления — иэ 6-Й-деревьев (замещение для кормя может быть найдено примерно за О(Х' м~) шагов). В четревьях для удаления, похоже, потребуется полнан перестройка поддерева, корнем которого является удаляемый узел (однако такое поддерево содержит в средне»» лишь около!об»у узлов).
Для почтовых деревьев удаление практически безнадежно. 16. Пусть каждая тройка соответствует кодовому главу и каждое кодовое слово имеет ровно трн равных единице бита, определяющих элементы соответствующей тройки. Ести и, о и ю -- различные кодовые слова, то глава и имеет не более двух равных единице битов с суперпозицней а и ш, поскольку оно может иметь не более одного общего бнта со словами а и и» па отдельности (аналогично из систсмы четверок порядка а можно построить о(о — 1)/12 кодовых слов, никакое из которых не содержится в суперпозиция любых трех других, и т, д.). 17.
(а) Пусть са = Ьа, а для 1 < 6 < и положим сз = (если 6»» = О, то "г", иначе — 6з), с з = (еслм Ьв» = 1, то "з", иначе — Ьз). Тогда базовый запрос с ... са... с„описывает содержимое блока 6а, Ь . (Следовательно, эта схема представляет собой частный глучай комбинаторного хеширования н ее среднее время запроса соответствует нижней границе в упр. 8, (Ь).) (Ь) Пусть дз = [бит 6 определен) для — п < 6 < п. Можно положить. что д з < Из при 1 < 6 < и. Тогда максимальное количество проверенных блоков получается, когда все определенные биты равны нулю и оно может быть вычислено следующим образом. Установим х З вЂ” у +- 1; затем дли Ь = и, и — 1,..., 0 выполним (х,у) +- (х, у)М» еею где Ме= (,,), И, наконец, выведем х (который может равняться у после Ь = 0).
Будем говорить, что (х,у) >- (х',у'), если х > х' и х+ у > х'+ у'. Тогда, если (х,у) З (*',у), имеем (х,у)Лзз Ь- (*',у)М» для Л= О, 1, 2. Теперь (х, у) М2 М! Ме = (Г! ! ах, Г! ! зх), (х У)М2М! М! (Г!»зх+ Г!»Зу Гз+Зх+ Г! ! 2У), (х У)МеМ! М2 — (Г!»2х + Г!»Зу ГЗ+2Х + Гзе2У) гшедовательно, (х, у)М, М',М, Ь- (х, у)МЗМЗМе, потому что 2У > х; и аналогично (х,у)МЗЛ4/М! >. (Х,у)МЗЛ»22МЗ, потому что х > у. Отсюда вытекает, что наихудший случай возникает либо при Л з + Л» < 1 для 1 < у < и, либо при Л з + Лз > 1 для 1 < Л < и.
Кроме того, (х,у)М,М' ,= (Л;+,я+Г„ЗУ,Г„!к+ Г„,у), (х, у)МЗМ» = (Г»гх+ ГЗ+Зу, ГЗ+Зх+ Г»ЗУ), (х, у)М,М,' = (Г,»ЗХ, Г»2Х), (х, у)М,'М, = (Г!»2Х+ Гзу, Г!»2х+ Г у). Значит, в худшем случае требуется следующее количество блоков: 2 юГ!те, если 0 <1 < и [нз М,'М +' 2' "Гз из 2, если и <1 < [3и/2[ [из М," '(М!МЗ)' "Ме[; 2~"т' ' еслзз [3~/2) < 1 < 2и [из МЗ' з" (М М )2" 'Щ [Эти резульшты, по сути, были получены В. О. Буркхардом (4У. А.
ВпгЬЬагЛ), В1Т 16 (1976), 13-31, и обобщены в Х Сошр. Яузг. Ясй 16 (1977), 280 — 299; более сложное ото- бражение Буркхарда из ае .. аз„на Ье... Ь„было упрощено здесь согласно предложению П. Дубоста (Р. ПвЬозс) и Ж.-М. Труссе (3.-М. Тгооззе), доклад 8ТАВ-Сб-76-611 (Зсап(огб Пшю, 1975).[ 18. (а) Всего, имеется 2" (т — и) символов "»", следовательно, 2"и цифр с 2" и/т цифр в каждом столбце. Половина цифр в каждом столбце должна быть равна нулю.
Значит, 2" 'и/гп — целое и в каждом столбце содержится (2" 'и/Зи)2 несоответствий. Поскольку каждая пара строк имеет минимум одно несоответствие, необходимо получить 2" (2"— 1)/2 < (2" 'и/т)~ш. (Ь) Рассмотрим 2 т-битовых чисел с нулем в т-и определенных столбцах.
Половина из них имеет нечетный паритет. Число строк с четным паритетом среди строк с символом »»» в любом нз неопределенных столбцов равно числу строк с нечетным паритетом (с) *000, »111, 0»10, 1»10, 00»1, 10»1, 010*, 110» Это построение не такое равномерное, как (13), поскольку запрос типа»01» подходит к четырем строкам, в то врелЗя как»10» — только к двум. Заметьте, что (13) имеет циклическую симметрию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
