Математическая кибернетика. Теория управляющих систем. Теория автоматов. Математическая теория информации. Теория кодов. Математические вопросы семиотики

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

Автор, исходя из позиций своей теории «Автономного адаптивного управления», представленной в книге «Автономный искусственный интеллект», предлагает ряд дополнительных аспектов и понятий к общей теории систем (ОТС), которые могут сделать ОТС более конкретным инструментом для разработчиков систем. Особое внимание уделяется системам, конфигурация которых близка к наиболее важным для нас системам — к живому мозгу. С предлагаемых позиций анализируются основные подходы ОТС — математический, физический и теория функциональных систем.

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

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

В работе рассматриваются мультилинейные формы над конечными полями. Муль-тилинейной формой над некоторым полем называется произведение, в котором каждый сомножитель является суммой переменных или элементов этого поля. Каждая мульти линейная форма определяет некоторую функцию над этим полем. Мульти линейная форма называется выполнимой, если она задает ненулевую функцию. Показана АГР-полнота задачи распознавания выполнимости мультилинейных форм над каждым конечным полем из q элементов при q ^ 3. Доказана теорема, разделяющая случаи полиномиальности и ЛГР-полноты задачи выполнимости мультилинейных форм при каждом возможном

Изучена задача линейной классификации четности перестановочных матриц. Эта задача связана с анализом сложности класса алгоритмов вычисления перманента матрицы, обобщающего алгоритм знаков Кастелейна. Получены экспоненциальные нижние оценки для величины коэффициентов функционала, классифицирующего четные и нечетные перестановочные матрицы, в случае поля действительных чисел, и аналогичные линейные нижние оценки на ранг классифицирующего отображения в случае поля характеристики 2. Библ. 10. Фиг. 2

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

Актуальность и цели. Булевы и многозначные функции – основной объект изучения дискретной математики. Они представляют собой зависимости между величинами, принимающими конечный набор значений. Существует несколько способов описания таких зависимостей, и на практике часто встречается табличное задание функции и задание в виде полинома. Оба эти представления функций можно выразить в виде векторов. В случае табличного задания функции это вектор ее значений, в случае полиномиального задания – вектор коэффициентов полинома. Преобразование вектора значений функции в вектор коэффициентов ее полинома в булевом случае является преобразованием Мёбиуса. Неподвижные точки такого преобразования мы будем называть стационарными функциями. Пусть α – вектор, состоящий из n элементов поля E3 . α-преобразованием функции f будем называть такую функцию g =ν (f), что g(x,,x)=f(x+α,,x+α).Если ν  (f)= f , то такую

Работа посвящена определению курса, скорости цели и дистанции до неё (ЭДЦ) при условии, что цель и преследователь двигаются постоянными курсами и скоростями, но при этом либо цель либо преследователь могут произвести один раз маневр курсом. Предполагается, что наблюдатель производит замеры пеленгов в пассивном режиме. В работе изложены принципы построения комплексного метода определения ЭДЦ при одном маневре курсом. Метод определения ЭДЦ основан на показателях, введенных в работе [1]: величина изменения расстояния логарифмическая (ВИРЛ), величина изменения пеленга (ВИП), которые определяются пеленгованием на прямом курсе и не требуют при этом знания ЭДЦ.

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

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

Для всех бесконечных базисов найдены оценки схемной глубины всех булевых функций с точностью до небольшой аддитивной постоянной.

Исследуется задача о сложности вычисления системы одночленов схемами композиции. Под сложностью в такой модели понимается минимальное число операций композиции, достаточное для вычисления системы по переменным. Установлено, что рассматриваемая мера сложности может быть значительно меньше известных мер сложности, соответствующих моделям, допускающим, например, либо только операцию умножения, либо операции умножения и деления, либо операцию умножения с возможностью использования величин, обратных к переменным. Однако это свидетельство значительной "вычислительной силы" изучаемой модели не носит универсальный характер, что подтверждено соответствующим примером. Кроме того, для системы, состоящей из двух одночленов от двух переменных, получено точное значение сложности. Также установлено, что при вычислениях с использованием операции композиции не работают (или работают в недостаточной мере) соображения двойственности.

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

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

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

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

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

Рассматриваются схемы из функциональных элементов, реализующие функции k-значной логики над произвольным конечным полным базисом B.

Для всех бесконечных базисов найдены оценки схемной глубины всех булевых функций с точностью до небольшой аддитивной постоянной.

О мультипликативной сложности квазиквадратичных функций алгебры логики

