Кафедра К3 Прикладная математика, информатика
и вычислительная техника

Теория автоматов

Вопросы к экзамену

При проведении промежуточной аттестации для оценки результатов изучения дисциплины вынесены следующие вопросы:

1. Системы счисления. Позиционные, непозиционные, однородные, неоднородные.
2. Кодированные позиционные системы счисления. Десятичные двоично-кодированные системы счисления с естественными весами разрядов (8421) и с избытком +3 (8421+3).
3. Системы счисления специального назначения.
4. Системы счисления с непостоянными весами разрядов. Код Грея.
5. Перевод целых чисел из одной системы счисления в другую.
6. Перевод правильных дробей из одной системы счисления в другую.
7. Перевод чисел в системы с кратным основанием.
8. Выбор системы счисления для ЭВМ.
9. Способы представления чисел в ЭВМ. Представление чисел с фиксированной запятой (точкой). Диапазон и точность представления чисел.
10. Представление чисел с плавающей запятой. Диапазон и точность представления чисел.
11. Представления отрицательных чисел в ЭВМ. Прямой, обратный и дополнительный коды.
12. Алгебраическое суммирование чисел с использованием обратного кода.
13. Алгебраическое суммирование чисел с использованием дополнительного кода.
14. Переполнение разрядной сетки. Модифицированные коды. Их использование для алгебраического суммирования чисел.
15. Умножение чисел, представленных в прямом и обратном кодах на два в степени ±К
16. Умножение чисел, представленных в прямом и дополнительном кодах на два в степени ±К.
17. Умножение чисел с фиксированной запятой, заданных в прямом коде с младших разрядов множителя со сдвигом сумм частичных произведений вправо.
18. Умножение чисел с фиксированной запятой, заданных в прямом коде с младших разрядов множителя и сдвигом множимого влево.
19. Умножение чисел с фиксированной запятой, заданных в прямом коде со старших разрядов множителя и сдвигом множимого вправо.
20. Умножение чисел с фиксированной запятой, заданных в прямом коде со старших разрядов множителя со сдвигом сумм частичных произведений влево.
21. Умножение чисел с фиксированной запятой, заданных в прямом коде одновременно на два разряда множителя.
22. Умножение чисел с фиксированной запятой, заданных в дополнительном коде с одним корректирующим шагом.
23. Умножение чисел с фиксированной запятой, заданных в дополнительном коде используя анализ двух смежных разрядов множителя.
24. Умножение чисел с фиксированной запятой, заданных в обратном коде.
25. Аппаратные методы ускорения умножения.
26. Деление чисел с фиксированной запятой, заданных в прямом коде с восстановлением остатка.
27. Деление чисел с фиксированной запятой, заданных в прямом коде со сдвигом остатка и автоматическим его восстановлением.
28. Деление чисел с фиксированной запятой, заданных в прямом коде со сдвигом делителя и автоматическим восстановлением остатка.
29. Деление чисел с фиксированной запятой, заданных в дополнительном коде.
30. Алгебраическое суммирование чисел с плавающей запятой.
31. Умножение и деление чисел с плавающей запятой.
32. Булева функция и переменная. Основные элементарные логические функции.
33. Основные законы алгебры логики. Коммутативный, ассоциативный, дистрибутивные и законы отрицания. Следствия из них.
34. Элементарное логическое произведение (сумма), конституента единицы (нуля), ранг. Правила алгебры логики: склеивания, развёртывания, поглощения.
35. Функционально полные системы элементарных логических функций. Канонические формы представления логических функций. СДНФ, СКНФ.
36. Базис «Шеффера». Представление логических функций в базисе «Шеффера».
37. Базис «Пирса». Представление логических функций в базисе «Пирса».
38. Задача анализа и синтеза логических функций. Минимизация функций алгебры логики. Этапы минимизации.
39. Минимизация логических функций методом Квайна.
40. Числовое и геометрическое представление функций алгебры логики.
41. Минимизация логических функций методом Квайна-мак-Класки.
42. Минимизация логических функций методом Карно.
43. Не полностью определенные логические функции и их минимизация.
44. Основные понятия и определения: абстрактные и структурные автоматы, конечные автоматы, полностью определенные и частичные автоматы, синхронные и асинхронные автоматы.
45. Автоматы МИЛИ и МУРА. Закон функционирования и способы задания автоматов МУРА.
46. Автоматы МИЛИ и МУРА. Закон функционирования и способы задания автоматов МИЛИ.
47. Эквивалентные автоматы. Преобразование автомата МУРА в автомат МИЛИ.
48. Эквивалентные автоматы. Преобразование автомата МИЛИ в автомат МУРА.
49. Совмещенная модель автомата (С автомат). Закон функционирования и способы задания С автоматов.
50. Последовательное соединение автоматов. Таблицы переходов и выходов результирующего автомата. Пример.
51. Параллельное соединение автоматов. Таблицы переходов и выходов результирующего автомата. Пример.
52. Соединение автоматов с обратной связью. Таблицы переходов и выходов результирующего автомата. Пример.
53. Задача структурного синтеза автоматов. Теорема о структурной полноте.
54. Элементарные полные автоматы с одним и двумя входами.
55. Основные этапы канонического метода структурного синтеза автоматов. Пример.
56. Состязания и гонки в автоматах. Способы устранения критических состязаний в автоматах.
57. Противогоночное кодирование состояний автомата.
58. Кодирование состояний автомата и сложность комбинационных схем, реализующих функции выходов и возбуждения элементов памяти.
59. Принцип микропрограммного управления. Модель дискретного преобразователя Глушкова.
60. Функции операционного и управляющего автоматов.
61. Функциональная микропрограмма. Язык функционального микропрограммирования.
62. Классы микроопераций. Функциональная и структурная совместимость микроопераций.
63. Содержательный и закодированный графы микропрограммы.
64. Структурная организация операционных автоматов. Структурный базис. Каноническая структура операционного автомата.
65. Управляющие автоматы с жесткой и программируемой логикой. Интерпретация микропрограммы автоматом МУРА.
66. Интерпретация микропрограммы автоматом МИЛИ.
67. Управляющие автоматы с программируемой логикой. Принудительная и естественная адресация микрокоманд.