Семейства деревьев смежности и критерий дополнительности

  • Анатолий Григорьевич Максимов Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия
  • Арсений Дмитриевич Завалишин Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия
  • Максим Викторович Абрамов Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия
  • Александр Львович Тулупьев Санкт-Петербургский государственный университет, Университетская наб., 7–9, 199034, Санкт-Петербург, Россия
Ключевые слова: графы смежности, теория графов, инварианты на графах, алгебраические байесовские сети

Аннотация

Статья направлена на обобщение понятий графа производной и первообразной графа для графов, обладающих магистральной связностью. Формулируются и доказываются теоремы о магистральной связности графа производной и о графе первообразной магистрально связных графов. Теоретическая и практическая значимость заключается в изучении структур, которые будут лучше всего подходить для работы с алгебраическими байесовскими сетями и, таким образом, становятся одной из
целей их машинного обучения. Отметим новизну взгляда на задачу, а точнее, на изучение вопроса, для каких семейств графов существует набор нагрузок, семейство МГС над которым в точности совпадает с заданным.

Биографии авторов

Анатолий Григорьевич Максимов, Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия

Младший научный сотрудник лаборатории теоретических и междисциплинарных проблем информатики СПИИРАН; студент кафедры информатики СПбГУ, agm@dscs.pro

Арсений Дмитриевич Завалишин, Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия

Младший научный сотрудник лаборатории теоретических и междисциплинарных проблем информатики СПИИРАН; студент кафедры информатики СПбГУ, adz@dscs.pro

Максим Викторович Абрамов, Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия

Кандидат технических наук, заведующий лабораторией теоретических и междисциплинарных проблем информатики СПИИРАН; доцент кафедры информатики СПбГУ, mva@dscs.pro

Александр Львович Тулупьев, Санкт-Петербургский государственный университет, Университетская наб., 7–9, 199034, Санкт-Петербург, Россия

Доктор физико-математических наук, профессор кафедры информатики, СПбГУ; главный научный сотрудник лаборатории теоретических и междисциплинарных проблем информатики СПИИРАН, alt@dscs.pro

Литература

V. V. Oparin, A. A. Fil’chenkov, A. V. Sirotkin, and A. L. Tulupyev, “Matroidnoe predstavlenie semeistva grafov smezhnosti nad naborom fragmentov znanii” [Matroid representation of a family of adjacency graphs over a set of pieces of knowledge], Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki, no. 4 (68), pp. 73–76, 2010 (in Russian).

A. L. Tulupyev, S. I. Nikolenko, A. V. Sirotkin, Osnovy teorii baiesovskikh setei [Fundamentals of Bayesian Network Theory], St Petersburg, Russia: Publishing house of St. Petersburg State University, 2019 (in Russian).

A. L. Tulupyev, D. M. Stolyarov, and M. V. Mentyukov, “Predstavlenie lokal’noi i global’noi struktury algebraicheskoi baiesovskoi seti v Java-prilozheniyakh” [Representation of local and global algebraic structure Bayesian network in Java-applications], in Trudy SPIIRAN, vol. 5, pp. 71–99, 2007 (in Russian).

D. G. Levenets, M. A. Zotov, A. V. Romanov, A. L. Tulupyev, A. A. Zolotin, and A. A. Filchenkov, ”Decremental and incremental reshaping of algebraic Bayesian networks global structures“ in Proc. of the 1st International Scientific Conference Intelligent Information Technologies for Industry”(IITI’16), Advances in Intelligent Systems and Computing, vol. 451, pp. 57–67, 2016; doi: 10.1007/978-3-319-33816-3_6

V. I. Gorodetskii and A. L. Tulupyev, “Generating consistent knowledge bases with uncertainty,” Journal of Computer and Systems Sciences International, vol. 36, no 5, pp. 683–691, 1997.

A. V. Romanov, D. G. Levenets, A. A. Zolotin, and A. L. Tulupyev, ”Incremental synthesis of the tertiary structure of algebraic Bayesian networks,“ in Proc. 2016 XIX IEEE International Conference on Soft Computing and Measurements (SCM), IEEE, 2016, pp. 28–30; doi: 10.1109/SCM.2016.7519673

E. A. Mal’chevskaya, A. I. Berezin, A. A. Zolotin, and A. L. Tulupyev, ”Algebraic Bayesian Networks: Local Probabilistic-Logic Inference Machine Architecture and Set of Minimal Joint Graphs,“ in Proc. of the First International Scientific Conference “Intelligent Information Technologies for Industry” (IITI’16), Advances in Intelligent Systems and Computing, vol. 451, pp. 69–79, 2016; doi: 10.1007/978-3-319-33816-3_7

”Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks“, Vestnik St. Petersburg University: Mathematics, vol. 45, no. 2, pp. 106–113, 2012; doi: 10.3103/S1063454112020057

A. L. Tulupyev, Algebraicheskie baiesovskie seti: global’nyi logiko-veroyatnostnyi vyvod v derev’yakh smezhnosti [Algebraic Bayesian networks: global logical-probabilistic inference in adjacency trees], Moscow: Anatoliya, 2007 (in Russian).

Опубликован
2020-03-28
Как цитировать
Максимов, А. Г., Завалишин, А. Д., Абрамов, М. В., & Тулупьев, А. Л. (2020). Семейства деревьев смежности и критерий дополнительности. Компьютерные инструменты в образовании, (1), 28-37. https://doi.org/10.32603/2071-2340-2020-1-28-37
Выпуск
Раздел
Алгоритмическая математика и математическое моделирование

Наиболее читаемые статьи этого автора (авторов)