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

  • A.K. Мельников
Ключевые слова: Вероятность, статистика, точное распределение, точное приближение, вектор кратности типов, линейное уравнение, алгоритмическая сложность

Аннотация

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

Литература

1. 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
exact and marginal approximations of the basic probability distributions 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 January 2019).
2. Zelyukin N.B., Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti
znacheniy statistik i oblast' primeneniya predel'nykh raspredeleniy [The complexity of calculating
accurate probability distributions of statistical values and the scope of limit distributions],
Elektronnye sredstva i sistemy upravleniya: Mater. dokladov XIII Mezhdunar. nauch.-
prakt. konf. (29 noyabrya – 1 dekabrya 2017 g.) [Electronic means and control systems: Materials
of reports of the XIII International Scientific and Practical Conference (November 29 –
December 1, 2017)]: in 2 parts. Part 2. Tomsk: V-Spektr, 2017, pp. 84-90. Available at:
https://storage.tusur.ru/files/115115/2017-2.pdf (accessed 13 July 2018).
3. 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]. Tomsk, 2017, Vol. 20, No. 4, pp. 126-130. ISSN 1818-0442.
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. Mel'nikov A.K. Analiz tochnykh i predel'nykh priblizheniy raspredeleniy veroyatnostey
znacheniy statistik [Analysis of exact and marginal approximations of probability distributions
of statistical values], Superkomp'yuternye tekhnologii (SKT-2018): Mater. 5-y Vserossiyskoy
nauchno-tekhnicheskoy konferentsii [Supercomputer Technologies (SCT-2018): Proceedings
of the 5th All-Russian Scientific and Technical Conference]: in 2 vol. Vol. 1. Rostov-on-Don;
Taganrog: Izd-vo YuFU, 2018, pp. 100-104. ISBN 978-9275-2834-9.
6. 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).
7. 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 calculation of probability distribution of statistical values] Informatika i ee primeneniya
[Informatics and its applications], 2016, Vol. 10, Issue 4, pp. 91-97. ISSN 1992-2264.
8. Mel'nikov A.K. Primenenie tochnykh i predel'nykh priblizheniy raspredeleniy veroyatnostey
znacheniy statistik pri reshenii zadachi obrabotke tekstov [Application of exact and limit approximations
of statistics probability distributions for the problem of text processing], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 8 (202), pp. 114-135.
9. Mel'nikov A.K. Otnositel'naya algoritmicheskaya slozhnost' rascheta tochnykh priblizheniy
raspredeleniy veroyatnostey znacheniy statistik [Relative algorithmic complexity of exact approximations
for probability distributions of statistics values], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2019, No. 7 (209), pp. 35-45.
10. Mel'nikov A.K. Napravlenie modernizatsii chastotnogo metoda rascheta tochnykh
raspredeleniy veroyatnostey znacheniy statistik [Direction of modernization of the frequency
method of exact probability distributions for statistics values], Obozrenie prikladnoy i
promyshlennoy matematiki [Review of applied and industrial mathematics], 2017, Vol. 24, Issue
5, pp. 324-325. Available at: https://tvp.ru/conferen/vsppmXVIII/kisso073.pdf (accessed
12 July 2018).
11. Zuev Yu.A. Sovremennaya diskretnaya matematika: Ot perechislitel'noy kombinatoriki do
kriptografii XXI veka [Modern discrete mathematics: From enumerative combinatorics to
cryptography of the XXI century]. Moscow: LENARD, 2019, 720 p. (Fundamentals of
Information security No. 17). ISBN 978-5-9710-5660-7.
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. Kramer G. Matematicheskie metody statistiki [Mathematical methods of statistics]. Moscow:
Mir, 1975, 648 p.
14. Knut D.E. Iskusstvo programmirovaniya dlya EVM. T. 3. Sortirovka i poisk [The art of computer
programming. Vol. 3. Sorting and Searching]. Moscow: Mir, 1978, 844 p.
15. Spisok TOR 500 55-y redaktsiya ot 22 iyunya 2020 goda [TOP 500 list 55 edition of june 22,
2020].
16. Voevodin V.V., Voevodin Vl.V. Parallel'nye vychisleniya [Parallel computing]. St. Petersburg:
BKhV-Peterburg, 2002, 608 p. ISBN 5-94157-160-7.
17. Murav'ev S.A. Istoriya otechestvennoy elektronnoy vychislitel'noy tekhniki [History of Russian
electronic computer technology], under the General editorship of the Director of the Department
of radio-electronic industry of the Ministry of industry and trade of Russia S.V.
Khokhlov. Moscow: OOO "Izdatel'skiy dom "Stolichnaya entsiklopediya", 2017, 680 p. ISBN
978-5-903989-34-8.
18. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy [Reconfigurable
computing systems], under the General ed. of I.A. Kalyayev. Taganrog: Izd-vo YuFU, 2016,
472 p. ISBN 978-5-9275-1918-7.
19. Sachkov V.N. Vvedenie v kombinatornye metody diskretnoy matematiki [Introduction to combinatorial
methods of discrete mathematics]. Moscow: Nauka. Gl. red. fiz.-mat. lit., 1982, 384 p.
20. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2018664980. Raschet
veroyatnostey znacheniy statistiki maksimal'noy chastoty. Pravoobladatel' Mel'nikov A.K. Avtor:
Mel'nikov A.K. i Zelyukin N.B. Zayavka № 2018662123. Data postupleniya 01 noyabrya 2018
g. Data gosudarstvennoy registratsii v Reestre programm dlya EVM 27 noyabrya 2018 g. [Certificate
of state registration of computer software № 2018664980. Calculation of probabilities of
maximum frequency statistics. Proprietor – A.K. Melnikov. Authors: A.K. Melnikov and
N.B. Zeliukin. Application № 2018662123. Date of filing – November 01, 2018. Date of state
registration in the Register of computer software – November 27, 2018].
21. Mel'nikov A.K. Otnositel'naya algoritmicheskaya slozhnost' rascheta tochnykh priblizheniy
raspredeleniy veroyatnostey znacheniy statistik [Relative algorithmic complexity of exact approximations
for probability distributions of statistics values], Modeli, metody i tekhnologii
intellektual'nogo upravleniya (IU-2019): Mater. 12-y Mul'tikonferentsii po problemam
upravleniya (MKPU-2019) [Models, methods and technologies of intelligent management (IU-
2019): Materials of the 12th Multi-Conference on Management Problems (ICPU-2019)]: in 4 vol.
Vol. 1. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2019, pp. 108-112. ISBN 978-5-9275-3189-9.
Опубликован
2021-02-25
Выпуск
Раздел
РАЗДЕЛ II. МАТЕМАТИЧЕСКОЕ И СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ СУПЕРКОМПЬЮТЕРОВ