Файл: Общее математическое обеспечение для решения задач экономики, статистики и управления на ЭВМ Минск-32 тезисы докладов и сообщений..pdf

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

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

Способ задания информации и режим работы подобраны так, чтобы максимально приблизить их к методике, принятой в СМО «Минск-32» (см. описание транслятора, сборщика, корректора). Минимизация требуемой для программы оперативной памяти достигается путем введения динамического распределения МОЗУ, что особенно важно при организации многопрограммной работы ЭВМ.

Исходными данными для работы программы, реализующей вышеназванный метод служат:

1.Магнитная лента с информацией, которую необходимо корректировать.

2.Магнитная лента, на которую выводится скорректирован­ ная информация.

3.Магнитная лента с корректировочной информацией (в не­ которых частных случаях может отсутствовать).

4.Заказ на корректировку на перфокартах.

Заказ на корректировку состоит из двух частей:

1) собственно заказа, в котором указываются имена магнит­ ных лент, участвующих в корректировке;

2) массива изменений, который содержит информацию для работы корректировочной программы.

Для записи ЗАКАЗа и изменений используются бланки для записи СИМП. Как и в других методах корректировки, информа­ ция для внесения изменений задается с помощью корректировоч­ ных операторов. Это операторы вставки, замены и удаления информационных совокупностей. Привязка осуществляется сог­ ласно номерам зон исходных массивов. Имя корректируемого массива записывается в графе «Идентификатор», а в соответ­ ствующих строках бланка для записи СИМП записываются кор­ ректировочные операторы. Они содержат сведения о номерах

42

вставляемых, заменяемых или удаляемых зон информационных массивов.

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

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

Вслучае удаления перечисляются номера удаляемых зон ис­ ходного массива. Если массив корректировочных операторов со­

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

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

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

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

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

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

43

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

Метод был разработан и внедрен на Вычислительном центре ЦСУ СССР. Он успешно применялся при обработке массовой информации по выборочному обследованию пенсионеров Совет­ ского Союза и ряде других задач.

В. Э. Гурари, Е. М. Дынькин, С. X. Шапиро

ПРОГРАММЫ КОРРЕКЦИИ ИСХОДНЫХ ТЕКСТОВ

ИАНАЛИЗА СЕГМЕНТОВ НА МЛ

Впроцессе обработки программ, написанных на алгоритми­ ческих и других языках, часто возникает потребность в оператив­ ной коррекции исходных текстов, записанных на МЛ. Заводские программы СМО «Минск-32» ВКОР и ВКОР1 рассчитаны на заранее подготовленные на перфокартах заказ и массив измене­ ний, что обременительно при небольших изменениях. Для устра­ нения этих неудобств создана программа КОРПМ, предназна­ ченная для коррекции стандартно оформленного текста, записан­ ного на магнитной ленте. Программа позволяет вставлять, заме­ нять и удалять строки. Номера корректируемых строк и текст изменений вводятся с пишущей машинки пульта оператора. Программа следит за правильной нумерацией строк и листов и может выдавать на АЦПУ протокол коррекции, в котором ука­ заны все внесенные изменения. Опыт эксплуатации программы КОРПМ показывает, что она сокращает время отладки программ

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

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

44

ций. Для этих целей созданы программы СПРОС (справка о сег­ менте на МЛ) и РБРЩК (разборщик).

Программа СПРОС анализирует записанный на МЛ сегмент

ивыдает на АЦПУ следующую информацию о нем:

—имя сегмента;

—имя МЛ с сегментом;

—длины основного, рабочего и индексного полей сегмента;

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

встеках сегмента;

—имена и длины общих областей модуля;

—начальные значения базисов;

—адреса описаний внутренних программ модуля, характер описания (ОПР, ОПРС и ОПРЗ) и признак наличия или отсут­ ствия подпрограммы в сегменте;

—адреса описаний модуля в сегменте;

—распечатываются в удобном виде словари обозначений заданных модулей.

Программа РБРЩК разбирает сегмент на составляющие его модули и приводит их к требуемому языком загрузки виду. После разборки модули можно использовать для сборки обычным об­ разом.

Опыт показывает, что эксплуатация программ СПРОС и РБРЩК расширяет возможности использования СМО «Минск-32».

Л. П. Гайфуллина, В. С. Зубов

ГЕНЕРАТОР ПРОГРАММ ВНУТРЕННЕГО УПОРЯДОЧЕНИЯ ИНФОРМАЦИИ ДЛЯ ЭВМ

«МИНСК-32»

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

данных.

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

45

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

Эффективность сортировки на ЭВМ зависит от многих факто­ ров:

—от конструкции ЭВМ (комплекса операций, емкости ОЗУ, устройства ввода — вывода);

—от особенностей сортируемых данных (величины записей, длины и числа ключей сортировки, распределения числового зна­ чения ключа);

—от примененного метода упорядочения.

При выборе метода упорядочения пользователь имеет воз­ можности :

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

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

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

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

В работе описывается попытка создания генератора программ внутреннего упорядочения для ЭВМ «Минск-32».

При разработке генератора учитывались следующие требо­ вания:

—минимум требований к пользователю и максимум удобств;

—специализация алгоритмов с максимальным использова­ нием средств математического обеспечения ЭВМ «Минск-32»;

—эффективность работы генератора исходя из времени и затраченных ресурсов.

Генератор организован по модульному принципу как в силу преимущества модульного принципа, так и в силу подобной

46

организации всего математического обеспечения «Минск-32». Генератор содержит базовый набор проблемно-ориентирован­

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

Создание собственной операционной системы генератора позволило бы резко сократить число прерываний при обращении к стандартному математическому обеспечению.

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

Модуль определения реализует схему выбора проблемного модуля на основании управляющей информации, задаваемой пользователем, и в соответствии с предоставляемыми ресурсами. Схема выбора оперирует временными оценками алгоритмов упо­ рядочения с учетом их конкретной реализации на ЭВМ «Минск-32» и величины резерва ОЗУ.

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

Наиболее часто используемые зависимости:

Т = Tin, m, К, N, q),

где п — объем упорядочиваемых данных в числе записей; m — длина одной записи в числе ячеек или разрядов;

R — величина резерва памяти в числе ячеек или разрядов;

N — длина признака, по которому производится упорядо­ чение в разрядах;

q — величина, зависящая от исходной упорядоченности дан

ных.

При внутреннем упорядочении основными операциями яв­ ляются операции сравнения и обращения к памяти, поэтому удобно временные оценки давать с учетом числа сравнений и об­ ращений к памяти

47