книги из ГПНТБ / Зингер И.С. Обеспечение достоверности данных в автоматизированных системах управления производством

Понятие «списка» и «списковой структуры» данных уни­ версальное. Например, структуру данных типа «дерево» можно представить как некоторую структуру, образую­ щую списки с иерархической ссылкой, между элементами списков. В этом случае деревья не должны иметь мно­ гократных ссылок, так как это может привести к более чем одному пути, сходящемуся па данном элементе или к циклам и контурам из элементов списков этой структу­ ры. «Цепная», или «решетчатая», структура является структурой как с иерархической, так и с многократной ссылкой [16]. Цепные списки фундаментально исследова-^ ны А. И. Китовым [10].

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

«Дерево» — направленный граф, в котором есть един и только один узел, называемый корнем, такой, что для любого узла х существует один и только один путь, начи­ нающийся с корня и кончающийся узлом я» [17, стр. 58]Г Существуют и другие определения дерева. Например, деревом называется связный граф, не содержащий циклов; такой граф, в частности, не имеет и кратных ребер. Из определения дерева вытекает также, что для каждой пары его вершин существует единственная соединяющая их цепь. Если граф, вообще говоря, не связный, не содержит циклов, то каждая его связная компонента будет деревом. Узлы дерева распределены по ярусам. На первом яру­ се находится только корень; к /-му ярусу принадлежат

все узлы, путь к которым от корня имеет длину / — 1. Множество узлов, путь к которым от узла» ж имеет длину 1 называется частным множеством узла х.

Многие структуры, называемые в литературе «деревья­ ми», имеют более сложную систему перекрестных ссылок по сравнению с тем, что допускает прямое определение де­ ревьев в работе [17].

Рассмотрим некоторые типы структур данных, органи­ зация которых может быть интерпретирована в виде де­ рева.

В работе [18] представлена информационная структура,

22

(за исключением узлов последнего уровня) состоят ровно из двух элементов. В каждом частном множестве один узел условно называется левым, другой — правым.

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

Узлу дерева х соответствует группа ячеек рабочего поля, содержащих код некоторого признака Rx и три адреса, два из которых—начальные адреса групп ячеек,

узла х. Построение дерева выполняется таким образом, что значения узлов левой ветви любого узла со значением R меньше Rx, а значения узлов правой ветви — больше [17].

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

Базовый каталог, или каталог нулевого уровня, может служить каталогом инвентарного перечня материалов. Тогда каталоги уровня 1 являются, например, каталогами перечня складов, объемами запасов по каждому материа­ лу, списком поставщиков и т. п. Каталогами уровня 2 слу­ жат каталоги отдельных секций на складах, адресная кни­ га поставщиков и т. д.

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

Матричная организация информационных массивов предполагает хранение экономических данных предприя­ тия или министерства в памяти ЭВМ в табличной форме. Количество таблиц и их размеры определяются организа­ ционной структурой предприятия, а также технологиче­ скими связями подразделений предприятия. Наибольшее влияние на структуру таблиц оказывает разнообразие и взаимосвязь технико-экономических показателей пред­ приятий [19].

\~ Любая таблица в общем случае имеет вид табл. 2. Как принято, наименованиями строк таблиц служат наименования объектов, а наименования граф (столбцов)

23

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

Значения характеристик (ац) могут выражаться чис­ лами и алфавитно-цифровым текстом. Вычисляемые ац могут быть функцией значений характеристик как данной таблицы, так н других таблиц. Значение характеристики (aji) одной таблицы может быть объектом или группой объ­ ектов других таблиц.

Запись информационных таблиц в память ЭВМ произ­ водится с разверткой по столбцам, т: е. в явном виде за­ даются связи значений характеристик с их наименования­ ми, а связи значений характеристик с объектами отра­ жаются позициями характеристик в столбце. Такая за­ пись вызвана необходимостью производить расчеты в

^ большинстве случаев не для отдельных объектов, а для

• класса характеристик.

