Компьютерные науки

Теория экспериментов с конечными автоматами

Программа об изучении конечных автоматов как моделей для описания структур цифровой аппаратуры. Излагаются передовые методы технической диагностики дискретных устройств.
Студентов 403 Выпускников 35 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Эта учебная программа подробно рассматривает диагностические эксперименты, распознавание неисправностей линейных автоматов и задачи кодирования. В обучение включен синтез экспериментов методами динамического программирования и анализ автоматов без потери информации. Особое внимание уделено интервальной арифметике. Учебная программа будет полезна инженерам-разработчикам цифровой техники, специалистам по технической диагностике и создателям программных трансляторов, которым требуются надежные модели для контроля функций устройств.
Цели
  • Сформировать понимание теории экспериментов с автоматами.
  • Дать инструменты для синтеза установочных и диагностических экспериментов.
  • Раскрыть подходы к распознаванию неисправностей.
Чему я научусь?
  • Проводить эксперименты по контролю функции выходов.
  • Оценивать устойчивость дискретных линейных систем.
  • Минимизировать время восстановления входных сигналов.

Авторы

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

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Эксперименты с автоматами, имеющими взвешенный входной алфавит В лекции приводятся определения основных понятий теории экспериментов: синхронизирующих, установочных и диагностических последовательностей, конструкции дерева преемников.... В лекции приводятся определения основных понятий теории экспериментов: синхронизирующих, установочных и диагностических последовательностей, конструкции дерева преемников. Описывается конструкция синхронизирующего (установочного, диагностического) дерева, используемая для построения минимальной по весу синхронизирующей (установочной, диагностической) последовательности, а также процедура ее построения. ещё
2 Синтез экспериментов методами динамического программирования Описываются рекурсивные методы построения графов синхронизации, установки и диагностики автомата. Показано, что задачи построения минимальных по... Описываются рекурсивные методы построения графов синхронизации, установки и диагностики автомата. Показано, что задачи построения минимальных по весу СП и УП сводятся к задачам выбора наискорейшего пути по сети дорог, эффективно решаемым методами динамического программирования из теории оптимального управления. Задача синтеза минимальной по весу ДП по графу диагностики автомата сводится к вырожденной в данном случае задаче поиска минимального пути между двумя вершинами. ещё
Синтез экспериментов методами динамического программирования тест для курса Теория экспериментов с конечными автоматами 40 мин
3 Обобщенные автоматы без потери информации Определен новый класс автоматов без потери информации, названных обобщенными автоматами БПИ. Приводится критерий принадлежности автомата этому... Определен новый класс автоматов без потери информации, названных обобщенными автоматами БПИ. Приводится критерий принадлежности автомата этому классу в терминах состояний с потерей информации. Описывается алгоритм распознавания проекции неизвестного входного слова по заданному множеству каналов. Предложена конструкция так называемого проверочного графа автомата, и в его терминах формулируется еще один критерий принадлежности автомата классу ОБПИ. ещё
4 Обобщенные автоматы без потери информации конечного порядка Определен новый класс автоматов без потери информации конечного порядка, названных обобщенными автоматами БПИК. Приводится критерий принадлежности... Определен новый класс автоматов без потери информации конечного порядка, названных обобщенными автоматами БПИК. Приводится критерий принадлежности автомата классу БПИК в терминах проверочного графа. Описан способ определения порядка БПИК-автомата. Описан метод построения комбинационной схемы, восстанавливающей проекцию неизвестного входного слова. ещё
5 Преобразования автоматов в автоматы без потери информации Исследуется задача преобразования произвольного автомата в автомат без потери информации на заданном регулярном множестве входных слов.... Исследуется задача преобразования произвольного автомата в автомат без потери информации на заданном регулярном множестве входных слов. Предложен метод решения, основанный на расширении выходного алфавита автомата. Описывается процедура построения проверочного графа для заданного автомата и заданного регулярного события. В терминах этого графа дается критерий того, что автомат является автоматом БПИ на словах этого события. Приводится процедура построения по исходному автомату автомата БПИ на заданном регулярном множестве слов за счет выведения дополнительных контрольных точек. ещё
Преобразования автоматов в автоматы без потери информации тест для курса Теория экспериментов с конечными автоматами 40 мин
6 Эксперименты по контролю функции выходов инициального автомата Исследуется задача контроля функции инициального автомата, которая с математической точки зрения сводится к задаче построения специального... Исследуется задача контроля функции инициального автомата, которая с математической точки зрения сводится к задаче построения специального обхода графа этого автомата. Приведен критерий существования такого обхода, который реализуется в процессе подачи на автомат так называемого характеристического слова. Доказываются различные утверждения, касающиеся оценок длинкратчайших обходов графа и характеристических слов. ещё
7 Контроль функции выходов неинициального автомата с использованием простого безусловного эксперимента Исследуется задача контроля функции выходов автомата в случае, когда неизвестно его начальное состояние. Приведен критерий разрешимости... Исследуется задача контроля функции выходов автомата в случае, когда неизвестно его начальное состояние. Приведен критерий разрешимости задачи. Показывается, что эта задача сводится к классической задаче распознавания автомата из известного класса. Описывается метод ее решения и приводится верхняя оценка длины контролирующего эксперимента. ещё
8 Контроль функции выходов инициального автомата с использованием кратного безусловного эксперимента Исследуется задача контроля функции выходов автомата с помощью кратного безусловного эксперимента. Вводятся понятия покрытия, приведенного и... Исследуется задача контроля функции выходов автомата с помощью кратного безусловного эксперимента. Вводятся понятия покрытия, приведенного и минимального покрытия графа множеством путей и кратности покрытия. Показано, что исходная задача редуцируется к задаче нахождения покрытия графа автомата. Приводятся критерий разрешимости задачи и оценки длин покрытия. Описывается алгоритм построения покрытия. ещё
Контроль функции выходов инициального автомата с использованием кратного безусловного эксперимента тест для курса Теория экспериментов с конечными автоматами 40 мин
9 Преобразование автомата для упрощения функционального контроля Описаны способы контроля автоматов с применением специальных схем, называемых схемами встроенного контроля. Предлагается одна из разновидностей... Описаны способы контроля автоматов с применением специальных схем, называемых схемами встроенного контроля. Предлагается одна из разновидностей такой схемы, основанная на принципе восстановления входных сигналов. В ней используются ОБПИК-автоматы порядка 1. Описывается метод преобразования произвольного автомата в автомат названного типа, базирующийся на выведении из исходного автомата дополнительных контрольных точек. ещё
10 Синхронизирующие эксперименты с линейными автоматами Описываются модели стационарных и нестационарных линейных автоматов, их структура и элементарные составляющие. Приводятся основные понятия теории... Описываются модели стационарных и нестационарных линейных автоматов, их структура и элементарные составляющие. Приводятся основные понятия теории экспериментов с линейными автоматами, формулы для вычисления конечных состояний и реакций автоматов. Исследуются синхронизирующие последовательности: критерий существования, их свойства, верхняя оценка длины минимальных СП. Описан метод решения задачи перевода автомата в заданное синхросостояние. ещё
11 Установочные и диагностические эксперименты со стационарными и нестационарными линейными автоматами Приводятся условия существования установочных и диагностических последовательностей для стационарных линейных автоматов, сформулированные в терминах характеристических матриц... Приводятся условия существования установочных и диагностических последовательностей для стационарных линейных автоматов, сформулированные в терминах характеристических матриц автоматов. Исследуются свойства последовательностей. Аналогичные результаты приводятся для нестационарных линейных автоматов. ещё
Установочные и диагностические эксперименты со стационарными и нестационарными линейными автоматами тест для курса Теория экспериментов с конечными автоматами 40 мин
12 Эксперименты в пространстве обобщенных состояний и с линейными автоматами с запаздыванием Введены понятия обобщенного состояния линейного автомата, обобщенных синхронизирующих, установочных и диагностических последовательностей. Для всех таких последовательностей... Введены понятия обобщенного состояния линейного автомата, обобщенных синхронизирующих, установочных и диагностических последовательностей. Для всех таких последовательностей сформулированы критерии их существования. Рассмотрены различные типы автоматов с запаздыванием (обыкновенные, по управлению, по состоянию), и для них получены критерии существования всех типов упомянутых выше последовательностей. ещё
13 Синхронизация и устойчивость дискретных линейных систем Для состояния линейного автомата определяются понятия равновесия и асимптотической устойчивости. Приводится критерий существования у свободного ЛА... Для состояния линейного автомата определяются понятия равновесия и асимптотической устойчивости. Приводится критерий существования у свободного ЛА асимптотически устойчивого состояния. Рассмотрена задача стабилизации ЛА и проблема ее разрешимости. Для дискретных линейных систем над полем R введено понятие e-синхронизирующей последовательности и приводится критерий ее существования. ещё
14 Эксперименты по распознаванию неисправностей линейных автоматов Рассматривается задача построения тестовой последовательности для заданной неисправности в стационарных и нестационарных ЛА, обнаруживающей эту неисправность.... Рассматривается задача построения тестовой последовательности для заданной неисправности в стационарных и нестационарных ЛА, обнаруживающей эту неисправность. Описаны простые в реализации методы построения такой тестовой последовательности для \mu-определенных и синхронизируемых линейных автоматов. Для произвольных ЛА предложен метод построения тестовой последовательности, основанный на наличии у любого ЛА конечной памяти. ещё
Эксперименты по распознаванию неисправностей линейных автоматов тест для курса Теория экспериментов с конечными автоматами 40 мин
15 Линейные автоматы существенно без потери информации Описывается класс автоматов без потери информации и доказывается эквивалентность двух разных его определений, данных Гиллом и... Описывается класс автоматов без потери информации и доказывается эквивалентность двух разных его определений, данных Гиллом и Хаффменом. Вводится новая разновидность автоматов БПИ, названных автоматами существенно БПИ конечного порядка, и приводится критерий принадлежности автомата этому классу. Описывается метод синтеза комбинационной схемы, восстанавливающей первый символ неизвестного слова, поданного на вход автомата БПИК. ещё
16 Обобщенные линейные автоматы без потери информации Вводится класс обобщенных линейных автоматов без потери информации и даются условия принадлежности автомата этому классу. Определяется... Вводится класс обобщенных линейных автоматов без потери информации и даются условия принадлежности автомата этому классу. Определяется понятие его оптимального подавтомата, описывается процедура выделения такого подавтомата из ЛА и доказывается его единственность. ещё
17 Минимизация времени восстановления неизвестных входных сигналов в сети из автоматов без потери информации Введено понятие корректной сети из линейных автоматов без потери информации, и для нее исследуется задача минимизации... Введено понятие корректной сети из линейных автоматов без потери информации, и для нее исследуется задача минимизации времени восстановления неизвестных входных сигналов по наблюдаемым выходам. Предложен метод решения этой задачи, основанный на сведении ее к классической задаче о потоке минимальной стоимости из теории потоков. ещё
Минимизация времени восстановления неизвестных входных сигналов в сети из автоматов без потери информации тест для курса Теория экспериментов с конечными автоматами 40 мин
18 Оптимальные эксперименты с линейными автоматами Вводится понятие линейного автомата с взвешенным входным алфавитом в пространстве обобщенных состояний. Исследуется задача построения обобщенных... Вводится понятие линейного автомата с взвешенным входным алфавитом в пространстве обобщенных состояний. Исследуется задача построения обобщенных синхронизирующих последовательностей с минимальным весом, переводящих ЛА из любого обобщенного состояния в заданное. Показано, что задача построения синхронизирующей последовательности минимального веса сводится к задаче целочисленного линейного программирования с линейными ограничениями. Исследуется задача построения обобщенной синхронизирующей последовательности с минимальным числом перепадов и описывается метод ее решения, который также основан на ее редукции к упомянутой задаче линейного программирования. ещё
19 Интервальная арифметика над конечным полем и ее приложения к теории экспериментов с автоматами Описывается интервальная арифметика над полем GF(p). Вводятся понятия интервала, обобщенного интервала, правильного и неправильного интервалов, бинарные... Описывается интервальная арифметика над полем GF(p). Вводятся понятия интервала, обобщенного интервала, правильного и неправильного интервалов, бинарные арифметические операции над интервалами и исследуются свойства этих операций. Рассматриваются вопросы решения интервальных уравнений. Вводятся понятия алгебраического, объединенного, допустимого и управляемого множества решений интервальных уравнений. ещё
20 Диагностическая задача в интервальной постановке Исследуется диагностическая задача для линейных автоматов, когда наблюдаемая на выходах реакция автоматов представлена в виде интервалов... Исследуется диагностическая задача для линейных автоматов, когда наблюдаемая на выходах реакция автоматов представлена в виде интервалов в поле GF(p). Предложены методы решения диагностической задачи с использованием модифицированной конструкции дерева преемников и путем сведения ее к решению систем линейных алгебраических уравнений с интервальной правой частью. Описан генетический алгоритм для решения упомянутой системы, значительно сокращающий время поиска решений. ещё
Диагностическая задача в интервальной постановке тест для курса Теория экспериментов с конечными автоматами 40 мин
21 Эксперименты с билинейными автоматами по распознаванию состояний Объектом исследования являются билинейные автоматы. Для автоматов такого типа приведены критерии существования синхронизирующих, установочных и диагностических... Объектом исследования являются билинейные автоматы. Для автоматов такого типа приведены критерии существования синхронизирующих, установочных и диагностических последовательностей, сформулированные в терминах их характеристических матриц. Предложены и обоснованы аналитические методы построения перечисленных последовательностей и исследованы их свойства. ещё
22 Разновидности экспериментов с билинейными автоматами Исследованы эксперименты по распознаванию неизвестного входного слова билинейного автомата и некоторые модификации понятия билинейного автомата без... Исследованы эксперименты по распознаванию неизвестного входного слова билинейного автомата и некоторые модификации понятия билинейного автомата без потери информации. Рассмотрены различные типы билинейных автоматов с запаздыванием и для них приведены критерии существования синхронизирующих, установочных и диагностических последовательностей. ещё
Разновидности экспериментов с билинейными автоматами тест для курса Теория экспериментов с конечными автоматами 40 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^