Примечание

Формулировки вопросов в некоторых случаях не совпадают с формулировками в задании. Вопросы располагаются в соотвествии с темой/примерной темой, как её видит автор. Нумерация не имеет смысла.

Абстрактный автомат

5. Абстрактный автомат -- это
   • математическая модель дискретного устройства
     
6. Абстрактный автомат S набор из
   • A, Z, W, lambda, delta
     
7. Состояние a_m и a_s -- эквивалентные, если их реакции равны, т.е.
   • w(a_m, e) = w(a_s, e)
     
8. Функция переходов
   • ставит в соответствие парам (a_m, z_f) состояние автомата a_s = (a_m, z_f)
     
9. Реакции автомата Мура на входное слова может быть получена по
   • отмеченной таблице переходов
     
   • графу
     
10. Реакция автомата Мили на входное слово может быть получена по
    • таблице переходов
      
    • таблице выходов
      
    • графу
      
11. Число состояний минимального абстрактного автомата равно
    • числу классов эквивалентности
      
12. Автомат Мура, обладающий неполнотой переходов и полнотой выходов
    • любой триггер
      
13. Полнота выходов автомата Мура означает, что
    • каждому состояний автомата соответствует свой сигнал
      
14. Полнота переходов автомата Мура означает, что
    • для любой пары состояний (b_i, b_j) найдётся входной сигнал, который переведёт автомат из состояния b_i в состояние b_j.
      
15. При переходе от абстрактного автомат к структурному автомату кодируются
    • входы
      
    • выходы
      
    • состояния
      
16. Цена логического элемента по Квайну равна
    • числу входов в этот логический элемент
      
17. Эквивалентные автоматы Мили
    • могут иметь разное число состояний
      
18. Эквивалентные автоматы Мура
    • могут иметь различное число состояний
      
19. Абстрактный автомат работает
    • в дискретные моменты времени
      
20. АА -- конечный, если
    • A -- конечное множество
      
    • Z -- конечное множество
      
    • W -- конечное множество
      
21. Два состояния k-эквивалентны, если
    • w(a_m, e_k) = w(a_s, e_k)
      
22. Функция выходов -- это функция, которая
    • некоторым парам (a_m, z_f) ставит в соотвествтие выходной сигнал автомата w_g = lambda(a_m, z_f)
      
23. Функция переходов -- это функция, которая
    • некоторым парам (a_m, z_f) ставит в соотвествтие состояние автомата a_s = delta(a_m, z_f)
      
24. Автоматы Мили и Мура называются эвивалентными, если у них при одинаковых входныи и выходных алфавитаз в состоянии a_1
    • одинаковые реакции на всевозможные одинаковые входные слова
      
25. В полностью определённых абстрактных автоматах можно минимизаировать
    • только состояния автомата
      
26. При графическом способе задания автомата Мура входной сигнал указывается
    • рядом с состоянием
27. При графическом способе задания автомата Мура входной сигнал указывается
    • в начале дуги
      
28. При графическом способе задания автомата Мили входной сигнал указывается
    • в начале дуги
29. При графическом способе задания автомата Мили выходной сигнал указывается
    • в конце дуги
30. При преобразовании автомата Мили в автомат Мура число состояний остётся неизменным, если
    • для каждого состояния автомата Мили имеется только одна входящая дуга
      
    • для каждого состояния автомата Мили может быть несколько входных дуг, но с одинаковыми выходными состояниями
      
31. При преобразовании автомата Мили в автомат Мура число состояний
    • с увеличивается или остётся прежним
32. При преобразовании автомата Мура в автомат Мили число состояний
    • всегда остаётся прежним
      
33. При преобразовании автомата Мили в автомат Мура функция переходов
    • не изменяется
34. При преобразовании автомата Мура в автомат Мили функция переходов
    • не изменяется
35. При преобразовании автомата Мили в автомат Мура функции выходов
    • изменяется
36. При преобразовании автомата Мура в автомат Мили функции выходов
    • изменяется
      
37. Абстрактный автомат Мура может быть задан
    • отмеченной таблице переходов
      
    • графом
38. Абстрактный автомат Мили может быть задан
    • таблице переходов
      
    • таблице выходов
      
    • графом
39. Разбиение автомата на классы экивалентности позволяет определить
    • избыточность элементов в множестве A
      
