Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 54
Текст из файла (страница 54)
Каково максимальное числа объектов с одинаковым значенисч первичного адреса расстановки? Можете провести этв вычисления на ЭВМ. Саммет [1969] дает необходимые наборы ключевых слов. "10.1.7. Покажите, что функция )?(й, л) для случайной расстановки приблизительно равна ( — 1?р)!Ой(1 †), где р = й?л. Начертите график этой функцин. Указан»ге: Аппраксимируйте (л?й) ~ (л+1)?(гг — 1-1-!) интегралом, =Р *10.1.8. Рассмотрим следуюгций генератор псевдослучайных чисел. Этот генератор вырабатывает последовательность го г„, .. , г, чисел, которые можно использовать для вычисления й (ц)=[)г»(О) ь г]!вобл при 1щ(-..л — 1. Каждый раэ, когда должна генери!юваться последовательность чисел, целому )? прясваи- вается значение 1.
Предполагается, что л = 2». Для того чтобы получить очередное число, надо выполнить такис шаги: (1) ??=5Р )?, (2) )?=-)? люб 4л, (3) выдать в качестве заачепия г =-[)??4]. Покажите, что для любого г все разности г,„„— »»для й) 1 и (-! Й С и — ! различны. **10.1.9. Покажите, что если й; = [8, + ар+ Ь)]шоб л для !< !<Π— 1, то различны не более половины позиций в после- довательности й,, йи й„..,, Й„Р При каком условии в этой по. следовательности будет в точности половина различных позиций? эва **10.1ЛО. Каково число различных позиций в последовательности й„ йо ..., й„ „ если для 1 ( 1 (р/2 йн,=-[/г,+О] шоб р йн=й» [( з ?+1~ шо" Р и р — простое числоз Определение.
Метадон разрешения конфликтов, более аффективных~ (чем описанный в равд. 10.1.4) с точки зрения внесения и поиска, является м»лад цепочек, В этом методе каждый элемент таблицы расстановки имеет дополнительное поле, содержащее указатель на дополнительные элементы с тем же, как у него самого, первичным адресом. Все элементы с одинаковым первичныьг адресом соединены и последовательный список, начиная с этой первичной позиции. Существует несколько способов реализации метода цепочек.
В одном из них, называемом прлныл методом цепочек, для хранения всех объектов используется сама таблица расстановки. Для того чтобы внести объект О, провернется позиции й,(О). (1) Если эта повинна пусга, ц помещается в пей. Если она занята и с нее начинается цепочка, находим некоторым подха. дящим способом пустой элемент таблицы расстановки и помещаем его в цепочку, начинающуюся с й,(и). (2) Если позиция Й,(и) заняга, но не началом цепочки, то перемещаем текущий элемент б, находящийся в ЙДО), в пустую позицию таблипы расстановки и ниосим и в й,(а).
(При этом надо заново вычислить Й(5), чтобы хранигь б в соответствующей цепочке,) Это перемещение элементов составляет главный недостаток прямого метода цепочек. Тем не менее метод даяольно быстр. Другое его достоинство в точ, чта в переполненную таблицу с помопгыо той же стратегии внесения и поиска иожно поместить дополнительные объенты. 10.1.11. Покажите, что если вторичные позиции выбираются случайно, та Ожидаемое время повска ??(й, О) для прямого метода цепочек равно 1+р?2, где р = й?л. Сравните эту функцию с )((й, л) в упр. !0.1.7. В другом методе цепочек, пе требующем перемещения объектов, перед таблицей расстановки применяется таблица индексов. Первичная функция расстановки Й, вычисляет адрес в таблице индексов. Элементами таблицы индексов служат уиазатели на таблицу расстановки, элементы которой заполняется по порядку.
Для !ого чтобы при этой схеме внес~и объект ц, вычнслвется й,(а), г. е, адрес в таблице индексов. Если позиция ЙА(и) пуста, га А.ААР,Д, У,т,а гл 1О арглнизАцня информации занимаем очередную доступную познг[ию в таблице расстановки и вносим в иее и. Указатель на эту позицию размещаем затем в й,(я). Если )г,(и) уже содержит укааатель на позицию в таблице расстановки, обращаемся в зту позицию. Затем просматриваем иа. чинающуюся с нее цепочку. Дастигвув конца пепочки, выбираем очередную доступную позипию в таблице расстановки, вносим в нес и и присоединяем эту позицию к концу цепочки. Если таблица расстановки заполняется сверх) вниз, то очередную доступную позицию можно найти очень быстро. В этой схеме нет необходимости перемешать объекты, поскольку каждый злеменг таблицы иидексоз всегда указывает иа начало цепочки. Кроме того, легко обрабатывать переполнения, добавляя место к концу таблицы расстановки.
'10.1.12. Каково ожидаемое время поиска объекта для метода цепочек с таблицей иидексову Считайте, что первичные позиции распределены равномерно. 10.1.13. Рассмотрвм систему случайной расстановки с а пазициями, как в равд, 10.1.6. Покажите, что если множество 5 состоит из й позиций и !25, ю ~р(ю!).=-1!(л — й), где сумма берется по всем цепочкам ю из й или менее различных позиций в 5. *10.1.14.
Докажите тождества (гг+!) (гг+й+!) ~.= а ~' (гг — г) (лт)) ~~+ !) ~п —,йб — !) (л+й+1) *10.1.10. Предположим, что объектами авля!отса цепочки длнвы от одной до шести латинских букв. Пусть СОВŠ— функция, онрелелениая в примере 10.4, а объекг и имеет вероятность (1)б) 20- ~ ч 1. Вычислите верая гности перестановок множества (О, 1, ..., л — 1), если (а) йг(и) =(СО1)Е(и)+г) пзоб л, О<!(и — 1, (б) йг(и) = (г(й,(и) — , '1)) щог)л, ! (г' " а — 1, где й„(и) = СОВЕ (я) !пой л. **10.1.10.
Покажите, что для линейной расстановки со случайно распределенной первнчвой познцией ~(и) предел ф»нк- УПРАЖНЕНИЯ ции Е(й, л) при й и и, стремящихся к са, и й)л р равен 1.1-[р(! — р/2)г(! — р)'). Как зто соотносится с соответствующей функцией от р Лля случайной расстановкиу Определение. Систему расстановки назовем й-розиомерноп, если для .тюбого множества 5 щ (О, 1, 2, ..., и†1), состоящего из й элементов, вероятность того, что последовательность из й различных позиций образована в точности позипиями из 5, улу равна !)1 ) (наиболее существенна здесь то, что вероятность не зависит от 5).
*10.1.!7. Покажите, что если система расстановки й-равномерна, то, как и для случайной расстановки, Е(й, л] = (а+ 1)1(л+ 1 — й) *!0,1.18. Покажите, что для любой системы расстановки, для которой существует такое чясло й, что Е(й, п)ц < (л ф1)1(пт! — й), сущеигвует такое й' < й, что Е(й', п) > (и 0 1)7(п -1-1 — й') Таким образом, есле для некоторого й данная система расстановки лучше случайной, то существует меньшее число й', для когорого эта система хуже случайной. Указали: Покажите, что если система расстановки (й — 1]-равномерна, но не й.равномерна, то Е(й, л) > (и+1)((л — й+1).
*!0.1.19. Приведите пример системы расстановки, й-равномерной для любого й, но не случайной. *10.1,20. Обобщите пример 10.7 иа случай неравных вероятностей для циклических перестановок. *10.1.21. Усильте теорему 10.2 с тем, чтобы включить системы, осуществляющие расстановку по позициям, на имеющие неравные вероятности ре Ощкрытые проблемы 10.1.22. Оптвмальна ля в смысло ожидаемого времени поиска объекта случайная расстановка.
Другими словами, верно ли, чта функция Й(й, и) всегда ограничена снизу величиной (1(й) Х (гг+1йп-)-1 — г) ю=з Мы думаем, что случайная расстановка оптимальна. 10.1.23. Найдите наибольшую нижню~о границу функции Е(й, л) для систем, осуществляющих расстановку по позициям $0' зэ1 гл, >л оеглнивм>ня ннаогмэции Любая нижняя граница, превышающая (о+ 1)7(л 1-1 — й), пРедставляет иатерес. 10.!.24. НайдитеианболыпуюнижнююграницуфункцинЕ(й,л) для произвольной систеыы расстанонки. В прил>ере 10.8 чы видели, гюо (и+1)7(л+1--й) такой границей не является. Проблема для исследования !0.1.25.
В некоторых применениях таблиц расстаноики вводимые объскгы известны заранее. Примерами служат библиотеки стандартных подпрограмм и.ти таблипы кодов операций языка ассемблера. Если известно, что именно размещается з таблице расстановки, то можно Выбрать систему расстановки так, чтобы минимизировать ожидаемое время просмогра. Ма>кете лн Вы привести алгоритм, который принимает на Вход список объектов, подлежащих запоминанию, и выдает систему расстановки, эффективно реализуемую и трсбующую мало времени прн поиске для этой конкретной вагрузки таблицы расстановки? Упражнения яо прогроммировпние 10.1.28. Запрограммируйте систему расстановки, осущестз. ляющую расстановку по позициям. Проверьте позедение системы на ключевых словах Фортрана и общеупотребительных именах функций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
