AOP_Tom3 (1021738), страница 148
Текст из файла (страница 148)
Камазов т-битовое бинарное число будет в таком случае соответствовать в точности одной строке. Например, (13) является АВП(4, 3). а) Докажите, что АВП(т, и) невозможна, кроме случаев, когда гл является делителем 2' 'и и пг > 2т(1 — 2 "). Ь) Будем говорить, чта строка АВП имеет нечетный паршпегп, если в ней содержится нечетное количество единиц. Покажите, что для любого выбора т — и столбцов в АВП(т, п) количество строк с нечетным паритетом с "*" в этих столбцах равна количеству строк с четным паритетом. В частности, каждое возможное расположение символов "*" должно встречаться в четном количестве строк. От Аз»ос»обое В!ое» Оезьзпз, — Прим. перев. с) Найдите АВВ(4, 3), которое не мажет быть получено из (13) путем перестановки и?или дополнения столбцов. 6) Постройте АВВ(16,9).
е) Постройте АВВ(16, 10). Начните с АВВ(16,9) из п. (4) вместо АВВ(8,5) из (15). 19. (М22) Проанализируйте АВВ(8,5) из (15) так же, как (13) было проанализировано в (14). Сколько из 32 позиций должно быть проверено при запросе с к неопределенными битами и среднем и в наихудшем случаях? 20. [ЛЦ?] Найдите все АВВ(гп,п) при и = 5 или и = 6. Ф Новый раздел 6.6 в следующем издании книги планируется посвятить постоянным структурамданных. Эти структуры позволяют представить измененную информацию таким образом, что история изменений может быть эффективно восстановлена.
Иными гдовами, можно сделать множество вставок н удалений, но, тем не менее, оставаться способными выполнить поиск тац как будто обновлений после некоторого данного момента времени вовсе не было. Пока что в настоящее издание включены лишь ссылки на литературу по этой теме: ° Ь К. Майш, Сотр. Х 24 (1981), 367-373; ° М. Н.
Очегшагв, Ьессиге Жосеэ !и Сошр. Яс!. 156 (1983), СЬар!ег 9; ° Е. ЪЪ". Муегв, АСМ сутр. Рг!пс!р?еэ аГ Ргоб. Ьапб, 11 (1984), 66 — ?5; ° В. СЬахе!!е, 1л1огшае!оп апг! Сол!го! 63 (1985), 77-99; ° В. ВоЬЫп апб !. 1. Монга, Х А!бопНнпв 6 (1985), 455 — 465; ° В. Со!е, .!. А!8огйбтэ 7 (1986), 202 — 220; ° В. Е!е!0, 1п1огтабол Ргосеэмлб Ьеесегэ 24 (1987), 95 — 96; ° С.
гг'. Ггаэег апй Е. 55г. Муегэ, АС51 Т?алэ, Ргой. Ьалб, апг! Бувеешв 9 (1987), 277 — 295; ° Л. В. ВПзса!1, 58 лагоа)г, В. В. Я!еасог, апг! Е. Е. Тат!ап, Х Онпр. Яуяа Ясб 38 (1989), 86 — 124; ° В. В. ВаппепЬегб, Яоуснаге Ргасбсе 3г Ехрепелсс 20 (1990), 109-132; ° 3. В. ВНэсой, В. В. К. 8!еасаг, апб В. Е. Тат!ап, 1АС51 41 (1994), 943"959. 7аблицы инстоукций (программы! будут создаваться матеиатиками с опытои вычислительной работы и, вероятно, с определенными способностяии к оешению головоломок. перевод на некоторой стадии каждого известного процесса в фоому таблиц инструкций, скорее всего, будет значительной частью такой оаботы. Процесс постооения таблиц инструкций должен очаРовывать.
Реальной опасности стать слугой машины нет, ибо любой более или менее механический процесс можно передать самой машине. — АЛАН ЭЛ. ТЬЮРИНГ (АЦАН ЬЛ. Т!Зггцхб) (1945) 6.4. ХЕШИРОВАНИЕ До сих пор мы рдссмдтривдлк методы поиска, основанные на сравнении данного аргумента К с ключами в таблице или на использовании его цифр для управления процессом разветвления. Третий путь заключается в том, чтобы отказаться от поиска по данным и выполнить арифметические действия над К, позволяющие вычислить некоторую функцию 7'(К).
Последняя укажет адрес в таблице, где хранится К и связанная с ннм информации. Например, рассмотрим хорошо известное нам множество из 31 английского слова, которое приводилось в разделах 6.2.2 и 6.3. В табл. 1 показана небольшая й1Х-програмьга, взаимно однозначно преобразующая 31 ключ в числа 7'(К) между — 10 и 30.
Если сравнить этот метод с !41Х-програьгмами для других рассматривавшихся методов (наприьгер, для бинарност) поиска, оптимального поиска по дереву, "лучевого" поиска, цифрового поиска по дереву), то можно обнаружить, что новый способ превосходит старые как с точки зрения быстродействия, так и с точки зрения количества используемой памяти (за исключением бинарного поиска, для которого необходим несколько меньший обьем памяти).
В самом деле, среднее время успешного поиска с помощью программы нз табл. 1 составляет около 17.8п н требует для хранения 31 ключа таблицу из 41 элемента. К сожалению, поиск таких функций 7(К) — довольно сложная задача. Имеется 41си = 10е" возможных функций, отсбражающих 31-элементное множество в 41-элементное; однако только 41 40 .... 11 = 41!С'1О! — 10"з из них дают различные значения для различных аргументов; следовательно, только одна из десяти миллионов функций подходит для достижения нашей цели. Функции, дающие неповторяющнеся значения, встречаются на удивление редко (даже для больших таблиц).
Например, в соответствии со знаменитым "парадоксом дней рождения" получается, что в компании из 23 человек более вероятяо совпадение дней рождения у двух из них, чем то, что у всех дни рождения окажутся различными. Иными словами, если выбрать случайную функцию, отображающую 23 ключа в таблицу размером 365, вероятность того, что никакие два ключа не будут отображены в одно и то же место таблицы, составляет 0.4927, т.
е. менее половины. Скептики могут проверить сгарцдокс на ближайшей многолюдной вечеринке*. (Парадокс дней рождения неформально обсуждался математиками в 30-е годы; происхождение этого парадокса неизвестно. См. 1. 3. Сепг!, РгоЬаЬг!Ыу апс! сЛе МегйЛ!ий ог" Еч!г1епсе (Ог!йсг, 1950), 38, а также В, чоп М!лев, 1агаиЬи! Ёп!четяСеэ! Реи Ра!гй!сел! Меспгиав' 4 (1939), 145-163; %. Ге!!ег, Ап 1исгог)исс!огс со РгоЬаЬЕйсу ТЛеогу (Хечг 'г'ог!с: %!!еу, 1950). Весйои 2.3.) С другой стороны, использованный в табл. 1 подход весьма гибок [см.
М. Огеи!едче!г! апг! %. Тисе!г1, САСА! 6 (1963), 322 — 323), и для таблиц небольшого размера подходящая функция может быть найдена за день-другой. Решать такого рода головоломки весьма занятно! Вопросы поиска подходящих функций рассматривались многими исгледователямн, включая, например, В. Вргийпо!1, САСМ 20 (1977), 841 850, 22 (1979), 104, 553; В..!. СкЬе!1с, САСМ 23 (1980), 17-.19; Т. 3.
Байег, САСМ 28 (1985), 523 — 532, 29 (1986), 557; В. 8. Ма)еччв!и', К. С. гтчогшаЫ, 6. Начав ' Любители математики могут обратиться эа подробностямн, напрнмер, к книге У. Болла н Г. Коксетера Математнческне лесе н раэвлеченнл (ХК Мнр, 1996. — 474 с.). Скептикам-нелюдимам рекомендуется вепамннть свой класс в школе нля группу в институте. — Прим. нерее.
Таблица 1 ВЗАИМНО ОДНОЗНАЧНОЕ ПРЕОВРАЗОВАНИЕ МНОЖЕСТВА КЛЮЧЕЙ В АДРЕСА Я М ш н ы 'ш ь эз м сэ а я в м ш ш ш и. ш ш ш й ш — 1 — 1 6 6 -2 -2 -6 -2 -2 — 6 14 18 2 14 18 2 14 18 2 14 18 2 9 . — 7 9 . — 7 23 23 23 3 13 14 16 3 13 14 16 3 13 14 16 9 18 23 9 18 23 9 18 23 7 — 3 7 -3 7 -3 аиб Е. Х СхесЬ, Солар. Х 39 (1996), 547 — 554; СгесЬ, Натая, апт( Ма)етиаЫ, ТБеогебса! Сатир. Яса'. 182 11997), 1 — 143. См.
также статью 3. Кбгпег апг) К. Матсов, Епгор. Х СоптЬша(олсз 9 (1988), 523 — 530, о теоретических ограничениях идеальных хешфункций. Конечно, этот метод имеет очень существенный недостаток, заключающийся в том, что содержимое таблицы должно быть заранее известна. Добавив всего один ключ, можно все испортить, и придется начинать всю работу с нуля. Впрочем, можно получить гораздо более гибкий метод, отбрасывая требование однозначности и используя гпециальные методы разрешения возникающих неоднозначных ситуаций после вычисления 7'(К).
Итак, мы вплотную приблизились к популярному классу методов поиска с общим названием хеширование (ЬавИтпу) или рассеяннал паяытть (вса((ег в1огауе). Глагол "со ЬазЬя означает "крошить, рубить и делать из этого месиво" в. Идея хеширования состоит в использовании некоторой частичной информации, полученной из ключа, в качестве основы поиска. Мы вычисляем хеш-адрес Ь(К) и используем его для проведения поиска. Парадокс дней рождения предостерегает нас, что, вероятно, найдутся различные ключи К; ф Кзч имеющие одинаковое значение хеш-функции Ь(Кэ) = Ь(К)). Такое событие именуется коллизией (сойтлэоп); для разрешения коллизий разработаны некоторые интересные подходы.
Для использования хеширования программист должен решить две практически независимые задачи - — выбрать хеш-функцию В связи с этим был очень велик соблазн нслользоаать для термина хеширование русское слово окрошка. — Прим. перев. Команда Е018 К(1:1) Е02 К(2:2) 1ИС1 -8,2 21Р а+2 1ИС1 16,2 Е02 К(З,З) )22 9Г ХИС1 -28,2 )1Р 9Г 1ИС1 11,2 ЕВА К(Я:4) )АК 9Г 0ЕС1 -5,2 э'1И 9Г 1ИС1 10 98 1.0А К СНРА ТА81Е, 1 зИЕ ГА1ьНЕЕ -1 — 1 -9 -9 7 7 б 7 6 — 18 -18 — 3 -3 -3 -1 -1 — 1 -2 -1 -1 — 1 — 2 10 13 14 -5 10 13 14 -5 16 10 13 14 16 10 13 14 16 — 13 — 13 3 3 3 -6 -8 — 6 — 8 5 — 15 5 — 15 2 5 2 5 2 — 7 — 22 — 7 — 22 20 -7 20 — 7 20 -7 9 9 19 19 — 7 19 — 7 19 -7 -8 -8 -8 — 8 — 8 -8 -15 -11 -11 -15 -11 -11 2 10 10 2 10 10 2 10 10 — 1 .
-1 -1 . -1 35 35 35 15 15 25 25 25 25 и и м а и а н а м ъ $ и лъ л~ ы ы ы ж а $ ФР ь ж ы ю ля ж ы н н ы ж а а а ~ л л ключом К после выполнения каманлы — 16 — 16 -9 -9 22 22 22 — 8 -9 -8 -9 — 7 — 17 — 7 — 1? 18 -1 18 -1 18 — 1 12 12 ЗО -10 30 -10 30 -10 29 5 6 20 4 29 5 6 20 4 29 5 6 20 4 22 22 22 -6 -2 -6 -2 — 6 — 2 17 11 -5 17 11 -5 17 11 -5 12 -1 12 -1 12 -1 Ь(К) и способ разрешения коллизий. В этом разделе будут рассмотрены обе эти задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