40. Закон функционирования автомата Мура задаётся уравнениями
    • w(t) = lambda(a(t))
      
    • a(t+1) = delta(a(t), z(t))
      
41. Закон функционирования автомата Мили задаётся уравнениями
    • a(t+1) = delta(a(t), z(t))
      
    • w(t) = lambda(a(t), z(t))
      
42. В момент времени t=0 абстрактный автомат находит в состоянии
    • a_1

Структурный автомат

9. Структурный автомат имеет
   • много выходов и много выходов
     
10. Память структурного автомат состоит из
    • триггеров
11. Таблица переходов СА строится по
    • таблице переходов абстрактоного автомата с учётом кодирования входных сигналов и состояний автомата
      
12. Таблица выходов СА строится по
    • таблице выходов АА с учётом кодирования входных и выходным сигналов и состояний автомата
      
13. Таблица сигналов функций возбуждения элементов памяти структурного автомата сроится по
    • таблице выходов структуного автомата с учётом закона функционирования заданного типа триггера
14. ДНФ для сигналов функций возбуждения строят по
    • таблице сигналов функций возбуждения СА
      
15. ДНФ для y_n, n = 1..N строят по
    • таблице выходов СА
16. При синтезе структурного автомата на D-триггерах таблица игналов функций возбуждения элементов пасяти совпадает с таблицей
    • переходов СА

КС

14. КС состоят из
    • логических элементов
15. При наличии структурно полной системы задача синтеза любого автомата сводится к синтезу его
    • КС
      
16. На вход КС СА поступают
    • двоичные входные сигналы и сигналы обратной связи с элементами памяти автомата
      
17. При каноническом методе структурного синтеза автомат представляется
    • в виде памяти и КС

Операторные схемы

15. Микрооперация --
    • элементарный неделимый акт обработки информации в операционном автомате
      
16. Микропрограммы КА --
    • реализуют микропрограмму работы у... устройства
      
17. Микропрограмму образуют
    • совокупность МК и функций переходов
18. Функция перехода от МК Y_i к Y_j
    • a_ij
19. Чтобы в операционном автомате выполнялась МО Y_i, должен прийти сигнал
    • единица
20. Распределение сдвигов --
    • каждому оператору Y_t поставлено в соответствие множество B_t двоичных переменных, которые могут изменяться в процессе выполнения оператора Y_t.
      (hint: Y_t, B_t, Y_t)
21. Преддешифратор обратной связи нужен для
    • сокращения числа синалов обратной связи
22. Свойства функции переходва от МК Y_i к Y_j
    • полнота
      
    • ортоганальность
23. Представление формулы перехода в виде Y_i -> x_e A v ~x_e B носит название разложение функции перехода
    • по переменной x_e
24. Если каждое из логических условий не может измениться никакой операцией Y_t, то распределение сдвигов
    • пустое
      
25. Если каждое из логических условий может измениться никакой операцией Y_t, то распределение сдвигов
    • универсальное
26. Под доопределение функции возбуждения перезодов из нескольких состояний называется
    • выдача на всез переходаз одного и того же множества сигналов функции возбуждения
27. X(a_m, a_s) -- это
    • входной набор, под действием которого определяется переход из состояни a_m в a_s
      
28. F(a_m, a_s) -- это
    • сигналы функции возбуждения
      
29. Y(a_m, a_s) -- это
    • выходной набор, который должен выбрабатываться на переходе МПА из состояния a_m в состояние a_s
30. Функционально-полная система логических элементов -- это система, включающая элементы
    • ИЛИ-НЕ
      
    • И, ИЛИ, НЕ
      
    • И-НЕ
31. При разложении системы формул перехода по переменным x и приведении их (формул перехода) к скобочному виду необходимо стремиться к
    • максимизации числа подобных членов
32. В матричной схеме алгоритма на пересечении строки Y_i столбца Y_j стоит
    • функция перехода a_ij
33. Система элементарных автоматов является структурно полной, если она
    • содержит автомат Мура, обладающий полнотой переходов и полнотой выходов и функционально-полную системуу логических элементов

ГСА

18. Выполнение ГСА на заданной последовательности опеределяется с помощью
    • блуждания по ГСА
      
19. Логические условия служат для
    • изменения порядка выполнения микрокоманд
      
20. Начальная вершина ГСА имеет
    • только один выход
      
21. Условная вершина -- ждущая, если
    • один из выходов соединён с её входом
      
