ОГРАНИЧЕНИЕ КОЛИЧЕСТВА РАЗЛИЧНЫХ ОПРОБУЕМЫХ ВЕКТОРОВ ДЛЯ ПОЛУЧЕНИЯ ВСЕХ РЕШЕНИЙ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ ВТОРОЙ КРАТНОСТИ НА МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

  • А.К. Мельников АО «Вычислительные решения»
Ключевые слова: Вероятность, точное распределение, точное приближение, система линейных уравнений, алгоритмическая сложность, многопроцессорная вычислительная система

Аннотация

Статья посвящена нахождению всех целочисленных неотрицательных решений сис-
темы линейных уравнений второй кратности типов, далее с.л.у., методом последователь-
ного опробования векторов на принадлежность к решениям системы. Рассматривается
количество различных векторов, опробование которых на принадлежности к решениям
с.л.у. приведет к получению всех решений с.л.у. Вектор опробований с.л.у. состоит из эле-
ментов определяющих число знаков алфавита, имеющих одинаковое число вхождений в
выборку. С.л.у. связывает между собой число вхождений элементов всех типов в рассмат-
риваемую выборку, мощность алфавита, объём выборки и ограничение на максимальное
число вхождений знаков алфавита в выборку. Решение с.л.у. является основой расчета
точных распределений вероятностей значений статистик и их точных приближений ме-
тодом второй кратности, где в качестве точных приближений выступают Δточные
распределения, отличающиеся от точных распределений не более чем на заранее заданную,
сколь угодно малую величину Δ. Величина, выражающая количество опробуемых векторов,
является одной из величин определяющих алгоритмическую сложность метода второй
кратности, без знания значения которой нельзя определить параметры выборок, для ко-
торых при ограничениях на вычислительный ресурс могут быть рассчитаны точные рас-
пределения и их точные приближения. Количество различных опробуемых векторов рас-
сматривается в условиях ограничения на максимальное значение числа вхождений элемен-
тов алфавита в выборку, так и без ограничений. Найдены аналитические выражения, по-
зволяющие для любых значений мощности алфавита, объёма выборки и ограничения на
значение максимального числа вхождений знаков алфавита в выборку вычислять количест-
во опробований различных векторов для получения всех целочисленных неотрицательных
решений системы линейных уравнений второй кратности типов. Вид полученного анали-
тического выражения для количества опробований векторов позволяет использовать его
при изучении алгоритмической сложности расчетов точных распределений и их точных
приближений с заранее указанной точностью Δ.

Литература

1. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy [Reconfigurable
computing systems], under the general ed. of I.A. Kalyaeva. Taganrog: Izd-vo YuFU, 2016,
472 p. ISBN 978-5-9275-1918-7.
2. Korneev V.V. Vychislitel'nye sistemy [Computing systems]. Moscow: Gelios ARV, 2004,
512 p. ISBN 5-85438-117-6.
3. Mel'nikov A.K. Avtomatizatsiya protsedury analiza soobshcheniy na gibridnykh vysokoproizvoditel'nykh
vychislitel'nykh kompleksakh [Automation of message analysis procedure
on hybrid high performance complexes], Superkomp'yuternye tekhnologii (SKT-2016): Mater.
4-y Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Proceedings of the 5 th All-Russia
Conference on Supercomputer Technologies (SCT-2016)]: in 2 vol. Rostov-on-Don: Izd-vo
YuFU, 2016, pp. 69-73. ISBN 978-5-9275-2039-8 (T. 1).
4. Chepovskiy A.M. Informatsionnye modeli v zadachakh obrabotki tekstov na estestvennykh
yazykakh [Information models in tasks of processing of natural language texts]. Moscow:
Natsional'nyy otkrytyy universitet «INTUIT», 2015, 228 p. ISBN 978-5-9556-0176-2.
5. Dvoynikova A.A., Karpov A.A. Analiticheskiy obzor podkhodov k raspoznavaniyu tonal'nosti
russkoyazychnykh tekstovykh dannykh [Analytical review of approaches to Russian text sentiment
recognition], Informatsionno-upravlyayushchie sistemy [Information and Control Systems],
2020, No. 4, pp. 20-30. Doi: 10.31799/1684-8853-2020-4-20-30.
6. Mal'tsev G.N., Dzhumkov V.V. Additivnaya granitsa veroyatnosti oshibki v diskretnom kanale
peredachi informatsii s pomekhoustoychivym kodirovaniem i gruppirovaniem oshibok [Additive
boundary of error probability in a discrete data transmission channel with noise-immune
coding and grouping of errors. Informatsionno-upravliaiushchie sistemy], Informatsionnoupravlyayushchie
sistemy [Information and Control Systems], 2020, No. 4, pp. 78-86. Doi:
10.31799/1684-8853-2020-4-78-86.
7. Dikiy D.I. Metod obnaruzheniya DoS-atak na prikladnom urovne v setyakh ≪izdatel'-
podpischik≫ [DoS attack detection at application level in publish-subscribe networks],
Informatsionno-upravlyayushchie sistemy [Information and Control Systems], 2020, No. 4,
pp. 50-60. Doi: 10.31799/1684-8853-2020-4-50-60.
8. Ronzhin A.F. Asimptoticheskaya lokal'naya otnositel'naya effektivnost' (ALOE) kriteriev soglasiya
[Asymptotic local relative efficiency (ALRE) of fitting criteria], Tez. dokladov Vsesoyuznoy
konferentsii «Veroyatnostnye metody v diskretnoy matematike» [Reports of All-USSR conference
“Probabilistic methods in discrete mathematics”]. Petrozavodsk, 1983, pp. 70-71.
9. Mel'nikov A.K. Sravnenie effektivnosti obrabotki tekstov pri primenenii v statisticheskikh
kriteriyakh tochnykh i predel'nykh priblizheniy bazovykh raspredeleniy veroyatnostey
znacheniy testovykh statistik [Comparison of the efficiency of text processing when applying
accurate and limiting approximations of basic probability distributions values of test statistics
in statistical criteria], Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied
and industrial mathematics], 2018, Vol. 25, Issue 4, pp. 375-378. ISSN 0869-8325. Available
at: https://tvp.ru/conferen/vsppmXIX/repso114.pdf (accessed 14 October 2019).
10. Mel'nikov A.K. Primenenie tochnykh raspredeleniy v protsedure dvukhetapnoy obrabotki
tekstov [Application of exact distributions in the procedure of two-step text processing],
Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied and industrial mathematics],
2018, Vol. 25, Issue 2, pp. 89-95. ISSN 0869-8325. Available at:
https://tvp.ru/conferen/vsppmXIX/repso051.pdf (accessed 24 January 2019).
11. Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti simmetrichnykh
additivno razdelyaemykh statistik i oblast' primeneniya predel'nykh raspredeleniy [The complexity
of calculating the exact probability distributions of symmetric additive-separated statistics
and the application of limit distributions], Doklady TUSUR [Proceedings of Tomsk State
University of Control Systems and Radioelectronics]. Tomsk, 2017, Vol. 20, No. 4, pp. 126-
130. ISSN 1818-0442.
12. Mel'nikov A.K. Metodika rascheta raspredeleniya veroyatnostey znacheniy simmetrichnykh
additivno razdelyaemykh statistik, priblizhennykh k ikh tochnomu raspredeleniyu [A method
for calculating the probability distribution of values of symmetric additively separated statistics
that are close to their exact distribution], Nauchnyy vestnik NGTU [Science bulle-tin of the
Novosibirsk state technical university], 2018, No. 1 (70), pp. 153-166. ISBN 1814-1196.
Doi: 10.17212/1814-1196-2018-1-153-166.
13. Kendall M.G., St'yuart A. Teoriya raspredeleniy [Distribution theory]. Moscow: Nauka, 1966,
302 p.
14. Zuev Yu.A. Sovremennaya diskretnaya matematika: Ot perechislitel'noy kombinatoriki do
kriptografii XXI veka [Modern Discrete Mathematics: From Enumerative Combinatorics to
XXI century Cryptography]. Moscow: LENARD, 2019, 720 p. (Fundamentals of information
security No. 17). ISBN 978-5-9710-5660-7.
15. Kramer G. Matematicheskie metody statistiki [Mathematical methods of Statistics]: trans.
from engl. Moscow: Mir, 1975, 648 p.
16. Mel'nikov A.K., Ronzhin A.F. Obobshchennyy statisticheskiy metod analiza tekstov,
osnovannyy na raschete raspredeleniy veroyatnosti znacheniy statistik [Generalized statistical
method of text analysis based on the calculation of probability distributions of statistical values],
Informatika i ee primeneniya [Informatics and its Applications], 2016, Vol. 10, Issue 4,
pp. 91-97. ISSN 1992-2264.
17. Shurygin V.A. Slozhnostnyy metod teorii algoritmov [The complexity method of the theory of
algorithms]. Moscow: Knizhnyy dom "LIBROKOM", 2009, 200 p.
18. Fisher R.A. Statisticheskie metody dlya issledovateley [Statistical methods for researchers]:
trans. from engl. Moscow: Gosstatizdat, 1958, 73 p.
19. Alekseev V.E. Diskretnaya matematika: ucheb. posobie [Discrete mathematics. Training manual].
Nizhniy Novgorod: Nizhegorodskiy gosuniversitet, 2017, 139 p.
20. Knut D.E. Iskusstvo programmirovaniya dlya EVM. T. 3. Sortirovka i poisk [The art of computer
programming. Vol. 3. Sorting and search]. Moscow: Mir, 1978, 844 p.
21. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2020664143. Raschet
chisla resheniy sistemy lineynykh uravneniy vtoroy kratnosti tipov. Pravoobladatel' Kolodzey
A.V. Avtor: Kolodzey A.V. i Mel'nikov A.K. Zayavka № 2020662473. Data postupleniya 19
oktyabrya 2020 g. Data gosudarstvennoy registratsii v Reestre pro-gramm dlya EVM 9
noyabrya 2020 g. [Certificate of state registration of computer software № 2020664143. Calculation
of the number of solutions to a system of linear equations of the second multiplicity of
types. Proprietor Kolodzey A.V. Authors: Kolodzey A.V и Melnikov A.K. Application
№ 2020662473. Date of filing – October 19, 2020. Date of state registration in the Register of
computer software – November 9, 2020].
22. Kholl M. Kombinatorika [Combinatorics]. Moscow: Mir, 1970, 424 p.
23. Riordan Dzh. Vvedenie v kombinatornyy analiz [Introduction to combinatorial analysis]. Moscow:
Izd-vo inostrannoy lit., 1963, 288 p.
Опубликован
2021-07-18
Выпуск
Раздел
РАЗДЕЛ IV. ИНФОРМАЦИОННЫЙ АНАЛИЗ И РАСПОЗНАВАНИЕ ОБРАЗОВ