11. [М25] В тексте раздела описано использование Штейнеровских систем троек в связи с включающими запросами. Для расширения их применения на все базовые запросы естественно определить следующую концепцию. Комплементарной системой троек порядка II является такое размещение 2v объектов {xi,..., ж„, xi,... в тройках, при котором каждая пара объектов встречается ровно в одной тройке, за исключением комплементарных пар {xi,Xi}, никогда не встречающихся вместе. Например,

{Х1,Х2,Хз}, {Х1,Х2,Хз}, {Х1,Х2,ХЗ}, {Х1,Х2,Хз}

представляет собой комплементарную систему троек третьего порядка.

Докажите, что комплементарные системы троек порядка v существуют для всех v>0, не имеющих вид Зк + 2.

12. [М23] Продолжая упр. И, постройте комплементарную систему четверок порядка 7.

13. [М25] Постройте систему четверок с v = 4" элементами, аналогичную системе троек из упр. 9.

14. [28] Обсудите проблему удаления узлов из четревьев, fc-d-деревьев и почтовых деревьев, подобных показанному на рис. 45.

15. [НМЗО] (П. Элиас (Р. Elias).) Дана большая коллекция т-битовых записей. Предположим, что необходимо найти запись, ближайшую к данному аргументу поиска в том смысле, что согласовано наибольшее количество битов. Разработайте алгоритм эффективного решения этой задачи в предположении, что задан т-битовый код из 2" элементов, исправляющий t ошибок, и что каждая запись хешируется в один из 2" списков, соответствующих ближайшему кодовому слову.

► 16. [25] (В. X. Кац (W. Н. Kautz) и Р. К. Синглтон (R. С. Singleton).) Покажите, что Штейнеровская система троек порядка v может использоваться для построения v{v - 1)/6 г;-битовых кодовых слов, таких, что никакое слово не содержится в суперпозиции двух других.

► 17. [МЗО] Рассмотрите следующий путь сведения (2т1Ч-1)-битовых ключей а-„ ... ао а„ к {п + 1)-битовому блоку адресов bo...b„:

bo <- Оо;

если Ьк-1 = О, то Ьк <- а-к, иначе Ьк <- ак для 1 < А; < п.

a) Опишите ключи, появляющиеся в блоке bo...b„.

b) Чему равно наибольшее количество блоков, которые необходимо проверить при базовом запросе с t определенными битами?

► 18. [Л55] {Конструирование ассоциативного блока.) Множество т-элементных наборов типа (13) с ровно т - п звездочками в каждой из 2" строк называется ABD(m, п)*, если в каждом столбце содержится одно и то же количество звездочек и если каждая пара строк имеет "несоответствие" (О против 1) в некотором столбце. Каждое т-битовое бинарное число будет в таком случае соответствовать в точности одной строке. Например, (13) является ABD(4,3).

a) Докажите, что ABD(m,n) невозможно, кроме случаев, когда т является делителем 2"-пип= >2т(1-2-").

b) Будем говорить, что строка ABD имеет нечетный паритет, если в ней содержится нечетное количество единиц. Покажите, что для любого выбора т - п столбцов в ABD(m, п) количество строк с нечетным паритетом с "*" в этих столбцах равно количеству строк с четным паритетом. В частности, каждое возможное расположение символов "*" должно встречаться в четном количестве строк.

* От Associative Block Designs. - Прим. перев.

c) Найдите ABD(4,3), которое не может быть получено из (13) путем перестановки и/или дополнения столбцов.

d) Постройте ABD(16,9).

e) Постройте ABD(16,10). Начните с ABD(16,9) из п. (d) вместо ABD(8,5) из (15).

19. [М22] Проанализируйте ABD(8, 5) из (15) так же, как (13) было проанализировано в (14). Сколько из 32 позиций должно быть проверено при запросе с к неопределенными битами в среднем и в наихудшем случаях?

20. [М47] Найдите все ABD(m, п) при п-5 или п = 6.

Новый ре13дел 6.6 в следующем издании книги планируется посвятить постоянным структурам данных. Эти структуры позволяют представить измененную информацию таким образом, что история изменений может быть эффективно восстановлена. Иными словами, можно сделать множество вставок и удалений, но, тем не менее, оставаться способными выполнить поиск так, как будто обновлений после некоторого данного момента времени вовсе не было. Пока что в настоящее издание включены лищъ ссылки на литературу по этой теме:

• J. К. Mullin, Сотр. J. 24 (1981), 367-373;

