УДК 519.21

Прискорене моделювання методом Монте-Карло кількості «хороших» перестановок на багатопроцесорному комплексі СКІТ-4

Перестановка (s₀, s₁, ... , s_{N - 1}) символів 0,1, ... , N - 1 називається «хорошею», якщо набір (t₀, t₁, ... , t_N-1), що утворюється за правилом t_i = i + s_i (mod N), i = 0, 1, ... , N - 1, також є перестановкою. Запропоновано метод прискореного моделювання, реалізація якого на багатопроцесорному комплексі СKIT-4 дозволяє оцінювати кількість «хороших» перестановок для N ≤ 305 з відносною похибкою, що не перевищує 1%. Наведено оцінки кількості «хороших» перестановок для N = 25, 35, ... , 305. Табл.: 3. Бібліогр.: 18 назв.

UDC 519.21

Fast simulation by the Monte Carlo method of the number of “good” permutations on multiprocessor computer SCIT-4

A permutation (s₀, s₁, ... , s_{N - 1}) of symbols 0,1, ... , N - 1 is called “good” if the set (t₀, t₁, ... , t_N-1) formed according to the rule t_i = i + s_i (mod N), i = 0, 1, ... , N, is also a permutation. A fast simulation method is proposed. Its implementation on multiprocessor computer SCIT-4 makes it possible to evaluate the number of “good” permutations for N ≤ 305 with relative error of only 1%. Estimates for the number of “good” permutations for N = 25, 35, ... , 305 are given. Tabl.: 3. Refs: 18 titles.

УДК 519.21

Ускоренное моделирование методом Монте-Карло количества «хороших» перестановок на многопроцессорном комплексе СКИТ-4

Перестановка (s₀, s₁, ... , s_{N - 1}) символов 0,1, ... , N - 1 называется «хорошей», если набор (t₀, t₁, ... , t_N-1), построенный согласно правилу t_i = i + s_i (mod N), i = 0, 1, ... , N - 1, также является перестановкой. Предложен метод ускоренного моделирования, реализация которого на многопроцессорном комплексе СКИT-4 позволяет оценить количество «хороших» перестановок для N ≤ 305 с относительной погрешностью, не превышающей 1%. Приведены оценки количества «хороших» перестановок для N = 25, 35, ... , 305. Табл.: 3. Библиогр.: 18 назв.

Ключові слова:

«хороша» перестановка, модифікований метод прискореного моделювання, незміщена оцінка, вибіркова дисперсія, відносна похибка.


ПОВНИЙ ТЕКСТ

Про автора(ів):

Кузнецов Николай Юрьевич, чл.-кор. НАН Украины, ведущий научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев; профессор Физико-технического института Национального технического университета «Киевский политехнический институт»,
e-mail: kuznetsov2016@icloud.com