English
Актуальный выпуск от 09.2016 - том 20 выпуск 3 к юбилею академика В.Б. Кудрявцева (PDF)
Коды с малой плотностью проверок на четность (LDPC) были впервые предложены Р. Галлагером в [1], позднее они были переоткрыты Д. МакКеем и Р. Нилом ([2]). Они демонстрируют возможности по исправлению ошибок, близкие к пределу Шеннона. Кроме того они позволяют реализацию кодека с высокой степенью параллелизма, что означает возможность эффективной программной и аппаратной реализации. Поэтому LDPC коды используются во многих областях: жестких дисках, беспроводных коммуникациях и т. д. В данной работе предлагается эффективный алгоритм кодирования для случая проверочной матрицы определенного вида, обладающей неполным рангом. В работе [3] предложен другой эффективный алгоритм, основанный на китайской теореме об остатках.
Ключевые слова: кодирование, коды НППЧ, квазициклические коды, нормальная форма Смита.
В настоящей статье доказано, что не существует алгоритма, с помощью которого из конечной полной системы полиномиальных функций с целыми коэффициентами можно было бы выделить базис.
Ключевые слова: полином, алгоритм, неразрешимость, проблема полноты, базис, операции суперпозиций, функциональная система, 10-я проблема Гильберта.
Доклад посвящен заданию логических процессов средствами пропозициональных исчислений. Будет рассказано о том, как логические системы задаются исчислениями, условия существования такого задания, свойства решетки логических систем, порожденных исчислениями, условия разрешимости проблемы вывода для пропозициональных исчислений и сложность этого вывода.
Ключевые слова: пропозициональные исчисления, логические системы, проблемы вывода, сложность вывода.
Данная статья посвящена условному тестированию схемы Кардо для трех и четырех переменных. Установлено, что для схемы Кардо четырех переменных минимальный полный диагностический условный тест имеет длину 14, а для схемы Кардо трех переменных - 8.
Ключевые слова: схема Кардо, тест, тестирование, длина теста, условный диагностичеcкий тест.
В работе исследуются относительные влияния переменных булевой функции. Множество булевых функций разбивается на классы \(\tau-Inf\)-эквивалентности в зависимости от максимального относительного влияния переменных. Приводятся нижняя и верхняя оценки количества классов \(\tau-Inf\)-эквивалентности для пороговых функций. Они равны \(2^{n/2}\) и \(n2^{2n}\).
Ключевые слова: пороговые функции, влияние переменных булевой функции, относительное влияние переменных булевой функции, классы \(\tau-Inf\)-эквивалентности.
В работе рассматривается задача о накрытии семейства \(A\) натуральных чисел минимальным количеством арифметических прогрессий с запретом на накрытие элементов другого конечного семейства \(B\). Более точно, нас интересует нахождение минимального количества \(f(A)\) элементов в семействе \(B\), которых достаточно, чтобы сделать накрытие семейства \(A\) наиболее сложным, то есть имеющим максимально возможное количество арифметических прогрессий. Приводятся соответствующие верхние и нижние оценки на \(f(A)\) в зависимости от мощности семейства \(A\).
Ключевые слова: арифметическая прогрессия, натуральный ряд, сложность накрытия.
Статья посвящена мощностной сложности плоских схем, реализующих функции из замкнутых классов. Плоскую схему можно представлять, как укладку схемы из функциональных элементов на целочисленную решётку на плоскости таким образом, что провода заменяются на клеточные элементы, реализующие тождественные функции. В качестве меры мощности схемы рассматривается средний и максимальный потенциал, равный среднему и, соответственно, максимальному количеству единиц на выходах элементов схемы. Будет сформулирована теорема о порядке функции Шеннона потенциала для класса монотонных функций и показано, как с учётом этого результата получаются оценки функции Шеннона для остальных замкнутых классов.
Ключевые слова:плоские схемы, клеточные схемы, активность схем, мощность схем, функция Шеннона, классы Поста, монотонные булевы функции.
Рассматривается система линейных полиномов с целыми коэффициентами. Предлагается схема эффективного вычисления этой системы. Схема вычислений позволяет устранить избыточность представления исходных данных, а также упростить вычисления устранением многократности вычислений одних и тех же значений при той же функциональности, что и без использования схемы. Приводится пример применения предлагаемой схемы вычислений.
Ключевые слова:линейный полином, сложность вычислений, классификация.
Пусть \(k > 2\), \(E_k = \{0, 1, \ldots, k-1\}\). Обозначим через \(P_k\) множество всех конечноместных функций на \(E_k\). Вследствие теоремы А. В. Кузнецова при любом \(k\) в \(P_k\) имеется конечное число предполных классов. Все они были описаны в 1965 г. И. Розенбергом в терминах сохранения некоторых предикатов.В данной работе доказан ряд утверждений о вложении некоторых пересечений предполных классов в некоторый (другой) предполный класс. Такие утверждения помогают построить для предполных классов так называемую решетку пересечений, являющуюся, в определенном смысле, \(«остовом»\) континуальной (при \(k > 2\)) решетки замкнутых классов в \(P_k\), в целях получения конечной классификации замкнутых классов. При \(k = 3\) решетка пересечений предполных в \(P_k\) классов построена автором ранее, тогда как при всех \(k > 3\) проблема пока остается открытой.
Ключевые слова: многозначная логика, предполные классы, замкнутые классы, решетка, решетка пересечений.
В статье представлены исследования задачи представления числа булевских решений линейного уравнения многих переменных с целыми коэффициентами, как функции от двоичного разложения этих коэффициентов.
Ключевые слова:уравнение в целых числах, двоичное разложение.
В работе предлагается метод синтеза неизбыточных схем из функциональных элементов в базисе Жегалкина, реализующих произвольные булевы функции без дополнительных входов и выходов и допускающих относительно произвольных константных неисправностей на входах и выходах элементов единичные проверяющие тесты, длина которых ограничена сверху константой 16.
Ключевые слова: схема из функциональных элементов, проверяющий тест, константная неисправность, функция Шеннона, легкотестируемая схема.
Одним из направлений исследования дискретных функций является исследование функциональных систем: множеств функций и множеств операторов, заданных над этими функциями. В частности, активно изучаются функциональные системы, в которых в отличие от классических над множеством \(k\)-значных функций, рассматриваются обобщения функций \(k\)-значной логики: частичные функции, мультифункции и гиперфункции. Гиперфункции представляют собой функции, заданные на конечном множестве \(A\) и принимающие в качестве своих значений все непустые подмножества множества \(A\) относительно оператора суперпозиции. Кроме оператора суперпозиции интерес представляют более сильные операторы замыкания, дающие нетривиальную классификацию функций. Например, для гиперфункций ранее получен критерий полноты для оператора разветвления по предикату равенства. Также известными сильными операторами являются оператор параметрического и позитивного замыкания. Для них известны все замкнутые классы на множестве булевых функций.
Ключевые слова: замыкание, параметрическое замыкание, гиперфункция, критерий полноты, суперпозиция.
В данной работе рассматривается проблема стабилизации булевых сетей, а именно, вопрос наличия точечных аттракторов в асинхронной булевой сети. Найден критерий стабилизации в зависимости от выбора компонент булевой сети: граф, булевы функции, начальное состояние, порядок обновления.
Ключевые слова: булевы сети, стабилизация.
Рассматриваются алгебраические системы, элементами которых являются отображения, реализуемые конечными автоматами. По богатству примеров и выразительности средств автоматы порой не уступают классическим алгебраическим системам. Полугруппы, группы, кольца, а также функциональные системы автоматов позволили решить ряд трудных математических проблем. Эти конструкции приводятся в книге наряду с примерами конкретных автоматов. Книга предназначена студентам, аспирантам, преподавателям и научным сотрудникам.
Ключевые слова: конечный автомат, алгебраическая система, группа, функциональная система.
Авторы вводят понятие расширенной суперпозиции, как суперпозиции с обязательным наличием в системе \(«задержки»\) и функции Шеффера. Для расширенной суперпозиции авторам удалось доказать алгоритмическую разрешимость задачи выразимости для широкого класса автоматных функций: константных автоматных функций, групповых автоматных функций Медведева, а также линейных автоматных функций, что в случае обычной суперпозиции было алгоритмически неразрешимо.
Ключевые слова: автомат, детерминированная функция, суперпозиция.
Автоматная функция (при подаче всех входных слов), вообще говоря, некоторые выходные слова не выдает, а некоторые из них выдает неоднократно. Если сопоставить слову число его появлений на выходе автомата, то возникает новая функция, названная авторами гистограммной функцией автомата, а само множество выходных слов становится мультимножеством. Изучаются свойства таких мультимножеств.
Ключевые слова: автомат, детерминированная функция.
В данной работе показано, что оптимальная функция выхода может быть получена алгоритмом, который используется в доказательстве критерия прогнозируемости для общерегулярных сверхсобытий в многозначном алфавите, а также, что степень прогнозирования сверхсобытия автоматом, полученным путем использования этого алгоритма, может отличаться от оптимальной в любое количество раз.
Ключевые слова: прогнозирующий автомат, прогнозирование сверхсобытий, автоматный цикл.
Изучается свойство автомата содержать во множестве своих выходных слов заданное регулярное множество. Устанавливается, что данное свойство может быть проверено путем изучения строения множества выходных слов автомата ограниченной длины.
Ключевые слова: абстрактный конечный автомат, регулярное событие, регулярное выражение, генератор, алгоритмическая разрешимость.
Данная работа посвящена изучению \(«линейно реализуемых»\) автоматов, то есть автоматов, обладающих тем свойством, что существует кодирование, при котором порождаемый кодированием, булевкий оператор является линейным. В работе приведен критерий линейной реализуемости автомата. Также приведены нижняя и верхняя оценка числа линейно реализуемых автоматов.
Ключевые слова: теория автоматов, автомат, переходные системы, перестановка, подстановка, кодирование, сложность.
Изучены особенности операторов K, S и A-замыкания в классе линейно-автоматных функций над полем из двух элементов.
Ключевые слова: конечный автомат, линейно-автоматная функция, операции композиции, операции суперпозиции, замкнутые классы, максимальные подклассы.
Данная работа является результатом анализа опыта создания дистанционных обучающих систем сотрудниками кафедры \(\mbox{МаТИС}\) МГУ имени М. В. Ломоносова. Работы по созданию интеллектуальных обучающих систем ведутся на кафедре с 1991 года. За это время были разработаны обучающие системы в различных предметных областях, а также инструмент (авторская система) для обеспечения процесса создания обучающих систем, см., например, [2].
Ключевые слова: дистанционное обучение, программирование, практикум на ЭВМ.
В данной работе предлагается формализация идей М.М. Ботвинника, которые отражают особенности логического мышления человека. В основе подхода лежит понятие цепочки, как последовательности действий, направленных на достижение цели. Существование логических связей между цепочками приводит к представлению шахматной позиции в виде набора цепочек. Предлагается формальная модель описания позиции и алгоритм эвристического нахождения оптимального представления.
Ключевые слова: шахматная позиция, цепочка, оптимизация, математическое моделирование, когнитивные процессы.
Предлагается классификационная структура гипотетической эволюции интеллектуальных систем, основанная на постнеклассических информационно-эволюционном подходе к системному анализу и моделированию объективной реальности, атрибутивно-ингредиентной концепции информации и концепции управляемой эволюции естественного языка. Вводятся новые подклассы расширенного класса интеллектуальных систем: аутоанагенные, коншентиальные и психоэйнические системы.
Ключевые слова: знания, информация, моделирование, системы аутоанагенные, системы интеллектуальные, системы коншентиальные, системы психоэйнические, феноменология, эволюция.
В статье рассматривается математическая модель динамических баз данных, которая обрабатывает три типа запросов: поиск, вставка и удаление. Она построена на взаимодействие информационного графа и конечного детерминированного автомата. Модель позволяет решать динамические задачи поиска и оценивать сложность их решения. Кроме этого, модель позволяет строить бесконечно распараллеливаемые алгоритмы решения.
Ключевые слова: динамические базы данных, информационный граф, автомат, потоки запросов, параллельная обработка данных.
Рассматривается алгоритм синтеза дискретных управляющих систем в виде программируемых логических матриц. Программируемые логические матрицы строятся на основе полиномиальных нормальных форм булевых функций. Для дискретных управляющих систем важен результат на определенном подмножестве всех входных значений. Такие системы можно моделировать с помощью частично заданных булевых функций. Предлагается использовать генетические алгоритмы для нахождения близких к минимальным полиномиальных представлений таких функций.
Ключевые слова: логический синтез, полиномиальная нормальная форма, генетические алгоритмы, булевы функции.
В работе рассмотрен подход к распознаванию визуальных образов, основывающийся на построении кодов изображений, инвариантных относительно геометрических преобразований.
Ключевые слова: распознавание визуальных образов, кодирование изображений.
Изучается взаимосвязь между обобщениями формальных понятий на случай нечётких контекстов. Рассматриваются чётко-порождённые нечёткие формальные понятия (Р. Белохлавек с соавторами), протонечёткие понятия (О. Кридло и С. Крайчи), узорные структуры (C. Кузнецов и Б. Гантер). Устанавливаемые соответствия между протонечёткими и чётко-порождёнными формальными понятиями позволяют переформулировать задачи и использовать полученные ранее критерии и свойства.
Ключевые слова: нечёткие формальные понятия, протонечёткие формальные понятия, чётко-порождённые формальные понятия, интервальные формальные понятия.
Работа посвящена изложению результатов компьютерного моделирования логических процессов в логической системе \(«Искра»\). Исследовались вопросы, связанные с обучением компьютерных решателей задач и автоматическим синтезом приемов.
Ключевые слова: интеллектуальная система, самообучение, логическая система, компьютерный решатель задач, автоматический синтез приемов.
Известно, что нейронные схемы реализуют кусочно-постоянные функции. Для соответствия нейронным сетям модели Мак-Каллока-Питтса следует разрешить использование только \(«цельных нейронов»\) В этом случае выход нейронной схемы будет принимать значение из множества \(\{0,1\}\), а функция реализуемая схемой – индикаторной. В работе доказана представимость произвольной индикаторной функции нейронными сетями с не более чем тремя слоями. Сформулирован критерий представимости функций индикаторов двуслойными нейронными сетями.
Ключевые слова: нейронная сеть, нейронная схема, нелинейная глубина, модель Мак-Каллока-Питтса.
Актуальными для медицины являются задачи автоматического анализа тактильных образов, регистрируемых инструментально при проведении эндоскопических операций. Важным элементом этого анализа является автоматическое обнаружение неоднородностей. В 2016 году Р. Ф. Солодовой с соавторами были предложены три метода автоматического обнаружения неоднородностей по инструментально зарегистрированным результатам одного нажатия тактильным механорецептором на исследуемый участок. Цель настоящего исследования - теоретическое сравнение согласованности срабатывания этих методов. Более конкретно, изучается вопрос, следует ли из того, что один из методов определил участок как неоднородный, утверждение, что тогда и другие методы определят этот участок как неоднородный.
Ключевые слова: тактильные образы, автоматический анализ, обнаружение неоднородностей, медицинский тактильный эндохирургический комплекс, тактильный механорецептор.
Рассмотрены основные проблемы развития компьютерных обучающих систем. Показано, что ключевой задачей и точкой роста для таких систем является персонификация процесса обучения. Формулируются необходимые условия персонификации обучения. Приводятся результаты экспериментов с данными, накапливаемыми в процессе обучения. Основные положения иллюстрируются на примере платформы Учи.ру.
Ключевые слова: компьютерные обучающие системы, персонификация, кластеризация, ранжирование.
В работе исследуется сложность решения следующей задачи. Дана система, разграничение доступа в которой основано на RelBAC-модели, введенной в статьях В. А. Васенина с соавторами, и пара (субъект, объект). Требуется определить, существуют ли условия, при которых субъект может получить заданный доступ к объекту. Мы показываем, что в общем случае эта задача NP-полна. Если же максимальная длина путей ограничена константой, то задача становится полиномиальной.
Ключевые слова: информационно-аналитические системы, NP-полнота, графы, информационная безопасность.
В работе формулируется критерий полиномиальной полноты квазигруппы простого порядка, а также показывается, что проверка полиномиальной полноты может быть проведена за время, полиномиальное от порядка.
Ключевые слова: квазигруппа, полиномиальная полнота, алгоритмическая сложность.
В работе исследуется модель долгосрочных профилей систем активного аудита, предложенная А. В. Галатенко, А. Е. Лебедевым и И. Н. Емельяновым в 2009 году. Доказывается, что предложенное авторами модели достаточное условие сходимости профилей является критерием.
Ключевые слова: выявление вторжений, состоятельность долгосрочных профилей.
В предлагаемой работе исследуется проблема синтеза пространственно распределенных систем управления в контексте существующего уровня развития систем связи и вычислительных устройств, обосновывается преимущество агентного подхода к систезу пространственно распределенных систем управления. Отдельное внимание уделяется некоторым аспектам онтологического обеспечения и проектирования распределенных многоагентнных систем управления.
Ключевые слова: система управления, агентный подход, интернет вещей.
Безопасный язык программирования C\(_s\) и операционная система, созданная компилятором этого языка, обеспечивают полную защиту от вредоносных программ и кибер-атак. Система, состоящая из C\(_s\) и его операционной системы, открыта только для программ, созданных компилятором C\(_s\) или удовлетворяющих стандартам C\(_s\). Имеется робот, преобразующий все существующие программы к этим стандартам.
Ключевые слова: информационная безопасность, языки программирования, вредоносные программы, кибер-атаки.
В работе излагается модель криптографических протоколов, основанная на теории процессов с передачей сообщений. Показано, как можно использовать данную модель для решения задач верификации криптографических протоколов (то есть построения математических доказательств утверждений о том, что криптографические протоколы обладают заданными свойствами). В качестве примера таких свойств рассматриваются свойства целостности и секретности. Данные свойства определяются формально, как некоторые соотношения, выражаемые в терминах наблюдаемой эквивалентности процессов с передачей сообщений. Показаны примеры верификации данных свойств для некоторых криптографических протоколов.
Ключевые слова: криптографические протоколы, верификация, наблюдаемая эквивалентность.
Описывается параллельная реализация алгоритма поиска в ширину на графе, разработанная в компании Т-Платформы. Ключевой особенностью является оптимизированное внутреннее представление графа, позволяющее упорядочить коммуникации между вычислительными процессами и разделить выполнение на потоки внутри каждого из процессов. Приводится описание оптимизации по направлению и ее многопоточной имплементации. Также приведены результаты исследования производительности разработанной реализации.
Ключевые слова: распределенные вычисления, параллельные вычисления, графы, поиск в ширину.
При математическом моделировании электрогидродинамических явлений основная трудность связана с включением в модель физических параметров, сведения о которых весьма неопределенны. Возникает потребность в разработке математических моделей с минимальным набором \(«эффективных»\) искомых переменных и задаваемых параметров. В работе описаны три модели возрастающей сложности и приведены результаты, полученные в рамках каждой из них.
Ключевые слова: электрогидродинамика, электрическое поле, слабопроводящие среды, математические модели, объемный электрический заряд, электрохимические реакции, электризация.
В работе исследуется задача объединения двух систем, в каждой из которых реализована политика безопасности take-grant. Объединение называется безопасным, если внутри каждой из объединяемых систем не появляется новых доступов. Предлагается критерий безопасности объединения, а также легко проверяемое достаточное условие безопасности.
Ключевые слова: формальные модели безопасности, модель take-grant, безопасное объединение.
В работе говорится о глубине аппаратной (схемной) реализации потокового шифра ZUC и способах ее минимизации. Сначала приводится простая реализация алгоритма. После этого показываются способы оптимизации данной реализации.
Ключевые слова: потоковые шифры, оптимизация глубины схем.