Без темы
<<  ОБРАЗОВАТЕЛЬНЫЙ ПРОЕКТ как цикл инновационной деятельности Общая часть  >>
Картинок нет
Картинки из презентации «Общая теория конечные цифровых автоматов с памятью» к уроку экономики на тему «Без темы»

Автор: Афанасьев В А. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока экономики, скачайте бесплатно презентацию «Общая теория конечные цифровых автоматов с памятью.pptx» со всеми картинками в zip-архиве размером 186 КБ.

Общая теория конечные цифровых автоматов с памятью

содержание презентации «Общая теория конечные цифровых автоматов с памятью.pptx»
Сл Текст Сл Текст
1Модуль 3. Общая теория конечные 8a2/w2. z2. a1 /w1. a2/w2. a5/ w2. a3/w1.
цифровых автоматов с памятью. Абстрактный a3/ w1.
автомат. Основные понятия и определения. 9Преобразование автомата Мили в автомат
Эквивалентные автоматы. Преобразование Мура (продолжение). Z\а. Z\а. w1. w2. w1.
автомата Мили в автомат Мура и наоборот. w1. w2. Z\а. a1. a2. a3. b1. b2. b3. b4.
Минимизация полностью определённых b5. z1. a3/w1. a1/w1. a1/w2. z1. b4. b4.
автоматов на основе выделения классов b1. b2. b2. z2. a1/w1. a3/w2. a2/w1. z2.
эквивалентных состояний. Определение b1. b1. b5. b3. b3. Состояние a1 автомата
структурного автомата. Теория автоматов. Мили А1 порождает 2 состояния автомата
Модуль 3. 1/16. Мура А4, которые обозначим b1 и b2 . Далее
2Абстрактный автомат. Основные понятия запишем группы состояний автомата Мура А4
и определения. В общем случае, автоматы для состояний a2 и a3 автомата Мили А1:
это устройства, выполняющие прием, (Мили А1 -> Мура А4). Теория автоматов.
хранение и преобразование дискретной 9/16. В дальнейшем символы bi можно
информации по заданному алгоритму. Теория заменить на ai. В качестве начального
автоматов (ТА) делится на две части: состояния автомата Мура A4 можно выбрать
абстрактные и структурные автоматы. любое из состояний, порождённых начальным
Абстрактная ТА отвлекается от структуры состоянием a1 в автомате Мили A1.
автомата и изучает лишь его поведение, или 10Результат преобразований. Z\а. a1. a2.
реакцию автомата на входное воздействие. a3. Z\а. Z\а. w1. w2. w1. w1. w2. a1. a2.
Абстрактный автомат – это математическая a3. a4. a5. z1. a3/w1. a1/w1. a1/w2. z1.
модель, с одним входом и одним выходом, a4. a4. a1. a2. a2. z2. a1/w1. a3/w2.
работающая в дискретном времени tn = nT, a2/w1. z2. a1. a2. a5. a3. a3. Z\а. a1.
где n = 0, 1, 2 …, а T – интервал a2. a3. a4. a5. Z\а. Z\а. w1. w2. w1. w1.
дискретизации. Предполагается, что w2. z1. a4/ w1. a4/ w1. a1/w1. a2/ w2.
переходные процессы в автомате a2/w2. b1. b2. b3. b4. b5. z1. b4. b4. b1.
укладываются в интервал дискретизации и, b2. b2. z2. a1 /w1. a2/w2. a5/ w2. a3/w1.
поэтому чтобы не ссылаться на значение Т, a3// w1. z2. b1. b1. b5. b3. b3.
вводится автоматное время: t= tn / T = 0, Вследствие свойства транзитивности
1, 2, … В каждый момент времени t автомат, отношений эквивалентности (теория
находящийся в состоянии а(t) Є А, способен множеств) имеем: Мура A4 эквивавалентен
воспринять букву входного алфавита z(t) Є Мили A3. Теория автоматов. Модуль 3.
Z и, в этот же момент времени, 10/16.
сформировать букву выходного алфавита w(t) 11Минимизация полностью определённых
Є W (t = 0, 1, 2, …). Например: t 0 1 2 3 автоматов. Эквивалентные между собой
z(t) z1 z2 z3 z4 w(t) w1 w2 w3 w4. Теория автоматы Мили или Мура могут иметь
автоматов. Модуль 3. 2/16. различное число состояний, в связи с чем
3Абстрактный автомат (продолжение). возникает задача нахождения среди них
Автомат Мили (G. Mealy) as = ?(am , zf ) автомата с минимальным числом состояний.
wl = ? (am , zf ). Автомат Мура (E. Moore) Избыточность состояний автомата
as = ?(am , zf ) wl = ? (am ). Теория устраняется склеиванием эквивалентных
автоматов. Модуль 3. 3/16. Работу автомата между собой состояний. Состояния am и as
можно определить следующими двумя считаются эквивалентными, если автомат
функциями: a(t+1)=?(a(t), z(t)) – функция находящийся в любом из них, формирует
перехода, w(t)= ?(a(t), z(t)) – функция одинаковые выходные слова при подаче на
выхода. Примем: a(t)=am - состояние для его вход произвольных входных слов или
момента времени t, a(t+1)= as - состояние последовательностей символов. Объединение
для момента t+1. Аналогично: z(t)=zf , всех эквивалентных друг другу состояний
w(t)=wl . Тогда: as = ?(am ,zf ) – функция образует класс эквивалентных состояний.
перехода, wl = ? (am ,zf ) - функция Если всё множество состояний автомата
выхода. Введем ряд понятий: Автомат будет разбить на классы эквивалентных состояний
конечным, если все множества A, W и Z с последующей заменой каждого класса одним
будут конечными. Детерминированный автомат состоянием, то будет получен автомат с
– такой автомат, который, находясь в минимальным числом состояний. Теория
состоянии am под воздействием входного автоматов. Модуль 3. 11/16.
сигнала zf перейдет в состояния as . 12Нахождение классов эквивалентных
Инициальный автомат: а(0)=а1 . Полностью состояний методом Ауфенкампа и Хона.
определенный автомат – если для каждой Делается это за ряд шагов, руководствуясь
пары (am , zf ) Є {A x Z} определены при этом более слабым отношением
функции ? и ?. Если это не выполняется – (определением) эквивалентности, а именно,
автомат будет неполным или частичным. Из принципом k- эквивалентных состояний.
всех автоматов наибольшее распространение Будем называть k- эквивалентными два
получили автоматы Мили и Мура. состояния автомата Мили (am и as ,
4Способы задания автоматов: а) k=1,2,3, ..), если автомат находясь в
табличный. t. 0. 1. 2. 3. 4. Z\а. a1. a2. любом из них, при подаче на его вход слов
a3. z(t). z1. z1. z2. z1. z1. a3/w1. из k- букв выдаёт на выходе одинаковые
a1/w1. a1/w2. w(t). w1. w2. w1. w1. z2. слова, т. е. (am? as), если ?(am, ?k
a1/w1. a3/w2. a2/w1. a(t). a1. a3. a1. a1. )=?(as, ?k ) для входных слов ?k длиной k.
a3. Ниже представлена совмещённая таблица Объединение всех k- эквивалентных
переходов и выходов автомата Мили А1, в состояний образуют класс k- эквивалентных
клетках которой на пересечении m- го состояний. Например, 1- эквивалентных
столбца (состояние am) и f-й строки (вх. состояний автомата Мили включает состояния
символ zf) указываются состояние автомата с одинаковыми выходными сигналами в
as = ?(am ,zf) в следующий момент времени таблице переходов и выходов. Доказано, что
t+1 и значение выходного символа (через если результаты разбиения состояний
косую линию) wl = ? (am ,zf ) в этот же автомата на классы k и k+1-
момент времени t. Ниже, основываясь на эквивалентности совпали, то классы
таблице переходов и выходов, определено k-эквивалентных состояний являются
выходное слово автомата как реакция на эквивалентными в строгом смысле этого
произвольное входное слово. Выходной понятия. Теория автоматов. 12/16.
сигнал wl в автомате Мили присутствует 13ПРИМЕР: минимизация автомата Мили.
только при наличии входного сигнала zf ! zi\ai. a1. a2. a3. a4. a5. a6. z1. a2/w2.
Выходное слово автомата. Мили А1. Теория a5/w1. a2/w1. a5/w1. a2/w1. a5/w2. z2.
автоматов. Модуль 3. 4/16. a1/w2. a2/w2. a5/w2. a3/w2. a5/w2. a6/w2.
5Способы задания автоматов: б) z3. a6/w1. a6/w1. a4/w2. a5/w2. a6/w1.
графический. Z\а. a1. a2. a3. Z\а. Z\а. a1/w1. zi\ai. zi\ai. b1. b1. b2. b2. b3.
w1. w2. w1. w1. w2. a1. a2. a3. a4. a5. b3. a1. a6. a2. a5. a3. a4. z1. b2. b2.
z1. a3/w1. a1/w1. a1/w2. z1. a4. a4. a1. b2. b2. b2. b2. Дальнейшее разбиение
a2. a2. z2. a1/w1. a3/w2. a2/w1. z2. a1. бессмысленно. Пусть: (a1, a6 )=a1, (a2, a5
a2. a5. a3. a3. Мили А1. Мура А2. Граф )=a2, (a3 )=a3, (a4 )= a4. Окончательный
автомата – это ориентированный граф, вид таблицы переходов автомата Мили
вершины которого соответствуют состояниям, приобретёт следующий вид. z2. b1. b1. b2.
а дуги – переходам между ними. Теория b2. b2. b3. z3. b1. b1. b1. b1. b3. b2.
автоматов. Модуль 3. 5/16. Таблица zi\ai. zi\ai. zi\ai. b1. b1. b2. b2. b3.
переходов и выходов автомата Мура b3. zi\ai. a1. a2. a3. a4. С1. С1. С2. С2.
отличается тем, что у него выходной сигнал С3. c4. a1. a6. a2. a5. a3. a4. z1. a2 /
есть функция только состояния wl = ? (am w2. a2 / w1. a2 / w1. a2 / w1. z1. С2. С2.
). Ниже приведён пример таблицы автомата С2. С2. С2. С2. z2. a1 / w2. a2 / w2. a2 /
Мура А2. w2. a3 / w2. z2. С1. С1. С2. С2. С2. С3.
6Синхронные и асинхронные автоматы. z3. a1 / w1. a1 / w1. a4 / w2. a2 / w2.
Предварительно определим, какое состояние z3. С1. С1. С1. С1. С4. С2. Теория
автомата является устойчивым. Состояние автоматов. 13/16. Обозначим классы 1
автомата as является устойчивым, если для -эквивалентных состояний как ?1, тогда:
любого входа zf Є Z такого, что as=?(am ?1={(a1, a6), (a2, a5), (a3, a4)} = {b1,
,zf ) справедливо as= ?(as ,zf ), т. е. b2, b3}. Преобразуем исходную таблицу
если автомат в состояние as пришёл под автомата Мили заменив в ней состояние as
действием входного сигнала zf , то выйти классами 1-эквивалентных состояний ?1.
из него он должен под действием другого ?2={(a1, a6), (a2, a5), a3, a4}={c1 , c2 ,
сигнала. Автомат является асинхронным, c3 , c4 }. ?3={(a1, a6), (a2, a5), a3,
если все состояния автомата являются a4}. ?2 = ?3!
устойчивыми. Следовательно, смена 14Постановка задачи структурного синтеза
состояний асинхронного автомата возможна автоматов. Z. x1. x2. … xK. W. y1. y2. …
только с изменением входного сигнала, yN. A. Q1. Q2. … QR. a1. 0. 0. … 0. z1. 0.
поэтому для данного типа автомата можно 0. … 0. w1. 0. 0. … 0. a2. 0. 0. … 1. z2.
ввести переменный шаг времени, связав его 0. 0. … 1. w2. 0. 0. … 1. … … … … … … … …
с изменением входного сигнала. Если хотя … … … … … … … aM. 1. 1. … 1. zF. 1. 1. …
бы одно состояние автомата является 1. wL. 1. 1. … 1. Теория автоматов. Модуль
неустойчивым, то такой автомат будет 3. 14/16. Цель структурного синтеза –
синхронным. Приведённые примеры автоматов разработка схемы автомата из логических
Мили А1 и Мура А2 являются синхронными. В элементов заданного типа, которая
дальнейшим, как правило, будет функционирования бы в соответствии с
рассматриваться данный тип автомата. таблицей переходов и выходов исходного
Теория автоматов. Модуль 3. 6/16. абстрактного автомата. Представление
7Связь между моделями Мура и Мили. символов первичного алфавита абстрактного
Понятие эквивалентных автоматов. Теория автомата (из множеств Z и W) в форме
автоматов. 7/16. Два автомата А1 и А2 удобной для передачи по линии связи
называются эквивалентными (независимо от называется кодированием. Для перехода от
модели автоматов), если будучи абстрактного автомата к структурному
установленными в начальное состояние а1 прежде всего необходимо осуществить
имеют одинаковые реакции (выходные слова) двоичное кодирование символов используемых
на любое входного слово. Выходным сигналом алфавитов, а также состояний автомата
автомата Мура (в отличие от автомата Мили) двоичными элементами памяти. Z={z1,…zf
находящегося в начальном состоянии ,.., zF }; W={w1,…wl ,.., wL }; A={а1,…аm
пренебрегают. Покажем, что автоматы Мили ,.., aM }; F=1 K=0, F=2 K=1, F=3 K=2, F=4
А1 и Мура А2 являются эквивалентными. При K=3 F=5 K=3, F=7 K=3, F=8 K=3, F=9 K=4
определении эквивалентности ……………. F=16 K=4. Двоичное кодирование
«разномодельных» автоматов необходимо определит следующие количественные
учитывать факт сдвига на один такт соотношения между мощностями первичных
(запаздывание) выходного слова автомата алфавитов и соответствующими им наборами
Мура относительно выходного слова автомата двоичных переменных (Z?X, W ?Y, A ?Q):
Мили. Z\а. Z\а. w1. w2. w1. w1. w2. Z\а. 15Постановка задачи структурного синтеза
a1. a2. a3. a1. a2. a3. a4. a5. z1. a3/w1. автоматов (продолжение). zi\ai. zi\ai. w1.
a1/w1. a1/w2. z1. a4. a4. a1. a2. a2. z2. w2. a1. a2. z1. a1. a1. z2. a2. a2. Теория
a1/w1. a3/w2. a2/w1. z2. a1. a2. a5. a3. автоматов. 15/16. На этапе структурного
a3. Реакции автоматов, установленных в синтеза автомат принято представлять в
состояние а1 на входное слово ? = z1 z1 z2 виде 2-х частей – памяти и КС (КС1 и КС2).
z1 z2 z2. Мили А1. Мили А1. Мили А1. ? z1. Память автомата состоит из элементарных
z1. z2. z1. z2. z2. a(t). a1. a3. a1. a1. автоматов Мура Q1 ,…,QR с двумя
a3. a2. a3. w(t). w1. w2. w1. w1. w1. w2. состояниями, обладающих полной системой
Мура А2. Мура А2. a(t). a1. a4. a2. a1. переходов и выходов. Полная система
a4. a3. a5. w(t). w1. w1. w2. w1. w1. w1. переходов предполагает наличие обоих
w2. состояний в каждом столбце таблицы, а
8Преобразование автомата Мура в автомат полная система выходов – когда каждому
Мили и наоборот. Мили А3. Теория состоянию соответствует свой выходной
автоматов. Модуль 3. 8/16. 1. символ. Этому условию на структурном
Преобразование автомата Мура в автомат уровне отвечают двоичные элементы памяти –
Мили (Мура А2 ? Мили А3) осуществляется триггеры. В структурной схеме автомата КС2
наиболее просто. Правило преобразования выполняет функцию выхода ? а КС1 и память
применительно к интерпретации автоматов в - функцию перехода ? автомата: Где:
виде графов: выходной сигнал wl, 16Контрольные вопросы. Запишите функции
записанный в вершине as переносится на все перехода и выхода абстрактных автоматов
дуги, входящие в эту вершину. Правило Мили и Мура. Какие вы знаете способы
преобразования применительно к заданию задания абстрактных автоматов? Основываясь
автоматов в виде таблиц: в клетки таблицы, на рисунке, дайте определение устойчивого
отражающие состояния переходов as= ?(as , состояния автомата. Какой автомат является
zf ) автомата Мура записываются (через синхронным (асинхронным)? Какие автоматы
косую черту) соответствующие этим являются эквивалентными? Правило
состояниям выходные сигналы. Т.О. новый преобразования автомата Мура в эквилентный
автомат Мили приобретает число состояний ему автомат Мили применительно к
автомата Мура. 2. Преобразование автомата интерпретации автоматов в виде графов. 7.
Мили в автомат Мура (Мили А1 ? Мура А4). Каким параметром определяются количество
Всевозможные состояния эквивалентного состояний автомата Мура, полученного путём
автомата Мура определятся множеством всех выполнения эквивалентных преобразований
пар (as,wl) автомата Мили, где wl – автомата Мили. 8. Изложите суть
выходной сигнал, приписанный к входящей в минимизации состояний полностью
as дуге . Пары объединяют в группы, определённых абстрактных автоматов. 9.
включающие одинаковые состояния as . Принцип k- эквивалентных состояний
Состояния эквивалентного автомата Мура Ауфенкампа и Хона. 10. Нарисуйте
будем обозначать как bs . Z\а. a1. a2. a3. структурную схему структурного автомата.
a4. a5. z1. a4/ w1. a4/ w1. a1/w1. a2/ w2. Теория автоматов. Модуль 3. 16/16.
Общая теория конечные цифровых автоматов с памятью.pptx
http://900igr.net/kartinka/ekonomika/obschaja-teorija-konechnye-tsifrovykh-avtomatov-s-pamjatju-125964.html
cсылка на страницу

