В лекции приводятся определения основных понятий теории экспериментов: синхронизирующих, установочных и диагностических последовательностей, конструкции дерева преемников. Описывается конструкция синхронизирующего (установочного, диагностического) дерева, используемая для построения минимальной по весу синхронизирующей (установочной, диагностической) последовательности, а также процедура ее построения.

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

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

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

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

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

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

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

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

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

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

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

Для состояния линейного автомата определяются понятия равновесия и асимптотической устойчивости. Приводится критерий существования у свободного ЛА асимптотически устойчивого состояния. Рассмотрена задача стабилизации ЛА и проблема ее разрешимости. Для дискретных линейных систем над полем R введено понятие e-синхронизирующей последовательности и приводится критерий ее существования.

Рассматривается задача построения тестовой последовательности для заданной неисправности в стационарных и нестационарных ЛА, обнаруживающей эту неисправность. Описаны простые в реализации методы построения такой тестовой последовательности для \mu-определенных и синхронизируемых линейных автоматов. Для произвольных ЛА предложен метод построения тестовой последовательности, основанный на наличии у любого ЛА конечной памяти.

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

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

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

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

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

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

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

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