Средства для описания данных

Символы

Для дальнейшего понимания излагаемого материала введем некоторые правила обозначения категорий хранимых данных. Таблица 1

Отношения положения

Для отображения динамики изменения ячейки или записи служат стенограммы, приведем их обозначения.

Содержимое ячейки. Ячейка содержит запись. Чтобы показать, какая именно запись находит­ся в определенной ячейке, используют скобки, которые эквива­лентны операции извлечения записи из ячейки. Например, запи­шем, что запись а содержится в ячейке А:

(А)=а. (4.1.1)

Местоположение записи. Обратная процедура: для данной записи найти содержащую ее ячейку. Эта операция запи­сывается с помощью квадратных скобок. Например, покажем, что запись а содержится в ячейке А:

[а]==А. (4.1.2)

Пересылка. Перемещение данных обозначается стрелкой, направленной в сторону их нового местоположения. Например, пусть запись b помещается в ячейку D:

b->D. (4.1.3)

Пересылка записи, находящейся в ячейке Е, в ячейку F пред­ставляется как

(E)->F. • (4.1.4)

Чтобы показать, что запись g заменит запись h в ячейке, кото­рую в данный момент занимает запись h, запишем:

g->[h]. (4.1.5)

Ключ.Каждая запись представляет объект. Объект распознается в предметной области по своим характеристикам и может быть выделен в ней среди других объектов. Аналогично этому мы должны найти способ выделения какой-либо записи среди других и, более того, полностью идентифицировать запись с объектом, который она представляет.

С этой целью в записи предусмотрено поле, называемое иден­тификатором илиключевым полем. Если для идентификации записи используется более одного поля, то такой случай рассмат­ривается как специальный. Однако формирующие идентификатор поля можно перегруппировать в одно поле, сведя таким образом специальный случай к общему.

В дальнейшем ключевое поле мы будем называть просто ключом. Таким образом, ключ записи является значением ключе­вого поля и однозначно идентифицирует эту запись.

Обозначим ключевое поле для записи либо для элемента в ячейке, где располагается данная запись, индексом К, Например, а_ik является значением ключевого поля для записи a_i. Оно нахо­дится в ячейке А = [a_i] в позиции А_ik == [а_ik].

Отношение порядка

Одним из наиболее важных свойств файла или списка являет­ся порядок, определяемый с использованием ключа каждой записи. Чтобы исследовать это свойство, разобьем значение ключа на образующие его литеры. Для этих литер, которые служат элемен­тарными единицами представления, определимотношение поряд­ка (или, как иногда говорят,последовательность упорядочений).То же отношение порядка должно сохраняться в коде представ­ления информации в ЭВМ .

Например, мы можем установить следующие неравенства меж­ду литерами алфавита:

0<1< А<В<С< ... <Z... и т. д. (4.1.6)

Чтобы ЭВМ выполняла требуемые нам операции, мы должны код для литеры А выбрать меньшим кода для литеры В и т. д. Эти соотношения в ЭВМ представлены комбинациями двоичных чисел коды таблицы ASCII. Двоичное число, представляющее А, меньше числа, пред­ставляющего В, т. е.

Аº065₍₁₀₎ =0100001₍₂₎ , Вº066₍₁₀₎= 0100010₍₂₎ 0100001₍₂₎ < 0100010₍₂₎, (4.1.4)

где знак º эквивалентен слову представляет.

Условие (4.1.6) удовлетворяется, если коды для десятичных цифр меньше кодов для букв. В результате 1 представляется шестнадцатеричной комбинацией 00011001, а Zº01011000₍₂₎ . Таким образом,

Z=01011000₍₂₎, l=00011001₍₂₎ , 00011001₍₂₎ <01011000₍₂₎. (4.1.8)

Ключевое поле образуется из нескольких литер. Оно может включать пробел, код которого равен 32₍₁₀₎.

Ранг записи

Утверждение о том, что одна запись меньше другой, является не вполне корректным, если сравниваются ключи этих записей, а не их длины. Тем не менее, для краткости мы воспользуемся этим определением, и будем считать, чторанг записи а_i ниже ранга записи а_j, если ключ (значение ключа) первой записи меньше ключа (значения ключа) второй записи, т. е. получаем:

а_i < а_j º (а_{i k} )< (а_jk ) (4.1.10)

ОТНОШЕНИЯ

Нам постоянно придется иметь дело с отношениями, сущест­вующими между данными, ячейками и другими переменными. В настоящем разделе мы рассмотрим способы наглядного изобра­жения этих отношений. Прежде всего, обсудим различные типы таких отношений, задавая вспомогательные средства их символи­ческого представления.

Отношение существует между двумя объектами. Обозначим эти объекты строчными буквами, например, а и b, а само отно­шение — буквой R. Тогда мы можем записать, что между а и b существует отношение R:

