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 относительно обрывов и замыканий контактов.

Ключевые слова: контактная схема, булева функция, обрыв контакта, замыкание контакта, единичный диагностический тест.