Общая теория конечные цифровых автоматов с памятью

другие презентации на тему «Общая теория конечные цифровых автоматов с памятью»

«Аналоговый и цифровой звук» - Мультимедиа. До недавнего времени вся техника передачи звука была аналоговой. Электропроигрыватель ''Электроника ЭП-017С''. Виды механической записи: 1-глубинная; 2-поперечная. Анимированная компьютерная графика. Телефонная связь. Ламповый радиоприёмник «ЗВЕЗДА». 150-метровая башня на Шаболовке с радиоантенной.

«Теория света» - Оптика- раздел науки, изучающий световые явления. Как называется восприятие организмом света? Как называется раздел физики, изучающий природу и свойства света? С какими видами источников света вы встречались на практике, в жизни (пояснить примерами)? Корпускулярная теория Свет – поток фотонов. Двойственность природы света называется корпускулярно – волновым дуализмом.

«Теория игр» - Рациональность ценностей ею не учитывается. «Дилемма заключенного» для случая игры со многими ходами. Игры с осмысленной реакцией противника. Типичным примером игры со смешанной мотивацией является защита окружающей среды. Cпираль гонки вооружений. Томский политехнический университет Институт международного менеджмента.

«Теория игр» - Итеративный метод Брауна – Робинсона. Пусть имеются два числовых множества A и B и функция . Пусть игрок 1 имеет всего m стратегий, а игрок 2 – n стратегий. План лекции. Выбор оптимальной стратегии в условиях неопределенности. Все ли матрицы имеют седловую точку? Матричные игры. Монотонный итеративный алгоритм.

«Цифровая обработка сигналов» - Историческая справка. Типовая блок-схема устройства ЦОС. Цифровая обработка сигналов. arctan. Цифровая обработка сигналов: лекция 1. Предмет курса. Определение. Вводные сведения по комплексной арифметике. Направления развития ЦОС. План лекции. Этапы построения систем ЦОС. Конспект лекций. У.М. Сиберт.

«Цифровые образовательные ресурсы» - Flash player для просмотра различных тренажеров, моделей в формате swf. Общие требования к цифровым образовательным ресурсам: «Инструменты». Энциклопедия «Кругосвет». «Региональные коллекции». Acrobat reader поможет просмотреть журнальные статьи в формате pdf. Использование цифровых образовательных ресурсов в предметах.

Без темы

757 презентаций
Урок

Экономика

125 тем
Картинки
900igr.net > Презентации по экономике > Без темы > Общая теория конечные цифровых автоматов с памятью