2020 год, том 24, выпуск 3 (PDF)

Суворова Е.И., Концевая А.В., Рыжов А.П., Сапунова И.Д., Мырзаматова А.О., Муканеева Д.К., Худяков М.Б., Драпкина О.М. Оценка и мониторинг эффективности популяционных мер профилактики заболеваний

Принятие эффективных управленческих решений в сфере охраны здоровья и профилактики заболеваний позволяет повысить продолжительность и качество жизни. Процесс принятия таких решений происходит в условиях ограниченной полноты и достоверности доступной информации и имеет существенную экспертную составляющую. В работе представлен один из подходов, позволяющих принимать обоснованные решения в области профилактической медицины.

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

Бернадотт А. Модификация конечного автомата через применение алгоритмов сжатия

Решение вопроса о принадлежности слова регулярному языку находит приложение в областях, где осуществляется поиск определенных паттернов в данных различной природы. Актуальной является проблема роста числа состояний распознающего детерминированного конечного автомата (ДКА) от числа регулярных выражений распознаваемого языка — проблема экспоненциального взрыва. В данной статье рассматривается модификация конечного автомата через применение алгоритмов сжатия, работающих без изменения распознаваемого языка и без добавления дополнительных структурных элементов автомата.

Ключевые слова: ДКА, НДКА, регулярный язык, экспоненциальный взрыв, алгоритм сжатия.

Воротников А.С. О синтезе колонии жуков с линейным ростом

Рассматривается динамическая система, описывающая поведение популяции жуков. Жуки живут на поле, которое в начальный момент представляет собой целочисленную решётку, к каждой клетке которой в начальный момент находится одинаковое количество еды для жуков. Жуки в соответствии с некоторым алгоритмом перемещаются по полю, едят расположенную в нём еду и размножаются, причём на все действия расходуется энергия. Система моделируется однородными структурами. В работе показано, что для любой прямой из некоторого класса существует колония, чей линеаризованный график численности бесконечное число раз пересекает выбранную прямую.

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

Быстрыгова А.В. Расшифровка булевых функций фиксированного веса

В работе исследуется сложность расшифровки класса булевых функций фиксированного веса при помощи запросов на значение, запросов на сравнение, запросов на ограниченную и расширенную эквивалентность. Причем, при расшифровке разрешено использовать только один из упомянутых типов запросов. Для всех типов запросов кроме запросов на сравнение получены точные оценки сложности расшифровки. Для запросов на сравнение приводится верхняя оценка, а также демонстрируется ее совпадение с нижней оценкой для функций веса 1, 2, 3.

Ключевые слова: булевы функции фиксированного веса, запросы на значение, запросы на сравнение, запросы на ограниченную эквивалентность, запросы на расширенную эквивалентность, точная расшифровка.

Васильев Д.И. Поиск ближайшего соседа на прямой с помощью клеточного автомата с локаторами

В данной статье рассматривается применение модели клеточного автомата с локаторами к задаче поиска ближайшего соседа на прямой. Модель клеточного автомата с локаторами подразумевает возможность каждой ячейки автомата передавать через эфир сигнал на сколь угодно большие расстояния. В статье показано, что эта возможность позволяет уменьшить сложность рассматриваемой задачи с линейной до логарифмической по сравнению с классической моделью клеточного автомата.

Ключевые слова: клеточные автоматы, однородные структуры, поиск ближайшей точки.

Кан А.Н. Решетка 1-следов замкнутых классов кусочно-линейных функций

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

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