УДК 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.
Инварианты матрицы данных в задаче
классификации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.
