Структуры данных и алгоритмы (1021739), страница 81
Текст из файла (страница 81)
а) перепишите программу вычисления вероятностей, показанную в листинге 10.2, если вероятность выигрыша первой командой любой игрыравняется р;б) если первая команда выиграла один матч, а вторая — два, и вероятностьвыигрыша 1-й командой любой игры равна 0,6, то у какой из командбольше шансов выиграть весь турнир?10.8. Программе вычисления вероятностей (листинг 10.2) требуется объем памятипорядка О(п2). Перепишите эту программу так, чтобы ей требовалось толькоО(п) объема памяти.*10.9. Докажите, что вычисление решения уравнения (10.4) требует ровно 2С' -1вычислений различных значений Р.10.10. Найдите минимальную триангуляцию для правильного восьмиугольника впредположении, что расстояния вычисляются как евклидовые расстояния.308ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВ10.11. Задачу разбиения на абзацы в простейшей форме можно сформулировать следующим образом.
Дана последовательность слов ш1( и>2, ... , wk длиной llt 12, ... ,I/,, которые нужно разбить на строки длиной L. Слова разделяются пробелами,стандартная ширина которых равна Ь, но пробелы при необходимости могутудлиняться или сжиматься (но без "наползания" слов друг на друга) так, чтобы длина строки wt и>м ... wt равнялась в точности L. Однако штрафом за такое удлинение или сжатие пробелов является общая величина, на которуюпробелы удлиняются или сжимаются, т.е. стоимость формирования строкиWj wi+1 ... Wj при j > i равна (j - i) b' - b\, где b' — фактическая ширина пробелов, равная (L - /j - 1M - ...
- lj)/(f - i). При j = k (речь идет о последней строке) эта стоимость равна нулю, если только Ь' не окажется меньше Ь, посколькупоследнюю строку растягивать не требуется. На основе метода динамическогопрограммирования разработайте алгоритм для разделения с наименьшей стоимостью последовательности слов wlt и>2, ... , wk на строки длиной L. Совет.Для i = k, k - 1, ... , 1 вычислите наименьшую стоимость формирования строкwit wi+1, ...
, wk.10.12. Допустим, есть п элементов xlt x2, ... , хп, связанных линейным порядкомxl < хг < ... < х„, которое нужно представить в виде двоичного дерева поиска.Обозначим р, вероятность запроса на поиск элемента х(. Тогда для любого заданного двоичного дерева поиска средняя стоимость поиска составит»2_,pt(dt +1), где di — глубина узла, содержащего #г. При условии, что заданыi=iвсе вероятности pt, и предполагая, что xt никогда не изменяются, можно построить двоичное дерево поиска, минимизирующее стоимость поиска. На основе метода динамического программирования разработайте алгоритм, реализующий такое двоичное дерево поиска. Каким будет время выполнения алгоритма? Совет. Вычислите для всех i я j оптимальную стоимость поиска средивсех деревьев, содержащих только элементы xit xi+i, ...
, xi+j-i, т.е. всего / элементов, начиная с xt.**10.13.Для монет какого достоинства "жадный" алгоритм, описанный в разделе 10.3,обеспечивает оптимальное решение выдачи сдачи?10.14. Составьте рекурсивный алгоритм триангуляции, обсуждавшийся в разделе 10.2. Покажите, что результатом выполнения этого рекурсивного алгоритмабудут ровно 3S~4 вызовов в случае нетривиальных задач, если начать с задачиразмером s > 4.10.15.Опишите "жадный" алгоритм дляа) задачи одномерного размещения блоков;б) задачи разбиения на абзацы (упражнение 10.11).Приведите пример, когда алгоритм не обеспечивает оптимального решения,или покажите, что таких случаев вообще не может быть.10.16. Постройте нерекурсивную версию алгоритма просмотра дерева, представленного в листинге 10.3.10.17.Рассмотрим дерево игры, в котором используются шесть шариков и игроки 1 и2 выбирают по очереди от одного до трех шариков.
Игрок, взявший последнийшарик, считается проигравшим.а) составьте полное дерево этой игры;б) если это дерево игры просматривать с помощью метода альфа-бета отсечений, а узлы, представляющие конфигурации с наименьшим количествомшариков, просматривать первыми, какие узлы будут отсечены?в) кто выиграет, если оба игрока будут действовать оптимальным образом?УПРАЖНЕНИЯ309*10.18.
Разработайте алгоритм ветвей и границ для задачи коммивояжера, взяв за основу идею, что маршрут должен начинаться с вершины 1 и ответвляться накаждом уровне, исходя из того, какой узел должен быть в этом маршруте следующим (а не из того, какое конкретное ребро выбрано на рис. 10.17). Чтоможет служить подходящим критерием оценки нижней границы для конфигураций, которые являются списками вершин 1, i;lt i>2, — » определяющих начало маршрутов? Как будет вести себя .алгоритм применительно к графу изрис.
10.16, если предположить, что вершина а является вершиной 1?* 10.19. Возможным вариантом алгоритма локального поиска для задачи разбиения наабзацы является применение локальных преобразований, которые перемещаютпервое слово одной строки на предыдущую строку или последнее слова строки — на последующую. Будет ли в этом случае каждое локально-оптимальноерешение являться глобально-оптимальным?10.20. Если локальные преобразования состоят лишь из двойных выборов, есть лидля графа из рис.
10.16 какие-либо локально-оптимальные маршруты, которые не являются глобально-оптимальными?Библиографические примечанияСуществует множество приложений алгоритмов декомпозиции, включая быстроепреобразование Фурье с временем выполнения O(n\ogn), описанное в [21], алгоритмумножения целых чисел с временем выполнения О(п lognloglogn), описанный в [96],и алгоритм умножения матриц с временем О(п2'81), рассмотренный в [104]. Алгоритмумножения целых чисел с временем выполнения О(и1>59) описан в работе [59].
В статье [76] представлено несколько эффективных алгоритмов декомпозиции для модулярной арифметики, а также для полиномиальной интерполяции и оценивания.С популярным изложением динамического программирования можно ознакомитьсяв [7]. Применение динамического программирования к триангуляции изложено в [40].Упражнение 10.11 заимствовано из [66]. В [64] содержится решение задачи построения оптимального дерева двоичного поиска (см. упражнение 10.12).В [68] описан эффективный эвристический алгоритм для задачи коммивояжера.Обсуждение NP-полных и других задач, сложных с вычислительной точки зрения, можно найти в монографии [3], а также в работе [41].310ГЛАВА 10.
МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВГЛАВА 11"Структурыданных иалгоритмыдля внешнейпамятиМы начинаем эту главу с обсуждения различий в характеристиках доступа к устройствам основной (оперативной) и внешней памяти (например, дисководов).
Затемпредставим несколько алгоритмов сортировки файлов данных, хранящихся на устройствах внешней памяти. Завершается глава обсуждением структур данных и алгоритмов, таких как индексированные файлы и В-деревья, которые хорошо подходятдля хранения и поиска информации на вторичных устройствах памяти.11.1. Модель внешних вычисленийВ алгоритмах, которые мы обсуждали до сих пор, предполагалось, что объемвходных данных позволяет обходиться исключительно основной (оперативной) памятью. Но как быть, если нам нужно, например, отсортировать всех государственныхслужащих по продолжительности их рабочего стажа или хранить информацию изналоговых деклараций всех граждан страны? Когда возникает необходимость решатьподобные задачи, объем обрабатываемых данных намного превышает возможностиосновной памяти.
В большинстве компьютерных систем предусмотрены устройствавнешней памяти, такие как жесткие диски, или запоминающие устройства большойемкости, на которых можно хранить огромные объемы данных. Однако характеристики доступа к таким устройствам внешней памяти существенно отличаются от характеристик доступа к основной памяти.
Чтобы повысить эффективность использования этих устройств, был разработан ряд структур данных и алгоритмов. В этойглаве мы обсудим структуры данных и алгоритмы для сортировки и поиска информации, хранящейся на вторичных устройствах памяти.В Pascal и некоторых других языках программирования предусмотрен файловыйтип данных, предназначенный для представления данных, хранящихся во вторичнойпамяти. Даже если в языке, которым вы пользуетесь, файловый тип данных не предусмотрен, в операционной системе понятие "внешних" файлов, несомненно, поддерживается.
О каких бы файлах мы ни говорили (файлах, предусмотренных в Pascal, или файлах, поддерживаемых непосредственно операционной системой), в любомслучае нам придется действовать в рамках ограничений, касающихся способов доступа к файлам. Операционная система делит вторичную память на блоки одинакового размера. Размер блока зависит от конкретного типа операционной системы иобычно находится в пределах от 512 до 4096 байт.Файл можно рассматривать как связанный список блоков, хотя чаще всего операционная система использует древовидную организацию блоков, при которой блоки,составляющие файл, являются листьями дерева, а каждый внутренний узел содержит указатели на множество блоков файла. Если, например, 4 байт достаточно, что'бы хранить адрес блока, а длина блока составляет 4096 байт, тогда корневой блокможет содержать указатели максимум на 1024 блока.
Таким образом, файлы, состоящие максимум из 1024 блоков (т.е. примерно четырех миллионов байт), можнопредставить одним корневым блоком и блоками, содержащими сам файл. Файлы, состоящие из максимум 220 блоков, или 232 байт, можно представить одним корневымблоком, указывающим на 1024 блока промежуточного уровня, каждый из которыхуказывает на 1024 блока-листа, содержащих определенную часть файла, и т.д.Базовой операцией, выполняемой по отношению к файлам, является перенос одного блока в буфер, находящийся в основной памяти. Буфер представляет собой зарезервированную область в основной памяти, размер которой соответствует размерублока. Типичная операционная система обеспечивает чтение блоков в том порядке, вкаком они появляются в списке блоков, который содержит соответствующий файл,т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
