Критерии и методы оценки вычислительных алгоритмов

2. Критерии и методы оценки вычислительных алгоритмов.

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

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

Преимущества упорядоченных последовательных структур данных, в частности, хорошо видны на примере с операцией пересечения двух массивов, определяемой как выбор записей с ключевым признаком, значение которого есть и в первом и во втором массиве. Если исходные массивы длиною М записей каждый не отсортированы по указанному признаку, то пересечение массивов потребует выполнения С=КМ² сравнений пар признаков, где 0,5£К£1. Когда массивы отсортированы, С»2М.

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

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

С = М log₂М

и временем сортировки

T = t ´ C = tM log₂M,

где t—константа с размерностью времени.

Метод слияния использует для сортировки резерв памяти длиной в половину массива.

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

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

Формирование инвертированного массива ведется путем заполнения его адресами и ключами, взятыми из основного массива. В таблице приведен пример такого заполнения инвертированного массива. При этом выделяется участок памяти V₁ для хранения ключей и связанных с ними адресов записей основного массива.

Путем первого просмотра основного массива выполняется разметка памяти. Фиксируются адреса полей и значения ключей в каждой группе. В таблице они изображены столбцами, в каждом из которых имеются значение ключа и 4 адреса.

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

При первом просмотре основного массива производится р пересылок значений ключей в поле памяти V₁. Во время второго просмотра в инвертированный массив пересылаются М адресов записей основного массива. Сортировка групп методом слияния потребует времени tplog₂p. Наконец, уплотнение инвертированной структуры данных означает пересылку байт за байтом всего поля за исключением первой группы. Общее время формирования инвертированного массива составляет:

T = t₁(pl + Ml' + V₁)+ tplog₂p,

где t₁ — время пересылки байта, l — средняя длина ключа, l' — длина адреса, р — число разных значений ключей.

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

Среднее число сравнений, необходимое для построения бинарного дерева, равно: С=1,39М log₂М, если М достаточно велико. Формирование бинарного дерева требует больших затрат времени и памяти, чем формирование строчной структуры данных.

Построение неуплотненной табличной структуры данных заключается в создании вектора описания записей, вектора описания ключей и матрицы значений ключей. При этом выполняются пересылки адресов и ключей. Время формирования неуплотненной табличной структуры из m строк и п столбцов составляет:

T = t₁(l'(m + n) + l mn).

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

T = t₁l'(m + n) + mn(t + t₁) + tdlmn, К

где t — время одного сравнения и d = — — плотность ненулевых

 тп

значений ключевого признака (К — число ненулевых значений ключевого признака).

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

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

T = t₁l'(m + n) + mn (t + t₂) + t₁dmn(l + 21"),

где t₂ — время одной операции сложения, а 1"— длина поля, хранящего номер строки или столбца.

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

Уплотнение табличной структуры данных с помощью логической шкалы эффективнее по времени формирования структуры, чем метод индексных пар, так как t₁ < t₂и l < l + 2l".

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

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

3. Составление баланса преследует цель установить равенство итогов средств, находящихся в активе и пассиве.

Проведены ряд операций. В банке получен кредит в размере 1000 р. Деньги зачислены на расчетный счет. Приобретены материалы на сумму 540 р. Их покупка оплачена из кассы. Погашена задолженность поставщику за поставку леса на сумму 3780 р. Деньги перечислены с расчетного счета. Частично погашен кредит банка в размере 500 р. с расчетного счета. Из прибыли направлено в фонд материального поощрения 700 р.

Пусть информационный поток отражает результаты работы частного предприятия “ФИН” в течение одного дня.

Набор характеристик следующий:

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

·     своевременность поступления данных в базу

·     полнота отображаемых факторов

·     достоверность

Похожие работы

Информация, информационные системы и экономические информационные системы: основные понятия и взаимосвязь

Скачать

17526

1

1

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

Экономические информационные системы: принципы построения и классификация

Скачать

12514

2

1

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

Автоматизированные экономические информационные системы и их элементы

Скачать

16362

0

0

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

Экономические информационные системы и их составляющие

Скачать

49421

0

0

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