Комбинаторные алгоритмы для программистов



   blackjack strategy has many variations that are possible to play here.            

Проблема представления: коды, сохраняющие разности


Чрезвычайно важной проблемой в комбинаторных вычислениях является задача эффективного представления объектов, подлежащих обработке. Она возникает потому, что обычно имеется много возможных способов представления сложных объектов более простыми структурами, которые можно заложить в языки программирования, но не все такие представления в одинаковой степени эффективны с точки зрения времени и памяти. Более того, идеальное представление зависит от вида производимых операций.

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

  1. Необходимы целые, больше имеющихся непосредственно в аппаратном оборудовании.
  2. Необходимы только небольшие целые, и требуется сэкономить память, упаковывая их по несколько в одну ячейку.
  3. Действия с целыми производятся не общепринятыми арифметическими операциями.
  4. Целые используются для представления других типов объектов, и необходимо иметь возможность легко обращать целое в соответствующий ему объект и обратно.

Проблемы кодов, сохраняющих разности, касаются случаев 2 и 3. В задачах распознавания образов и классификации для решения вопроса, будут ли два объекта

X,Y
эквивалентными,стандартной является следующая процедура.
X,Y
представляются векторами признаков
(x_{1},x_{2},\ldots,x_{f}),(y_{1},y_{2},\ldots,y_{f})
соответственно, где каждая компонента означает признак объекта, выраженный целым значением. Считается, что
X,Y
эквиваленты тогда и только тогда, если
\sum_{i=1}^f|x_{i}-y_{i}|\le t,
где
t
— целое, называемое порогом.




Содержание  Назад  Вперед