При составлении информационных таблиц обычно ис­ пользуют классификацию объектов по фунциональному признаку (перечни наименований объектов). Наряду с наименованиями объектов и характеристик на входах таб­ лицы задаются признаки (шифры) объектов (строк), ото­ бражающие родо-видовые отношения или отношения ти^ па «целое — часть» с объектами как этой таблицы, так и с объектами других таблиц (табл. 3).

24

может быть отличным от нуля (равен 1), т. е. матрица является нуле-единичной. Это указывает на родо-видовые отношения двух объектов — объект Nf может быть «ча­ стью» только одного объекта («целого») таблицы tk.

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

Более сложные отношения между двумя комплексами объектов представлены в табл. 4.' Это могут быть отноше­ ния такого вида, как связь объектов — наименований продукции — с объектами — наименованиями материаль­ но-сырьевых ресурсов. Эта связь, как правило, имеет ко­ личественные оценки (а$ч). Кроме того, наименования ма­

25

табл. 2, построенной для комплекса объектов Np, служат характеристиками (например, рубрики: сырье со стороны, вспомогательные материалы, топливо, полуфабрикаты, реагенты и т. д.). Хранить такую таблицу в развернутом виде нерационально, так как она содержит незначитель­ ное число а)% =j= 0. (Как правило, в практических задача a)i =f= 0 не превышает 2%) . Однако необходимо учитывать возможность появления элемента, отличного от нуля, с любыми координатами [19].

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

Из других способов использования табличного метода организации информационных массивов следует указать на организацию памяти типа «матричный каталог» [17].

Рассмотрим соответствующие оценки эффективности для некоторых типов информационных структур.

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

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

26

однако, затруднен поиск элемента при решении задач й при исключении либо изменении содержимого элемента.

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

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

Эффективность различных структур информационных массивов оценивается путем сравнения определенных по­ казателей — критериев эффективности, в качестве кото­ рых могут быть выбраны:

время поиска Тп элемента информации в массиве, вы­ раженное числом циклов поиска. Здесь цикл поиска — совокупность арифметических и логических операций, необходимых для осуществления одной идентификации родного сравнения заданного кода с кодом элемента в ма­

шинном массиве); число сдвигов элементов массива при внесении измене­

ний — S;

объем дополнительной памяти, выраженной числом элементов массива,— W.

Для последовательных неупорядоченных списков бу­ дем иметь следующие оценки.

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

Максимальное время поиска одного элемента, если он имеется в данном массиве, по способу перебора равно времени, которое необходимо для просмотра всех элемен­ тов массива:

27

При этом число сдвигов элементов массива при внесе­ нии изменений и объем дополнительной памяти равны нулю.

Для последовательных упорядоченных списков соот­ ветствующие оценки будут следующие.

Среднее время поиска при поиске последовательным делением массива пополам

объем дополнительной памяти, выраженный числом элементов, W = 0.

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

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

Включение нового члена в список производится путем замены адресных связей: в предшествующем члене про­ ставляется адресная связь, указывающая на новый член, в новом члене проставляется адресная связь, взятая из предшествующего члена [10].

Рассмотрим соответствующие оценки для списковых структур, организованных в виде двоичных деревьев. Дерево можно определить как совокупность точек, орга­ низованных по уровням. Дерево из тг-уровней является симметричным, если его (п — 1)-уровней заполнены пол­ ностью.

28

sa начало иерархии (корень дерева), т. е. начальную стро­ ку, с которой начинается поиск по дереву, то можно по­ строить N\ несимметричных деревьев. Среднее время поис­ ка одного элемента в этом случае равно:

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

деления массива пополам Тср.п — log2 iV [20].j

Каждый элемент требует Кх ячеек для заполнения ад­ ресов, причем Кх не зависит от числа ячеек К для разме­ щения элементов массива и W — N-Kx.

Необходимо отметить трудность и даже невозможность (по крайней мере на данном этапе) получения соответ­ ствующих точных оценок для сложных типов информа­ ционных структур.

