<< Вернуться у выбору материала

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

Введите ваш запрос для начала поиска.

ЧОП стоимость.

4.1 Символы

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

Уровень категорий Представления реального мира Абстрактные представления Практическая реализация
    данные символ Хранимые данные символ
Наибольший Предметная область Библиотека   База данных  
  Подмножество приложений Файл a Список А
  Объект Запись аi Ячейка Ai
  Имя атрибута Имя поля aij Элемент Aij
Наименьший Значение атрибута Значение поля      

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

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

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

(А)=а. (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 является значением ключевого поля для записи ai. Оно находится в ячейке А = [ai] в позиции Аik == [аik].

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

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

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

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

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

Аº065(10)=0100001(2) , Вº066(10)= 0100010(2) 0100001(2) < 0100010(2), (4.1.4)

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

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

Z=01011000(2), l=00011001(2), 00011001(2) <01011000(2). (4.1.8)

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

Ранг записи

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

аi < аj º (аi k )<(аjk) (4.1.10)

4.1 Отношения

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

Отношение существует между двумя объектами. Обозначим эти объекты строчными буквами, например, а и 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.2 Графы

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

Граф

Рис. 4.1. Граф

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

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

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

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

Направление

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

Асимметрия

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

Орграф

Орграф

Рис. 4.2. Орграф

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

Типы отношений, изображаемых с помощью графа

На рис. 3.4 показаны в форме графа три типа отношений (рефлексивное, симметричное и транзитивное).

Рефлексивное (1), симметричное (2) транзитивное (3) отношения

Рис. 3.4. Рефлексивное (1), симметричное (2) транзитивное (3) отношения

Для рефлексивного отношения стрелка начинается и заканчивается в вершине а, поскольку отношение устанавливается между элементом и им самим. В симметричном отношении первая стрелка начинается в а и заканчивается в b, а вторая начинается в b и заканчивается в а, так как отношение устанавливается в двух направлениях. Для транзитивного отношения первая стрелка направлена от а к b, вторая - от b к с, а третья, определяющая транзитивность, - от а к с.

4.1.1 Некоторые свойства графов

Маршруты

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

• структуры файла или списка его графа; метода поиска — выбора последовательности ребер

На рис. 4.4 изображен граф с несколькими вершинами и ребрами.

Рассмотреть несколько последовательностей ребер. Самая прямая из них — acdeb. Поскольку здесь возможны варианты, определим принцип их классификации. Будем считать, что последовательность ребер:

Цикл

Последовательность ребер, в которой исходная и конечная вершины совпадают, называется циклом. Если последовательность ребер включает циклы, она не может быть элементарной. На рис, 4.5, например, последовательность gjkg является циклом, так как она берет начало и заканчивается в одной точке g.

Последовательность ребер acdgjkgeb содержит цикл gjkg. Эта последовательность является простой, так как в ней не повторяются ребра, но она не элементарная, так как вершина g появляется дважды.

По аналогии с последовательностью ребер можно провести классификацию циклов, разделяя их на элементарные, простые и т. д., причем к ним применимы те же определения. Воспользовавшись в качестве иллюстрации рис. 4.5, определим цикл как

Изображение нескольких типов циклов

Рис 4.5 Изображение нескольких типов циклов

Маршруты орграфа

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

Орграф

Рис 4.6 Орграф

На рис. 4.6 изображен орграф. Здесь также существует несколько последовательностей дуг между вершинами а и b. При определении таких последовательностей важно установить направление дуги. Мы можем перемещаться по дуге только в соответствии с указанием стрелки. Так, на рис. 4.6 acdgeb — элементарная последовательность дуг от а до b. Последовательность же acdeb является недопустимой, так как дуги de не существует, а есть только дуга ed.

Последовательности дуг также можно делить на: элементарные, простые и непростые, в зависимости от того, повторяется ли в них вершина или ребро.

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

Из четырех циклов, представленных на рис. 4.7, только три являются петлями. Действительно, вершину h можно покинуть двумя путями, но нет пути, по которому можно было бы в нее вернуться.

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

Петли и циклы орграфа, изображенного на рис 4.6

Рис. 4.7. Петли и циклы орграфа, изображенного на рис 4.6

Концепция петли, введенная теорией графов, сравнима с понятием “петли” или цикла используемым программистом. Очевидно, команды в программе можно рассматривать как вершины графа.

Дуги, которые соединяют команды, определяют последовательность, в которой ЭВМ переходит от одной команды к другой.

Геометрия

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

Изоморфные орграфы

Рис. 4.8. Изоморфные орграфы

На рис. 4.8 первые три орграфа графически эквивалентны: каждый содержит три вершины и три соединяющие их, в одной и той же последовательности дуги. Их эквивалентность не зависит от того, как изображены дуги - прямыми, круговыми или волнистыми линиями. Третий и четвертый орграфы состоящие из трех дуг и трех вершин , не являются эквивалентными по теории графов. Дело в том, что в одном из них можно продвигаться по петле в обратную сторону, а в другом нельзя.

4.1.1 Деревья

Основные определения

Дерево представляет собой граф, не содержащий циклов, что упрощает его структуру.

Дерево

Рис. 4.9 Дерево

Это связный граф, так как каждая вершина в нем завершает, по крайней мере, одно ребро, и не существует вершин, которые не завершали бы ребро. Вершина, у которой отсутствуют исходящие ребра, называется изолированной точкой. Изолированная точка в дерево входить не может. Более того, дерево с v вершинами обязательно включает v - 1 ребер. Пример дерева показан на рис.4.9

Генерация

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

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

Генерация дерева

Рис. 4.10. Генерация дерева

эта точка стала частью дерева, добавим ребро, соединяющее h с некоторой вершиной (на рисунке hf). Если попытаться ввести дополнительное ребро, соединяющее h с какой-либо другой вершиной, то образуется цикл. Другими словами, если вслед за hf мы добавим ребро hg, то получим цикл hfgh, и граф на рис. 4.10 перестанет быть деревом.

Типы вершин

Число ребер, которые оканчиваются одной вершиной, называется инциденцией. В зависимости от инциденции для дерева определяются два типа вершин;

• висячая, которая инцидентна только к одному ребру;

• точка ветвления, или узел, инцидентный по крайней мере к двум ребрам.

На рис. 4.10 a, b, e, g - висячие вершины, с, d и f - узлы. Очевидно, их можно рассматривать как часть последовательности ребер, соединяющих другие вершины.

Деревья-орграфы

Вернемся к рассмотренной выше структуре и заменим в ней ребра дугами. В результате получим орграф, который также является деревом, - дерево-орграф. Эта структура вызывает больший интерес, чем дерево, так как является средством представления иерархической организации.

Направленное дерево

Рис. 4.11. Направленное дерево

В зависимости от направления дуги здесь различают два типа висячих вершин:

• корень, который имеет одну или несколько исходящих дуг и ни одной входящей;

• лист, который имеет одну или несколько входящих дуг и ни одной исходящей.

Тип узла также определяется направлением связанной с ним дуги и, кроме того, инциденцией. Выделяются следующие типы узлов:

• корнеподобный, имеющий больше входящих дуг, чем исходящих;

• листоподобный, имеющий больше входящих дуг, чем исходящих;

• связующий, в котором число входящих дуг равно числу исходящих;

• простой связующий с одной входящей и одной исходящей дугами (инцнденция равна двум).

Корни, листья и все типы узлов изображены на рис.4.11.

Древовидная структура

Древовидная структура

Рис. 4.11. Древовидная структура

Направленное дерево - это простая структура орграфа. Еще более простой древовидной структурой является направленное дерево с одним корнем (иногда его называют древовидной структурой с корнем).

Древовидная структура с двоичным ветвлением

Рис.4.12. Древовидная структура с двоичным ветвлением

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

Ценность древовидной структуры не вызывает сомнений. Примером такого графа может служить схема управления какой-либо организации.

Корнем здесь является президент или директор. От корня исходят одна или несколько дуг к заместителям, которые занимают первый уровень. По мере удаления от корня располагаются более низкие уровни управления. Наконец, в качестве листьев выступают рабочие, которые и завершают эту схему. Древовидная структура показана на рис.4.11.

Двоичное ветвление. Древовидная структура с двоичным ветвлением содержит всего четыре типа вершин:

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

Транзитивные графы

Транзитивный граф

Рис. 4.13. Транзитивный граф

Более простым типом графа является транзитивный граф — связный орграф, в котором могут присутствовать циклы и не могут - петли. Это обеспечивает сохранение транзитивности. На рис. 4.13 изображен транзитивный орграф с корнем.

4.1.1 Раскрашенные графы как инструмент представления данных

Раскрашенные графы

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

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

Действительно, между объектами одной и той же группы могут существовать различные отношения. Так, в группе “семья” присутствуют несколько отношений. Например “отец”, “брат”, “двоюродный брат” и “дядя”. Они могут иметь место в рассматриваемой группе людей. Интересно, что эти отношения можно свести к двум основным - “родитель” и “супруг” — и через них выразить все остальные. Мы можем сконструировать полную схему семьи, если нам известен способ передачи основных отношений.

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

Обозначение записей и ячеек

Обычно мы имеем дело с различными элементами данных — записями, ячейками, файлами и списками. Однако в данном случае наибольший интерес для нас представляют записи и ячейки.

Граф ячеек в списке

Рис. 4.14. Граф ячеек в списке (1, 2). Записи в файле (3)

Чтобы упростить восприятие графов, воспользуемся системой обозначений, в которой записи изображены в виде окружностей, а ячейки — в виде - квадратов. Пустая ячейка показана при помощи квадрата с пересекающимися внутри двумя прямыми.

Отношения данных

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

Так, ячейка А2 соседствует с А3, но поскольку ее индекс меньше, ясно, что А2 предшествует А3.

Тонкой линией также отображается текущее позиционное отношение записей относительно списка, в который они входят. Так, на рис. 4.14 (3) файл содержит запись а2, которая предшествует записи а3 в списке.

Отношение «меньше чем» отображается штрихпунктирной линией. Отношение «указывает на» точечной линией, которая направлена от указанной записи к целевой.

Пересылка. Пересылка данных по определенному адресу изображается утолщенной линией направленной от места хранения данных к адресату

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

Изменения. “Раскрашивая” - стрелку в различные цвета (или используя различные типы линий), на графе можно представить выполняемые в списке или файле изменения:

• линия, образованная последовательностью знаков “х”, показывает, что представляемое ею отношение больше не существует;

• линия, образованная последовательностью знаков “о”, показывает, что представляемое ею отношение является новым, т. е. раньше оно не существовало.

Поиск мест размещения записи в списке

Рис. 4.15. Поиск мест размещения записи в списке

Включение новой записи в список

Рис. 4.16. Включение новой записи в список

Пример. Рассмотрим пример, который имеет большое значение, так как объединяет некоторые концепции теории графов. На рис.4.15 изображен список L, содержащий множество ячеек. Из этого множества на рисунке показаны только ячейки с А до J. Перекрестные линии в ячейках Н, I, J означают, что эти ячейки пустые. S является ячейкой-указателем. Она содержит указатель на ячейку Н и позволяет перейти к оставшимся пустым ячейкам в списке L. Записи в списке L упорядочены. Это можно определить с помощью линий предшествования, отображающих последовательные переходы от А к В, от В к С и т. д. Между G и Н нет стрелки, так как G является последней записью массива, содержащегося в списке L.

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

Размещение записи. В данный момент у нас нет места для размещения записи t. Для его получения необходима реорганизация списка. Записи, хранящиеся в ячейках DG, должны быть перемещены на одну позицию вниз. Другими словами, необходимо выполнить следующие действия:

(G)->H, (F)->G, (E)->F, (D)->E, t->D. (4.3.1)

В результате записи, расположенные в ячейках D-G, сместятся вниз на одну ячейку каждая. С момента пересылки записи из D в Е я до тех пор, пока в D не попадет на последнем шаге запись t, в этих ячейках будут находиться одинаковые записи.

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

Рис.4.16 иллюстрирует процесс внесения изменения. В список L. Утолщенные линии отображают перемещение записей, а цифры в кружках указывают, в какой последовательности выполнялась пересылка,

например, 1 означает, что запись из ячейки G первой переслана в Н, а 5 - что последней была переслана запись t в D. S указывает на следующую доступную свободную ячейку: раньше эта ячейка указывала на Н, теперь - на I. Таким образом, на рисунке изображают старый и новый указатели.

Упражнения

4.1. Для списка, ячейки и элемента:

а) объясните, что означает, каждое понятие;

