2018 год, том 22, выпуск 4 (PDF)
В работе изложена система требований и принципов, определяющих методологические аспекты создания отечественных аппаратнопрограммных платформ для автоматизированных систем в защищенном исполнении как основы критической информационной инфраструктуры Российской Федерации, описан опыт создания защищенной аппаратнопрограммной платформы «Синтез-АПП», в полном объеме удовлетворяющей самым строгим требованиям по информационной безопасности, надежности, масштабируемости, обеспечивающей независимость критической информационной инфраструктуры от зарубежных технологий и программ.
Ключевые слова: автоматизированная система в защищенном исполнении, аппаратно-программная платформа, информационная безопасность, критическая информационная инфраструктура, «СинтезАПП»
Рассматриваются методы внешних штрафных функций, внутренних штрафных функций и квазибарьерных функций для решения задач математического программирования. Предложены новые квазибарьерные функции. Доказаны теоремы сходимости указанных методов к решению задач математического программирования. Рассмотрены свойства указанных функций при их преобразованиях: дифференцирование, интегрирование, построение обратных к ним функций.
Ключевые слова: внешние штрафные функции, внутренние штрафные функции, барьерные штрафные функции, обратные функции, квазибарьерные функции, задача математического программирования, дифференциальные барьеры, степенные дифференциальные барьеры, энтропийные дифференциальные барьеры, сходимость методов дифференциальных барьеров к решению задачи математического программирования.
Приведены методы восстановления стертого фрагмента музыкальной композиции, основанные на алгоритме Витерби, а именно метод, основанный только на алгоритме Витерби, метод, использующий кроме алгоритма Витерби, также смещенную высоту и смещенную длительность, метод, основанный на алгоритме Витерби и принципах музыкальной гармонии. Выяснен метод с наилучшим результатом (алгоритм Витерби, совмещенный с методом музыкальной гармонии), введен способ оценки похожести фрагментов, приведены примеры мелодий, такты которых были лучше всего восстановлены. Все методы вписаны в программу на языке Java, которая решает заданную задачу, кроме того используется программа GuitarPro, помогающая перевести всю необходимую информацию о мелодии в текстовый формат.
Ключевые слова: алгоритм Витерби, смещенная высота, смещенная длительность, гармонизация аккордами.
В работе рассматривается задача персонализации нечётких пользовательских понятий с помощью действия модификаторов на данные нечёткие множества. Исследован и модифицирован существующий алгоритм персонализации, для новой его версии получена оценка числа выполняемых итераций.
Ключевые слова: нечёткие множества, персонализация.
Протоколы аутентификации – это распределенные алгоритмы, предназначенные для обеспечения аутентификации агентов и передачи конфиденциальной информации (криптографических ключей, и т.п.) в небезопасной среде. Они используются, например, в электронных платежах, электронных процедурах голосования, системах доступа к базам данных, и т.д. Учитывая большой финансовый и социальный ущерб в случае неправильной работы таких протоколов, необходимо использовать математические методы для обоснования их корректности и безопасности. В настоящей работе вводится новая математическая модель таких протоколов аутентификации, позволяющая описывать как сами протоколы, так и их свойства. Показывается, как на базе данной модели можно решать задачи верификации протоколов аутентификации.
Ключевые слова: протоколы аутентификации, распределенные алгоритмы, верификация.
Предложен и обоснован вычислительно эффективный метод синтеза семейства дискретных многочленов комплексного аргумента с единичной весовой функцией, удовлетворяющих условию ортогональности на заданном произвольном конечном множестве несовпадающих узлов. Приведён детальный алгоритм расчёта коэффициентов и табуляции значений многочленов на языке GNU Octave/Mathworks Matlab. Дана оценка сложности, показано, что она минимально возможная.
Ключевые слова: цифровая обработка сигналов, устойчивая интерполяция, ортогональные многочлены дискретной комплексной переменной, произвольные узлы, расчёт коэффициентов, оптимальный алгоритм, вычислительная сложность.
В статье З.А.Ниязовой "Расшифровка арифметических сумм монотонных конъюнкций” получена точная оценка сложности расшифровки функции, имеющей не более двух нижних единиц. На самом деле, эту оценку можно понизить на 1 запрос, что и демонстрируется в данной работе.
Ключевые слова: точная расшифровка, суммы монотонных конъюнкций, запросы на значение.
Доказывается, что всякая абсолютно арифметически реализуемая предикатная формула является классически истинной, однако не всякая классически истинная предикатная формула является абсолютно арифметически реализуемой.
Ключевые слова: конструктивная семантика, реализуемость, арифметическая реализуемость, абсолютная реализуемость, формальная арифметика.
Найдены множества всех предполных классов в классах линейных автоматов над конечными полями, являющиеся приведенными критериальными системами в этих классах.
Ключевые слова: конечный автомат, линейный автомат, операции композиции, операции суперпозиции, обратная связь, проблема полноты, предполный класс, критериальная система, приведенная критериальная система, сумматор, задержка.
В докладе изложена работа по созданию алгоритма обучения системы с дискретным управлением действовать и достигать целей. Обучение происходит на основе проб и ошибок. Весь опыт системы сохраняется в Базе Данных. Оптимизация алгоритма производится по двум критериям: точность достижения поставленных целей и максимальное сокращение времени обучения. Сокращение времени обучения реализуется, главным образом, уменьшением количества пробных действий с помощью методов прогнозирования и интерполяции по опытным данным.
Ключевые слова: позиционирование, алгоритм обучения, робот, интерполяция, аппроксимация.
В статье изучаются операции выпадения/вставки, продвижением которых занимался В. И. Левенштейн. Вводятся операторы замыкания относительно этих операций. Для оператора вставки доказывается существование, конечность и единственность базиса в замкнутых классах, а для оператора выпадения — несуществование для бесконечного класса и существование, конечность и единственность — для конечного. Исследуется автоматная сложность замкнутых классов. Решаются проблемы полноты, предполноты и выразимости.
Ключевые слова: операции выпадения и вставки; замкнутый класс; регулярный язык; базис; автоматная сложность; проблемы полноты/предполноты/выразимости.
2018 год, том 22, выпуск 3 (PDF)
В рамках теории упругопластических процессов А.А.Ильюшина [1], в [3] для математического моделирования процессов сложного нагружения использовано квазилинейное определяющее уравнение с тремя функционалами состояния. Калибровка определяющих функционалов там проведена с использованием экспериментальных результатов [4] (Р.А.Васин и др.) по трехмерным винтовым траекториям деформаций. Выяснилось, что отклик на винтовую траекторию деформации принимает, по исчерпанию некоторого следа запаздывания, вполне определенную форму предельного режима. Поэтому для произвольных трехмерных процессов деформации в [2] предлагалось последовательно аппроксимировать траектории деформации отрезками винтовых линий, на которых вычислять определяющие функционалы по уравнениям предельных режимов. Тогда на траекториях указанного вида реализуется соответствие геометрии траектории деформаций форме отклика. Это соответствие по А.А.Ильюшину назовем теоремой изоморфизма, уточняя для процессов высокой размерности уравнения самих винтовых сплайнов в пространстве деформаций и форм отклика. Принятый в [2] алгоритм относился исключительно к трехмерным траекториям и базировался на использовании смешанного пространственного базиса, включающего, помимо традиционных в определяющих соотношениях векторов (направляющих векторов напряжений и скоростей деформаций), еще и сам направляющий вектор деформаций. Здесь рассматриваются варианты модификации общей теории, годные для описания произвольных процессов нагружения с траекториями деформаций любой размерности. В качестве репера во всех новых теориях использованы направляющий вектор напряжений и векторы, построенные на основе векторов естественного сопровождающего репера Френе. Поскольку далее рассматриваются процессы деформации высокой размерности, то растет число определяющих функционалов и несколько усложняются методы их идентификации.
Ключевые слова: пластичность, пластические деформации, сложное нагружение, определяющие соотношения, идентификация функционалов,теорема изоморфизма.
В данной работе производится оценка зависимости избыточности записи (Write Amplification) от размера резервной области памяти (Overprovision) твердотельного накопителя (SSD) при разных значениях числа секторов в блоке N . Сборка мусора, т.е. перезапись частично заполненных блоков производится в соответствии с жадным алгоритмом (Greedy Garbage Collection). Получена более точная формула чем в [1], поскольку отсутствует предположение N → ∞. Показано, что при фиксированном размере резервной области избыточность записи является монотонно возрастающей функцией от N .
Ключевые слова: избыточность записи, резервная область памяти, сборщик мусора, твердотельный накопитель.
Для каждого счетного расширения L языка арифметики определяется абсолютная L-реализуемость предикатных формул. Доказывается, что интуиционистская логика не является корректной относительно этих семантик.
Ключевые слова: конструктивная семантика, реализуемость, абсолютная реализуемость, формальная арифметика, интуиционистская логика.
Рассматривается задача создания программы, осуществляющей семантический анализ юридических текстов на русском языке. Получив на вход текст, программа должна выдать схему вычисления значений всех сущностей, описанных в тексте. В работе приведены приемы, позволяющие автоматически строить такую схему при наличии морфологической информации о всех словах текста.
Ключевые слова: cемантический анализ, синтаксический анализ, юридический текст, логическая формула, прием.
Рассматриваются вычислительные библиотеки, использующие архитектуру CUDA для работы с целыми числами произвольной длины. Сравниваются возможности и производительность находящихся в открытом доступе таких библиотек.
Ключевые слова: длинная арифметика, GPU, CUDA.
Данная работа посвящена изучению свойств графов с заданными параметрами толщины и обхвата. Приведена верхняя оценка на хроматическое число графов, зависящая от толщины k и обхавата g, где k ≥ 1 и g ≥ 3. В частности, для бипланарных графов с обхватом не менее 10 доказана 5-раскрашиваемось.
Ключевые слова: хроматическое число, обхват, толщина, планарный граф, бипланарный граф.
В работе рассматривается модель движения точки на экране, представляющем из себя бесконечный вправо одномерный клеточный автомат. Выделено подмножество множества состояний экрана, которое называется изображением точки на экране. Закон движения определяется бесконечной последовательностью из нулей и единиц, которые в каждый момент времени задают остановку или движение точки соответственно. Описан алгоритм реализации на экране широкого класса законов движения и исследована мера Бернулли множества реализуемых законов движения. Показано, что почти все законы движения являются реализуемыми. Также доказано, что относительно тихоновской топологии множество реализуемых законов движения относится к первой категории Бэра, то есть мало.
Ключевые слова: клеточный автомат, универсальный экран, движение точки, закон движения, мера Бернулли, тихоновская топология, категории Бэра.
Пусть L - некоторое расширение языка арифметики, V - некоторый класс числовых функций. Определяется понятие V реализуемости для формул языка L таким образом, что индексы функций из класса V используются для интерпетации импликации и квантора всеобщности. Доказывается, что семантика V реализуемости для языка L совпадает с классической семантикой этого языка тогда и только тогда, когда класс V содержит все функции, определимые в языке L.
Ключевые слова: конструктивная семантика, реализуемость, обобщенная реализуемость, формальная арифметика.
Доказаны следующие утверждения: для любого натурального k и любой булевой константы p существует базис, состоящий из булевой функции от max(k + 1; 3) переменных и отрицания одной переменной (существует базис, состоящий из булевой функции от не более чем 2,5k +2 переменных и отрицания этой функции), в котором любую булеву функцию, кроме константы p, можно реализовать схемой из функциональных элементов, неизбыточной и допускающей проверяющий (соответственно, диагностический) тест длины не более 2 относительно не более k однотипных константных неисправностей типа p на входах и выходах элементов. Показано, что при рассмотрении только однотипных константных неисправностей типа p на входах элементов указанные оценки длин тестов можно понизить до 1.
Ключевые слова: схема из функциональных элементов, однотипная константная неисправность, проверяющий тест, диагностический тест.
2018 год, том 22 выпуск 2 (PDF)
В работе рассмотрены возможности применения технологии оценки и мониторинга сложных процессов обеспечения информационной безопасности в задаче устойчивого развития критической инфраструктуры Российской Федерации. Предложена структура модели устойчивости критической инфраструктуры, возможные сценарии использования системы оценки и мониторинга информационной безопасности, обсуждаются аналитические возможности системы.
Ключевые слова: информационная безопасность, критическая инфраструктура, технология оценки и мониторинга сложных процессов, устойчивое развитие.
В рамках теории упругопластических процессов А.А.Ильюшина [1], в [3] для математического моделирования процессов сложного нагружения использовано квазилинейное определяющее уравнение с тремя функционалами состояния. Калибровка определяющих функционалов там проведена с использованием экспериментальных результатов [4] (Р.А.Васин и др.) по трехмерным винтовым траекториям деформаций. Выяснилось, что отклик на винтовую траекторию деформации принимает, по исчерпанию некоторого следа запаздывания, вполне определенную форму предельного режима. Поэтому для произвольных трехмерных процессов деформации в [2] предлагалось последовательно аппроксимировать траектории деформации отрезками винтовых линий, на которых вычислять определяющие функционалы по уравнениям предельных режимов. Тогда на траекториях указанного вида реализуется соответствие геометрии траектории деформаций форме отклика. Это соответствие по А.А.Ильюшину назовем теоремой изоморфизма, уточняя для процессов высокой размерности уравнения самих винтовых сплайнов в пространстве деформаций и форм отклика. Принятый в [2] алгоритм относился исключительно к трехмерным траекториям и базировался на использовании смешанного пространственного базиса, включающего, помимо традиционных в определяющих соотношениях векторов (направляющих векторов напряжений и скоростей деформаций), еще и сам направляющий вектор деформаций. Здесь рассматриваются варианты модификации общей теории, годные для описания произвольных процессов нагружения с траекториями деформаций любой размерности. В качестве репера во всех новых теориях использованы направляющий вектор напряжений и векторы, построенные на основе векторов естественного сопровождающего репера Френе. Поскольку далее рассматриваются процессы деформации высокой размерности, то растет число определяющих функционалов и несколько усложняются методы их идентификации.
Ключевые слова: пластичность, пластические деформации, сложное нагружение, определяющие соотношения, идентификация функционалов, теорема изоморфизма
В статье изучаются операции выпадения/вставки, продвижением которых занимался В. И. Левенштейн. Cтавятся и даются ответы на следующие два вопроса. Какие регулярные языки устойчивы относительно операций выпадения/вставки? Существуют ли нерегулярные языки, которые устойчивы относительно операций выпадения/вставки?
Ключевые слова: операции выпадения и вставки, замкнутый класс, регулярный язык.
Статья посвящена изучению структуры графа, порождаемой на множестве перестановок моделью ошибки канала перестановки пакетов, введенной в работе И.Б. Казакова “Кодирование в скрытом канале перестановки пакетов”. Установлено, что граф можно разделить на слои, являющиеся независимыми множествами. Введено понятие характеристического графа перестановки и доказано, что номер слоя определятся числом его ребер. Получен результат о степенях вершин слоя в (Sn)2, и на основании его дана оценка мощности конструируемого послойного кода. Разработан инстументарий для получения верхних оценок мощности кодов. Введены понятия симметрического слоя и разбиения графа. Приведены конкретные примеры разбиения Sn на призмы, а также на произведения графов обобщение понятия призмы. Построено вложение в E_n(n−1)/2, Sn оказывается ограничением E_n(n−1). Получен побочный результат алгебраического характера, связывающий размер подгруппы H, принадлежащей Sn и содержание в ней n-шаговых перестановок.
Ключевые слова: перестановки; графовая структура; код, исправляющий ошибки
В настоящей работе дано полное описание решётки всех клонов трёхзначной логики, содержащих одновременно все константы 0, 1, 2 и функции min, max. Клоны описаны как множества сохранения предикатов.
Ключевые слова: теория клонов, решетка клонов, трёхзначная логика.
Назовем гиперавтоматом конечный автомат, состояниями которого являются множества состояний некоторого конечного автомата. Гиперавтомат называется групповым, если полугруппа автомата, на базе которого он построен, является группой. В работе изучается вопрос о максимальном количестве регулярных языков, представимых в групповых гиперавтоматах.
Ключевые слова: конечные автоматы, гиперавтоматы, регулярные языки, конечные группы.
В работе представлены основные проблемы разработки систем оценки и мониторинга процессов в социотехнических системах. Рассмотрены связанные с ними задачи и технологии. Приведены примеры их решения. Затронуты перспективные направления персонализации взаимодействия человека с цифровым миром и дополненного интеллекта (augmented intelligence). Статья подготовлена по результатам выступления автора на кафедральном семинаре кафедры Математической теории интеллектуальных систем механико-математического факультета МГУ имени М.В. Ломоносова "Теория автоматов" под руководством профессора В. Б. Кудрявцева 21 марта 2018 года.
Ключевые слова: Социотехнические системы, оценка и мониторинг сложных процессов, нечеткие множества, персонализация.
Флеш память в последнее десятилетие стала доминирующей технологией для хранения информации как в персональных вычислительных средствах, так и в корпоративных продуктах: серверах, сетевых хранилищах и дата-центрах. Первоначально технология флеш памяти предполагала хранение одного бита информации в ячейке (SLC-память). Далее с развитием технологий изготовления флеш памяти, а также в связи с использованием во флеш памяти более мощных помехоустойчивых кодов, стало возможных хранить в каждой ячейке 2 бита (MLC-память) или даже 3 бита (TLC-память) информации. Увеличение объема информации, содержащейся в каждой ячейке, приводит к значительному росту вероятности ошибки при чтении. При этом, по мере износа флеш памяти, электрические заряды, хранящиеся в ячейках, имеют тенденцию к уменьшению. Этот процесс приводит к еще большему росту вероятности ошибок чтения и, фактически, приводит к выходу флеш памяти из строя через некоторое время эксплуатации. Ранковый способ хранения информации в ячейках флеш памяти устойчив к процессу постепенного снижения электрических зарядов в ячейках. Более того, данный способ позволяет хранить в том же количестве ячеек больший объем информации. В работе приводится общее описание устройства флеш памяти, описана процедура чтения и рассмотрена простейшая модель ошибок. Далее описан способ хранения информации во флеш памяти с помощью ранков (перестановок). Даны оценки емкости данного типа памяти в сравнении с обычной флеш памятью. Введено понятие Кендалл-Тау расстояния на множестве перестановок. С помощью данного расстояния получена оценка на размер ранковой макроячейки с учетом технологических ограничений. В заключение приведено сравнение плотности записи ранковой и обычной флеш памяти. Явным образом показаны случаи большей плотности ранковой памяти по сравнению с обычной.
Ключевые слова: ранковая флеш память, SLC/MLC/TLC флеш память, эффективность флеш памяти в части занимаемой площади.
Рассматриваются классы линейных автоматов над конечными полями с операциями композиции (суперпозиции и обратной связи). Ранее для этих классов получен алгоритм проверки полноты конечных подмножеств. В случае простого поля найдены все предполные классы, множество которых является счетной приведенной критериальной системой. В общем случае ранее было построено множество замкнутых классов, являющееся критериальной системой, включающее семейство классов, порожденных максимальными подполями в трансцендентном расширении рассматриваемого конечного поля. Для простых полей все классы этого семейства поглощались другими классами из приведенной критериальной системы. Поэтому в настоящей работе оно исследуется в случае конечных полей, не являющихся простыми. Оказалось, что часть элементов семейства поглощается и в этом случае, но также среди его элементов существуют предполные классы, являющиеся конечно-порожденными и не содержащиеся среди предполных классов других семейств.
Ключевые слова: линейный автомат, сумматор, задержка, обратная связь, операции композиции, алгоритм проверки полноты, предполный класс.
2018 год, том 22 выпуск 1 (PDF)
В работе рассматривается класс нейронных кусочно-параллельных функций с двоично-рациональными коэффициентами. Доказано что для любой функции из класса кусочно-параллельных функций существует функция из класса кусочно-параллельных функций с двоично-рациональными коэффициентами, приближающая ее с наперед заданной точностью. Также, для рассматриваемого класса функций показано, что существуют базисы, состоящие из заданного (произвольного) числа элементов, в частности, найдена Шефферова функция.
Ключевые слова: класс кусочно-параллельных функций, класс нейронных функций с двоично-рациональными коэффициентами, операции суперпозиции, Шефферова функция, базисы.
В работе анализируются всевозможные латинские квадраты порядка 4, порождаемые с помощью правильных семейств функций. Оказывается, что все такие квадраты задают квазигруппы, не являющиеся полиномиально полными. Предлагается обобщение конструкции, связанной с правильными семействами. В результате удается в 4 раза увеличить число порождаемых латинских квадратов и получить значительное число полиномиально полных квазигрупп.
Ключевые слова: Квазигруппа, латинский квадрат, параметрическое задание, полиномиальная полнота, правильные семейства функций.
Известно, что автоматы с магазинной памятью сохраняют множество периодических последовательностей. Ранее автор привёл верхние и нижние оценки на максимальный период выходной последовательности автономного автомата с магазинной памятью в зависимости от характеристик автомата. В данной работе приводятся оценки на максимальный период выходной последовательности для общего случая. Период выходный последовательности был изучен главным образом как функция от периода входной последовательности.
Ключевые слова: автомат с магазинной памятью, детерми-нированная функция, периодические последовательности.
В статье исследуется связь между площадью и максимальным потенциалом плоских схем, реализующих булевы операторы. Максимальный потенциал мера сложности плоских схем, отражающая энергопотребление схемы в худшем случае, его также часто называется активностью. Он равен максимальному числу выходов элементов схемы, равных 1, где максимум берётся по всем входным наборам схемы. В работе показано, что для произвольного булева оператора потенциал U не меньше, чем √S/4√2, где S - площадь минимальной схемы, реализующей данный оператор.
Ключевые слова: клеточные схемы, активность, потенциал, связь мер сложности, нижние оценки, булевы операторы.
Вопрос о сложности доказательств теорем в формальных системах возникает во многих областях. С точки зрения вычислительной сложности точные нижние оценки сложности доказательств служат средством отделения классов вычислительной сложности. В современных SAT- и SMT-решателях анализ лежащих в их основе систем доказательств позволяет оценить производительность и ограниченность решателей. Центральное место в вопросе сложности доказательств отводится доказательству теорем классического исчисления высказываний. Несмотря на то, что за последние десятилетия удалось разработать много разнообразных техник для доказательства верхних и нижних оценок в различных пропозициональных системах, успеха в получении нижних оценок для классических систем доказательств достичь так и не удалось. Тем не менее, среди специалистов в области сложности доказательств сложилась прочная уверенность в том, что существует тесная связь между прогрессом в получении нижних оценок сложности булевых схем и прогрессом в получении нижних оценок размера пропозициональных доказательств. В работе будет рассказано о связи между булевыми схемами и системами доказательств теорем, о том, как идеи и методы, применяемые для оценки сложности схем, применяются для оценки сложности доказательств теорем.
Ключевые слова: Системы пропозициональных доказательств, сложность доказательств, булевы схемы, сложность схем, классы сложности.
Традиционно считается, что при переходе от двузначного к многозначному случаю свойства решетки замкнутых классов функций координально меняются. В докладе будет показано, что несмотря на различия, эти решётки во многом похожи, а очень многие свойства, которые следуют из решетки Поста, могут быть обобщены на многозначный случай. Одним из таких примеров является решение задачи удовлетворения ограничениям для многозначного случая - показано, что самый общий полиномиальный алгоритм является во многом лишь комбинацией методов, давно известных для двузначного случая.
Ключевые слова: Булевы функции, k-значные функции, отношения, соответствие Галуа, задачи удовлетворения ограничениям.
Диагностические эксперименты с конечными автоматами впервые были описаны в классической работе Э. Мура, и с тех пор применяются для тестирования цифровых схем и коммуникационных протоколов. Одна из основных задач тестирования конечных автоматов состоит в определении начального состояния наблюдаемого автомата. Пусть имеется полное описание некоторого конечного автомата Мили, но про его начальное состояние известно лишь то, что оно принадлежит некоторому фиксированному подмножеству состояний. Тогда диагностическая задача состоит в нахождении начального состояния путем последовательной подачи входных символов на автомат. В данном докладе будет рассказано об оценках длины для таких последовательностей входных символов и показана связь данной задачи с комбинаторными проблемами, возникающими в теории гиперграфов.
Ключевые слова: конечный автомат, условный диагностиче-ский эксперимент, теорема Мура, гиперграф.