Лекции по количественной оценке информации
Вопросы - Компьютеры, программирование
Другие вопросы по предмету Компьютеры, программирование
p>
Если в строке массива несколько повторяющихся участков, то можно вместо вставлять специальные символы, указывающие на необходимое число пропусков.
Например, если обозначить количество пропусков, соответственно, Х - 2; Y - 3; Z - 5, то исходный и свернутый массивы будут иметь вид:
Процесс развертывания массива осуществляется следующим образом: длина строки известна, количество пропусков определяется символами X, Y, Z
Пропущенные цифры заполняются по аналогичным разрядам предыдущей строки. Условием перехода на следующую строку является заполнение предыдущей строки.
Метод Г. В. Ливинского основан на том, что в памяти машины хранятся сжатые числа, разрядность которых меньше разрядности реальных чисел. Эффект сжатия достигается за счет того, что последовательности предварительно упорядоченных чисел разбиваются на ряд равных отрезков, внутри которых отсчет ведется не по их абсолютной величине, а от границы предыдущего отрезка. Разрядность чисел, получаемых таким образом, естественно, меньше разрядности соответствующих им реальных чисел [18, 21].
Для размещения в памяти ЭВМ М кодов, в которых наибольшее из кодируемых чисел равно N, необходим объем памяти
С ростом N длина кодовой комбинации будет расти как . Для экономии объема памяти Q, число , где выражение в скобках - округленное значение до ближайшего целого числа, разбивают на L равных частей. Максимальное число в полученном интервале чисел будет не больше . Величина определяет разрядность хранимых чисел, объем памяти для их хранения будет не больше . Если в памяти ЭВМ хранить адреса границ отрезков и порядковые номера хранимых чисел, отсчитываемых от очередной границы, то определяет разрядность чисел для выражения номера границы (в последнем интервале должно быть хотя бы одно число); объем памяти для хранения номеров границ будет где - число границ между отрезками (это число всегда на единицу меньше, чем число отрезков). Общий объем памяти при этом будет не больше
(89)
Чтобы найти, при каких L выражение (89) принимает минимальное значение, достаточно продифференцировать его по L и, приравнять производную к нулю. Нетрудно убедиться, что будет при
(90)
Если подставить значение в выражение (89), то получим. значение объема памяти при оптимальном количестве зон, на, которые разбиваются хранимые в памяти ЭВМ числа,
(91)
Для значений при вычислениях можно пользоваться приближенной формулой
(92)
При поиске информации в памяти ЭВМ прежде всего определяют значение и находят величину интервала между двумя границами
Затем определяют, в каком именно из интервалов находится искомое число х
После этого определяется адрес искомого числа как разность между абсолютным значением числа и числом, которое является граничным для данного интервала.