5. Еще о суперприведении

Суперприведение, как метод, охватывает большое число NP-полных задач, а поэтому можно его применять:
   - при проектировании чипов (СБИС) для электронной промышленности [25], [26];
   - при осуществлении логического анализа в самых разных сферах  [27], [28];
   - для проектирования эффективных компиляторов различных языков программирования и в первую очередь для языков логического программирования типа Пролог  [29];
   - для анализа последовательностей ДНК  [30] и во многих других случаях, начиная от теории переключательных схем и кончая теорией графов. Даже перечень  NP-полных задач трудно осуществим, поскольку он составляет тысячи наименований.

Прорыв, обусловленный суперприведением, открывает труднообозримые возможности. В самом деле, как уже говорилось в  п. 3, названия "суперприведенная" и "сверхлегкая" задача могут рассматриваться как синонимы и, таким образом, задача, считавшаяся труднорешаемой, алгоритмом суперприведения превращается в сверхлегкую задачу. Такое преобразование задачи может рассматриваться как процесс ее структуризации. Задача была (или казалась) труднорешаемой, пока она не была структуризирована. Значит, процесс преобразования, в результате которого некоторые операторы были исключены, а другие заменены вновь образованными из тех, что входили в текст задачи, может рассматриваться как процесс структуризации.

Такой процесс структуризации сродни процессу обучения, где по-видимому происходят аналогичные явления. Поэтому к суперприведению применяются приемы, аналогичные приемам обучения. Имеется ввиду, что для суперприведения всей задачи вначале выполняется ее сегментация. Затем применяется суперприведение каждого сегмента. Потом применяется суперприведение всей задачи, где уже каждый сегмент суперприведен.

Сама задача сегментации представляет определенный интерес. Но имеются и естественные процессы сегментации. Они возникают в процессе поблочного логического описания проектируемого устройства. Применение программ суперприведения позволяет на этапе проектирования системами CAD (computer-aided design) получать лишь задачи сверхлегкорешаемые.

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

5 а). Использование суперприведения на практических задачах.

  Первая страница