б) укажите, какие типы символов используются для них;

в) объясните, что является их содержимым;

г) укажите, какие типы символов используются для описания их содержимого.

4.2. Объясните предложения;

а) (адрес) = данное; б) [данное] = адрес.

4.3. Разберите предложение: “Ключ однозначно идентифицирует запись”. Объясните его. Почему “однозначно”?

4.4. На чем основывается выбор ключевого поля файла?

4.5. Что означает выражение “один ключ больше другого”? Как это определяется? Как это представляется символически? Объясните, почему это может зависеть от ЭВМ?

4.6. Как в ASCII обеспечивается кодирование пробела символов и цифр?

4.7. Для списков порядок должен устанавливать: отношение между ячейками в списке или отношение между записями в файле.

4.8. Дайте точное определение для списков:

а) порядка по возрастанию;

б) порядка по убыванию.

4.9. Что такое граф? Какие функции выполняют линии и точки при представлении графа? Как он используется?

4.10. Что вы понимаете под отношением? Какое отношение называется:

а) рефлексивным;

б) симметричным;

в) транзитивным?

4.11. Определите, являются ли приведенные ниже отношения рефлексивными, симметричными и (или) транзитивными. Подтвердите это примерами и контрпримерами:

а) отец; б) брат; в) родной брат или сестра; г) равен; д) не равен; е) больше чем; ж) между; з) меньше чем; и) предшествует; к) любит.

