78 2. Начала молекулярных вычислений
рабатываются параллельно. Можно сказать, что эта парадиг-
ма составляет суть молекулярных вычислений вообще.
Как и в [291], мы проиллюстрируем стикерную модель на
примере решения задачи о минимальном покрытии, ЗМП. Она
может быть сформулирована следующим образом. По данно-
му конечному множеству S = {1, 2, . . . , p} и конечному набо-
ру {C
1
, . . . , C
q
} подмножеств множества S нужно найти наи-
меньшее подмножество I ⊆ {1, 2, . . . , q} такое, что ∪
i∈I
C
i
= S.
Конечно, полный перебор всех 2
q
подмножеств I решает эту
задачу.
Опишем решение, использующее стикерную модель. Запо-
минающие цепочки состоят из k = p + q подцепочек. Исходная
пробирка N
0
есть (p + q, q)-библиотека. (Следует подчеркнуть,
что широкое применение стикерной модели возможно только
при условии, что уже имеются библиотеки определенных раз-
меров. Построение же запоминающих цепочек с k подцепочка-
ми с ростом k становится все более сложным.)
Обозначим через card(X) мощность множества X, т. е. чис-
ло элементов в X. Элементы множества C
i
, 1 6 i 6 q обозна-
чаются c
j
i
, 1 6 j 6 card(C
i
). Таким образом, каждый элемент
c
j
i
— это целое число от 1 до p.
Запоминающие комплексы в исходной пробирке N
0
со-
ответствуют всевозможным подмножествам I множества
{1, 2, . . . , q}. А именно, первые q участков комплекса, буду-
чи включены или выключены, показывают, какие из чисел
1, 2, . . . , q, принадлежат множеству I, отвечающему данному
комплексу. Последние p участков каждого запоминающего
комплекса M первоначально выключены, а по завершении
вычисления подцепочка с номером q + j, 1 6 j 6 p, оказы-
вается включенной в том и только в том случае, когда число
j принадлежит множеству C
i
для некоторого i из множества
индексов I, отвечающего комплексу M. Для этого с M про-
делываются следующие операции. Мы просматриваем первые
q подцепочек в M. Всякий раз, когда мы встречаем вклю-
ченную подцепочку (пусть она имеет номер i; включенные и
выключенные подцепочки р азлич аются с помощью операции