image001.gif

Содержание

Барковский Е. А. (ПетрГУ) Оптимальное управление двумя очередями, работающими по принципу настраиваем 3

Шац В. Н. Инварианты матрицы данных в задаче классификации

17

 

Abstracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Barkovsky E. A. (Petrozavodsk) Optimal control of two queues working on the principle of custom queues 33

Shats V. N. (SPb) Invariants of matrix data in a classication problem

34

 

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 12

Выпуск 2

Издательство С.-Петербургского университета, 2 0 1 6


УДК 519.712 ВКК 32.811.7

С82

Ответственный редактор: д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия:           

Б. Т. Поляк (ипу ран),

А. В. Соколов  (ИПМИ КарНЦРАН),

П. С. Щербаков (ипу ран)

Стохастическая оптимизация в информатике. Том 12 (Вып. 1) / Под ред. О. Н. Граничина — СПб.: Издательство С.-Петербургского университета, 2016. — 36 с.

 ISSN 1992-2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2—11 — в 2006—15 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск десятого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2015-16 г. на математико-механическом факультете С.-Петербургского университе­та под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №13-07-00250-а.

Издание предназначено для специалистов в области информатики, сту­дентов старших курсов и аспирантов, обучающихся на специальностях, связанных с обработкой информации.

ББК 32.811.7

©   Авторы статей, 2016

 


Оптимальное управление двумя очередями, работающими по принципу настраиваемых очередей

Е. А. Барковский

Петрозаводский государственный университет, 

barkevgen@gmail.com

В работе предлагается математическая модель и решается задача оптимального разбиения общей памяти для настраиваемой очереди, представлен- ной в виде двух очередей в случае их последовательного циклического представления. На нечетном шаге допускаются операции включения элементов в одну из очередей (с заданными вероятностями), а на четном шаге – операции исключения элементов из очередей. Наряду с последовательным, возможно и параллельное выполнение операций с очередями.

Ключевые слова: Структуры данных, настраиваемые очереди, случайные блуждания, регулярные марковские цепи.

Список литературы

[1]Cisco Systems Cisco IOS 12.0 Quality of Service. Cisco Press. 1999.

[2]Knuth D. The Art of Computer Programming. Vol. 1. Addison-Wesley. 2001.

[3]Yao A.C. An Analysis of a Memory Allocation Scheme for Implementing Stacks // SIAM Journal on Computing. 1981. Vol. 10. P.398–403.

[4]Flajolet P. The Evolution of Two Stacks in Bounded Space and Random Walks in a Triangle // Lecture Notes in Computer Science. 1986. Vol. 223. P. 325–340.

[5]Louchard G., Schott R. Probabilistic Analysis of Some Distributed Algorithms // Lecture Notes in Computer Science. 1990. Vol. 431. P.239–253.

[6]Louchard G., Schott R., Tolley M., Zimmermann P. Random Walks, Heat Equation and Distributed Algorithms // Journal of Computational and Applied Mathematics. 1994. No. 53. P. 243–274.

[7]Maier R.S. Colliding Stacks: A Large Deviations Analysis // Random Structures and Algorithms. 1991. No. 2. P. 379–421.

[8]Соколов А.В. О распределении памяти для двух стеков // Авто- матизация эксперимента и обработки данных. 1980. С. 65–71.

[9]Aksenova E.A., Sokolov A.V. The Optimal Implementation of Two FIFO-Queues in Single-Level Memory // Applied Mathematics. 2011. Vol. 2. P. 1297–1302.

[10]Sokolov A.V., Drac A.V. The Linked List Representation of n LIFO-Stacks and/or FIFO-Queues in the Single-Level Memory // An Information Processing Letters. 2013. Vol. 13. P. 832–835.

[11]Аксенова Е.А., Драц А.В., Соколов А.В. Оптимальное управление n FIFO-очередями на бесконечном времени // Информационно- управляющие системы. 2009. № 6. С. 46–54.

[12]Драц А.В., Соколов А.В. Математический анализ процесса работы с M FIFO-очередями // Стохастическая оптимизация в информатике. 2012. Т8. № 2. С. 75–82.

[13]Sedgewick R. Algorithms in C++. Parts 1-4. Addison-Wesley. 1998.

[14]Барковский Е.А., Соколов А.В. Оптимальное управление двумя параллельными FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2015. № 5. С. 65–71.

[15]Кемени Дж., Снелл Дж. Конечные цепи Маркова. Наука. 1960.

http://www.htmlpublish.com/newTestDocStorage/DocStorage/0fc0589095bc4e4fa86812111bb21a11/sb12_2_images/sb12_217x1.jpg

Инварианты матрицы данных в задаче классификации1

В. Н. Шац, д. т. н. 

Санкт-Петербург

vlnash@mail.ru

В статье представлено решение задачи классификации, основанное на вычислении матриц индексов, которые аппроксимируют инварианты матрицы данных. Индексами служат номера интервалов значений признаков, а объекты c одинаковыми индексами образуют гранулы. Из соотношения длин гранул получены частоты индексов признаков для всех классов обучающей выборки, которые одинаковы для соответствующих объектов контрольной выборки. Из них для произвольного объекта найдены оценки вероятности объекта в каждом классе и затем наиболее вероятный класс объекта. Высокая точность метода и устойчивость его результатов подтверждена для девяти баз данных из репозитория UCI.

Ключевые слова: Искусственный интеллект, алгоритм классификации, анализ данных, гранулированные вычисления.

Список литературы

[1]Bishop C. Pattern Recognition and Machine Learning, Springer.2006. 738 p.

[2]Hastie T., Tibshirani R., and J. Friedman R. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer-Verlag. 2009. 764 p.

[3]Murphy K. Machine Learning. A Probabilistic Perspective. MIT Press: Cambridge, Massachusetts, London. 2012. 1098 p.

[4]Zadeh L. Outline of a new approach to the analysis of complex systems and decision processes // IEEE Trans. on Systems, MAN, and Cybernetics. Vol. SMC-3. No. 1. Jan. 1973. P. 28–44.

[5]Zadeh L. Fuzzy sets and information granularity // Advances in Fuzzy Set Theory and Applications, N. Gupta, R. Ragade, and R. Yager (Eds.). Amsterdam. 1979. P. 3–18.

[6]Calabrese M., Amato A., Di Lecce V., and V. Piuri V. Holonic- granularity holonic modelling // J Ambient Intell. Human. Comput. V. 1(3). 2010. P. 199–209.

[7] Yao J.., Vasiliacos V., and Pedrycz W. Granular computing: perspective and challenges // IEEE Trans. on Cybernetics. Vol. 43. No. 6. 2013. P. 1977–1989.

[8] Шац В.Н. Двухуровневая метрика и новая концепция машинного обучения // Стохастическая оптимизация в информатике.   Т. 9. Вып. 1. 2013. С. 128-143.

[9]Шац В.Н. О новой технологии вычислений в машинном обуче- нии // “Нейроинформатика-2011”. XVII Всероссийская научно- техническая конференция. Сборник научных трудов. ч. 2. M: МИ- ФИ. 2015. С. 148–158.

[10]Asuncion A., Newman D.J. UCI Machine Learning Repository. Irvine CA: University of California. School of Information and Computer Science. 2007.

[11]Ashby W. Ross An Introduction to Cybernetics. 2nd ed. Chapman and Hall. London. 1957. 295 p.

[12]Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оце- нивания при почти произвольных помехах. — М.: Наука. 2003. 291 c.

[13]Cios K.J. and Kurgan L. CLIP4: Hybrid inductive machine learning algorithm that generates inequality rules // Inform. Sci. 163. 2004. P. 37–83.