AOP_Tom3 (1021738), страница 117
Текст из файла (страница 117)
630 г., книга Х), а в Согрив С!овввгу (ок. 725 г.) использовались только две первые буквы каждого слова, Эти две работы были, пожалуй, крупнейшими нечигловыми файлами данных, скомпилированными в средние века. Впервые описание алфавитного порядка появилось в Сасйо!!соп Джованни Генуэзского (Сютапп! с!! Сепоа'в) в 1286 году.
В предисловии поясняется, что ьзьо ас!ео предшествует предшествует предшествует предшествует предшествует предшествует ато аЬео ата!зм !тргиг(еив !гьв!!с!а ро!!в!и!Ьегоп атос гтриг!епв !ив!ив ройввеппв (т. е. приводятся примеры ситуаций, в которых порядок следования слов определяется первой, второй, ..., шестой буквами) Яи далее точно так же". Он отмечает, что для изобретения подобного способа упорядочения слов потребовались значительные усилия. ЯЯ прошу тебя, читатель, не презирать мой огромный труд и этот порядок, как нечто ничего не стоящее." Подробным изучением развития алфавитного порядка до начала книгопечатания занимался Ллойд В.
Дейли (! !оус! %'. Па!у) (Со!!ес!!оп Ъагоппм 90 (1967), 100 р.). ь Такая же систеиа была принята в Древней Руси: применялись алфавит и специальный символ ("гнело"), а также некоторые дополнительные обозначения для тысяч, миллионов и т. д. — Прим. перев. " Один из грамматиков древности; выходец из Александрии. **в Римский врач н естествоиспытатель, классик античной медицины. вввв Исидор Севильский — испанский епископ, выдаюгянйся ученый и писатель. Им найдено несколько интереснейших старинных рукописей, которые, несомненно, использовались в качестве черновых записей прн сортировке слов по первой букве (см. с.
89-90 его монографии). В первом словаре английского языка Роберта Коудри (НоЪег! Сазгбгеу) ТаЫе А!рЬаЬейса)! (Ьопбоп, 1604) содержатся следующие инструкции. Если слово, которое ты ищешь, начинается с "а", то нши его в начале, а если оно начинается с «ч", то ищи его в конце книги. Опять-таки, если слово начинается с "са", то искать его следует в начале буквы "с", а если с "си", то смотреть надлежит в конце этой буквы. И так поступай до конца слова.
Создается впечатление, что Коудрн сам учился своему методу расставления слов в алфавитном порядке в процессе работы — — на первых страницах словаря многие слова находятся не на своих местах, в то время как остальная часть словаря содержит гораздо меньше ошибок. Бинарный поиск был впервые упомянут Джоном Мочли (ЛоЬп МапсЬ!у) в, понгалуй, первой опубликованной дискуссии о нечисленных методах программирования ]Тйеогу апг! ТесЬшг!иеа Гог гйе Реэ!8п о1 Е!есгготс Прга! Сотригегв, ег)!ген Ьу С. 1Ч. Рас!егэоп, 1 (1946), 9.7-9.8; 3 (1946), 22.8 — 22.9].
Метод становится хорошо известным программистам, однако ни у кого не возник вопрос, как работать с Лг, не равным 2" — 1. ]См. А. Р. Воо!Ь, Ха!иге 176 (1955), 565; А. 1. Ритеу, Сотригегэ апс! Аиготайоп 5 (РесетЬег, 1956), 7 (здесь бинарный поиск назван так: "Двадцать вопросов"); Рап!е! Р. МсСгаскеп, Р78!га! Согпригег Рго8гагппиг18 (Ч'!!еу, 1957), 201 — 203; М. На1регп, САСМ 1, 1 (РеЬгпагу, 1958), 1 — 3.] Д. Г. Лехмер (Р. Н. ЬеЬтег), пожалуй, был первым, кто опубликовал алгоритм бинарного поиска, работающий при любых Л' (Ргос.
сутр. Арр!. Май. 10 (1960)„ 180-181]. Следующий шаг был сделан Г. Боттенбруком (Н. Во!!епЬгпсЬ), который представил интересный вариант алгоритма В, в котором отдельные проверки равенства отодвигаются в конец алгоритма ]ХА СМ 9 (1962), 214]. Используя ( < — !'(1+и)/2] вместо 1 г- '!(! + и)/2] на шаге В2, он устанавливает ! е- 1 прн К > К;; тогда и — ! уменьшается на каждом шаге. В конце, когда ! = и, мы имеем Кс < К < К! ы и можем проверить, является ли поиск успешным, при помощи еще одного сравнения (Боттенбрук полагал, что изначально К > К,).
Данная идея позволяет несколько ускорить внутренний цикл на многих компьютерах; этот же принцип мажет быть применен н к другим алгоритмам поиска, обсуждавшимся в этом разделе. Впрочем, успешный поиск потребует в среднем около одной дополнительной итерации в соответствии с (2) . Так как внутренний цикл выполняется примерно около !8 Лг раз, более быстрый цикл сможет компенсировать дополнительную итерацию только прн очень больших Л' (см. упр. 23). С другой стороны, алгоритм Боттенбрука будет находить крайнее справа вхождение ключа в таблицу, имеющую дубликаты; а это свойство алгоритма может оказаться важным для определенного класса задач. К. Ю. Айверсон (К.
Е. 1гегвоп) !А Ргойгатгшпб Ъзпйиа8е (ЪЪ'!!еу, 1962), 14Ц привел описание алгоритма В, однако не рассмотрел случай неудачного поиска. Д. Э. Кнут (Р. Е. КппгЬ) ]САСМ 6 (1963), 556-558] представил алгоритм В в качестве примера, использованного автоматической системой построения блок-схем. Однородный бинарный поиск (алгоритм С) был предложен автору А. К.
Чандрой (А. К. СЬапбга) из Станфордского университета в 1971 году. Поиск Фибоначчи изобретен Дэвидом Э. Фергюсоном (Пат1с[ Е. Регйпэоп) [САСМ 3 (1960), 648[. Бинарные деревья, подобные деревьям Фибоначчи, паявнлнсь в "пионерской" работе норвежского математика Акселя Тью (Ахе1 ТЬпе) еше в 1910 году (см. упр.
28). Деревья Фнбоначчи без меток появились также в качестве курьеза в популярной книге Хьюго Штейнгауза (Нпйо Бге1пЬацэ) МабйетаБса) БпарэЛогэ (Лгетг Уог)с 81есЬег1, 1938, с. 28). Они изображались корнем вниз н выглядели почти как настоящие деревья, с правыми ветвями, которые были в два раза длиннее левых (так что все листья находились на одном уровне) Интерполяционный поиск был предложен В. В.
Петерсоном (Ч~. %. Ре1егэоп) [1БМ з'. Веэ. Яг Ретей 1 (1957), 131 — 132), однако корректный анализ этого метода был сделан значительно позже (см. упр. 22). УПРАЖНЕНИЯ 1. [21[ Докажите, что если на шаге В2 бинарного поиска и с 1, то и = 1 — 1 и К„< К ( Кь (Полагаем, что Ко = — со и Кн.ы = +со, хотя эти искусственно введенные ключи в действительности алгоритмом не используются и не обязаны находиться в таблице.) 2. [ЯЯ[ Будет ли алгоритм В продолжать корректно работать при наличии Л в таблице, если мы: (а) установим на шаге В5 "1 +- ~'" вместо "1 з- 1+ 1"; (Ь) установим на шаге В4 "и +- Р вместо "и +- 1 — 1"; (с) внесем оба эти изменения? 3.
[151 Какой метод поиска соответствует дереву Каково среднее число сравнений выполняется при успешном и неудачном поиске? 4. [ЯО[ Если поиск с использованием программы 6.18 (последовательный поиск) выполняется ровно 638 единиц времени, то как долго будет работать программа В (бинарный поиск)? 5.
[МЯХ[ Для каких значений Л' программа В в среднем выполняется медленнее последовательного поиска (программа 6.16)') в случае успешного поиска? 6. [ЯЯ[ (К. Ю. Айверсон (К. Е. 1тешоп).) Упр. 5 приводит нэс к мысли, что отбит иметь некий гибридный метод, переходящий от бинарного поиска к последовательному при достаточном уменьшении интервала поиска. Напишите соответствующую программу для И1Х-компьютера и определите наилучший момент перемены метода поиска 7.
[МЯЯ[ Будет ли алгоритм П корректно работать, если мы изменим шаг Ш так, что а) и й и т установятси равными [Х/2); Ъ) и й и тп установятся равными [Ж/2)? [Указание. Предположите, что первый шаг был "Установить 1 < — О, ш +-?у (или Ж+ 1), перейти к шагу 114".[ 8. [МЯО[ Пусть б, = Вйьга Ц3 является 1'-и приращением в алгоритме С, как определено в (6). а) Чему равна сумма Ц ко~~ аз 5„? Ь) Чему равны минимальное и максимюъное значения й которые могут появитьси на шаге С2? 9.
[ЯО[ Существует ли значение Л > 1, при котором алгоритмы В и С в точности эквивалентны в том смысле, что они оба выполняют одну и ту же последовательность сравнений для всех аргументов поиска? 10. [21] Поясните, как написать йХХ-программу для алгоритма С, которая будет содержать около 718 Х инструкций и выполняться примерно за 4.5 18 М единиц времени. 11. [М25] Найдите формулы зависимости средних значений С1, С2 и А от Х и Я а частотном анализе программы С.
12. [80] Изобразите дерево бинарного поиска, соответствующее методу Шара при Х = 12. 13. [МЯ4] Протабулируйте средние значения количества сравнений и методе Шара для 1 < /9 < 16, рассматривая случаи как успешного, так и неудачного поиска. 14. [81] Поясните, как распространить алгоритм Р на нсе зяачения Х > 1. 15. [М19] Дли каких значений 1. дерево Фибоначчи порядка 1с определяет оптимальную процедуру поиска (имеется в виду наименыпее среднее количество выполняемых сравнений)2 16. [21] На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