22. На отмеченной ГСА с узлами можно выделить пути
    • сост. -- сост.
      
    • сост. -- узел
      
    • узел -- сост.
      
    • узел -- узел
23. При объединении частных ГСА в единую граф-схему решается задача
    • минимизации суммарного чсла операторных условий и условных вершин
      
24. ГСА Г1 и Г2 эквивалентны, если
    • их значения совпадают на всевозможных последовательностях наборов
25. В различных операторных вершинах ГСА
    • разрешается запись одинаковых микроопераций
26. ГСА -- ориентированный связный граф с вершинами
    • 4-х типов
27. Условнaя вершина ГСА имеет
    • один вход и два выхода
      
28. Операторная вершина имеет
    • один вход и один выход
      
29. Конечная вершина имеет
    • один выход
30. Скобочные формулы переходв служат для
    • построения фрагментов ГСА
31. В каждой опрераторной вершине ГСА записывается один из элементов множества
    • Y {y, ... y_n}
32. В каждой условной вершине ГСА записывается один из элементов множества
    • X = {x1, ... x_L}
33. Если вход условной вершины отмечен и состоянием, и узлом, то отметка состояние располагается
    • выше отметка-узла
34. Процедура выполнения ГСА на заданной последовательности наборов заканчивается, если
    • исчерпаны все наборы
      
    • достигнута конечная верршина Y_k
35. Узлом ГСА называется
    • вход условной вершины, если он соединяется с выходами не менее чем двух операторных вершин

МПА

24. При составлении путе перехода (синтез МПА по ГСА на основе автомата Мили) рассматривают пути перехода
    • a_m x^{e_m1}{m1} ... x^{e_mn}{mn} Y_t a_s
      
    • a_m x^{e_m1}{m1} ... x^{e_mn}{mn} a_s
25. В обратной таблице переходв МПА группируются переходы вида
    • [многие к одному]
26. В прямой таблице переходов МПА группируются переходы вида
    • [один ко многим]
27. Матричные схема алгоритма
    • квадратная матрица, у который строки отмеченны Y_0, Y_1, ... Y_k, а столбцы -- Y_1, ... Y_t, Y_k
28. Таблицы переходов МПА
    • структурны и не структурны
      
    • прямые и обратные
      
    • с узлами и без узлов
29. Выражение a_ij Y_j = { Y_j, if a_ij = 1; 0, if a_ij = 0 }
    • отмеченная булевая функция
30. Разложение формулы перехода производится до тех пор, пока во внутренних скобках не окажется выражение вида
    • x_t Y_p v ~x_t Y_q
31. Для борьбы с критическими состязаниями (гонками) применяют
    • алгоритмы противогоночного кодирования
      
    • двойную память
      
    • тактирование входных сигналов
32. Состязания медлу элементами памяти начинаются тогда, когда при переходе из состояний a_m в состояние a_s изменяют свои состояния
    • два и более элементов памяти

Кодирование состояний

88. Алгоритм кодирования состояний автомата позволяет
    • минимизировать суммарное число переключений элементов памяти
89. Расчёт коэффициента кодирования состояний автомата
    • K = sum t_ms / p
90. Итоги алгоритма кодирования состояний автомата считаются удовлетворительными, если коэффициент кодирования
    • k <= 1.5

Число шагов/этапов

26. Синтез МПА по ГСА
    • в 2 этапа
      
27. Алгоритм минимизации числа схем ИЛИ включает в себя
    • 4 шага
      
28. Алгоритм получения отмеченной ГСА (для автомата Мили) включает в себя
    • 4 шага
      
29. Алгоритм кодирования состояний состоит из
    • 7 шагов
      
30. Алгоритм объединения частных ГСА в единую граф-сеху включает в себя
    • 8 этапов

Триггеры

36. RS-триггер имеет
    • два входа и два выхода
37. D-триггер имеет
    • один вход, два выхода

Алгоритмы

7. Идея алгоритма минимизации
   • разбиение всех состояний исходного автомата на попарно не пересекающиеся классы эквивалентных состояний.
8. Люобой алгоритм может быть представлен в виде
   • системы скобочных формул перехода
     
   • граф-схемы алгоритма
     
   • матричной схемы алгоритма
     
   • системой формул перехода

9. Правильная взаимосвязь алгоритмов

    +----ГСА----+
    |     ^     |
    v     |     v
   МСА <-----> СФП
          |     |
         ССиФП <+