2023 год, том 27, выпуск 4 (PDF)

А.А. Часовских, В.С. Половников, А.А. Хусаенов, Г.В. Боков, А.Ю. Коновалов, А.С. Дробышев, В.А. Бирюкова Автоматизация поиска архитектур искусственных нейронных сетей

Представлен обзор работ о методах автоматизации генерирования архитектур искусственных нейронных сетей. Наиболее подробно излагается материал по использованию для этого больших языковых моделей. Для экспериментов использован ChatGPT & Midjourney, который доступен в мессенджере Telegram.

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

П.С. Дергач, Д.Б. Бахрамова Об автоматных неисправностях при алфавитном кодировании

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

Ключевые слова: алфавитное кодирование, диаграмма Мура, автоматные неисправности.

Н.П. Корчагин Сложность задачи о существовании сюръективного гомоморфизма на рефлексивные циклы

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

Ключевые слова: сюръективные гомоморфизмы, сложность вычислений, удовлетворение ограничениям, полиморфизмы.

Н.Ф. Алексиадис Замкнутые классы в функциональной системе рациональных функций с рациональными коэффициентами

Функциональная система представляет собой множество функций с некоторым набором операций, применяемых к этим функциям и приводящих к получению других функций из этого же множества. Функциональные системы являются одним из основных объектов дискретной математики и математической кибернетики, поскольку они являются математическими моделями реальных и абстрактных управляющих систем. Проблематика функциональных систем обширна. Одной из основных задач является проблема полноты, состоящая в описании таких подсистем функций, которые являются полными, т.е. из этих функций с помощью заданных операций над ними можно получить все функции. Мы рассматриваем функциональную систему рациональных функций с рациональными коэффициентами, где в качестве операций выступают операции суперпозиции, и для этой системы исследуем задачу о замкнутых классах (структура, базис, число конечных и бесконечных замкнутых классов). Это обусловлено тем, что проблема полноты решается с помощью (максимальных) замкнутых классов. В настоящей статье для функциональной системы рациональных функций с рациональными коэффициентами:
1. описаны в явном виде все конечные замкнутые классы;
2. найдено число всех конечных замкнутых классов, всех бесконечных замкнутых классов и всех замкнутых классов;
3. изучена задача о базисах замкнутых классов, а именно, установлено, что существует замкнутый класс, имеющий конечный базис, существует замкнутый класс, имеющий бесконечный базис, и существует замкнутый класс, не имеющий базиса; приведены конкретные примеры соответствующих замкнутых классов;
4. найдено число замкнутых классов, имеющих конечный базис, число замкнутых классов, имеющих бесконечный базис, и число замкнутых классов, не имеющих базиса.

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

Д.Н. Бабин, А.А. Летуновский О выразимости автоматов с операцией суперпозиции

Задача выразимости для константных автоматов и линейных автоматов для расширенной суперпозиции алгоритмически разрешима. Имеет место теорема об алгоритмической разрешимости задачи выразимости автоматов с линейными переходами над полем конечной характеристики.

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

П.С. Дергач, Н.С. Ботирова Об изменении длины минимальной склейки при алфавитных неисправностях

Целью данной статьи является исследование характера изменения минимальной длины склейки для алфавитного кодирования при различных типах неисправностей в схемах. Рассматриваются три вида операций: удаление, добавление и замена одной буквы. Основной вопрос, изучаемый в работе, заключается в оценке того, во сколько раз может измениться длина минимальной склейки после выполнения каждой из указанных операций. В результате исследования был найден критерий сохранения свойства неоднозначности в терминах схемы кодирования, а также получены верхние и нижние оценки на скорость изменения длины минимальной склейки в каждом из трех случаев. Данные оценки являются важным практическим инструментом для проектирования алфавитных кодировок с учетом возможных неисправностей в схемах.

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