AOP_Tom3 (1021738), страница 147
Текст из файла (страница 147)
Интересно отметитгь что мозг человека гораздо лучше компьютера справляетсн с поиском информации па вторичным ключам. Люди достаточно легко распознают лица, мелодии и т. п. по фрагментам информации, в то время как дли компьютера зто практически непосильная задача. Таким образом, вполне вероятно, что в один прекрасный день будет найден совершенно новый подход к решению задач, связанных с поиском информации по вторичным ключам, который сделает зто примечание, да и весь текущий раздел, безнадежно устаревшим.
УП РАЖ НЕ Н ИЯ 1. (М87) Пусть О < й < п/2. Докажите, что следующая конструкция дает (,",) перестановок множества (1,2,...,и), таких, что каждое Ьэлементное подмножество множества (1, 2,..., а) встречается в качестве первых 1 элементов как минимум одной перестановки при 1 < к или г > и — к. Рассмотрим путь на плоскости из точки (О, О) в точку (н, г), где г > и — 21; в котором ьй шаг выполняется из точки (1 — 1,1) в точку (Ь у+1) илн (0 1 — 1); последняя воэможность разрешена только нрн у > 1, так что путь никогда не проходит ниже оси х.
Существует равно (") таких путей. Для каждого из них соответствующая перестановка строится с использованием трех первоначально пустых списков следующим образом: для 1 = 1, 2,..., п, если 1-й шаг идет вверх, поместим число 1 в список В; если шаг ивет вниз, поместим 1 в список А и пе1жместим максимальный на текущий момент список В в список С. Результирующая перестановка представляет собой содержимое списка А, затем списков В и С, причем содержимое каждого списка приводится в порядке возрастания. Например, при и = 4 н к = 2 такая процедура определяет шесть путей и перестановок.
(Вертикальные линии отделяют списки А, В и С. Эти шесть перестановок соответствуют составным атрибутам в (8),) 7. [М24) (Р. Л. Ривест (Н. П %«еэг).) Найдите функции Це), определенные в предыдущем упражнении, для гледующих комбинаторных хеш-функций. (а) ш = 3, и = 2 (Ь) нг = 4,п = 2 О 0 « -> 0 1«0-+1 «11-+2 1 0 1 -+ 3 0 1 0 -> 3 О О «« -«О «1«0-+1 * 1 1 1 -+ 2 101«-+2 «101-«3 100«-«3 8. [Муй] (Р. Л. Ривест.) Рассмотрим множество Щ, всех 2'[,) базовых т-битовых запросов типа (10), в которых определено ровно 1 бит.
Дано множество «и-битовых записей Я. Пусть /«(о) описывает количество запросов в Яь, в ответах на которые содержатся члены множества о, а /~(э, тп) представляет собой минимум /~(5) по всем таким множествам Я с э элементами при 0 < э < 2 . По определению /~(0,0) = 0 и /«(1,0) = бсо. а) Докажите, что для всех 1 > 1 и ш > 1 при О < э < 2 Л(э,т) = Л([э/2],гп — 1) + Л вЂ” «([э/2] т 1) + /~ ~([э/2],т — 1). Ь) Рассмотрим некоторую комбинаторную хеш-функцию Ь, отображающую 2 возможных записей на 2" списков, причем каждый список соответствует 2ж " зш«исям. Если все запросы ф,«, равновероятны, то среднее количество проверяемых списков на запрос составляет 1/2'[„), умноженное на Указание.
Представьте каждое г-элементное подмножество 5 в виде пути, который идет из (О, 0) в (и, п-21), г'-ый шаг которого идет из (1 — 1, у) в (1, 2+1) при 1 р о и в (Ь у -1) прн 1 б Я. Преобразуйте каждый такой путь в путь описанного выше вида. 2. [М25] (Сакти П. Гош (шайб Р. СЬоэЬ).) Найдите минимально возможную длину 1 списка г«гэ...
г~ ссылок на записи, такого, что множество всех ответов на любой из включающих запросов ««1, «1«, 1*«, «11, 1«1, 11*, 111 по трем вторичным ключам с двумя возможными значениями оказывается расположенным в последовательных позициях г;... гм 3. [19] Какие включающие запросы к табл. 2 вызовут ложное выпадение (а) старинного сахарного печенья, (Ь) овсяных палочек с финиками? 4. [МУО] Найдите точные формулы для вероятностей в (11), предполагая, что каждая запись имеет г различных атрибутов, случайным образом выбираемых из [") )«-битовых кодов в и-битовом поле, и что запрос включает о различных (но в остальном случайных) атрибутов (не волнуйтесь, если формулы не будут упрощаться).
б. [4 0] Проэкспериментируйте с различными путями снижения избгяточности текста прн использовании метода Харрисона для поиска подстрок. б. [М20[ Общее количество т-битовых базовых запросов с 1 определенными битами составляет э = [,)2'. Если комбинаторная хеш-функция наподобие (13) конвертирует такие запросы в позиции 1«, (м ..., 1, соответственно, то среднее количество позиций на запрос составляет б(1) = (1~ + 1« + + 1,)/э (напрнмер, в (13) получим ЦЗ) = 1.75).
Рассмотрим теперь составную хеш-функцию над (пц + тэ)-битовым полем, построенную путем отображения первых т«бит с помощью одной хеш-функпин н оставшихся тэ с помощью другой, а Ц(1) и 1 э(1) — соответствующие средние количества позиций на запрос. Найдите формулу, выражающую значение б(1) в случае составной функции через ЦиЦь (списки, проверяемые для л„г) = аея .- (запросы Яс м, относящиеся к Я) > 2"~с(2 ", т).
с смз Покажите, чта Ь оптимальна в том смысле, что нижняя грань достигается, когда каждый из списков представляет собой "субкуб"; другими словами, покажите, что в случае, когда каждый спиогк соответствует множеству записей, удовлетворяющих базовому запросу с ровно п определенными битами, неравенство превращается в равенство. 9. (МЯО) Докажите, что если в = 3", то множество всех троек вида ((аг...ал г ОЬ«...6„-«)г, (аг...а«-г 1сг...с„-л)г,(ас...ал-г 2йг...й -«)г), 1 < lс < и, где а, Ь, с и с( принимает значения О, 1 или 2 и Ь„+ с, + с4г ы 0 (по модулю 3) при 1 < у' < и — Ь образует Штейнеровскую систему троек, 10. (МУУ) (Томас П.
Киркман (ТЬогпаз Р. К!г1стап), СапгбгЫУе апс1 ТгиМ«п МаСЛ. Лоигла1 2 (1847), 191- 204.) Назовем системой троек Киркмеио порядка в такое упорядочение в + 1 объектов (хе,хг,..., х,) в тРойки, пРи котоРом кажДаЯ паРа (х„хг), г ~ 1 встРечаетсЯ ровно в одной тройке, за исключением в пар (х„хб+гг,„,е„),0 < г < в, которые не встречаются в тройках.
Например, (хе, хг, хс), (хс, хг. хс) представляет собой систему троек Киркмана порядка 4. а) Докажите, что система троек Киркмана может существовать только для в щод6 = 0 или 4. Ь) Дана Штейнеровская система троек 5 над в объектами (хг,..., х„). Докажите, что следующее построение дает другую Штейнеровскую систему троек о' над 2в + 1 объектами и систему троек Киркмана К' порядка 2в — 2. Тройки о' представляют собой все тройки нз 5 плюс г) (х„у;,у«), где ) + lс = г (по людулю в) и г < Й, 1 < г З Й < в; й) (хь уг, г), где 21 = с (по модулю в), 1 < г, 2 < в. Тройки системы К' представляют собой множество троек Я' минус все тройки, содержащие уг исили у„.
с) Дана система троек Киркмана К на множестве (хе,хь, х„), где в = 2и. Докажите, что следующее построение дает Штейнеровскую систему троек Я' над 2в+ 1 объектами и систему троек Киркмана К' порядка 2в — 2. Тройки Я' представляют собой тройки К плюс ') (хахбегг ос улг).0<с<в; и) (х,,Уг,рл),1+1=2«+1(помодУлюв — 1),1<У<Ус — 1<в — 2,1<с<в — 2 гй) (х,, Уг, У ), 21 се 2« + 1 (по модулю в — 1), 1 < 1 < в — 1, 1 < г < в — 2; 1в) (хе, Угг, Угг+г), (х г, Угг — г, угг), (х„, р, у,;), 1 < 2 < и; в) (х,у„,у,). Тройки К' представляют собой множество троек Я' минус все тройки, содержащие уг н/или у„ с() Исггользуйте предыдущие результаты для доказательства того, чта аисте««а троек Киркмана порядка в существует для всех в > 0 вида бй или 6(с+ 4 н Штейнеровская система троек над в объектами существует для всех в > 1 вида 6)с+ 1 или 6)с+ 3.
11. [М25[ В тексте раздела описана использование Штейнеровских систем троек в связи с включающими запросами. Для расширения их применения на все базовые запросы естественно определить следующую концепцию. Комплемептарной системой евреек порядка о является такое размещение 2о обьектов (хг,..., х„,хм...,х,) в тройках, при котором каждая пара объектов встречается ровно в одной тройке, за исключение»» комплементарных пар (ха х,), никогда не встречающихся вместе. Например, (хг,хг,хз), (хг,хг,хз), (хг,хг,хз), (хг,хз,хз) представляет собой комплементарную систему троек третьего порядка.
Докажите, что комплементарные системы троек порядка о существуют для всех и > О, не имеющих вид ЗЬ + 2. 12. [МУЗ) Продолжая упр. 11, постройте комплементарную систему четверок порядка 7. 13. [М25[ Постройте систему четверок с о = 4" элементами, аналогичную системе троек из упр. 9. 14.
[ЯЗ] Обсудите проблему удаления узлов иэ четревьев, ?е-д-деревьев и почтовых деревьев, подобных показанному на рис. 45. 13. [НМЗО[ (П. Элиас (Р. Е!!аз).) Дана большая коллекция т-битовых записей. Предположим, что необходимо найти запись, ближайшую к данному аргументу поиска в том смысле, что согласовано наибольшее количество битов. Разработайте алгоритм эффективнога решения этой задачи в предположении, что задан гп-битовый код из 2" элементов, исправляющий ! ошибок, и что каждая запись хешируется в один из 2" списков, соответствующих ближайшему кодовому слону. ь 16.
[Яб[ (В. Х. Кац (ее'. Н. Каизх) и Р. К. Синглтон (Н. С. 3!ий!езои).) Покажите, что Штейнеровская система троек порядка о может использоваться для построения о(о — 1)/6 в-бнтовых кодовых слав, таких, что никакое слава не содержится в суперпозииии двух других. ь 12.
[МЗО) Рассмотрите следующий путь сведения (2п+1)-битовых ключей а „... ао... а„ к (и + 1)-битовому блоку адресов Ьо... Ь: Ьо»- ао~ если Ь» г = О, то Ь»»- а», иначе Ь»»- а» для 1 (?е < и. а) Опишите ключи, появляющиеся в блоке Ьо... Ь„, Ь) Чему равна наибольшее количество блоков, которые необходимо проверить при базовом запросе с Г определенными битами? ь 18. [МЗ5) (Конструирование ассоциативного блока.) Множество т-элементных наборов типа (13) с ровно т — и звездочками в каждой из 2" строк называется АВП(т, и)*, если в каждом столбце содержится одно и то же количество звездочек и если каждая пара строк имеет "несоответствие" (О иратив 1) в некотором столбце.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