Эта работа – одна из первых работ, в которой подробно, со всеми доказательствами рассматривается задача синтеза надежных схем с элементами, подверженными неисправностям двух типов. Предполагается, что базисным элементам приписана функция штрих Шеффера (антиконъюнкция) и базисные элементы в неисправные состояния переходят независимо друг от друга. Первый тип неисправностей характеризуется тем, что при любом входном наборе базисного элемента на его выходе с некоторой вероятностью появляется значение, противоположное конъюнкции входных значений (т. е. имеем инверсные неисправности на выходах). Второй тип неисправностей появляется также на любом входном наборе элемента с некоторой (возможно, отличной от инверсной неисправности) вероятностью и характеризуется тем, что на выходе элемента появляется неопределенность. Отметим также, что в каждый такт работы базисный элемент подвержен только одной из двух названных неисправностей. Цель данной работы: исследовать возможность построения надежных схем, найти метод синтеза надежных схем, получить нетривиальные верхние и нижние оценки ненадежности схем.

Рассматривается один из важнейших разделов математической кибернетики - теория синтеза, надежности и сложности управляющих систем. К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. В ряде результатов, относящихся к реализации булевых функций надежными схемами из ненадежных функциональных элементов, фигурирует параметр N[g] - наименьшее число функциональных элементов, необходимых для реализации функции голосования x в рассматриваемом полном базисе. Оказалось, что еще и другие функции (обозначим их множество через G), обладают свойствами, аналогичными свойствам функции голосования. Эти функции в статье называются обобщенными функциями голосования. Цель данной работы - получить верхнюю оценку величины N[G], которая была бы справедлива в произвольном базисе.

Доказываются 28 свойств, связывающих предполные классы трехзначной логики.

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

Рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки (стоп-оператором) в произвольном полном конечном базисе. В исправном состоянии стоп-оператор прекращает работу программы, если на его вход поступает единица. Предполагается, что и функциональные операторы, и стоп-операторы программы ненадежны, переходят в неисправные состояния независимо друг от друга. Считаем, что вычислительные операторы с вероятностью [эпсилон] ([эпсилон] принадлежит множеству (0, 1/2) ) подвержены инверсным неисправностям на выходах. А для операторов условной остановки рассматриваются два типа неисправностей. Неисправность первого типа характеризуется тем, что при поступлении единицы на вход стоп-оператора он с вероятностью [дельта] ([дельта] принадлежит множеству (0, 1/2) ) не срабатывает, и, следовательно, работа программы продолжается. Неисправность второго типа такова, что при поступлении нуля на вход стоп-оператора он с вероятностью [эта] ([эта] принадлежит множеству (0, 1/2) ) срабатывает, и, следовательно, работа программы прекращается. Доказано, что любую булеву функцию f можно реализовать программой, ненадежность которой не больше max {[эпсилон], [эта]} + 145 [сигма]{2} при всех [эпсилон] принадлежит множеству (0, 1/960] и [сигма]=max{[эпсилон], [дельта], [эта]}.

Рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки в полном конечном базисе B, содержащем некоторую функцию вида x{a[1]} [1] v x{a[2]} [2], a[1], a[2] {0, 1}. Предполагается, что функциональные операторы с вероятностью [эпсилон] ([эпсилон] (0, 1/2) ) подвержены инверсным неисправностям на выходах, а операторы условной остановки абсолютно надежны. Доказано, что любую булеву функцию f можно реализовать неветвящейся программой, функционирующей с ненадежностью не больше [эпсилон] + 81[эпсилон]{2} при [эпсилон] (0, 1/960).

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе B, содержащем специальные функции. Предполагается, что все элементы схемы независимо друг от друга с вероятностью [эпсилон] (0, 1/2) подвержены неисправностям типа 0 на выходах. Доказано, что почти для всех булевых функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной [эпсилон] при [эпсилон] [стрелка вправо] 0. Эта оценка ненадежности в два раза меньше, чем в случае инверсных неисправностей на выходах элементов в соответствующих базисах.

Рассматривается реализация булевых функций схемами из ненадежных элементов в полном базисе B B[3] (B[3] - множество всех булевых функций, зависящих от переменных x[1], x[2], x[3]). Предполагается, что все элементы схемы независимо друг от друга с вероятностью [эпсилон] ([эпсилон] (0, 1/2) ) подвержены инверсным неисправностям на выходах. Найдены базисы, в которых почти булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью 5[эпсилон] при [эпсилон] [стремящемуся к] 0. Других таких базисов B B[3], в которых почти булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью 5[эпсилон], нет.

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисах, содержащих функцию h (x[1],..., x[2k+1]) множества H[2k+1]. Предполагается, что базисные элементы независимо друг от друга с вероятностью ? (? принадлежит множеству (0, 1/2) ) подвержены инверсным неисправностям на входах элементов. В работе показано: 1) в произвольном конечном полном базисе B, содержащем функцию h (x[1],..., x[2k+1]) множества H[2k+1], все булевы функции можно реализовать схемами с ненадежностью не более a? {k+1} + ? {k+2} при ? ? {1}[48am{2} (2k+1) ], где a = C{k+1}[2k+1], m - наибольшее число входов элементов в полном конечном базисе B, 2) в базисе B{? }, содержащем все функции, зависящие не более чем от двух переменных, и функцию h (x[1],..., x[2k+1]) принадлежит множеству H[2k+1], функции 0, 1, x[1], x[2],..., x[n] можно реализовать абсолютно надежно, а все остальные функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически (при ? > 0) равной a? {k+1}, где a = C{k+1}[2k+1].

