РАСПАРАЛЛЕЛИВАНИЕ ОБХОДА ДЕРЕВА ПОИСКА ДЛЯ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ НА КЛАСТЕРНОЙ СИСТЕМЕ В.А.Беляев, Н.Е.Тимошевская Томский государственный университет Введение Задача о рюкзаке относится к классу комбинаторно-логических за-
дач, связанных с нахождением подмножества конечного множества с
заданными свойствами, причем она известна как труднорешаемая за-
дача, лежащая в классе NP-полных задач [1]. Этот факт обусловил
возможность применения данной задачи в криптографии для создания
криптосистем с открытым ключом [2]. Необходимость решения задачи
о рюкзаке возникает при попытке вскрытия криптосистемы c откры-
тым ключом рюкзачного типа, а также при анализе её стойкости.
В принципе, любую задачу о рюкзаке можно решить тривиальным
перебором всех возможных подмножеств. Некоторые из известных
последовательных алгоритмов решения задачи о рюкзаке основаны на
построении и обходе специального дерева поиска решений[3]. Обход
дерева может быть организован по нескольким ветвям одновременно и
независимо, что позволяет использовать параллельные вычисления.