Главные этапы обеспечения концентрации информации АСУ и организации централизованного нормативного

хозяйства следующие:

определение организационных форм ведения норма­ тивного хозяйства предприятия в условиях АСУ;

упорядочение и подготовка нормативно-справочной информации к вводу в ЭВМ;

формирование массивов нормативно-справочных данных в памяти машины;

организация внесения изменений в нормативную базу АСУ;

организация использования нормативно-справочной информации и автоматизация нормативно-плановых рас­ четов с помощью ЭВМ.

Применение ЭВМ требует изменения существующих организационных форм административно-управленческих работ, в частности, приспособления их к новым тех­ ническим условиям. Большинство структурно-организа­ ционных изменений, связанных с применением ЭВМ, воз­ никает с созданием на предприятиях информационновычислительных центров (ИВЦ). Учитывая немаловажное значение нормативно-справочных данных в общей сово-

^--купности экономической информации, рекомендуется организовать в составе ИВЦ самостоятельные подразделе­ ния — бюро нормативного хозяйства (БНХ).

29

На стадии перехода к АСУ основными функциями ЁНХ должны быть: упорядочение, систематизация и шифров­ ка имеющейся на предприятии нормативно-справочной информации; получение недостающих нормативно-спра­ вочных данных; запись их на перфорационные носители информации; разработка инструкций по их сбору, обра­ ботке и обновлению.

Упорядочение и подготовка нормативно-справочных данных к условиям АСУ включает проведение следующих работ:

определение перечня и краткое описание задач, под­ лежащих решению с помощью ЭВМ;

установление информационного содержания постоян­ ных массивов нормативно-справочных данных;

составленпе списка первичных документов, содержа­ щих нормативно-справочные данные;

разработку технологии получения недостающих нор­ мативов;

определение объемов базисных массивов нормативносправочных данных;

разработку типовых форм первичной нормативно-спра­ вочной документации для упорядочения нормативно-спра­ вочной информации;

выбор типа перфорационных носителей информации; разработку рациональной системы кодирования нор­

мативно-справочной информации.

Методика отбора задач, подлежащих решению в АСУП в первую очередь, а также на этапах развития и усовер­

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

30

Наиболее трудоемкой и ответственной задачей пред­ ставляется организация массивов нормативно-справочных данных в памяти ЭВМ (на магнитных лентах внешней памяти) и разработка алгоритмов и программ работы с массивами. Формирование постоянных массивов норма­ тивно-справочных данных в памяти ЭВМ основывается, как правило, на следующих трех принципах: 1) создание дифференцируемых (локальных) массивов для каждой отдельно решаемой задачи АСУ; 2) хранение массивов нормативно-справочных данных на внешних запоминаю-

"~щих устройствах (ЗУ) в виде документов принятой на пред­ приятии стандартной формы; 3) создание эталонных мас­ сивов с упорядоченным последовательным расположением элементов массива, из которых в процессе решения отдель­ ных задач формируются вспомогательные (промежуточ­ ные) рабочие массивы нормативно-справочной информа­ ции.

К недостаткам первого принципа организации инфор­ мационных массивов следует отнести:

многократное дублирование данных в рабочих масси­ в а х ;

необходимость .внесения изменений одновременно во все рабочие массивы;

большая трудоемкость формирования рабочих масси­ вов и входных документов;

сложное хозяйство обслуживания хранимых данных (сравнительно большое количество магнитных лент);

необходимость подготовки новых массивов на ЗУ в случае эволюции АСУ (подключение новых задач), что вызывает увеличение количества магнитных лент, пере­ смотр каталогов и т. д.;

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

Но этот принцип имеет и определенные преимущества: возможность разработки структур входных массивов дифференцированно, вне связи с рабочими массивами дру­

гих задач системы; оперативный вызов необходимых массивов;

возможность дифференцированно внедрять отлаженные задачи в производство.

^- Принцип записи информации на ЗУ в виде документов без привязки к конкретным задачам тоже имеет ряд су­ щественных недостатков:

31