Рассматривается задача синтеза асимптотически оптимальных схем, реализующих булевы функции, при инверсных неисправностях на выходах элементов в полном базисе {xІy, xvy, x&y, xvy, x}. Доказано, что в рассматриваемом базисе все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, причем почти для всех функций эти схемы функционируют с ненадежностью, асимптотически равной 3? при ? >0, где ? - вероятность инверсной неисправности на выходе базисного элемента.

Решается задача реализации булевых функций надежными схемами из ненадежных функциональных элементов в базисе {x[1]x[2] v x[1]x[3] v x[2]x[3], x[1] v x[2] v x[3], x[1] & x[2] & x[3], x{-}[1]}. Для решения задачи предлагаются два разных метода повышения надежности схем: первый - с использованием дизъюнктора и конъюнктора, а второй - с использованием элемента голосования. Рассматриваются три типа неисправностей элементов: 1) инверсные неисправности на входах элементов, 2) однотипные константные неисправности на выходах элементов, 3) однотипные константные неисправности на входах элементов. В каждом случае применяются два названных метода и сравниваются полученные оценки ненадежности схем. Показывается, что при однотипных константных неисправностях на входах элементов использование элемента голосования (второй метод) дает худшую оценку ненадежности, чем использование конъюнктора и дизъюнктора.

Рассматривается задача синтеза асимптотически оптимальных схем, реализующих булевы функции, при инверсных неисправностях на выходах элементов в базисе {x & y, x v y, x{-}}. Доказано, что почти все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, которые функционируют с ненадежностью, асимптотически равной 3? при ? > 0, где ? - вероятность инверсной неисправности на выходе базисного элемента. Сложность предлагаемых схем превышает сложность минимальных схем, построенных только из надежных элементов, не более чем в 3 раза.

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

Показано, что если к базису {x[1] & x[2], x[1]} добавить, по крайней мере, еще одну булеву функцию, зависящую не более чем от двух переменных, то асимптотическая оценка ненадежности значительно понижается.

Решается задача построения асимптотически оптимальных по надежности схем в базисе. Доказано, что любую булеву функцию f (x[1], x[2],..., x[n]), не равную x[i] (i = 1, 2,..., n) и константам 0 и 1, можно реализовать асимптотически оптимальной по надежности схемой, функционирующей с ненадежностью асимптотически равной [гамма{k}] при [гамма] стремится к 0. Функции x[i], i = 1, 2,..., n, можно реализовать абсолютно надежно, а константы 0 и 1 - схемами сколь угодно высокой надежности.

Международный стандарт IEC 61499 в области промышленной автоматизации вводит класс систем управления нового поколения, которые характеризуются как разумные реконфигурируемые распределенные компонентно-базированные системы. Стандарт IEC 61499 поддерживает парадигму проектирования на основе функциональных блоков (ФБ). Одной из наиболее важных моделей выполнения ФБ является циклическая модель. Отсутствие точно определенной формальной семантики для циклической модели выполнения может негативно отразиться на качестве проектируемого управляющего программного обеспечения, в частности, это может затруднить проведение верификации и имитационного моделирования систем автоматизации.

Предлагается синтактико-семантическая модель базисных функциональных блоков стандарта IEC 61499. Для определения абстрактного синтаксиса используется теоретико-множественный подход, а для представления операционной семантики - аппарат машин абстрактных состояний.

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

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

Учебно-методическое пособие содержит изложение теоретического, практического материалов, задания для самостоятельной работы и предназначено для изучения дисциплины «Оптимизация в управлении» магистерской программы «Математические методы в управлении и образовании» направления 050100.68 «Педагогическое образование». Данное издание может быть рекомендовано бакалаврам направления 010500.62 «Математическое обеспечение и администрирование информационных систем» для изучения дисциплины «Исследование операций», а также всем студентам для освоения курса «Оптимизация в управлении» элективного модульного блока «Бизнес-математика».

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