Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 72
Текст из файла (страница 72)
Основополагающим принципом семантического зквивалентирования является то, что знание конкретных запрещенных моделей, присутствующих в модели ф, и мешающих ей обладать свойством Я„позволяет определить те локальные структуры, преобразование которых необходимо для того, чтобы получить модель ф„которой присуще свойство Я,. При атом осуществляется только минимальный (неизбежный) перебор вариантов преобразований, т. е. вычислительный процесс в смысле трудоемкости улучшить нельзя. При семантическом зкви- Гп. 5.
Прикладная теория аягаритмае 398 15.1. Принципы характеризациоииога аиаяиза 399 валентиравании дерево решений (см. рис. 5.1,в) состоит иэ двух звезд. Первая эвеада соответствует преобразованию Ф, -+ Фь, Ро(Ф„ Фь) = 1, вторая — Ф, -+ Фь. При поиске минимального решения необходим обход всех ветвей первой звезды, во второй звезде достаточно взять любую ветвь, так как с тачки зрения минимальности решения, определяемого значением у(Ф,), все ветви второй звезды равнозначны.
Рассмотрим подробно процесс семантического эквивалентирования. Основу этого процесса составляют способы преобразования запрещенных фигур в эквивалентные разрешенные. Эквивалентность определяется смыслом преобразования Ф, -+ Фь. Как правило, способом преобразования запрещенной фигуры в разрешенную является удаление, введение или расщепление элемента носителя или сигнатуры либо переход к некоторой цодчнненной модели. Для семантического эквивалентирования или преобразования графа в двудольный существует несколько способов преобразования запрещенных фигур — циклов нечетной длины. В случае использования преобразования для вложения графа в гиперкуб прн проектировании надежных автоматов запрещенная фигура преобразуется в разрешенную введением на ребро нечетного числа вершин (строго говоря, здесь не одно преобразование, а множество).
Если преобразование используется для оптимальной декам- позиции базы данных, то способ преобразования заключается в удалении ребра. Принципиальным является то, что способ преобразования запрещенной фигуры в разрешенную существует всегда, когда преобразование Ф, -+ Фь имеет смысл. Действительно, для каждой модели Ф, существует эквивалентная модель Ф„обладающая свойством Я,. Следовательно, существует преобразование Ф„в Ф„а любое преобразование модели Ф, в модель, обладающую свойством Я„обязательно преобразует запрещенные фигуры в разрешенные.
Таким образом, способ преобразования запрещенной фигуры в разрешенную существует всегда. В общем случае существует множество преобразований запрещенной фигуры в разрешенную. Пусть В; = (г<,~ — множество способов преобразований запрещенной фигуры Ф; б К, (т. е. для всякого у г;, (Ф;) — разрешенная фигура). Построим множество базисных способов преобразований Яо С В;, т. е. такое минимальное по включению множество го, что для любого г;, найдется последовательность преобразований из Во, переводящая Ф; в г;у(Ф;).
Рассмотрим способы преобразования запрещенных фигур для преобразования мографа в линейный, что важно в задачах ор- ганизации данных в информационно-поисковых системах и базах данных. Основными характеристиками размещения данных в памяти являются объем занимаемой памяти и время доступа. При представлении информационно-поисковой системы мографом объем памяти определяется мощностью носителя, а время доступа — временем считывания слов модели. Одним вз способов оптимальной организации данных в памяти является линейное размещение, которое предполагает такое линейное (полное) упорядочение объектов данных, что ответ на каждый вопрос есть цепочка непосредственно следующих в этом упорядочении объектов данных. Поставим в соответствие объектам данных элементы носителя мографа, ответам на запросы — слова.
Мограф называется яинебныяе, если допускает линейное размещение элементов носителя, при котором все слова представляются цепочками. Таким образом, для получения оптимальной организации данных необходимо преобразовать маграф в линейный и, следовательно, решить характеризационную проблему линейности мографа. Не конкретизируя вид запрещенных фигур (этот вопрос подробно рассмотрен далее), отметим, что возможны два способа преобразования запрещенных фигур в разрешенные: 1) расщепление элемента носителя х на х и х' с соответствующей заменой х на х' в некоторых словах, в которые входил элемент х; 2 расщепление слова М, т.
е. замена его на два слова. ажно показать, что эти способы образуют базисное множество способов преобразований запрещенных фигур в разрешенные. Пренппюстрнруем спе сабы ар собр ваев анни аапр стенных фигур в р перстенные на прнмере мегрвфв (рнс. Ь.б, а), препставпиюшего гнкететнтескую бнбпно. Ь*э[ Самарский Л.
Л мар у м *ара и.м. 2[ невский В. В б Рнс. 5.8 400 Гл. 5. Прикладная теория алгоритмов $5.1. Принципы харакгперизаиионкого анализа 401 течную информационную систему, ввлючаюшую информацию о следуюших книгах: к» вЂ” Ржевский В.В. Процессы открытых горных работ. — Мл Недра, 1978; кэ — Самарский А.А.
Теория ревностных схем. — Мл Наука, 1977; кз — Марчук Г.В. Методы вычислительной математики. — Мл Наука, 1977; к» вЂ” Оснокы автоматязапии управления производством / Под ред. Макарова И.М. — Мл Высшая швола, 1988. В ней реалнауются следующие запросы: Мг — Книги цо вычислительным метолам, Ответ (хэ, кэ»; Мэ — Книги по автомвпюапин пропессов. Ответ (кп л»»; Мэ — Книги авторов (редакторов), фамилии которых начинаются с букв от А до М.
Ответ (кэ, к»»; М» — Книги авторов (редакторов), фамилии которых начинаются с букв от Н до Я. Ответ (зг, хт». Данный мограф не является лвнейным. Можно показать, что каждый элемент носителя и каждое слова входят в аекрешенную фигуру. Расгцевленне элемента носителя нви слова долина преабрааовать мограф в линейный. Рассмотрим, например, расшепление элемента т». Преобразованный мограф является линейным и представляется лннейно упорядоченным, приведенным на рис. 5.8,6. При расщеплении любого слова, например, Мэ, мирзф такие становится линейным и представляется линейно упорядоченным, дрнведенным на рис. 5.8, е. В первом случае увеличивается объем памяти, занимаемый объектами данных, во втором — увеличивается среднее время ответа не запросы.
Каждый способ преобразования г<,. характеризуется стоимостью с;,. Функционал качества преобразования»р(Фь) определяется стоимостью произведенных преобразований запрещенных фигур в разрешенные. Для выполнения преобразования Ф, ~ Ф, неизбежно преобразование каждой запрещенной фигуры в разрешенную, поэтому выберем для каждой запрещенной фигуры Ф,» С Ф, один из способов ее преобразования; их совокупность определит глобальное преобразив»)ние Ф, — у Ф,. Такое преобразование в общем случае может не достигать экстремума функционала»р(Ф5), даже если для каждой фигуры Ф„выбран способ преобразования с наименьшей стоимостью.
'Это обусловлено тем, что возможен способ преобразования Ф.». пусть имеющий не наименьшую стоимость, но преобразующий заодно и другую запрещенную фигуру Ф,» Более того, взаимосвязь способов преобразования запрещенных фигур может оказаться очень сложной, поэтому простой выбор способов преобразования по одному на каждую фигуру Фм С Ф, не обеспечивает достижения экстремума функционала качества»р(Фь). Процедура семантического эквивалентирования основана на построении семантической таблицы. Столбцам этой таблицы соответствуют запрещенные фигуры, присутствующие в модели, строкам — компоненты запрещенных фигур. Элемент (т, у) таблицы равен 1, если преобразование т-й компоненты превращает у'-ю запрещенную фигуру в разрешенную, и 0 в противном случае.
По- крытие столбцов строками семантической таблицы определяет минимальное по включению множество преобразований, которые необходимо выполнить для получения из Ф, модели Фо, обладающей свойством 5,. Учитывая, что каждый способ преобразования может иметь собственную стоимость, делаем вывод, что для достижения экстремума»р(Фб) необходимо найти минимальное по стоимости покрытие семантической таблицы. Рассмотрим задачу семантического эквнвалентирования графа, изображенного на рнс. 5.6,б, в двудольный.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
