Теория экспериментов с конечными автоматами: Информация
Автор: Дмитрий Сперанский
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 3 студентам
Уровень:
Специалист
Длительность:
25:24:00
Студентов:
367
Выпускников:
35
Качество курса:
5.00 | 5.00
Конечные автоматы представляют собой удобные и адекватные математические модели, широко применяющиеся для описания структур и процессов функционирования цифровой аппаратуры, при разработке программных систем и трансляторов и во многих других предметных областях.
В данном курсе лекций излагаются результаты теории экспериментов с автоматами, востребованные при решении задач технической диагностики дискретных
устройств, кодирования и декодирования информации, задач распознавания, расшифровки и идентификации и т.п.
Специальности: Математик
ISBN: 978-5-9963-0268-0
Теги: beta, автомат мили, автоматы, алгоритмы, анализ, асимптотическая устойчивость, генетические алгоритмы, диагностическая задача, запаздывания, компоненты, критерий существования, оценки длины, порожденная сеть, потоки, проверочный граф, программирование, процедуры, теория, функция выходов, хромосомы, элементы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 3 минуты
Эксперименты с автоматами, имеющими взвешенный входной алфавит
В лекции приводятся определения основных понятий теории экспериментов: синхронизирующих, установочных и диагностических последовательностей, конструкции дерева преемников. Описывается конструкция синхронизирующего (установочного, диагностического) дерева, используемая для построения минимальной по весу синхронизирующей (установочной, диагностической) последовательности, а также процедура ее построения.
Оглавление
-
Лекция 2
51 минута
Синтез экспериментов методами динамического программирования
Описываются рекурсивные методы построения графов синхронизации, установки и диагностики автомата. Показано, что задачи построения минимальных по весу СП и УП сводятся к задачам выбора наискорейшего пути по сети дорог, эффективно решаемым методами динамического программирования из теории оптимального управления. Задача синтеза минимальной по весу ДП по графу диагностики автомата сводится к вырожденной в данном случае задаче поиска минимального пути между двумя вершинами.
Оглавление
-
Лекция 3
1 час 6 минут
Обобщенные автоматы без потери информации
Определен новый класс автоматов без потери информации, названных обобщенными автоматами БПИ. Приводится критерий принадлежности автомата этому классу в терминах состояний с потерей информации. Описывается алгоритм распознавания проекции неизвестного входного слова по заданному множеству каналов. Предложена конструкция так называемого проверочного графа автомата, и в его терминах формулируется еще один критерий принадлежности автомата классу ОБПИ.
Оглавление
-
Лекция 4
47 минут
Обобщенные автоматы без потери информации конечного порядка
Определен новый класс автоматов без потери информации конечного порядка, названных обобщенными автоматами БПИК. Приводится критерий принадлежности автомата классу БПИК в терминах проверочного графа. Описан способ определения порядка БПИК-автомата. Описан метод построения комбинационной схемы, восстанавливающей проекцию неизвестного входного слова.
Оглавление
-
Лекция 5
1 час 38 минут
Преобразования автоматов в автоматы без потери информации
Исследуется задача преобразования произвольного автомата в автомат без потери информации на заданном регулярном множестве входных слов. Предложен метод решения, основанный на расширении выходного алфавита автомата. Описывается процедура построения проверочного графа для заданного автомата и заданного регулярного события. В терминах этого графа дается критерий того, что автомат является автоматом БПИ на словах этого события. Приводится процедура построения по исходному автомату автомата БПИ на заданном регулярном множестве слов за счет выведения дополнительных контрольных точек.
Оглавление
-
Лекция 6
1 час 31 минута
Эксперименты по контролю функции выходов инициального автомата
Исследуется задача контроля функции инициального автомата, которая с математической точки зрения сводится к задаче построения специального обхода графа этого автомата. Приведен критерий существования такого обхода, который реализуется в процессе подачи на автомат так называемого характеристического слова. Доказываются различные утверждения, касающиеся оценок длин кратчайших обходов графа и характеристических слов.
Оглавление
-
Лекция 7
48 минут
Контроль функции выходов неинициального автомата с использованием простого безусловного эксперимента
Исследуется задача контроля функции выходов автомата в случае, когда неизвестно его начальное состояние. Приведен критерий разрешимости задачи. Показывается, что эта задача сводится к классической задаче распознавания автомата из известного класса. Описывается метод ее решения и приводится верхняя оценка длины контролирующего эксперимента.
Оглавление
-
Лекция 8
1 час 17 минут
Контроль функции выходов инициального автомата с использованием кратного безусловного эксперимента
Исследуется задача контроля функции выходов автомата с помощью кратного безусловного эксперимента. Вводятся понятия покрытия, приведенного и минимального покрытия графа множеством путей и кратности покрытия. Показано, что исходная задача редуцируется к задаче нахождения покрытия графа автомата. Приводятся критерий разрешимости задачи и оценки длин покрытия. Описывается алгоритм построения покрытия.
Оглавление
-
Лекция 9
33 минуты
Преобразование автомата для упрощения функционального контроля
Описаны способы контроля автоматов с применением специальных схем, называемых схемами встроенного контроля. Предлагается одна из разновидностей такой схемы, основанная на принципе восстановления входных сигналов. В ней используются ОБПИК-автоматы порядка 1. Описывается метод преобразования произвольного автомата в автомат названного типа, базирующийся на выведении из исходного автомата дополнительных контрольных точек.
Оглавление
-
Лекция 10
51 минута
Синхронизирующие эксперименты с линейными автоматами
Описываются модели стационарных и нестационарных линейных автоматов, их структура и элементарные составляющие. Приводятся основные понятия теории экспериментов с линейными автоматами, формулы для вычисления конечных состояний и реакций автоматов. Исследуются синхронизирующие последовательности: критерий существования, их свойства, верхняя оценка длины минимальных СП. Описан метод решения задачи перевода автомата в заданное синхросостояние.
Оглавление
-
Лекция 11
1 час 5 минут
Установочные и диагностические эксперименты со стационарными и нестационарными линейными автоматами
Приводятся условия существования установочных и диагностических последовательностей для стационарных линейных автоматов, сформулированные в терминах характеристических матриц автоматов. Исследуются свойства последовательностей. Аналогичные результаты приводятся для нестационарных линейных автоматов.
Оглавление
-
Лекция 12
1 час 6 минут
Эксперименты в пространстве обобщенных состояний и с линейными автоматами с запаздыванием
Введены понятия обобщенного состояния линейного автомата, обобщенных синхронизирующих, установочных и диагностических последовательностей. Для всех таких последовательностей сформулированы критерии их существования. Рассмотрены различные типы автоматов с запаздыванием (обыкновенные, по управлению, по состоянию), и для них получены критерии существования всех типов упомянутых выше последовательностей.
Оглавление
-
Лекция 13
1 час 12 минут
Синхронизация и устойчивость дискретных линейных систем
Для состояния линейного автомата определяются понятия равновесия и асимптотической устойчивости. Приводится критерий существования у свободного ЛА асимптотически устойчивого состояния. Рассмотрена задача стабилизации ЛА и проблема ее разрешимости. Для дискретных линейных систем над полем R введено понятие e-синхронизирующей последовательности и приводится критерий ее существования.
Оглавление
-
Лекция 14
55 минут
Эксперименты по распознаванию неисправностей линейных автоматов
Рассматривается задача построения тестовой последовательности для заданной неисправности в стационарных и нестационарных ЛА, обнаруживающей эту неисправность. Описаны простые в реализации методы построения такой тестовой последовательности для \mu-определенных и синхронизируемых линейных автоматов. Для произвольных ЛА предложен метод построения тестовой последовательности, основанный на наличии у любого ЛА конечной памяти.
Оглавление
-
Лекция 15
39 минут
Линейные автоматы существенно без потери информации
Описывается класс автоматов без потери информации и доказывается эквивалентность двух разных его определений, данных Гиллом и Хаффменом. Вводится новая разновидность автоматов БПИ, названных автоматами существенно БПИ конечного порядка, и приводится критерий принадлежности автомата этому классу. Описывается метод синтеза комбинационной схемы, восстанавливающей первый символ неизвестного слова, поданного на вход автомата БПИК.
Оглавление
-
Лекция 16
1 час 7 минут
Обобщенные линейные автоматы без потери информации
Вводится класс обобщенных линейных автоматов без потери информации и даются условия принадлежности автомата этому классу. Определяется понятие его оптимального подавтомата, описывается процедура выделения такого подавтомата из ЛА и доказывается его единственность.
Оглавление
-
Лекция 17
56 минут
Минимизация времени восстановления неизвестных входных сигналов в сети из автоматов без потери информации
Введено понятие корректной сети из линейных автоматов без потери информации, и для нее исследуется задача минимизации времени восстановления неизвестных входных сигналов по наблюдаемым выходам. Предложен метод решения этой задачи, основанный на сведении ее к классической задаче о потоке минимальной стоимости из теории потоков.
Оглавление
-
Лекция 18
59 минут
Оптимальные эксперименты с линейными автоматами
Вводится понятие линейного автомата с взвешенным входным алфавитом в пространстве обобщенных состояний. Исследуется задача построения обобщенных синхронизирующих последовательностей с минимальным весом, переводящих ЛА из любого обобщенного состояния в заданное. Показано, что задача построения синхронизирующей последовательности минимального веса сводится к задаче целочисленного линейного программирования с линейными ограничениями. Исследуется задача построения обобщенной синхронизирующей последовательности с минимальным числом перепадов и описывается метод ее решения, который также основан на ее редукции к упомянутой задаче линейного программирования.
Оглавление
-
Лекция 19
57 минут
Интервальная арифметика над конечным полем и ее приложения к теории экспериментов с автоматами
Описывается интервальная арифметика над полем GF(p). Вводятся понятия интервала, обобщенного интервала, правильного и неправильного интервалов, бинарные арифметические операции над интервалами и исследуются свойства этих операций. Рассматриваются вопросы решения интервальных уравнений. Вводятся понятия алгебраического, объединенного, допустимого и управляемого множества решений интервальных уравнений.
Оглавление
-
Лекция 20
1 час 10 минут
Диагностическая задача в интервальной постановке
Исследуется диагностическая задача для линейных автоматов, когда наблюдаемая на выходах реакция автоматов представлена в виде интервалов в поле GF(p). Предложены методы решения диагностической задачи с использованием модифицированной конструкции дерева преемников и путем сведения ее к решению систем линейных алгебраических уравнений с интервальной правой частью. Описан генетический алгоритм для решения упомянутой системы, значительно сокращающий время поиска решений.
Оглавление
-
Лекция 21
55 минут
Эксперименты с билинейными автоматами по распознаванию состояний
Объектом исследования являются билинейные автоматы. Для автоматов такого типа приведены критерии существования синхронизирующих, установочных и диагностических последовательностей, сформулированные в терминах их характеристических матриц. Предложены и обоснованы аналитические методы построения перечисленных последовательностей и исследованы их свойства.
Оглавление
-
Лекция 22
46 минут
Разновидности экспериментов с билинейными автоматами
Исследованы эксперименты по распознаванию неизвестного входного слова билинейного автомата и некоторые модификации понятия билинейного автомата без потери информации. Рассмотрены различные типы билинейных автоматов с запаздыванием и для них приведены критерии существования синхронизирующих, установочных и диагностических последовательностей.
Оглавление
-