2020 год, том 24, выпуск 4 (PDF)
В работе рассматривается задача проверки возможности получения пользователем информационной системы доступа к выделенному объекту при заданной атрибутивной политике безопасности. Показывается, что при некоторых ограничениях на модель информационной системы и правила политики эта задача сводится к задаче интеллектуального планирования. Определяется древовидная структура, построение которой соответствует планированию в пространстве планов и позволяет учитывать специфику решаемой задачи при построении эвристических алгоритмов проверки доступа. Доказывается, что существование такой структуры является необходимым и достаточным условием возможности получения доступа к целевому объекту.
Ключевые слова: ABAC, проверка доступа, интеллектуальное планирование.
В работе излагаются результаты дискуссии на тему проблем и перспектив искусственного интеллекта, состоявшейся на кафедре математической теории интеллектуальных систем 14 октября 2020 года. Тематика дискуссии восходит к классическим работам А. Тьюринга «Может ли машина мыслит» и Дж. фон Неймана «Вычислительная машина и мозг», которые возникли на заре становления кибернетики как науки. С тех пор дискуссии на тему «Может ли машина мыслить» то возникали, то затухали и в понимании этого вопроса особой ясности они не вносили. В последние годы, в связи с мощным развитием технологической базы вычислительных систем, тематика стала вновь актуальной. Вместе с научной базой, наработанной в теории искусственного интеллекта и прикладных программ в этой области, возникло множество работ спекулятивного типа, готовых объявить любое устройство со встроенными в его систему управления тривиальными алгоритмическими добавками «системой искусственного интеллекта». В работе делается попытка отделить «зерна от плевел», изложив несколько точек зрения по этому вопросу.
Ключевые слова: искусственный интеллект, машинное обучение, нейронные сети.
В работе [1] дано определение клеточного автомата с локаторами. В данной работе указаны некоторые неточности и недостатки этого определения и предлагаются уточнения, позволяющие избавиться от этих недостатков. Также приводятся примеры классов клеточных автоматов с локаторами, обладающих в определённом смысле хорошими свойствами.
Ключевые слова: клеточные автоматы, однородные структуры.
Для класса кусочно-параллельных функций, реализуемых схемами из линейных элементов и функций Хэвисайда, получен алгоритм проверки полноты конечных подмножеств, дополненных одноместными функциями. Таким образом, для рассматриваемого класса решена задача Слупецкого.
Ключевые слова: кусочно-линейная функция, кусочно-параллельная функция, проблема полноты, критерий Слупецкого.
Если в диаграмме Мура автомата без выходов убрать информацию о входных буквах, то получится ориентированный граф. Обратная операция, когда эта информация восстанавливается, называется разметкой графа автомата. В этой статье приводятся оценки числа разметок графов, приводящих к групповым автоматам.
Ключевые слова: групповой автомат, граф переходов, диаграмма Мура, перманент матрицы, факторизация.
В работе рассматривается одно семейство квантовых LDPC кодов с весом стабилизатора 6 и двумя логическими кубитами, где имеется фрактальная структура некоторых логических операторов. Эти коды можно представить в виде локальных кодов на трёхмерной решётке L×L×L с периодическими граничными условиями. Для этого семейства кодов доказана нижняя оценка кодового расстояния Ω(L^α), где α=log_2 (2(√5-1))≈1.306.
Ключевые слова: квантовый LDPC код, локальный квантовый код, кодовое расстояние, линейный клеточный автомат, фрактальная размерность.
Рассматривается задача определения порядка инициального линейного над полем рациональных чисел автомата относительно операции суперпозиции. Выведена верхняя оценка на порядок автомата, зависящая от размерности.
Ключевые слова: линейные автоматы, порядок в полугруппе.
2020 год, том 24, выпуск 3 (PDF)
Принятие эффективных управленческих решений в сфере охраны здоровья и профилактики заболеваний позволяет повысить продолжительность и качество жизни. Процесс принятия таких решений происходит в условиях ограниченной полноты и достоверности доступной информации и имеет существенную экспертную составляющую. В работе представлен один из подходов, позволяющих принимать обоснованные решения в области профилактической медицины.
Ключевые слова: профилактическая медицина, оценка и мониторинг процессов, гибридных интеллект.
Решение вопроса о принадлежности слова регулярному языку находит приложение в областях, где осуществляется поиск определенных паттернов в данных различной природы. Актуальной является проблема роста числа состояний распознающего детерминированного конечного автомата (ДКА) от числа регулярных выражений распознаваемого языка — проблема экспоненциального взрыва. В данной статье рассматривается модификация конечного автомата через применение алгоритмов сжатия, работающих без изменения распознаваемого языка и без добавления дополнительных структурных элементов автомата.
Ключевые слова: ДКА, НДКА, регулярный язык, экспоненциальный взрыв, алгоритм сжатия.
Рассматривается динамическая система, описывающая поведение популяции жуков. Жуки живут на поле, которое в начальный момент представляет собой целочисленную решётку, к каждой клетке которой в начальный момент находится одинаковое количество еды для жуков. Жуки в соответствии с некоторым алгоритмом перемещаются по полю, едят расположенную в нём еду и размножаются, причём на все действия расходуется энергия. Система моделируется однородными структурами. В работе показано, что для любой прямой из некоторого класса существует колония, чей линеаризованный график численности бесконечное число раз пересекает выбранную прямую.
Ключевые слова: автоматное моделирование биологической системы, скорость роста динамических систем, клеточный автомат.
В работе исследуется сложность расшифровки класса булевых функций фиксированного веса при помощи запросов на значение, запросов на сравнение, запросов на ограниченную и расширенную эквивалентность. Причем, при расшифровке разрешено использовать только один из упомянутых типов запросов. Для всех типов запросов кроме запросов на сравнение получены точные оценки сложности расшифровки. Для запросов на сравнение приводится верхняя оценка, а также демонстрируется ее совпадение с нижней оценкой для функций веса 1, 2, 3.
Ключевые слова: булевы функции фиксированного веса, запросы на значение, запросы на сравнение, запросы на ограниченную эквивалентность, запросы на расширенную эквивалентность, точная расшифровка.
В данной статье рассматривается применение модели клеточного автомата с локаторами к задаче поиска ближайшего соседа на прямой. Модель клеточного автомата с локаторами подразумевает возможность каждой ячейки автомата передавать через эфир сигнал на сколь угодно большие расстояния. В статье показано, что эта возможность позволяет уменьшить сложность рассматриваемой задачи с линейной до логарифмической по сравнению с классической моделью клеточного автомата.
Ключевые слова: клеточные автоматы, однородные структуры, поиск ближайшей точки.
В настоящей работе найдена решетка 1-следов замкнутых классов кусочно-линейных функций.
Ключевые слова: кусочно-линейные функции, непрерывные кусочно-линейные функции, финитно-параллельные функции, непрерывные финитно-параллельные функции, непрерывные финитно-линейные функции, кусочно-параллельные функции, финитно-линейные функции, параллельные финитно-линейные функции, решетка 1-следов, функция Хэвисайда, 2-предполный класс.
2020 год, том 24, выпуск 2 (PDF)
В статье поставлена задача планирования персональной стратегии обучения и приведены результаты применения различных подходов к ее решению на примере курса обучения программированию.
Ключевые слова: компьютерная обучающая система, предсказание элементов последовательности, нейронная сеть, рекуррентная нейронная сеть, компактное дерево предсказаний.
С использованием технологии обучения нейронных сетей, дистилляции знаний, были получены модели, решающие задачу бинарной классификации с производительностью, превышающей производительность сети-учителя примерно в 5 раз при несущественном падении качества. Сверточная нейронная сеть ResNet-18 была обучена двумя способами по данной технологии (с помощью предобученной сети ResNet-50) и классическим методом. Введено понятие степени неуверенности модели на множестве объектов как величины отклонения предсказаний нейронной сети от принимаемых за ответ значений. Были также проведены эксперименты по рекурсивному применению технологии дистилляции знаний.
Ключевые слова: дистилляция знаний, бинарная классификация, остаточная нейронная сеть, сверточная нейронная сеть, степень неуверенности модели на множестве объектов, рекурсивное обучение нейронных сетей.
Вводится кодирующая функция, инвариантная относительно аффинных отображений и исследуются ее свойства. Найдены необходимые и достаточные условия того, что данный набор чисел является кодом невырожденного изображения.
Ключевые слова: код изображения, кодирование изображений, аффинная эквивалентность.
В работе рассматривается кооперативная игра о доставке транспорта на прямоугольной решетке. Вводятся понятия затора и столкновения автомобилей на ней, а так же автоматов как агентов в светофорах решетки, регулирующих движение. Показано существование структуры автоматов с локальной областью видимости, приводящей к самоорганизации системы светофоров, обеспечивающих сколь угодно длительную корректную доставку автомобилей без заторов и столкновений для любого количества выходов решетки.
Ключевые слова: кооперативная игра, доставка, организация движения транспорта, агент, однородная структура, автомат.
В настоящей статье рассматривается связь между задачей минимизации числа состояний нечёткого автомата и проблемой поиска интервальных формальных понятий с максимальным объёмом. Метод кластеризации, основанный на поиске интервальных формальных понятий, позволяет объединить состояния нечёткого автомата в подмножества со сходными строками достоверностей перехода в другие состояния. При этом мера близости строк определяется заранее заданным параметром σ. В работе показано, что для определённого вида нечётких матриц перехода, начиная с некоторого момента поведение исходного нечёткого автомата, как и поведение минимизированного автомата, стабилизируется. Кроме того, доказано, что при минимизации автомата достоверность слова, распознаваемого нечётким автоматом, не уменьшается. Этот факт позволяет сравнить нечёткий язык, распознаваемый исходным автоматом, и язык, распознаваемый минимизированным.
Ключевые слова: нечёткие автоматы, интервальные формальные понятия, нечёткие языки.
В работе вводится новый математический объект — клеточный автомат с локаторами. Он получается добавлением к клеточному автомату новой возможности - посылать сигналы в “эфир” и получать из “эфира” суммарный сигнал всех элементарных автоматов. Приведены примеры задач, решение которых существенно упрощается, если для их решения использовать клеточные автоматы с локаторами вместо традиционных клеточных автоматов.
Ключевые слова: клеточные автоматы, однородные структуры, задача о стрелках, конструирование движущихся изображений, построение кратчайшего пути.
Автомат предугадывает символ входного сверхслова, если он выдаёт этот символ на выходе в предыдущий момент времени. В работе вводится понятие степени предугадывания на отрезке. Исследуется вопрос о взаимосвязи предугадывания на отрезке и бесконечности. Получен результаты, позволяющие судить о степени предугадывания на отрезке по степени предугадывания на бесконечности и о степени предугадывания на бесконечности по степени предугадывания на отрезке.
Ключевые слова: предугадывающий автомат, автоматное предугадывание общерегулярных сверхслов, степень предугадывания на отрезке.
Рассматривается задача определения порядка линейного автомата. Доказан критерий конечности порядка линейного автомата, позволяющий решать задачу алгоритмически. Дана верхняя оценка на порядок линейного автомата.
Ключевые слова: конечные автоматы, линейные автоматы, порядок в полугруппе.
2020 год, том 24, выпуск 1 (PDF)
Рассматривается алгоритм верификации формализованных математических доказательств. Основная его часть формулируется в виде продукционной системы с метапеременными. Доказываются теоремы о его корректности и полноте.
Ключевые слова: автоматическое доказательство теорем, система автоматизации дедукции, верификация доказательств, язык первого порядка, исчисление предикатов, продукционная система, искусственный интеллект.
В статье вводятся графовые объекты, соответствующие функциональным программам, называемые диаграммами состояний. Показано, как можно использовать диаграммы состояний для решения задач верификации функциональных программ. Предлагаемый подход иллюстрируется примером верификации функциональной программы сортировки.
Ключевые слова: верификация программ, функциональные программы, диаграммы состояний.
Интерпретируемость решения, возможность обучения без учителя, масштабируемость сделали тематическое моделирование одним из наиболее популярных инструментов статистического анализа текстов. Тематические модели позволяют снизить размерность пространства данных, так как описывают каждый документ как вероятностную смесь абстрактных тем, каждую тему как распределение над словами словаря коллекции. Переход из пространства слов в пространство тем приводит к естественному решению проблем синонимии и полисемии терминов. Однако есть и ряд недостатков, вызванных зависимостью решения от инициализации. Неустойчивость тематических моделей являются общеизвестным фактом, однако связанная с ней проблема полноты до сих пор в литературе не изучалась. Для решения этой задачи в статье исследуется новый алгоритм нахождения полного набора тем, основанный на построении выпуклой оболочки. Экспериментально подтверждается эффективность данного алгоритма. На практике полный набор тем использовался в качестве инициализации модели ARTM (additive regularization for topic modeling). По сравнению с рандомизированным начальным приближением, базис тем позволяет повысить устойчивость, перплексию на более 10%, когерентность в разы.
Ключевые слова: вероятностное тематическое моделирование, устойчивость тематических моделей, полный набор тем тематических моделей, латентное размещение Дирихле, LDA, регуляризация, ARTM, BigARTM.
Определяется семантика арифметической реализуемости для формул языка теории множеств, основанная на гиперарифметических видах. Доказывается корректность конструктивной теории множеств без аксиомы объемности относительной этой семантики.
Ключевые слова: конструктивная семантика, реализуемость, арифметическая реализуемость, аксиоматическая теория множеств, гиперарифметические виды.
В работе рассматриваются одномерные сверточные схемы в базисе Маккалока-Питтса. Показано, что рассматриваемые схемы могут быть реализованы схемой из априорной и динамической части, в которой вычисления в априорной части не зависят от входных данных. При этом априорная и динамическая части имеют нелинейную глубину, равную 2.
Ключевые слова: сверточная нейронная сеть, нейронная схема, нелинейная сложность, модель Маккалока-Питтса.
В работе рассматривается соответствие между правильными семействами булевых функций и реберными ориентациями с единственным стоком на булевых кубах. Данное соответствие позволяет перенести часть результатов, полученных для указанных ориентаций, на язык правильных семейств: получить оценки на число правильных семейств порядка n ≥ 5 и показать, что задача распознавания правильности семейства является coNP-полной.
Ключевые слова: правильные семейства булевых функций, реберные ориентации с единственным стоком.
Автомат прогнозирует следующий символ входного сверхслова, если он выдает этот символ на выходе в предыдущий момент времени. В работе исследуется вопрос сужения класса автоматов для задачи прогнозирования произвольного общерегулярного сверхсобытия в многозначном алфавите. Получен класс автоматов достаточный для задачи прогнозирования, а также с его помощью доказан переход от оценок простых сверхсобытий к оценкам составных.
Ключевые слова: прогнозирование автоматами, общерегулярное сверхсобытие, автоматное прогнозирование общерегулярных сверхсобытий.
Для коэффициентов полиномов функций над конечными полями Fq рассматривается задача отыскания нижней оценки на максимум минимума числа ненулевых коэффициентов в полиноме, где максимум берется по всем функциям, а минимум — по их преобразованиям, соответствующим различным заданиям поля. При этом возможно рассматривать различные типы таких преобразований. В работе получена оценка L(q) ≥ q − 2 на максимум минимума числа ненулевых коэффициентов в полиноме для определенного типа преобразований, оставляющих нулевой элемент поля на месте.
Ключевые слова: коэффициенты полиномов, булевы функции, полином булевой функции, таблица значений функции, sagemath.
Данная статья посвящена описанию изменения размерности периодических подмножеств натурального ряда при, казалось бы, таких незначительных операциях, как удаление/добавление к множеству одного числа. В работе исследуется случай, когда размерность исходного множества равна 1 или 2. Под размерностью множества понимается минимальное число непересекающихся арифметических прогрессий, дающих в объединениее это множество. Для множеств размерности 2 результат получен только в случаях пар прогрессий общего положения. В работе приводятся результаты о том, как именно меняется размерность в зависимости от того, откуда удаляется/куда добавляется число x.
Ключевые слова: арифметическая прогрессия, натуральный ряд, прогрессивное множество.
Доказано, что почти любую булеву функцию от n переменных можно реализовать неизбыточной двухполюсной контактной схемой, допускающей единичный диагностический тест длины 8 относительно обрывов и замыканий контактов.
Ключевые слова: контактная схема, булева функция, обрыв контакта, замыкание контакта, единичный диагностический тест.