Аннотация.

Представлено решение задачи алгоритмического синтеза автоматных моделей марковских функций на основе укрупнения конечных цепей Маркова. Введены эквивалентные автоматные модели марковских функций. Определена зависимость сложности алгоритмической реализации автоматных моделей от размера стохастической матрицы, описывающей закон полученной укрупненной цепи Маркова, и длины имплицирующего вектора этой матрицы. Дана сравнительная оценка сложности рассматриваемых моделей.

Ключевые слова:

Цепь Маркова, стохастическая матрица, автономный вероятностный автомат, автоматные модели марковских функций, имплицирующий вектор, оценки сложности, укрупнение цепи.

Стр. 32-42.

 Полная версия статьи в формате pdf.

REFERENCES

1. Bukharaev R.G. Avtomatnoe preobrazovanie veroyatnostnykh posledovatelnostey // Veroyatnostnye metody i kibernetika. Vyp. 4. Kazan: Izd-vo KGU, 1966. S. 24-33.
2. Bukharaev R.G. Osnovy teorii veroyatnostnykh avtomatov. M.: Nauka, 1985. 287 s.
3. Levin B.R., Shvarts V. Veroyatnostnye modeli i metody v sistemakh svyazi i upravleniya. M.: Radio i svyaz, 1985. 312 s.
4. Davis A.S. Markov chains as random input automata. Amer. Math. Monthly, 1961, 68, 3, pp. 264-267.
5. Chentsov V.M. Ob odnom metode sinteza avtonomnogo stokhasticheskogo avtomata // Kibernetika. Kiev, 1968. №3. S. 32-35.
6. Pospelov D. A. Veroyatnostnye avtomaty. M.: Energiya, 1970. 88 s.
7. Bukharaev R.G., Zakharov V.M., Upravlyaemye generatory sluchaynykh kodov. Kazan: Izd-vo Kazan. un-ta, 1978. 160 s.
8. Gabbasov N.3. Zadacha ob implitsiruyushchem vektore i ee prilozheniyakh // Veroyatnostnye metody i kibernetika. Kazan: Izd-vo KGU, 1987. S. 36-50.
9. Kuznetsov S.Ye., Nurmeev N.N., Salimov F.I. Zadacha o minimalnom implitsiruyushchem vektore // Matematicheskie voprosy kibernetiki. Vyp. №3. Sbornik statey / Pod red. S.V. Yablonskogo. M.: Nauka, Gl. red. fiziko-matematicheskoy literatury, 1991. S. 199-216.
10. Zakharov V.M., Eminov B.F. Analiz algoritmov razlozheniya dvoichno-ratsionalnykh stokhasticheskikh matrits na kombinatsiyu bulevykh matrits // Informatsionnye tekhnologii, №3. M.: Novye tekhnologii, 2008. S. 54-59.
11. Chentsov V.M. Ob odnom metode sinteza avtonomnogo stokhasticheskogo avtomata // Kibernetika. Kiev, Kibernetika, 1968. №3. S. 32-35.
12. Romanovskiy V. Diskretnye tsepi Markova. M.:Gostekhizdat, 1949.436 s.
13. Kemeny J., Snell L. Finite Markov chains. Princeton: Van Nostrand Company. 1960. 210 pp. Kemeni D., Snell D. Konechnye tsepi Markova. M.: Nauka, 1970. 272 s.
14. Korolyuk V.S., Turbin A.F. Polumarkovskie protsessy i ikh prilozheniya. Kiev: Naukova Dumka, 1976. 184 s.
15. Zakharov V.M., Eminov B.F. Algoritmy ukrupneniya tsepey Markova // Vestnik Kazanskogo gosudarstvennogo tekhnicheskogo universiteta im. A.N. Tupoleva, №2 (vypusk 1), 2013. S.125-133.
16. Gambin, A., Pokarowski, P. A new combinatorial algorithm for large Markov chains. Proc. Computer Algebra in Scientific Computing, CASC'01, Springer, Berlin 2001, pp. 195-212. http://bioputer.mimuw.edu.pl/papers/aggr.pdf
17. Ferrari D. Otsenka proizvoditelnosti vychislitelnykh sistem. M.: Mir, 1981. 576s.
18. Franceschinis G., Muntz R. Bounds for quasi-lumpable markov chains. Los Angeles: University of California, 1993. 37 p.
19. Stewart W.J. Introduction to the numerocal solution of Markov chains, Princeton University Press, 1994.
20. Mazurenko I. L. Effektivnyy sposob vvedeniya metriki na mnozhestve nepreryvnykh SMM-avtomatov //Intellektualnye sistemy, tom 11, vypusk 3. M.: Izd-vo MGU, 2007. S. 593-608 (SMM - skrytaya markovskaya model).
21. Deundyak V.M., Zhdanova M.A. Polinomialnoe predstavlenie skrytoy polumarkovskoy modeli fergnesovskogo tipa // Vestnik VGU: sistemnyy analiz i informatsionnye tekhnologii, 2013, №2. S. 71-78.
22. Pogorelov B.A., Pudovkina M.A. Ob obobshcheniyakh markovskogo podkhoda pri izuchenii algoritmov blochnogo shifrovaniya // Prikladnaya diskretnaya matematika. Prilozhenie. Sentyabr 2014. № 7, 2014. S. 51-52.
23. Derisavi, S., Hermanns, H., Sanders, W. H.: Optimal State-Space Lumping in Markov Chains. Information Processing Letters 87 (6), 2003. pp.309–315.
24. Hillston J. Compositional Markovian modelling using a process algebra // Computations with Markov Chains, 1995, pp. 177-196.
25. Geiger B., Temmel C. Lumpings of Markov chains, entropy rate preservation, and highe-order lumpability // Advances in Applied Probability, 51(4), 2014. pp. 1114-1132.
27. Bolch G., Greiner S. Queuing Networks and Markov Chains Modeling and Performance Evaluation with Computer Science Application. Wiley. 2006. 896 p.
28. Katehakis M., Smit L. A Successive Lumping Procedure for a Class of Markov Chains // Probability in the Engineering and Informational Sciences 26 (4), 2012. pp 483-508.
29. Ponomarenko L.A., Melikov A.Z., Nagiev F.N. Analiz sistemy obsluzhivaniya s razlichnymi urovnyami prostranstvennykh i vremennykh prioritetov // Informatsionno-upravlyayushchie kompleksy i sistemy, № 2(18), 2006. S. 80-89.
30. Rozhkov M.I. Summirovanie markovskikh posledovatelnostey na konechnoy abelevoy gruppe//Diskretnaya matematika, №3, t.22, 2010. S.44-62.
31. Maksimov Yu.I. Nekotorye rezultaty dlya zadachi ukrupneniya sostoyaniy tsepey Markova // Trudy po diskretnoy matematike, №8. M.: Fizmatlit, 2004. S. 148-154.
32. Pokhodzey B.B. Slozhnost tablichnykh metodov modelirovaniya konechnykh diskretnykh raspredeleniy // Izv. Vuzov. Matematika. Kazan: Izd-vo KGU, 1985, №7. S. 45-50.
33. Lorents A.A. Sintez nadezhnykh veroyatnostnykh avtomatov. Riga: Zinatne, 1975. 187 s.
34. Eminov B.F., Zakharov V.M. Metody i algoritmy postroeniya i analiza polinomialnykh funktsiy nad konechnym polem na osnove stokhasticheskikh matrits. Saarbrucken: LAP Lambert Academic Publishing, 2011. 161 s.