Прикладная дискретная математика №3 2013

Стр.1

Стр.2

Стр.3

ПДМ. 2013. № 3(21). ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ 5–10 Ганопольский Р. М. Производящие функции последовательности чисел связных покрытий // ПДМ. 2013. № 3(21). C. 5–10. 11–25 Камловский О. В. Количество появлений элементов в выходных последовательностях фильтрующих генераторов // ПДМ. 2013. № 3(21). C. 11–25. 26–31 Ларионов В. Б. О надструктуре класса квазиоднородных k-значных функций // ПДМ. 2013. № 3(21). C. 26–31. 32–34 Рацеев С. М. Об экспонентах некоторых многообразий линейных алгебр // ПДМ. 2013. № 3(21). C. 32–34. МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ 35–51 Романьков В. А. Криптографический анализ некоторых схем шифрования, использующих автоморфизмы // ПДМ. 2013. № 3(21). C. 35–51. МАТЕМАТИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРНОЙ БЕЗОПАСНОСТИ 52–67 Шумилин А. В. Основные элементы мандатной сущностно-ролевой ДП-модели управления доступом и информационными потоками в СУБД PostgreSQL ОС специального назначения Astra Linux Special Edition // ПДМ. 2013. № 3(21). C. 52–67. ПРИКЛАДНАЯ ТЕОРИЯ ГРАФОВ 68–75

Стр.1

Абросимов М. Б., Моденова О. В. Характеризация орграфов с тремя дополнительными дугами в минимальном вершинном 1-расширении // ПДМ. 2013. № 3(21). C. 68–75. 76–85 Монахова Э. А. О построении циркулянтных сетей размерности четыре с максимальным числом вершин при любом диаметре // ПДМ. 2013. № 3(21). C. 76–85. 86–92 Ураков А. Р., Тимеряев Т. В. О двух задачах аппроксимации взвешенных графов и алгоритмах их решения // ПДМ. 2013. № 3(21). C. 86–92. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ И ПРОГРАММИРОВАНИЯ 93–104 Агибалов Г. П., Липский В. Б., Панкратова И. А. О криптографическом расширении и его реализации для Русского языка программирования // ПДМ. 2013. № 3(21). C. 93–104. ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ МАТЕМАТИКЕ 105–111 Панкратов И. В. О задаче определения линейной и аффинной эквивалентности подстановок // ПДМ. 2013. № 3(21). C. 105–111. 112–122 Рыжов А. С. О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа // ПДМ. 2013. № 3(21). C. 112–122.

Стр.2

ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2013 Теоретические основы прикладной дискретной математики ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ УДК 519.1 ПРОИЗВОДЯЩИЕ ФУНКЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ СВЯЗНЫХ ПОКРЫТИЙ Р.М. Ганопольский Тюменский государственный университет, г. Тюмень, Россия E-mail: rodion@utmn.ru Вводится понятие связных покрытий, рассматриваются производящие функции последовательности комбинаторных чисел, исчисляющих количество связных покрытий конечного множества подмножествами с заданными мощностями и свойствами. Проведён анализ производящих функций, приведены примеры преобразований, получен ряд рекуррентных соотношений. Ключевые слова: покрытие, связное покрытие, конечное множество, подмножества, комбинаторные числа, производящие функции, связные графы. Введение В работе [1] введены комбинаторные числа неупорядоченных покрытий конечного множества мощности n подмножествами с фиксированными мощностями nN(k1, k2, . . . , kn), (1) где ki —количество подмножеств мощности i в покрытии. В случае, когда часть коэффициентов ki = 0, используется альтернативное обозначение nNk1k2···km l1 l2···lm , где ki —количество подмножеств мощности li в покрытии. Для введённых комбинаторных чисел получена формула nNk1k2···km где Ci l1 l2···lm =  i=1 m Cki C lin + i1 (−1)iCi  j=1 m n Ckj C lj , n−i j = j! i!(j −i)! —биномиальный коэффициент, и соотношение  i0 Ci n n−iNk1k2···km l1 l2···lm =  i=1 m Cki C lin . В случае, когда в (1) kn = 1, получим nN(k1, k2, . . . , kn−1, 1) = нято, что 0N0 пустых подмножеств равно 1. n−1 i=1 Cki C i . Кроме того, приn 0 = 1, то есть число покрытий пустого множества нулевым количеством №3(21)

Стр.3