• М. И. Overmars, Lecture iVotes in Сотр. Sci. 156 (1983), Chapter 9;

• E. W. Myers, ACJVf Symp. Principles of Prog. Lang. 11 (1984), 66-75;

• B. Chazelle, Information and Control 63 (1985), 77-99;

• D, Dobkin and J. 1. Munro, J. Algorithms 6 (1985), 455-465;

• R. Cole, J. Algorithms 7 (1986), 202-220;

• D. Field, Information Processing Letters 24 (1987), 95-96;

• C. W. Eraser and E. W. Myers, ACJVf Trans. Prog. Lang, and Systems 9 (1987), 277-295;

• J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan, J. Сотр. Syst. Sci. 38 (1989), 86-124;

• R. B. Dannenberg, Software Practice & Experience 20 (1990), 109-132;

• J. R. Driscoll, D. D. K. Sleator, and R. E. Tarjan, JACJVf 41 (1994), 943-959.

Таблицы инструкций (программы) будут создаваться математиками с опытом вычислительной работы и, вероятно, с определенными способностями к решению головоломок. Перевод на некоторой стадии каждого известного процесса в форму таблиц инструкций, скорее всего, будет значительной частью такой работы. ... Процесс построения таблиц инструкций должен очаровывать. Реальной опасности стать слугой машины нет, ибо любой более или менее механический процесс можно передать самой машине.

- АЛАН М. ТЬЮРИНГ (ALAN М. TURING) (1945)

ПРИЛОЖЕНИЕ А

ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ

Таблица 1

ВЕЛИЧИНЫ, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАММАХ И ПРИ АНАЛИЗЕ КОМПЬЮТЕРНЫХ ПРОГРАММ (40 ДЕСЯТИЧНЫХ ЗНАКОВ)

\/2 = 1.41421 35623 73095 04880 16887 24209 69807 85697-х/3 = 1.73205 08075 68877 29352 74463 41505 87236 69428+ х/5 = 2.23606 79774 99789 69640 91736 68731 27623 54406+ \Л0 = 3.16227 76601 68379 33199 88935 44432 71853 37196-\pi = 1.25992 10498 94873 16476 72106 07278 22835 05703- = 1.44224 95703 07408 38232 16383 10780 10958 83919- = 1.18920 71150 02721 06671 74999 70560 47591 52930-1п2 = 0.69314 71805 59945 30941 72321 21458 17656 80755+ 1пЗ = 1.09861 22886 68109 69139 52452 36922 52570 46475-1п 10 = 2.30258 50929 94045 68401 79914 54684 36420 76011+ 1/1п 2 = 1.44269 50408 88963 40735 99246 81001 89213 74266+ 1/1п 10 = 0.43429 44819 03251 82765 11289 18916 60508 22944-7г = 3.14159 26535 89793 23846 26433 83279 50288 41972-1° = 7Г/180 = 0.01745 32925 19943 29576 92369 07684 88612 71344+ 1/7Г = 0.31830 98861 83790 67153 77675 26745 02872 40689+ 7г = 9.86960 44010 89358 61883 44909 99876 15113 53137-v= Г(1/2) = 1.77245 38509 05516 02729 81674 83341 14518 27975+ Г(1/3) = 2.67893 85347 07747 63365 56929 40974 67764 41287-Г(2/3) = 1.35411 79394 26400 41694 52880 28154 51378 55193+ е = 2.71828 18284 59045 23536 02874 71352 66249 77572+ 1/е = 0.36787 94411 71442 32159 55237 70161 46086 74458+ = 7.38905 60989 30650 22723 04274 60575 00781 31803+ 7 = 0.57721 56649 01532 86060 65120 90082 40243 10422-1п7г = 1.14472 98858 49400 17414 34273 51353 05871 16473-ф = 1.61803 39887 49894 84820 45868 34365 63811 77203+ е> = 1.78107 24179 90197 98523 65041 03107 17954 91696+ е"/" = 2.19328 00507 38015 45655 97696 59278 73822 34616+ sinl =0.84147 09848 07896 50665 25023 21630 29899 96226-COS 1 = 0.54030 23058 68139 71740 09366 07442 97660 37323+ -С(2) = 0.93754 82543 15843 75370 25740 94567 86497 78979-С(3) = 1.20205 69031 59594 28539 97381 61511 44999 07650-1пф = 0.48121 18250 59603 44749 77589 13424 36842 31352-1/1п(А = 2.07808 69212 35027 53760 13226 06117 79576 77422--1п1п2 = 0.36651 29205 81664 32701 24391 58232 66946 94543-