Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 71
Текст из файла (страница 71)
5,3 подграфы (Ег) с максимальной суммой: Ег — — ((Ьг> Ьг, Ье)> И) -+ ) р; = 3+ 3+ 2 = 8> Ег = ((Ьг Ье, Ьв) И) -+ Е р> = 3+ 3 + 2 = 8, Ез = ((Ьь Ьз, Ье), о) -+ ~', р; = 3+ 3+ 2 = 8, Е» = ((Ьз Ье> Ьв), Э) -+ )'; р> = 3 + 3+ 2 = 8 Ев = ((Ьь Ь>ь Ье), Я) — ь ~., р' = 2+ 2+ 2 = 6 > Ее — — ((Ь», Ьв, Ьв), Я) ~ ) рг = 2+ 2+ 2 = 6. > В результате получим четыре эквивалентных диверсифицированных портфеля: (к;) = ((Ьь Ьг, Ье), (Ьг> Ье, Ьв), (Ьь Ьз, Ье) (Ьз, Ье, Ьв)). Рассмотрим синтез портфелей мощности, равной 4. Расширяем носитель пустых подграфов, каждый нз которых в предыдущем случае образовал портфель мощности 3.
Оцениваем расширение суммой ггь корреляционных коэффициентов добавленных ребер. Выбираем подграф с минимальной суммой. Подграф Ег расширяется вершиной Ьг, при этом сумма ггь = = 0,6. Добавилось ребро (Ьв, Ьг), остальные расширения увеличивают значение аь. В результате получили первый портфель кг = (Ьь Ьг, Ье, Ьг). Аналогично расширяем остальные 3 портфеля; в результате получаем еще 4 портфеля с суммой ггь = О, 6: кг = (Ьг Ьв, Ьг> Ьв) > ггз = (Ьь Ьз, Ь»> Ьв) >г» = (Ьз, Ь», Ье, Ьв)> в'е — (Ьз, Ье, Ьг, Ьв).
Добиться максимального быстродействия комбинированных алгоритмов без порождения всех эквивалентных решений, т. е. использовать малый объем памяти, позволяют алгоритмы третьего класса, реализующие семантическое эквивалентирование. Прй семантическом эквивалентировании известна не только полная система аксиом, но и конструктивный критерий, который позволяет: для задачи анализа проверить истинность предиката 1' 1, если модель Ф, обладает заданным свойством, 10 в противном случае; для задачи синтеза связать две различные абстракции — модели Ф, н Фь — в единую систему с помощью предиката функциональной целостности 1, если преобразование Ф, -+ Фь существует при взаимно однозначном соответствии О( я, Ь)яа между элементами моделей Ф, и Фь, 0 в противном случае.
Общее, что характеризует модели Ф, и Фь и что отличает их от других, — это смысл преобразования Ф, -ь Фь. Суть преобразования Ф, -+ Фь — это свойство языковых выражений, инвариантное относительно их модельных представлений. Изучением смысла занимается логическая семантика, которая является разделом металогики. Под семантикой, как правило, понимают дескрнптивную (описательную) семантику, изучающую связь между знакосочетаниями формализованного языка и их интерпретациями (толкованнями) в терминах той системы понятий, формализацией которых является данный язык.
Здесь под семантикой понимают изучение интерпретации одного формализованного языка в категориях другого, причем оба языка являются формализацией одного и того же объекта (явления). Этот вид семантики будем называть яроекягивнылг. В частном случае, когда оба языка совпадают и исследуется выполнимость определенного свойства изучаемой модели, проективную семантику будем называть рейглексивной.
Рефлексивная семантика позволяет решать задачи анализа моделей. Проектнвная семантика преобразования Ф, -+ Фь позволяет вычислять экстремальное значение функционала качества решения ~р(Фь) и строить соответствующую оптимальную модель Фь, Э 5.1. Принципы характеризацивнногв анализа 395 Гл. 5. Прикладная теория алгоритмов 394 не строя все эквивалентные модели (Фь,.), что намного уменьшает трудоемкость алгоритмов. Для определения проективной семантики преобразования Ф, -+ Фь необходимо: 1) найти числовые характеристики (ьц) модели Фь, однозначно определяющие значение чт(Фь); 2) установить свойства Яь модели Фь, при наличии которых вычислимы 1щу; 3) выявить свойства 5, модели Ф„однозначно определяющие свойства Яь модели Фь; 4) найти числовые характеристики модели Ф„ обладающей свойствами Я„однозначно определяющие у(Фь).
Таким образом, наличие свойств з', позволяет однозначно вычислить ~р(Фь) без фактического построения Фь. Для нахождения рефлексивной семантики анализа модели Ф, необходимо: 1) выявить свойства Я, модели Ф„однозначно определяющие предикат Ро(Ф,); 2) найти числовые характеристики модели Ф„определяющие наличие свойств Я,. В обоих случаях основным моментом является установление свойств Я, модели Ф, которые определяют истинность предпката Ро(Ф,) или Ро(фвт Фь ). Эти свойства модели Ф, будем определять отсутствием запреще ных фигур, образующих основу критерия выполнения свойств Я,. Знание запрещенных фигур позволяет эффективно решать задачи анализа и конструктивно вычислять функционал Ф(Фь) без генерации всех эквивалентных моделей (Фь,) (см.
рис. 5.1, в) при решении задач синтеза, Поиск проективных и рефлексивных семантик, основой которых являются запрещенные фигуры, и их изучение отнесем к разделу метало- гики и будем называть констпруктивной семантикой. Взаимоотношение всех трех семантик преобразования иллюстрирует рис. 5.4. Рефлексивные семантики Рис. 3.4 Проблему поиска запрещенных фигур называют харакптгризационной проблемой. Эта проблема определяется классом рассматриваемых моделей К, = (Ф,) и характеризуется свойством Я„определяющим предикат Ро(Ф,) или Ро(Ф„Фь).
Для решения характеризационной проблемы требуется определить множество аапрещенных фигур К, = (Ф;1, т. е. таких моделей Ф<, отсутствие которых в данной модели Ф, Е К, является необходимым и достаточным условием того, что Ф, обладает свойством 5„ и при этом никакая нз моделей Ф< Е К, не присутствует в другой запрещенной фигуре — модели Ф Е К,. Формализуем понятие отсутствия и присутпсптвия одной модели в другой. На множестве моделей К, можно задать отношение упорядочения Р„такое, что (Ф,", Ф ) Е Р„, если Ф< присутствует в Ф .
Отношение Р„называется отношением подчинения, а модель Ф; — подчиненной модели Ф . Отношение подчинения моделей служит обобщением известного отношения быть подмодглью. Модель Ф; является подмоделью модели Ф , если получена из Ф . удалением некоторых элементов носителя и/нли сигнатуры. Характеризационная проблема с заданным отношением подчинения Р„в классе моделей определяет характеризационные задачи. Поскольку в классе моделей К, может быть задано много отношений упорядочения, характеризационную проблему можно рассматривать как целое множество характеризацнонных задач, каждая из которых имеет собственное решение в виде множества запрещенных фигур.
От выбора отношения подчинения в решении характеризацнонной задачи зависит многое: и компактность множества запрешенных фигур, и разрешимость этой задачи вообще. Принципиальным является тот факт, что характеризационная проблема всегда разрешима. Нужно только правильно выбрать отношение подчинения и соответственно получить постановку разрешимой характеризацнонной задачи. Покажем, каким должно быть отношение подчинения. Теорем а 5.1 (принцин локальности).
Множество запрещенных фигУР Кв = (Фв,у длл класса моделей К, = (Ф,у с отношением подчинения Р„и свойством Я, существует (характгризационнаг задача разрешима) тогда и только тогда, когда справедливо, что всякая модель Фн подчиненная модели Ф., обладающей свойством Я~, также обладаетп им. Доказательство. Допустим, что множество запрещенных фигур существует. Тогда по определению запрещенной фигуры никакая модель Ф„обладающая свойством Я„не имеет запрещенной фигуры в качестве подчиненной.
С другой стороны, пусть отношение подчинения таково, что моделям Ф„которым присуще свойство Я„подчинены только модели, которые им также обладают (рис. 5.5). В этом случае по 396 с с а Рис. 5.7 б Рис. 5.5 Гл.5. Прикладиая п1еория алгоритмов определению запрещенной фигуры множество запрещенных фигур Кв образуется вз минимальных злементов отношения улорядочения Р„на множестве К, 1К„ где К, С К, — подкласс моделей ф„обладающих свойством Я,.
В качестве примера рассмотрим проблему характеризацин двудольных графов. Задачи онределения двудольности графа и преобразования графа в двудольный имеют много приложений: от проектирования надежных автоматов до построения аффективных информационных систем с распараллеливанием обработки. Пусть, например, библиотечная информаРис. 5.5 ционная система реализуется на ЭВМ, имеющей два дисковых устройства (рис. 5.6,а). Для достижения максимальной производительности информационно-поисковой системы необходимо так декомпозировать базу данных на две части, чтобы за счет одновременной установки головок чтения-записи на двух дисковых устройствах время обработки запроса оказалось минимальным.
Файлам базы данных поставим в соответствие вершины графа, Две вершины смежны, если оба соответствующих файла необходимы для ответа на запрос некоторого типа (рис. 5.6, б). Оптимальное распределение файлов по дискам определяется разбиением $5.1. Принципы гарактериэационмого амалиэа 397 множества вершин графа на два множества, внутри которых как можно меньше ребер (что соответствует достижению максимального параллелизма). Эта задача сводится к выявлению проективной семантики преобразования графов в двудольные с минимальным удалением ребер. Семантику определяет решение характеризационной проблемы двудольности графов (рис. 5.6, в). Класс К, состоит из моделей, сигнатура которых образуется одним бинарным симметричнь|м, антирефлексивным отношением.
Свойство Я, означает быть двудольиым. Исследуем два отношения подчинения: Р1 — быть частичным подграбУом и Рэ— быть сводимым графом, Сводимым называется граф С„получающийся нз Сь в результате последовательного склеивания смежных вершин (объединения их в одну) с соответствующим объединением их окрестностей. Оба отношения удовлетворяют принципу локальности. Следовательно, в обоих случаях характеризационная задача разрешима.
Диаграммы отношения подчинения приведены на рис. 5.7. В случае отношения подчинения Р1 множе- О 0 ством запрещенных фигур является множество нечетных циклов, в случае отношения подчинения Рт — множество полных графов порядка ) 2. Итак, всегда можно решить характеризационную проблему, а следовательно, получить множество запрещенных фигур, Это множество определяет конструктивный семантический критерий для решения задачи анализа. Более того, знание множества запрещенных фигур используется в методе семантического зквивалентирования в задачах синтеза.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
