Двоичные представления недоопределённых данных и дизъюнктивные коды // ПДМ. <...> Представление системы семантически осмысленного ролевого управления доступом в виде цветной сети Петри // ПДМ. <...> Алгоритм поиска кратчайших путей для разреженных графов большой размерности // ПДМ. <...> Асимптотика вероятности связности графа с низконадёжными рёбрами // ПДМ. <...> Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений // ПДМ. <...> О верхней границе плотности инъективных векторов // ПДМ. <...> Линейной рекуррентной последовательностью над полем GF(q) с характеристическим многочленом f(x) будем называть последовательность u = u(0)u(1)u(2) . . . элементов этого поля, удовлетворяющую соотношению u(i+m) = a0u(i)+a1u(i+1)+. . .+am−1u(i+m−1), i 0. <...> Назовём эти последовательности линейно независимыми над полем GF(q), если для всех ненулевых векторов ¯ последовательность c1u1 + c2u2 + . . . + crur является ненулевой. <...> Обозначим через χ аддитивный характер поля GF(q), определённый на элементах поля равенством χ(x) = = exp{trq ля GF(q) в поле GF(p); i—мнимая единица. <...> ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2013 Теоретические основы прикладной дискретной математики УДК 621.391: 519.728 ДВОИЧНЫЕ ПРЕДСТАВЛЕНИЯ НЕДООПРЕДЕЛЁННЫХ ДАННЫХ И ДИЗЪЮНКТИВНЫЕ КОДЫ1 Л. А. Шоломов Институт системного анализа РАН, г. Москва, Россия E-mail: sholomov@isa.ru Рассматриваются достаточно компактные представления недоопределённых данных, позволяющие полностью восстановить исходные данные (а не только их доопределения). <...> Ключевые слова: недоопределённые данные, сжатие, двоичное представление, базис системы множеств, длина представления, дизъюнктивная матрица, дизъюнктивный код, свободное от покрытий семейство, полиномиальный алгоритм. <...> Если Λ и ˜ ния основных и недоопределённых символов, то при мощности m основного алфавита матрица Λ состоит изmстолбцов, а число столбцов матрицы ˜ Это делает процедуры представления недоопределённых последовательностей, применяющие матрицу <...>
Прикладная_дискретная_математика_№1_2013.pdf
ПДМ. 2013. № 1(19).
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ
ДИСКРЕТНОЙ МАТЕМАТИКИ
5–13
Биляк И. Б. Оценки числа появлений элементов на отрезках линейных рекуррентных
последовательностей // ПДМ. 2013. № 1(19). C. 5–13.
14–16
Коломеец Н. А. О верхней оценке нелинейности некоторого класса булевых функций с
максимальной алгебраической иммунностью // ПДМ. 2013. № 1(19). C. 14–16.
17–33
Шоломов Л. А. Двоичные представления недоопределённых данных и дизъюнктивные коды //
ПДМ. 2013. № 1(19). C. 17–33.
МАТЕМАТИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРНОЙ
БЕЗОПАСНОСТИ
34–49
Семенова Н. А. Представление системы семантически осмысленного ролевого управления
доступом в виде цветной сети Петри // ПДМ. 2013. № 1(19). C. 34–49.
50–68
Смольянинов В. Ю. Правила преобразования состояний СУБД ДП-модели // ПДМ. 2013. № 1(19).
C. 50–68.
ПРИКЛАДНАЯ ТЕОРИЯ ГРАФОВ
69–83
Бадеха И. А. Исследование кликовых покрытий рёбер графа // ПДМ. 2013. № 1(19). C. 69–83.
84–92
Ураков А. Р., Тимеряев Т. В. Алгоритм поиска кратчайших путей для разреженных графов большой
размерности // ПДМ. 2013. № 1(19). C. 84–92.
93–98
Стр.1
Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Асимптотика вероятности связности графа с
низконадёжными рёбрами // ПДМ. 2013. № 1(19). C. 93–98.
ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ
МАТЕМАТИКЕ
99–109
Колоколов А. А., Адельшин А. В., Ягофарова Д. И. Исследование задач дискретной оптимизации с
логическими ограничениями на основе метода регулярных разбиений // ПДМ. 2013. № 1(19). C.
99–109.
110–116
Кузнецов А. А., Кузнецова А. С. Быстрое умножение элементов в конечных двупорождённых
группах периода пять // ПДМ. 2013. № 1(19). C. 110–116.
117–124
Мурин Д. М. О верхней границе плотности инъективных векторов // ПДМ. 2013. № 1(19). C. 117–
124.
Стр.2
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
2013
Теоретические основы прикладной дискретной математики
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК 621.391.1:004.7
ОЦЕНКИ ЧИСЛА ПОЯВЛЕНИЙ ЭЛЕМЕНТОВ НА ОТРЕЗКАХ
ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
И. Б. Биляк
г. Москва, Россия
E-mail: bil-ib@mail.ru
Рассмотрен некоторый класс тригонометрических сумм от линейных рекуррентных
последовательностей. Эти суммы исследуются с использованием метода
В.М. Сидельникова. Получены оценки числа появлений элементов на отрезках
линейных рекуррент, которые в некоторых случаях уточняют ранее известные
результаты.
Ключевые слова: тригонометрические суммы, линейные рекуррентные последовательности,
число появлений элементов.
Введение
Изучение числа появлений элементов в линейных рекуррентных последовательностях
(ЛРП) над кольцами является одной из важных математических задач. Интерес
к этой задаче связан прежде всего с построением на основе ЛРП генераторов псевдослучайных
чисел, использующих различные способы усложнения аналитического
строения линейных рекуррент (см., например, [1]).
Пусть GF(q)—конечное поле из q элементов, f(x) = xm−am−1xm−1−. . .−a1x−a0 —
реверсивный (a0 = 0) неприводимый многочлен степени m над этим полем. Линейной
рекуррентной последовательностью над полем GF(q) с характеристическим многочленом
f(x) будем называть последовательность u = u(0)u(1)u(2) . . . элементов этого поля,
удовлетворяющую соотношению
u(i+m) = a0u(i)+a1u(i+1)+. . .+am−1u(i+m−1), i 0.
Каждая такая ненулевая ЛРП u является чисто периодической последовательностью,
при этом её период T(u) равен периоду T(f) многочлена f(x) и делит qm − 1 (см.,
например, [2]).
Рассмотрим линейные рекуррентные последовательности u1, u2, . . ., ur с характеристическим
многочленом f(x). Назовём эти последовательности линейно независимыми
над полем GF(q), если для всех ненулевых векторов ¯
последовательность c1u1 + c2u2 + . . . + crur является ненулевой. Обозначим через
c = (c1, c2, . . . , cr) ∈ GF(q)r
Nl(z,u1, . . . ,ur) количество целых чисел i ∈ {0, 1, . . . , l−1}, удовлетворяющих условиям
u1(i) = z1, u2(i) = z2, . . ., ur(i) = zr, где z = (z1, z2, . . . , zr) ∈ GF(q)r. Таким образом,
величина Nl(z,u1, . . . ,ur) равна количеству появлений r-граммы z на отрезке длины l
последовательности векторов, элементы которой имеют вид (u1(i),u2(i), . . . ,ur(i)) для
всех i 0.
№1(19)
Стр.3