Составители:
Рубрика:
Существует несколько представлений, удовлетво- ряющих пере-
численным критериям, и обычно САВ используют два или три из
них.
6. Плотные и разреженные представления
Обычно различают два типа представлений: плотные и разре-
женные. На наш взгляд больше соответствуют содержанию терми-
ны полные и частичные представления.
Традиционно этим понятиям не придают чёткого математиче-
ского содержания, поскольку они касаются возможных реализа-
ций и носят обычно утилитарный характер. Следуя этой тради-
ции, можно сказать, что представлением какого-либо класса объ-
ектов называется представление, ориентированное на экономное (в
том или ином смысле) представление выделенного класса объектов.
Полным представлением называется представление, не обладающее
упомянутым свойством.
Например, сравним следу щие два представления многочлена:
1) представление многочлена a
0
+ a
1
x + . . . + a
n
x
n
таблицей его
коэффициентов
[a
0
a
1
. . . a
n
], (6.1)
2) представление многочлена списком пар упорядоченных чисел
(коэффициент, степень), где пара с нулевым коэффициентом про-
пускается, так что многочлен 1 + x
10
представляется в виде списка
(1, 0), (1, 10). (6.2)
Заметим, что здесь следует ввести ещё представление нулевого
многочлена (оно должно быть особым).
Если считать, что под каждое число отводится одинаковая па-
мять (не зависящая от числа), то первое представление экономнее,
если число ненулевых слагаемых больше entier(n/2), иначе эконом-
нее второе представление (здесь, конечно, не у читываются допол-
нительные технические детали).
Второе представление принято называть разреженным, а первое
плотным представлением многочлена. Согласно нашей терминоло-
гии и то, и другое представление можно называть (первое – от-
носительно подкласса многочленов, число ненулевых слагаемых в
45
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
