Примечание ---------- Формулировки вопросов в некоторых случаях не совпадают с формулировками в задании. Вопросы располагаются в соотвествии с темой/примерной темой, как её видит автор. Нумерация не имеет смысла. Абстрактный автомат ------------------- 5. Абстрактный автомат -- это * математическая модель дискретного устройства 31. Абстрактный автомат S набор из * A, Z, W, lambda, delta 1. Состояние a_m и a_s -- эквивалентные, если их реакции равны, т.е. * w(a_m, e) = w(a_s, e) 32. Функция переходов * ставит в соответствие парам (a_m, z_f) состояние автомата a_s = (a_m, z_f) 2. Реакции автомата Мура на входное слова может быть получена по * отмеченной таблице переходов * графу 3. Реакция автомата Мили на входное слово может быть получена по * таблице переходов * таблице выходов * графу 4. Число состояний минимального абстрактного автомата равно * числу классов эквивалентности 10. Автомат Мура, обладающий неполнотой переходов и полнотой выходов * любой триггер 12. Полнота выходов автомата Мура означает, что * каждому состояний автомата соответствует свой сигнал 75. Полнота переходов автомата Мура означает, что * для любой пары состояний (b_i, b_j) найдётся входной сигнал, который переведёт автомат из состояния b_i в состояние b_j. 13. При переходе от абстрактного автомат к структурному автомату кодируются * входы * выходы * состояния 28. Цена логического элемента по Квайну равна * числу входов в этот логический элемент 33. Эквивалентные автоматы Мили * могут иметь разное число состояний 65. Эквивалентные автоматы Мура * могут иметь различное число состояний 34. Абстрактный автомат работает * в дискретные моменты времени 50. АА -- конечный, если * A -- конечное множество * Z -- конечное множество * W -- конечное множество 51. Два состояния k-эквивалентны, если * w(a_m, e_k) = w(a_s, e_k) 82. Функция выходов -- это функция, которая * некоторым парам (a_m, z_f) ставит в соотвествтие выходной сигнал автомата w_g = lambda(a_m, z_f) 83. Функция переходов -- это функция, которая * некоторым парам (a_m, z_f) ставит в соотвествтие состояние автомата a_s = delta(a_m, z_f) 73. Автоматы Мили и Мура называются эвивалентными, если у них при одинаковых входныи и выходных алфавитаз в состоянии a_1 * одинаковые реакции на всевозможные одинаковые входные слова 74. В полностью определённых абстрактных автоматах можно минимизаировать * только состояния автомата 112. При графическом способе задания автомата Мура входной сигнал указывается * рядом с состоянием 66. При графическом способе задания автомата Мура входной сигнал указывается * в начале дуги 101. При графическом способе задания автомата Мили входной сигнал указывается * в начале дуги 113. При графическом способе задания автомата Мили выходной сигнал указывается * в конце дуги 68. При преобразовании автомата Мили в автомат Мура *число состояний* остётся неизменным, если * для каждого состояния автомата Мили имеется только одна входящая дуга * для каждого состояния автомата Мили может быть несколько входных дуг, но с одинаковыми выходными состояниями 8. При преобразовании автомата Мили в автомат Мура *число состояний* * с увеличивается или остётся прежним 67. При преобразовании автомата Мура в автомат Мили *число состояний* * всегда остаётся прежним 97. При преобразовании автомата Мили в автомат Мура *функция переходов* * не изменяется 6. При преобразовании автомата Мура в автомат Мили *функция переходов* * не изменяется 105. При преобразовании автомата Мили в автомат Мура *функции выходов* * изменяется 84. При преобразовании автомата Мура в автомат Мили *функции выходов* * изменяется 89. Абстрактный автомат Мура может быть задан * отмеченной таблице переходов * графом 90. Абстрактный автомат Мили может быть задан * таблице переходов * таблице выходов * графом 91. Разбиение автомата на классы экивалентности позволяет определить * избыточность элементов в множестве A 106. Закон функционирования автомата Мура задаётся уравнениями * w(t) = lambda(a(t)) * a(t+1) = delta(a(t), z(t)) 108. Закон функционирования автомата Мили задаётся уравнениями * a(t+1) = delta(a(t), z(t)) * w(t) = lambda(a(t), z(t)) 109. В момент времени t=0 абстрактный автомат находит в состоянии * a_1 Структурный автомат ------------------- 9. Структурный автомат имеет * много выходов и много выходов 11. Память структурного автомат состоит из * триггеров 85. Таблица переходов СА строится по * таблице переходов абстрактоного автомата с учётом кодирования входных сигналов и состояний автомата 86. Таблица выходов СА строится по * таблице выходов АА с учётом кодирования входных и выходным сигналов и состояний автомата 93. Таблица сигналов функций возбуждения элементов памяти структурного автомата сроится по * таблице выходов структуного автомата с учётом закона функционирования заданного типа триггера 52. ДНФ для сигналов функций возбуждения строят по * таблице сигналов функций возбуждения СА 38. ДНФ для y_n, n = 1..N строят по * таблице выходов СА 92. При синтезе структурного автомата на D-триггерах таблица игналов функций возбуждения элементов пасяти совпадает с таблицей * переходов СА КС -- 14. КС состоят из * логических элементов 77. При наличии структурно полной системы задача синтеза любого автомата сводится к синтезу его * КС 35. На вход КС СА поступают * двоичные входные сигналы и сигналы обратной связи с элементами памяти автомата 37. При каноническом методе структурного синтеза автомат представляется * в виде памяти и КС Операторные схемы ----------------- 15. Микрооперация -- * элементарный неделимый акт обработки информации в операционном автомате 46. Микропрограммы КА -- * реализуют микропрограмму работы у... устройства 43. Микропрограмму образуют * совокупность МК и функций переходов 17. Функция перехода от МК Y_i к Y_j * a_ij 21. Чтобы в операционном автомате выполнялась МО Y_i, должен прийти сигнал * единица 22. Распределение сдвигов -- * каждому оператору Y_t поставлено в соответствие множество B_t двоичных переменных, которые могут изменяться в процессе выполнения оператора Y_t. (hint: Y_t, B_t, Y_t) 29. Преддешифратор обратной связи нужен для * сокращения числа синалов обратной связи 41. Свойства функции переходва от МК Y_i к Y_j * полнота * ортоганальность 42. Представление формулы перехода в виде Y_i -> x_e A v ~x_e B носит название разложение функции перехода * по переменной x_e 23. Если каждое из логических условий не может измениться никакой операцией Y_t, то распределение сдвигов * пустое 59. Если каждое из логических условий может измениться никакой операцией Y_t, то распределение сдвигов * универсальное 63. Под доопределение функции возбуждения перезодов из нескольких состояний называется * выдача на всез переходаз одного и того же множества сигналов функции возбуждения 49. X(a_m, a_s) -- это * входной набор, под действием которого определяется переход из состояни a_m в a_s 61. F(a_m, a_s) -- это * сигналы функции возбуждения 100. Y(a_m, a_s) -- это * выходной набор, который должен выбрабатываться на переходе МПА из состояния a_m в состояние a_s 102. Функционально-полная система логических элементов -- это система, включающая элементы * ИЛИ-НЕ * И, ИЛИ, НЕ * И-НЕ 103. При разложении системы формул перехода по переменным x и приведении их (формул перехода) к скобочному виду необходимо стремиться к * максимизации числа подобных членов 104. В матричной схеме алгоритма на пересечении строки Y_i столбца Y_j стоит * функция перехода a_ij 107. Система элементарных автоматов является структурно полной, если она * содержит автомат Мура, обладающий полнотой переходов и полнотой выходов и функционально-полную системуу логических элементов ГСА --- 18. Выполнение ГСА на заданной последовательности опеределяется с помощью * блуждания по ГСА 19. Логические условия служат для * изменения порядка выполнения микрокоманд 20. Начальная вершина ГСА имеет * только один выход 16. Условная вершина -- ждущая, если * один из выходов соединён с её входом 27. На отмеченной ГСА с узлами можно выделить пути * сост. -- сост. * сост. -- узел * узел -- сост. * узел -- узел 25. При объединении частных ГСА в единую граф-схему решается задача * минимизации суммарного чсла операторных условий и условных вершин 39. ГСА Г1 и Г2 эквивалентны, если * их значения совпадают на всевозможных последовательностях наборов 80. В различных операторных вершинах ГСА * разрешается запись одинаковых микроопераций 56. ГСА -- ориентированный связный граф с вершинами * 4-х типов 78. Условнaя вершина ГСА имеет * один вход и два выхода 57. Операторная вершина имеет * один вход и один выход 58. Конечная вершина имеет * один выход 70. Скобочные формулы переходв служат для * построения фрагментов ГСА 71. В каждой опрераторной вершине ГСА записывается один из элементов множества * Y {y, ... y_n} 98. В каждой условной вершине ГСА записывается один из элементов множества * X = {x1, ... x_L} 48. Если вход условной вершины отмечен и состоянием, и узлом, то отметка состояние располагается * выше отметка-узла 94. Процедура выполнения ГСА на заданной последовательности наборов заканчивается, если * исчерпаны все наборы * достигнута конечная верршина Y_k 96. Узлом ГСА называется * вход условной вершины, если он соединяется с выходами не менее чем двух операторных вершин МПА --- 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 81. В обратной таблице переходв МПА группируются переходы вида * [многие к одному] 87. В прямой таблице переходов МПА группируются переходы вида * [один ко многим] 44. Матричные схема алгоритма * квадратная матрица, у который строки отмеченны Y_0, Y_1, ... Y_k, а столбцы -- Y_1, ... Y_t, Y_k 62. Таблицы переходов МПА * структурны и не структурны * прямые и обратные * с узлами и без узлов 69. Выражение a_ij Y_j = { Y_j, if a_ij = 1; 0, if a_ij = 0 } * отмеченная булевая функция 79. Разложение формулы перехода производится до тех пор, пока во внутренних скобках не окажется выражение вида * x_t Y_p v ~x_t Y_q 95. Для борьбы с критическими состязаниями (гонками) применяют * алгоритмы противогоночного кодирования * двойную память * тактирование входных сигналов 110. Состязания медлу элементами памяти начинаются тогда, когда при переходе из состояний a_m в состояние a_s изменяют свои состояния * два и более элементов памяти Кодирование состояний --------------------- 88. Алгоритм кодирования состояний автомата позволяет * минимизировать суммарное число переключений элементов памяти 64. Расчёт коэффициента кодирования состояний автомата * K = sum t_ms / p 99. Итоги алгоритма кодирования состояний автомата считаются удовлетворительными, если коэффициент кодирования * k <= 1.5 Число шагов/этапов ------------------ 26. Синтез МПА по ГСА * в 2 этапа 54. Алгоритм минимизации числа схем ИЛИ включает в себя * 4 шага 60. Алгоритм получения отмеченной ГСА (для автомата Мили) включает в себя * 4 шага 30. Алгоритм кодирования состояний состоит из * 7 шагов 47. Алгоритм объединения частных ГСА в единую граф-сеху включает в себя * 8 этапов Триггеры -------- 36. RS-триггер имеет * два входа и два выхода 53. D-триггер имеет * один вход, два выхода Алгоритмы --------- 7. Идея алгоритма минимизации * разбиение всех состояний исходного автомата на попарно не пересекающиеся классы эквивалентных состояний. 45. Люобой алгоритм может быть представлен в виде * системы скобочных формул перехода * граф-схемы алгоритма * матричной схемы алгоритма * системой формул перехода 72. Правильная взаимосвязь алгоритмов ``` +----ГСА----+ | ^ | v | v МСА <-----> СФП | | ССиФП <+ ```