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

         

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


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

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

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

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

эквивалентными,стандартной является следующая процедура.
представляются векторами признаков
соответственно, где каждая компонента означает признак объекта, выраженный целым значением. Считается, что
эквиваленты тогда и только тогда, если
где
— целое, называемое порогом.



Содержание раздела