Некоторые приложения двоичной лунной арифметики

Abstract

В общем виде задача извлечения корня n–й степени из языка формулируется следующим образом: для заданного языка A и заданного nN требуется найти все языки B такие, что A = B n . Эта теоретическая задача тесно связана с практической задачей декодирования сообщений, где требуется найти разбиение кодового сообщения на элементарные коды, соответствующие символам алфавита источника. Ранее мы получили решение задачи извлечения корня n–й степени для языков специального вида, а именно содержащих всевозможные слова длины от n  n 1 до n  n 2 (n 1  n 2 ). Рассматриваемая задача была сведена к задаче о рюкзаке и решена методом программной реализации предложенных алгоритмов. Были получены количественные оценки числа корней n–й степени, при различных значениях n и k, где k – мощность множества {n 1 , n 1 +1,…, n 2 }. При n=2 последовательность количества квадратных корней совпала с последовательностью, опубликованной на сайте онлайн энциклопедии целочисленных последовательностей http://oeis.org/A191701, и представляющей собой число двоичных чисел длины k, квадраты которых не содержат нулей в двоичной лунной арифметике. В данной статье нами установлено и теоретически обосновано соответствие между операциями в двоичной лунной арифметике и в кольце многочленов с целыми коэффициентами. На основе установленного соответствия разработан алгоритм, который позволяет решать, как частную задачу нахождения корней из языка, так и более общую задачу о рюкзаке с применением операций в лунной двоичной арифметике. Проведено сравнение программной реализации предложенного алгоритма с известными классическими вариантами решения задачи о рюкзаке. In general, the problem of extracting the root of n-th order from a language is stated as follows: for a given language A and a given nN it is required to find all the languages B, such that A = B n . This theoretical problem is closely related to the practical task of decoding messages, where it is required to find the fragmentation of the coded message into elementary codes, which correspond with certain symbols of the source alphabet. We previously found a solution to the problem of extracting the n-th root for languages of a special form, which is containing all the possible words of the length from n  n 1 to n  n 2 (n 1  n 2 ). The considered problem was converted to a knapsack problem and solved by software implementation of the algorithms, suggested in the paper. Quantitative estimates of the number of roots of the n-th degree were obtained, at different values of n and k, where k is the cardinal number of the set {n 1 , n 1 +1,..., n 2 }. For n=2 the sequence of the number of square roots coincided with the sequence that was published on the website of the online encyclopedia of integer sequences http://oeis.org/A191701. This sequence represented in base 2 lunar arithmetic, number of binary numbers x of length k such that x  x has no zeros. In the paper, we have established and theoretically proven a correspondence between operations in binary lunar arithmetic and in the ring of polynomials with integer coefficients. Based on the established correspondence we have developed an algorithm, which enables us to solve both special problem of finding roots from a language and more general knapsack problem, using operations in binary lunar arithmetic. Program implementation of the suggested algorithm has been compared to well- known classical alternate solutions of a knapsack problem.