а R b. (4.2.1)

Например, R может выражать отношение “больше чем”. В этом случае формула (4.2.1) означает, что “а больше, чем b”. Мы также можем ввести другие отношения, например “равно”, “предшествует”, “старше чем”.

Классификация отношений

Отношения можно разбить на: рефлексивные, симметричные и транзитивные.

Рефлексивные отношения. Говорят, что отношение рефлексивное, если оно устанавливается между одним и тем же объектом. Например,

a R a. (4.2.2)

Лишь немногие отношения являются рефлексивными. Так, отношение “равно” — рефлексивное, а отношение “старше чем” — нерефлексивное.

Симметричные отношения. Отношение считается симметричным, если оно применимо к элементам а и b при их рас­смотрении как в данном порядке, так и в обратном:

a R b & b R а. (4.2.3)

Отметим, что для большинства отношений (но не для симмет­ричных) важен порядок расположения элементов. Отношение “отличается от” является симметричным, так как два объекта отличаются друг от друга независимо от того, какой из них рас­полагается первым. Вместе с тем это нерефлексивное отношение, так как нельзя сказать о каком-либо объекте, что он отличается сам от себя.

Многие отношения являются несимметричными(асимметрич­ными). Простым примером может служить отношение “стар­ше чем”.

Транзитивные отношения. Представимтранзитив­ное отношение в символической форме:

a R b & b R cÞ a R c. (4.2.4)

Отсюда следует, что отношение R является транзитивным, если оно, существуя между а и b и одновременно между b и с, сущест­вует между а и с. Так, если Катя старше Гали, а Галя стар­ше Изабеллы, то Катя старше Изабеллы.

На первый взгляд может показаться, что все отношения должны быть транзитивными. Однако это не так и примером тому может слу­жить отношение “не равно”. Подставьте в таком отношении вместо а - 6, вместо b 5, а вместо с – 6 и вы увидите, что отноше­ние “не равно” не является транзитивным (ононетранзитивное),иначе вам придется признать, что 6 не равно 6.

Графы

Необходимым условием текстуального описания является последовательное изложение. Действительно, при чтении книги мы последовательно переходим от одного предложения к друго­му. Возможен, однако, альтернативный способ представления, при использовании которого не требуется выполнять этот процесс последовательно (как в случае запрограммированного обучения). Здесь будет рассматриваться множество объектов и отношений, которые устанавливаются между ними. Каким образом мы смо­жем описать эти отношения одновременно? Решить эту проблему нам поможет граф.

Рис 4.1. Граф

Граф дает наглядное изображение, как объектов, так и отно­шений между ними. Более того, он позволяет рассматривать их в любой последовательности. Таким образом, граф обеспечивает способ представления без последовательного (во времени) про­смотра, присущего тексту,

Граф состоит из ряда вершин и ребер. Он должен содержать, по крайней мере, одну вершину.Ребро является отрезком прямой, вершина—точкой. Для каждого ребра также должна существо­вать вершина, которая его завершает. Пример графа показан на рис. 4.1.

Вершины графа представляют объекты, а ребра — отношения между этими объектами. Так как отношение существует между двумя объектами, естественно, что в графе каждое ребро имеет две терми­нальные вершины.

Математики рассматривают граф как нечто абстрактное. Мы же, вкла­дывая в понятие “ребра” и “верши­ны” смысловую нагрузку, получаем полезную концепцию для представле­ния данных.

Направление

Выше уже обсуждались симмет­ричные отношения, такие, как “ра­вен”, “следующий”, “родной брат”. Эти отношения не опреде­ляют направления; они устанавливаются между элементами без указания на то, какой из них задается первым. Симметричные отношения легко представить с помощью рассмотренного только что графа. В данном случае ребро отображает симметричное от­ношение, а вершины — объекты, к которым это отношение приме­няется.

Асимметрия

Отношение называется асимметричным, если между а и b оно существует, а между b и а - нет. В качестве примера можно при­вести отношения “больше чем”, “отец”, “дядя”. Направлениеопределяет, какой объект служит под­лежащим, а какой дополнением по от­ношению к глаголу, выражающему отношение. Здесь важно определить объект, который устанавливается пер­вым. Так, мы говорим, что Максим — отец Валеры , но обратное утвержде­ние неверно: Валера не отец Максима. Ребро графа не показывает, какой из объектов упоминается первым.

Орграф

Для указания подлежащего и дополнения ребру придается ориентация. Такое ребро в дальнейшем мы будем называть ду­гой. Дуга изображается в виде стрелки, направленной от подле­жащего к дополнению. Граф, в котором задана ориентация, на­зываетсяориентированным графом илиорграфом. В орграфе дуги по-прежнему связывают вершины (рис. 4.2),

• ⇐ Назад
• 4
• 5
• 6
• 7
• 8
• 9
• 101112
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• Далее ⇒