Файл: Зайцев Н.Г. Информационное и математическое обеспечение АСУП.pdf

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

Процесс сортировки маосива информации в общем случае может быть схематично представлен следующим образом:

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

Сортировать информацию, размещенную в оператив­ ной памяти, можно: включением; обменом; объединени­ ем; разрядной сортировкой; выборкой записи с наимень­ шим (наибольшим) значением признака; вычислением адреса по ее признаку; методом Шелла; сортировкой с использованием матричного каталога; разрядным обме­ ном и т. д. Алгоритмы большинства из этих методов сортировки несложны, программы' компактны. Напри­ мер, сущность сортировки методом выборки состоит в том, что из всех сортируемых записей выбирают запись, имеющую наименьшее (наибольшее) значение признака. Эту запись помещают на первое место в фиксируемой последовательности. Потом из оставшихся записей сно­ ва выбирают запись с наименьшим (наибольшим) зна­ чением признака и т. д. Алгоритмы большинства мето­ дов описываются в работах [1, 4].

107

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

Анализ выше упомянутых методов сортировки на ос­ нове этого критерия дает возможность утверждать сле"- дующее: время сортировки для большинства из методов прямо пропорционально N2, где N — количество записей в массиве; те методы, время сортировки для которых сравнительно небольшое, требует большого дополнитель­ ного объема оперативной памяти.

Одним из методов внутренней сортировки, отвечаю­ щим как минимуму затрат времени, так и минимуму до­ полнительного объема оперативной памяти, является метод ступенчатой группировки [7]. Алгоритм метода основывается на вычислении адреса записи по ключу сортировки и является очень экономичным с точки зре­ ния использования МОЗУ и времени сортировки, причем признак может быть распределен как равномерно, так и неравномерно.

Сортировка массивов осуществляется внутренней сор­ тировкой массива по частям, а затем — их слиянием.

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

Доступ к данным. При решении задач необходимо обеспечить доступ к нужным элементам хранимой ин­ формации или же к местам их будущего хранения. Раз­ решение этого вопроса состоит из трех аспектов: сопо­ ставление; поиск; передача.

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

108

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

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

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

определении последовательности операций переноса между полями памяти при их выполнении.

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

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

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

109

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

Функцию a=A{q), где а — адрес размещения эле­ мента, значение которого равно q, назовем адресной функцией. Она сюръективна, так как одно и то же зна­ чение может размещаться в нескольких адресах. Обла­ стью ее определения является все множество значений, однако в каждом конкретном случае будет рассматри­ ваться частичное определение, присущее только задан­ ному элементу. Функцию, обратную адресной q—Q(a), где Q = A~\ назовем функцией размещения. Эта функ­ ция инъективна, так как в одном адресе может быть раз­ мещено только одно значение. Важным свойством вы­ числительной машины является то, что операция чтения дает значение функции размещения в данном адресе.

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

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

Q ( f l ) 7зад ~

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

110

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

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

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

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

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

Каталог — это упорядоченная по возрастанию или по убыванию последовательность значений какого-либо элемента данного массива с указанием адресов записей, к которым это значение относится. Например, для мас­ сива «Кадры» может быть составлен каталог по номеру специальности, по которому отыскиваются данные о ра­ ботниках с заданной специальностью.

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

1 П

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

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

Каталоги, главным образом, строят для основных элементов данных массива, по которым осуществляется частый поиск данных. По составленным каталогам мож­ но быстро определять адреса на магнитной ленте, где находятся требуемые записи в соответствующих масси­ вах. Для поиска записи с заданным признаком могут быть применены способы последовательного деления списка каталога пополам и непосредственного просмот­ ра по каталогу. Первый способ обеспечивает нахожде­ ние требуемой величины приблизительно за N = log2 п операций сравнения, где п — общее число характеристик каталога. Этот способ необходим при большой длине каталога, когда непосредственный просмотр является очень медленным. Второй способ может быть применен для небольших каталогов, когда на просмотр идет мало времени.

Таким образом, с помощью каталога получают отно­ сительные адреса требуемых записей на магнитной лен­ те. Этот набор адресов упорядочивают так, чтобы счи­ тывание с магнитной ленты происходило по возрастанию адресов и одним прогоном магнитной ленты можно было сосчитать все требуемые записи в МОЗУ. При необходи­ мости данная совокупность записей является уже отдель­ ным подмассивом и записывается на внешние накопители или она является только предметом для разовой обра­ ботки и после работы не сохраняется.

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

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

112

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

в местах деления. Вследствие упорядоченности массива

вслучае неравенства можно определить половину массива,

вкоторой следует вести поиск, и затем осуществить поиск уже только в этой части и так последовательным

делением пополам, пока не найдется запись.

4. ПРОГРАММЫ ОБЩЕГО ПРИМЕНЕНИЯ

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

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

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

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

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

Возможны различные алгоритмы программ, исполь­ зуемых при сортировке информации. Однако с точки зрения использования процедуры имеет смысл разделе­ ние сортировок на два класса:

внутренняя сортировка, когда сортируется массив, размещенный в оперативной памяти;

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

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

ОБРАБОТКА ЕДИНИЦ ИНФОРМАЦИИ

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

114

по 1-му обобщенному адресу, сравнивается со словом, размещенным по 2-му адресу. Слова считаются равны­ ми, если Д \ —Д 2 и каждый символ 1-го слова равен со­ ответствующему символу 2-го слова. В случае равенства в ячейку результата засылается 0, в противном случае засылается 1;

МОД-3 — в слове, размещенном в указанном обоб­ щенном адресе, определяется длина части слова до пер­ вого из указанных разделителей. Если в слове нет последних, искомая длина принимается равной длине всего слова.

Параметры обращения: обобщенный адрес 1-го слова; обобщенный адрес 2-го слова; модификация подпро­

запись, или же для извлечения его из записи. Имеет че­ тыре модификации:

МОД-1— число из заданной ячейки заносится в за­ данную запись в соответствии с его описанием;

МОД-2 — число извлекается из записи и пересыла­ ется в заданную ячейку в соответствии с указанным в описании типом;

МОД-3 — число извлекается из записи, преобразует­ ся в число с плавающей запятой и пересылается в за­ данную ячейку;

МОД-4 — число извлекается из записи, преобразует­ ся в целое число и пересылается в заданную ячейку.

Параметры обращения; адрес ячейки для числа; адрес описания числа; адрес начала записи, с которой выполняется операция; модификация.

Подпрограмма перевода числа в машинный код предназначена для перевода числа, представленного в коде ГОСТ 10859—64, в машинный код. Имеет четыре

модификации:

А40Д-1 — число преобразуется в машинное число в восьмеричной системе счисления в форму с плавающей запятой4,