AOP_Tom3 (1021738), страница 110
Текст из файла (страница 110)
Второе доказательство. Заменим каждую вероятность р; на (21) р;(е)=р,+е' — (е'+с +. +е )/Х, где е — очень малое поломоительное число. При этом равенство х~р~(с) + + хор)г(е) = рэрг(с) + . + рмргя(«) справедливо только в том случае, когда х~ — — рэ, ..., хл = ум. Отсюда, в частности, следует, что в (20) равенство никогда не будет выполняться. Рассмотрим М! перестановок записей. Среди них есть, по меньшей мере, одна оптимальная, которая в соответствии с первой частью доказательства удовлетворяет условию (20). Однако поскольку теперь в условии (20) равенства невозможны, то н оптимальная перестановка может быть только одна.
Следовательно, условие (20) однозначно определяет некоторую оптимальную перестановку для вероятностей р;(е), причем е достаточно мало. Исходя из непрерывности тот же порядок должен быть оптимален н при е = О. (Такой тип доказательств нередко используется в комбинаторной оптимизации.) Теорема 5 была доказана В.
И. Смитом (%. Е. БписЬ) [Лага! ВезелгсЫ ох!эе!сэ )мнаггег(у 3 (1956), 59-66]. В приведенных ниже упражнениях содержатся дополнительные результаты оптимальной орпзннзацин файлов. УПРАЖНЕНИЯ 1. [М20[ Пусть все ключи поиска равновероятны. Определите стандартное среднеквадратичное отклонение числа сравнений прн успешном последовательном поиске в таблице с Х записями. 2. [15[ Измените алгоритм Б для использования связанных записей вместо индексов. (Если Р указывает на запись в таблице, полагаем, что КЕ1(Р) — ключ, 1КРО(Р) — связанная с ключом информация и 11кк(Р) указатель на следующую запись.
Полагаем также, что Р1КБТ указывает на первую запись, а последняя зались указывает на Л.) 3. [10) Напишите М11-программу для алгоритма иэ упр. 2, Чему равно время выполнения программы (с использованием С н 5 из (1))? 4. [17) Можно ли испольэовать идею алгоритма 1) длн таблиц в янлв связанных записей (см. упр. 2)? 5. (20) Программа 14' выполняется существенно быстрее программы О при больших значениях С. Существуют ли значения С н 5, при которых программа ч' будет выполняться дольше, чем программа ь)? б. [20) Добавьте три инструкции в программу Ч", которые поэваэят ей выполняться за время около (З.ЗЗС + сопэгапс) и.
7. [М20) Определите среднее число сравнений (3) н случае "бинарного" распределения вероятности (5). 8. [ВМ22) Найдите аснмптотическнй ряд для Н~*~ при н — > оо; х ф 1. 9. [ИМИ] В тексте отмечено, что распределения вероятностей, данные в (11), (13) и (16), приблизительно одинаковы нри О < о < 1 и чта среднее число сравнений с использованием (13) равно „в, Аг+ О(г1"' в). а) Означает ли зто, что число сравнений равно 37?гв + 0(дг ) при использовании в г — в распределения (11)? Ъ) Верно ли это утверждение дли распределения (16)? с) Сравните (11) и (16) с (13) при 9 < О.
10. [Мйд] Наилучшее расположение записей в последовательной таблице определиется условием (4). А чта горюй представляет наихудшее расположенггет Покажите, что имеется простое соотношение между средним количеством сравнений при наилучшем и наихудшем размещениях записей. 11. [МУО] Цель этого упражнения заключается в анализе предельного поведения самоорганизуюигегося файла при использовании эвристического метода перемещения записи в начала файла Сначала введем некоторые обозначения.
Пусть /„,(хг, хг,, х ) равно бесконечной сумме всех различных упорядоченных произведений хй х„... хсю тахих, что 1 < Н,, гь < ти, причем каждое хг, хз,..., х„, входит ва все произведения. Например, /г(х,у) = ~ (хььзу(х+у)" +у''х(х+у) ) = У ( + — ). гл>а Исходя из множества Х из и переменных (хг,..., х ), положим — Е 1 ('г ° = 1 — х.—. — х, г<гг« ° г < Р = ~~ /„,(хгг,...,хг ); г<гг«-.г' < Например, Раз = /з(хг, хг) + /з(хг,хз) + /г(хг,хз) и гэгзг = 1/(1 — хг — гг) + 1/(1 — хг— хз) + 1/(1 — хг — хз) По определению полагаем Р о = Цоо = 1.
а) Предположим, чта в самаорганизующийся файл запросы на поиск элемента й, поступают с вероятностью рь Покажите, что после достаточно длительной работы системы элемент /7, оказывается на т-м месте с предельной вероятностью р,Рсч гд,„ г„ где множество Х представляет собой (рг,...,р, г,р,ег,.,.,рл). Ъ) Суммируя результат (а) для т = 1, 2,..., получаем тождество Р + Рщ В+ + Р о = Г/ Получите отсюда следующие соотношения: + (и ™+1)Рщ О+ ..+ (и + )Р, гз С) ~ — ( )С2 <т-гг+ +( — 1) ( )гг о=Р с) Вычислите предельное среднее расстояние гв, = 2 >, гор,Рч г г записи 7?г от начала таблицы, затем вычислите СЯ = 2"," г Р ггг. 12. [Мйу] Используйте (17) дли вычисления среднего количества сравнений, необходимого для поиска в самоорганизуюнгеыся файле при бинарном распределении вероятностей ключей поиска (5).
13. [Мс?] Используя (17), вычислите Сл для распределения вероятностей (6). 14. [М31] Даны две последовательности действительных чисел — (х г, хг,..., х„) и (уг, ум ..., у„). Какая перестановка индексов ог аз... а„делает сумму 3 ', х,,у, максимальной, минимальной? ° 15. (Мйй] В тексте было показано, как оптимально расположить программы на ленте системной библиотехи для поиска только одной программы. Однако при работе с библиотекой подпрограмм, когда для работы программы пользователя необходимо загрузить различные подпрограммы, следует принять другой набор предположений.
В этом случае предположим, что запрос на подпрограмму 1 поступает с вероятностью Рм причем вызовы различных подпрограмм независимы. Тогда, например, вероятность того, что не потребуется ни одна подпрограмма, равна (1 — Р~)(! — Рз)... (1 — Рк), а вероитиость того, что поиск прекратится после загрузки 1'-й поДпрограммы, равна Ру (1— Р,э~) .. (1 — Рл). Если Ь~ — длина 1>й подпрограммы, то среднее время поиска будет пропорционально Ь! Р1 (1 — Рз) ..
(1 — Рл) + (Гч + Г г) Рг (! — Рз) .. (1 — Ря) + . + (Хо + " + Г и)Ри. Каким в этом случае должно быть оптимальное расположение подпрограмм на ленте? 16. [Мйй] (Г Ризель (Н. Н!еэе!).) Зачастую необходимо проверить, выполняются ли одновременно и, заданных условий. (Например, может понадобиться проверить, что х > 0 и у < г, и при этом не ясно, какое условие должно проверяться первым ) Предположим, что з проверка Его условия занимает Т, единиц времени и что условие выполняетси с вероятностью р„(причем эта вероятность не зависит от результатов выполнения других условий). В каком порядке должны выполняться проверки? 17. [М23] (В.
И. Смит (Ж. Е. Бш!сп).) Предположим, имеется и заданий; 1'-е задание занимает Т, единиц времени; крайний срок его выполнения — П,. Другими словами, 1>е задание должно быть выполнено не позже момента 121 . Какое расписание работ а~ аз... аь минимизирует макси.вольное запаздывание, т е. 10. [Муй] (Сцепленный поиск.) Предположим, что Х записей расположены в памяти в виде линейного массива Лю .. 2?я и вероятность поиска записи Е, равна р,. Поиск называется "сцепленным", если каждый последующий поиск начинается с того места, где завершился предыдущий.
Если последовательные поиски независимы, то среднее время поиска составляет 2 р рзй(цб), где Н(йу) — время, которое необходимо для поиска, гй о<я начинающегося в позиции ! и заканчивающегося в позиции 1 Эта модель может быть применима, например, ко времени поиска дискового файла (при этом Ы(1, !) представляет собой время перемещения между 1- и 1>м цилиндрами диска) Цель данного упражнения — описать оптнмютьное размещение записей для сцепленного поиска в случае, когда <111, 1) представляет собой монотонно возрастающую функцию от [! — 1], т.е 4(ьй) = г?О,! и 4 < А « ..
бк-~ (величина оо не существенна). Докажите, что размещение будет оптимально тогда и только тогда, когда будет выполняться условие либо р~ < ри < рг < ря-~ < < р,яг„!эч, либо рл < р~ < ря-~ < рз < < р!л?з!. (Другими словами, наилучшее расположение — в виде 'органных труб', показанных на рис. 2 ) Указание. Рассмотрите расположение, которому соответствуют вероятности д~ дг...
дь в гь... ге г~ 1~ .. Г,„для нехаторых т > О и и > 0;?д = 2)г+ т+ 1. Покажите, что расположение д', д~ .. д[ э гь... г] г', гю .. Г лучше, если д; = гпш (до г;) и г[ = шах (д„г,), за исключением случая, когда д] = д, и г[ = г, для всех и и случая д, = г;, г[ = д, и Гз = О для всех ! из. То же самое справедливо при отсутствии э и?д = 2й+ пь 19. [МЯ0] Продолжая выполнять упр. 18, найдите оптимальное расположение для сцепленного поиска, если функция Ы(01) обладает слелующим свойством г?(01) + Ы(1',1) = с длн всех 1 Р 1'.
(Такая ситуация возможна, например, при поиске на ленте без возможности обратной перемотки и с неизвестным нам направлением поиска; для ! < 1' имеем И(цу) = Рт Рэ Рис. 2. Расположение в виде "органных труб" минимизирует среднее время сцепленного поиска. а+Ь(Т +1+..
+?с) и й(1 1) = а+Ь(?141+ +Тн)+г+Ь(Тн -~- .. +Л), где т — времи перемотки.) 20. [М28) Продолжая выполнять упр. 18, найдите оптимальное расположение лля сцепленного поиска в случае, когда й(1, 1) = ш1п(ОЬ з„й„р д) и А < бе < (Эта ситуация встречается, например, в двусвязном циклическом списке или в запоминающем устройстве с возможностью перемещения в обе стороны.) 21. (Ма8) Рассмотрим и-мерный куб с координатами вершин (ои, и'„), где Н~ — — 0 или 1; две вершины называются соседними, если оии различаются только одной координатой. Предположим, что набор из 2" чисел то < х1 « тэ 1 должен быть сапоставлен 2" вершинам таким образом, чтобы минимизировать сумму 2 ~я; — х~(; сумма берется по всем 1 и 1, таким, что щ и та сопоставлены соседним вершинам.
Докажите, что этот минимул~ достигается тогда, когда для всех 1 х, сопоставлено вершине, координаты которой являются двоичным представлением числа 1. ь 22. (00) Предположим, что в большом файле вам необходимо найти 1 000 ближайших к данному ключу записей, т. е. записей, для которых функция расстояния Ы(Л~, К) принимает наименьшие значения. Какая структура данных будет самой подходящей для такого последовательного поиска? Пытайся до конца, сомнений поочь оскал, И, все преодолев, найдеш~ ты, что искала. — РОБЕРТ ХЕРРИК (РОВЕРТ НЕРЕПСК), ищите н обРящете (5ееке апп бпбе) (1648) * Перевод Светланы Трнгуб. ГЛАВА 5 СОРТИРОВКА Нет дела, коего устройство было бы труднее, ведение опаснее, а успех сомнительнее, нежели замена старых пооядков новыми.
— НИККОЛО МАКИАВЕЛЛИ, Государь (1513) "Но мы не успеем просмотреть все номера автомобилей", — возразил Дрейгг. "А нам и не нужно этого делать, Поп. Мы просто расположим их пО пОрядку и поищем одинаковые." — ПЕРРИ МЕЙСОН, Иэ Тле Сазе от Гле Апдгу Моцгпег (1951) компьютер "тгеезогг": при новом "компьютерном подходе" К ИЗУЧЕНИЮ ПРИРОДЫ ВЫ прпучитЕ ВОЗмвжНОСть быстро распознавать более збп видов деРевьЕВ США, Аляски и Канады, включая пальмы, растительность пустынь и прочую "экзотикуе Чтобы определить породу дерева, достаточно просто вставить спицу.
— каталог ебптцпо бсгепвггс согпрапу (1964) В этой главе мы изучим вопрос, который часто возникает в программировании: переразмещение элементов в порядке возрастания или убывания. Представьте, насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти компьютера, во многом зависит скорость выполнения и простота алгоритмов, предназначенных для их обработки. Хотя в словарях слово "сортировка" (вогсгпй) определяется как процесс разделения объектов по виду или сорту, программисты традиционно используют его в гораздо более узком смысле, обозначая им такую перестановку предметов, прн которой они располагаются в порядке возрастания или убывания.
Такой процесс, пожалуй, следовало бы назвать не сортировкой, а упорядочением (огдег)пй), но использование этого слова привело бы к путанице из-за перегруженности значениями слова "порядок'! Рассмотрим, например, следующее предложение: чТак как только два из имеющихся у нас лентопротяжных механизмов в порядке, меня призвали к порядку и обязали в срочном порядке заказать еще несколько устройств„чтобы можно было упорядочивать данные разного порядка на несколько порядков быстрее".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
