Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

KS=XN(1)=1;

K=1: NZ(KS=1) =13  KS=KS+1=2 ;

K=2: NZ(KS=2) =4 3 ;

a₃₁= 0;

a₄₁=? K1=XL(1)=1; K2=XL(2) -1=2;

KS=XN(1)=1;

K=1: NZ(KS=1)=14 KS=KS+1=2;

K=2: NZ(KS=2)=4=4;

a₄₁=LN(2);

a₃₂-? K1=XL(2)=3; K2=XL(3) -1=4-1=3;

KS=XN(2)=2;

NZ(KS=2)=43;

a₄₂=0;

Сравнение обычной и компактной схем хранения

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

10.3. Представление целочисленных и булевых разреженных матриц

Хранение целочисленных списков.

Целые списки заслуживают специального рассмотрения из-за их важности для технологии разреженных матриц. Элементы списка принадлежат множеству (1, 2, ..., n); некоторые из них могут повторяться, хотя случай, когда все они различны, пред­ставляет для нас особый интерес. Пусть т — число элементов списка; п называется размером списка. Будем говорить, что список разреженный, если т < п. Целый список можно хранить в компактной форме, пользуясь массивом (скажем, JA) длины, не меньшей т.

Так, для списка 3, 11, 7, 4:

позиция	1	2	3	4	5	6
JA	3	11	7	4
M	4

Кроме массива JA нужно еще хранить (посредством перемен­ной М) число т элементов списка; для нашего примера т — 4. Пустой список опознается по нулевому значению М. Чтобы вклю­чить в список новый элемент, достаточно увеличить М на единицу и затем записать новый элемент в позицию с номером М. Чтобы исключить элемент из позиции i, мы просто переносим в эту позицию последний элемент и уменьшаем М на единицу. Разу­меется, если требуется сохранять упорядоченность целых чисел, то включение или исключение элемента в какой-то позиции вы­зовет сдвиг всех элементов, находящихся справа от нее.

Целые списки с повторениями или без них могут храниться как связные линейные или кольцевые списки посредством мас­сива JA длины, не меньшей т, и дополнительного массива NEXT. Этот тип хранения также является ком­пактным и потому вполне подходит для разреженных списков, Для целых списков с различными элементами имеется важная альтернатива. Такой список может храниться одним массивом (скажем, JA) длины п или большей в форме связного списка, линейного или кольцевого. Если в приведенном выше примере использовать кольцевой связный список, а несущественные для нас позиции пометить символом х, то получим

позиция	1	2	3	4	5	6	7	8	9	10	11	12
JA			11	3			4				7
IP	3

Число, хранимое в каждой позиции JA, дает одновременно зна­чение элемента списка и адрес следующего элемента; тем самым дополнительный массив NEXT становится излишним. Для входа в цепь необходим еще указатель IP, задающий позицию первого числа в списке. Этот тип хранения называют расширенным, в противоположность компактному, потому что для него нужен массив длины по крайней мере п. В любом месте списка несложно включить или исключить элемент, не меняя порядка, в котором хранятся прочие элементы. Предположим, например, что i, k — два последовательных элемента списка, находящегося в массиве JA, так что JA (i) = k. Пусть теперь требуется вставить j между i и k. Тогда мы просто полагаем

JA (j) ← JA (i); JA (i) ← j

Если, наоборот, хотим исключить k, то полагаем

JA (i)← JA (k)

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

позиция	1	2	3	4	5	6	7	8	9
JA					5
IP	5

Пустой список можно опознать по нулевому или отрицательному значению указателя входа. Одно из главных применений расширенной схемы — это хра­нение нескольких непересекающихся списков, т. е. списков, не имеющих общих элементов. В большинстве случаев все списки имеют одинаковый размах, но чтобы наше рассуждение стало более общим, будем считать п максимальным из размеров отдельных списков. Все списки можно хранить в одном и том же массиве (скажем, JA), длины п или большей. Необходим еще массив указателей входа (скажем, IP). Достаточно проиллюстрировать предлагаемый способ хранения примером. Рассмотрим три не­пересекающихся целых списка:

1-й список: 2, 8, 6, 3; 2-й список: 5, 4, 9; 3-й список: 7, 1, 10.

Они могут быть размещены как кольцевые связные списки в одном массиве длины 10:

позиция	1	2	3	4	5	6	7	8	9	10
JA	10	8	2	9	4	3	1	6	5	7
IP	2	5	7

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

Представление целочисленных матриц в ЗУ ЭВМ.

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

P int (log₂ N + 0,5) (2)

где int - процедура выделения целой части. Если известно, что все элементы заданной целочисленной матрицы А не превосходят некоторого числа N_max

a_{i j <} N_max ,

то для хранения каждого из них достаточно Р_max двоичных разрядов. Значение Р_max определяется по (2) при N=N_max. Обычно Р_max в несколько раз меньше длины S разрядной сетки ЭВМ.

Пусть для определенности

Тогда возможно в k раз уменьшить объем памяти, необходимой для хранения матрицы А. Для этого достаточно в каждое машинное слово длиной S записывать k элементов исходной матрицы, отводя каждому из них Р_max разрядов.

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

где l_k - длина k -ой строки 1  j  l _i

Пример: Пусть дана целочисленная матрица:

При описанном методе хранения она будет представлена последовательностью:

В=41352772431652623374,

где подчеркнуты элементы, задающие длины строк.

При таком представлении число хранимых элементов матрицы определяется по формуле:

где n - число строк в матрице.

Способы представления булевых матриц

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

Булевыми называются целочисленные матрицы, элементы которых могут принимать только два значения: 0 и 1. Каждому элементу матрицы соответствует некоторое логическое высказывание, причем единичному значению элемента соответствует утверждение истинности этого высказывания, а нулевому - утверждение его ложности. Таким образом, элементы булевых матриц - это логические переменные.

Характеристики

Список файлов лекций