Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 74
Текст из файла (страница 74)
Можно показать, что последний способ наиболее экономичен прн больших размерностях графов, что характерно для практики. Но задание графа перечислением окрестностей равносильно заданию мографа, носителем которого является носитель графа, а словами — окрестности его вершин. Возможны варианты в задании $5.2. Методы оптимального раэмегцеиия данных 405 графа, но в любом случае абстракцией представления может быть мограф. Например, в базах данных, основанных на сетевой модели данных (фрагмент сетевой схемы данных приведен на рис. 5.12,а), абстракцией данных является ориентированный граф.
При обработке запросов поиск информации осуществляется в направлении, которое указывается дугами (от данных о процессах к данным об оборудовании), поэтому хранить необходимо только окрестности нижнего яруса графа (рис. 5.12, б). Эта информация задается мографом, приведенном на рис. 5.12, о. Нзк было показано выше, мограф яэляется абстракцией информационнопоисковой системы с фиксированным ьаюжестзом запросов. Другим примером, когда мограф представляет информационную систему, является органиаакия файлов с несколькими ключами доступа.
Файл представляет собой последовательность ааписей, состотцнх яз идентичных волей (записи могут быть неодинаковой длины). Ключом называется поле илн множество полей, значения которых идентифицируют записи. Доступ к файлу осушествляется с комогвью указания значения ключа. Для ускорения обработки запросов организуются индексы — таблицы, в которых для каждого зиаченян ключа указываются адресе аэвисей, имеюшнх зто значение. Если индевс хранит адреса всех записей, имеющих данное аначение, хо такая органиаавия нааываегся опеергпороеаппмми списками. Ннформавия, храняшаяся в инвертированных списках, кредставляется мографом, носитель которого образуется множеством адресов аапнсей, а слова — множествами адресов записей, имеюших идентичные значения ключе. Рассмотрим файл бяблиотечной информационной системы (рнс.
5.13). Ои имеет несколько ключей доступа: ко фамилии автора, по нвзвашао яэдательсхва, по кюочевому слову и др. Длл ускорения досхука файл можно упорядочить во одному из ключей (обычно во фамилии), ло другим же ключам записи будут совершенно неупорядочены. В рассматриввемюе примере индекс по ключу доступа "влючевое слово" предсхавляегся уже криведенным ранее мографом (см. Ь ис. 5.12, е), слову Мг соответствует значение "математические методы", слову т — "автоматизация" и т д Мограф может вздевать ие только инвертированные списки, но и другие свисковые организации ннхексов: мультнсвисви, секционные списки.
Наконец, просто двоичная матрица может рассматряваться как матрица ннювдентяостей мографа. Основными критериями при размещении данных в памяти ЭВМ являются минимизация объема памяти и времени доступа. Элементы носителя мографа однозначно соответствуют объектам 407 406 Фамилия И.О. Название Ключевые слова Выходные данные Адрес Мс Наука, 1977 Математические методы Самарский А.А. Теория Разно- стнвх схем Мз Наука, 1977 Методы вычис- лительной ма- тематики Математические методы, математическое модели- рование Марчук Г.И. Макаров И.М./ ред. Математические методы, вроиаводственные кооцессы, авто- матиаацня школа, 65 Основы автомз- тиаацни уцрав- ления произ- водством Гузфы сети, Мз Мнр, 1984 Математиче- ские методы, теоретико- графовые модели, ал- горитмы на графах Свами М., Тхулзснрвман К. Мз Мнр, 1977 Брейер М.
Те овин н мето- ды взтоматн- ззвни вооек- тноованв я вы- числительных сйстем Автоматиза- ция, алго- ритмы на графах Мс Недра, 1978 Риевский В.В. Пооцессы открытых горных рабат Пвоивводст- венные вро- цессы Мг Мир, 1984 Математическое моделирование, тео. ретик~ьграфо. вые модели Питерсон Ди. Теория сетей Петри н моде- лирование систем Рис.
8.13 Гл. б, Прикладная теория аягоритмоо данных, размещенным в памяти, следовательно, критерий минимизации объема памяти определяет функционал качества у(Фь) при семантическом эквивалентировании как минимум мощности носителя Фь. Мограф Фь определяет размещение, в котором все слова отыскиваются максимально быстро. Если мограф Ф, не допускает такого размещения, то поиск некоторого слова эквивалентен поиску нескольких слов, что равносильно тому, что данное слово расщеплено на несколько слов.
Таким образом, критерий минимизации времени доступа определяет функционал качества у(Фь) как минимум мощности сигнатуры Фь. В рассмотренных примерах организации данных, представляемых мографом, при условии минимального времени доступа важно минимизировать объем памяти. Возможен и обратный критерий: минимизация времени доступа при неизменном объеме памяти. Он важен, например, в задаче такого упорядочения записей файла (рис. 6.14), при котором быстрее осуществляется поиск по ключу. 86.2.
Методы оптимального размещения данных Доступ к объектам данных осуществляется с помощью некоторой стандартной процедуры поиска, реализующей переход от одного элемента памяти к другому. Переход осуществляется однозначно, поэтому эту процедуру поиска можно формализовать функ- цией осмотра памяти 5 — частичной функцией на множестве элементов носителя мографа 5: Х -ь Х; 5(х) — элемент, к которому осуществляется переход после элемента х. Рассмотрим такое размещение данных и такую функцию осмотра памяти 5 (модель Фь), при которых для каждого слова М модели Фь имеется такой элемент хо бМ,что М = (хо, 5(хо), 5 (хо), ..., 5~ ~ (хо)), т. е. каждое слово отыскивается с помощью Рис.
8.14 функции 5 на основании только информации о мощности слова и начальном элементе хо. Подобные мографы называются дояустимыии. Очевидно, что на практике большинство мографов не являются допустимыми. Для их реализации в памяти ЭВМ необходимо расщепление элементов носителя или расщепление слов. При этом увеличивается либо объем памяти, либо время доступа. Допустимые же мографы представляются в памяти ЭВМ безызбыточным образом и требуют минимального времени доступа. Таким образом, задача оптимального размещения данных заключается в преобразовании мографа в допустимый и в построении функции осмотра памяти.
При этом функционалом качества 409 408 <з> хт (3> «,2,3,4,5> " «,2,3) (3) «, 3, 4) «.г,з) «,2,5> (г> «. з> (2) д (г) г Рпс. 5.15 т з т т ь т а т и г т Рис. 5.15 Гл.5. Прикладная тпеория алгоритпмоа является минимальное расширение носителя без изменения сигнатуры или минимальное расширение сигнатуры без изменения носителя.
Эта задача имеет графовую интерпретацию. Рассмотрим функцию осмотра памяти 5: Х -+ Х допустимого мографа Фь как отношение смежности Я С Х х Х вершин в ориентированном графе Су = (Х, 5), построенном на множестве вершин Х. Граф Су является функциональным (у-графом), т, е.
из каждой вершины его исходит не более одной дуги. Теорема 5.2. Саязнытг г-графяеляетпсялибоациклическим, либо содержит точно один цикл, Из этого утверждения следует, что практически важными являются следующие классы у-графов и допустимых мографов, представляющихся соответствующими у"-графами: линейные (пути), циклические (контуры), ациклические (ориентированные деревья). На практике функция осмотра памяти реализуется либо с помощью указателей, либо переходом к соседнему элементу памяти. Для представления в памяти линейных графов можно использовать второй вариант реализации функции осмотра памяти.
Представление циклических у-графов также основано на переходе к соседнему элементу памяти, на с одним исключением: Я(х„) = = х<, где х>, х„— соответственно первый и последний в размещении элементы. Для представления ациклических у-графов необходимы указатели. Однако представление ациклического у'-графа парами (х,5(х)) для каждой вершины х избыточно (рис.5.15, а, б). ного представлераф на линейные 15.2.
Методы оптимального размен<ения данных фрагменты, внутри которых в качестве функции осмотра будем использовать переход к соседнему элементу памяти, а связь фрагментов задавать указателями (рис. 5.15, а). Для решения характеризационных проблем представления мографов у-графами различных классов ввелем отношение подчинения. Мограф Ф1 подчинен могрофу Фг е отмен<енин подчинения Р> если он получен из Фг последовательностью ограничений, пт сужений, расширений и сверток.
Под ограничемием мографа понимаем удаление некоторых его слов, под сужением — удаление некоторых элементов носителя, под раси>иремием — введение нового слова, являющегося пересечением имеющихся, под саерткотг — склеивание всех вершин некоторого слова с объединением (3) (3) «, з) <з> «,2.З> (2, 3) «,2) (2> (2) <2> а 5 их весов. Введенные операции иллюстрируют рис. 5.16.
Отношение подчинения Р1 используется для характеризации линейных и ациклических мографов. Отношение подчинения Рг, кроме операций, используемых в Р1 включает еше одну операцию — замыкание слова, т. е. замену пт его на дополнение в множестве элементов х «, 2) носителя мографа (рис. 5.17), а на операцию расширения Рг накладывает слепую- «,5>х ( х ц, З> шее ограничение: можно включать только слово М, являющееся пересечением слов <4, х х М;, М таких, что их объединение не образует весь носитель маграфа (возможное «, 2, 3) расширение).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