4.12. Что такое ориентированный граф? Что такое дуга? Что показывает стрелка? Какие типы отношений представляет граф?

4.13. Что такое маршрут? Какое он имеет значение в графе списка? в схеме организации?

4.14. Что означают определения элементарный, простой и непростой? Что такое цикл?

4.15. а) Какая разница между петлей и циклом?

б) Может ли граф иметь цикл и не иметь петли? Объясните.

в) Может ли граф иметь петлю и не иметь цикла? Объясните.

4.16, а) Что такое связный граф и связный орграф?

б) Может ли орграф быть связным, а соответствующий ему граф нет? Объясните.

4.17. Дайте простое определение дереву, направленному дереву.

4.18. Что представляют в схеме организации лист и корень7 Что можно сказать о такой схеме, если число корней больше одного? Как представить графически схему обычной организации?

4.19. Должен ли граф программы

а) иметь древовидную структуру? Объясните;

б) иметь древовидную структуру с двоичным ветвлением? Объясните;

в) быть транзитивным? Объясните.

4.20. а) Что такое раскрашенный граф?

б) Может ли орграф быть раскрашенным? Объясните.

4.21. Дан состав семьи: прародители – Петр, Евдокия.

Их дети – Евгений, Ольга, Галина.

Евгений был женат на Валентине, от их брака родились дети – Надежда и Владимир. Надежда вышла замуж за Виктора у них сын Валерий.

Ольга замужем за Георгием, у них дочь Наталья, у Натальи сын Николай

Галина замужем первым браком за Виктором, от их брак родился Александр, второй брак Галины с Владимиром, от их брака родились Светлана и Наталья.

1.Сконструировать полную схему семьи с использованием отношений:

А) «родитель», «супруг»

Б) «отец», «мать», «муж», «жена», «сестра», «брат», «дядя», «тетя», «кузен» и т.д.

В) построить раскрашенный граф, данной семьи.

Рейтинг@Mail.ru