Дискретная математика тест-драйв по дискретной математике и математи
..pdft21. Задача называется NP-полной (универсальной), если к ней может быть полиномиально сведена любая … задача
(1): P
(2): NP (3): Е (4): N
t22. Задача называется NP-полной (универсальной) в том смысле, что построение полиномиального алгоритма для нее влечет автоматически возможность построения такого же алгоритмадля всех задач
(1): Е (2): P (3): NP (4): PR
III.Автоматы
1.Переключательные функции
1.1.Понятие переключательной функции
Уровень – легкий
t1. Переключательная функция – это функция, у которой
(1): аргументы и сама функция принимают значение из бинарного множества
(2): только аргументы принимаютзначение изконечных множеств (3): только сама функция принимает значение из конечных мно-
жеств (4): аргументы и сама функция принимают значение из конеч-
ных множеств
t2. Бинарнаяпереключательная функция – это функция, у которой (1): или аргументы, или сама функция принимают значение из
бинарного множества (2): только аргументы принимают значение из бинарного мно-
жества
81
(3): аргументы и сама функция принимают значение из бинарного множества
(4): только сама функция принимает значение из бинарного множества
t3. Вектор двоичной двухместной переключательной функции «импликация» в порядке переменных а, b = 00, 01, 10, 11 равен
(1): 1, 0, 1, 1 (2): 1, 1, 0, 1 (3): 1, 1, 0, 0 (4): 0, 1, 1, 1
t4. Вектор двоичной двухместной переключательной функции «эквиваленция» в порядке переменных а, b = 00, 01, 10, 11 равен
(1): 1, 0, 0, 1 (2): 0, 1, 1, 0 (3): 1, 1, 0, 0 (4): 0, 0, 1, 1
t5. Вектор двоичной двухместной переключательной функции «суммапо модулю два» впорядкепеременныха, b = 00, 01, 10, 11 равен
(1): 1, 0, 0, 1 (2): 0, 1, 1, 0 (3): 1, 1, 0, 1 (4): 1, 0, 1, 1
t6. Двоичный вектор переключательной функции, представленной десятичным числом 174, это
(1): 01 111 100 (2): 11 100 111 (3): 10 101 110 (4): 10 100 111
t7. Двоичный вектор переключательной функции, представленной десятичным числом 174, это
(1): 01 111 100 (2): 10 101 110
82
(3): 11 100 111 (4): 10 100 111
Уровень – средний
t8. Закон исключенного третьего в алгебре переключательных функций формулируется следующим образом
(1): конъюнкция переменной и ее инверсии равна единице (2): конъюнкция переменной и ее инверсии равна нулю
(3): суммапо модулю двапеременнойи ее инверсии равнаединице (4): дизъюнкция переменной и ее инверсии равна единице
t9. Закон противоречия в алгебре переключательных функций формулируется следующим образом
(1): конъюнкция переменной и ее инверсии равна нулю (2): конъюнкция переменной и ее инверсии равна единице (3): дизъюнкция переменной и ее инверсии равна нулю
(4): сумма по модулю два переменной и ее инверсии равна нулю
t10. Закон Де Моргана относительно дизъюнкции двух переменных в алгебре переключательных функций: отрицание дизъюнкции двух переменных равно … этих переменных
(1): дизъюнкции отрицания (2): конъюнкции отрицания (3): эквиваленции отрицаний
(4): сумме по модулю два отрицаний
t11. Закон Де Моргана относительно конъюнкции двух переменных в алгебре переключательных функций: отрицание конъюнкции двух переменных равно … этих переменных
(1): конъюнкции отрицаний (2): эквиваленции отрицаний (3): дизъюнкции отрицаний
(4): сумме по модулю два отрицаний
83
t12. Закон повторения относительно дизъюнкции в алгебре переключательных функций: дизъюнкция переменной с этой же переменной равна
(1): инверсии этой переменной
(2): нулю
(3): единице (4): этой переменной
t13. Закон повторения относительно конъюнкции в алгебре переключательных функций: конъюнкция переменной с этой же переменной равна
(1): тильде (2): этой переменной
(3): нулю
(4): единице
Уровень – сложный
t14. Формула равносильных преобразований относительно конъюнкции некоторой переменной с подформулой, зависящей от этой переменной, предполагает замену всех вхождений этой переменной в подформуле
(1): на единицу
(2): ноль
(3): тильду (4): инверсию этой переменной
t15. Формула равносильных преобразований относительно дизъюнкции некоторой переменной с подформулой, зависящей от этой переменной, предполагает замену всех вхождений этой переменной в подформуле
(1): на единицу
(2): ноль
(3): тильду (4): инверсию этой переменной
84
t16. Получить результат вычислений трехзначной дизъюнкции (для переменных 0, 1, 2) «2 или 1»
(1): 1 (2): 2 (3): 3 (4): 0
t17. Получить результат вычислений трехзначной конъюнкции (для переменных 0, 1, 2) «2 и 1»
(1): 2 (2): 1 (3): 21 (4): 3
t18. Получить результат вычислений трехзначной суммы по модулю 3 (для переменных 0, 1, 2) «2 + 1 (по модулю 3)»
(1): 0 (2): 1 (3): 2 (4): 3
t19. Получить результат вычислений трехзначной арифметической суммы (для переменных 0, 1, 2) «2 + 2»
(1): 10 (2): 2 (3): 11 (4): 4
t20. Получить результат вычислений трехзначного арифметического произведения «2 × 2»
(1): 11 (2): 4 (3): 2 (4): 10
85
1.2. Минимизация методом карт Карно
Уровень – легкий
t1. Метод минимизации по картам Карно основан (1): на использовании закона обобщенного склеивания (2): использовании разложения Шеннона
(3): использовании формул равносильных преобразований
(4): использовании n-мерной таблицы истинности и нахождении правильных контуров единиц или нулей
t2. Клетке 0 карты Карно на три переменные являются соседними клетки
(1): 4 (2): 2
(3): 1, 4, 2 (4): 1
t3. Клетке 3 карты Карно на три переменные являются соседними клетки
(1): 0, 1, 2 (2): 3, 4, 5 (3): 1, 7 (4): 1, 2, 7
t4. Клетке 3 карты Карно на четыре переменные являются соседними клетки
(1): 0, 1, 2, 4 (2): 1, 2, 7, 11 (3): 3, 4, 5, 6 (4): 1, 2, 7
t5. Клетке 0 карты Карно на четыре переменные являются соседними клетки
(1): 4, 8 (2): 2, 3, 4, 5
(3): 1, 2, 3, 4 (4): 1, 4, 2, 8
86
Уровень – средний
t6. Результат минимизации функции трех переменных 7, 6, 5, 3 в классе ДНФ по карте Карно равен
(1): (11–) (1–1) (–11) (2): (10–) (0–1) (–01) (3): (00–) (0–0) (–00) (4): (01–) (1–0) (–10)
t7. Результат минимизации функции трех переменных 4, 2, 1, 0 в классе ДНФ по карте Карно равен
(1): (10–) (0–1) (–01) (2): (00–) (0–0) (–00) (3): (11–) (1–1) (–11) (4): (01–) (1–0) (–10)
t8. Результат минимизации функции трех переменных 1, 2, 3, 5, 7 в классе ДНФ по карте Карно равен
(1): (1–1) (–11) (–1) (2): (–1) (01–)
(3): (110) (101) (–11) (4): (01–) (100) (110)
t9. Результат минимизации функции трех переменных 2, 3, 5, 6, 7 в классе ДНФ по карте Карно равен
(1): (1–0) (–10)
(2): (11–) (1–1) (–11) (3): (–1–) (1–1)
(4): (01–) (10–) (110)
Уровень – сложный
t10. Результат минимизации функции четырех переменных «диагональные единицы» по карте Карно в классе ДНФ равен
(1): (–1–1) (2): (–0–0)
87
(3): (–1–1) (–0–0) (4): (–0–1) (–1–0)
t11. Результат минимизации функции четырех переменных «единицы по краям» по карте Карно в классе ДНФ равен
(1): (–1–0) (2): (–0–1)
(3): (–0–1) (–1–1) (4): (–0– –) (– – –0)
t12. Результат минимизации функции четырех переменных «диагональные единицы» по карте Карно в классе КНФ равен
(1): [(–0– –) (– – –1)][(–1– –) (– – –0)] (2): [(–1– –) (– – –1)][(–0– –) (– – –0)] (3): [(–00–) (– – –1)][(–10–) (– – –0)] (4): [(–0–1) (– – –1)][(–1–1) (– – –0)]
t13. Результат минимизации функции четырех переменных «единицы по краям» по карте Карно в классе КНФ равен
(1): (–1–0)
(2): (–0– –) (– – –0) (3): (–0–1)
(4): (–0–1) (–1–1)
t14. Метод минимизации Блейка – Порецкого основан на использовании закона
(1): обобщенного склеивания (2): Де Моргана (3): склеивания (4): Порецкого
88
1.3. Метод поразрядного сравнения рабочих и запрещенных наборов
Уровень – легкий
t1. Минимизация методом Л.Ф. Викентьева основана
(1): на минимизации каждого отдельного разряда рабочего восьмеричного набора
(2): на минимизации каждого отдельного разряда запрещенного восьмеричного набора
(3): на использовании закона обобщенного склеивания (4): на использовании закона Порецкого
t2. Минимизация каждого восьмеричного рабочего набора в методе Л.Ф. Викентьева производится
(1): по таблице покрытий (2): по таблице переходов (3): по временной диаграмме (4): по кубу соседних чисел
t3. После минимизации очередного рабочего набора в методе Л.Ф. Викентьева необходимо определить покрытие полученной импликантой
(1): запрещенных наборов (2): рабочих наборов (3): условных наборов
(4): только очередного рабочего набора
t4. При минимизации очередного разряда рабочего восьмеричного набора в методе Л.Ф. Викентьева в качестве рабочих чисел функции трех переменных
(1): берутсявсеразрядыочередногорабочеговосьмеричногонабора (2): берутсядваразрядаочередногорабочеговосьмеричногонабора (3): берется один очередной разряд (4): берутся три разряда очередного рабочего восьмеричного на-
бора (данный и два соседних)
89
Уровень – средний
t5. Запрещенные цифры для каждого разряда в методе Л.Ф. Викентьева – это такие разряды, которые в комбинации с оставшимися разрядами могут привести к получению
(1): разрешенных наборов (2): запрещенных наборов (3): условных наборов (4): данного набора
t6. Минимизация путем поразрядного сравнения рабочих и запрещенных двоичных наборов основана на определении
(1): минимального количества переменных в рабочем наборе, позволяющих обеспечить ортогональность по отношению к очередному запрещенному набору запрещенным наборам
(2): минимального количества переменных в рабочем наборе, позволяющих обеспечить ортогональность по отношению к следующему рабочему набору наборам
(3): максимального количества переменных в рабочем наборе, позволяющих обеспечить ортогональность по отношению ко всем запрещенным наборам
(4): минимального количества переменных в рабочем наборе, позволяющих обеспечить ортогональность по отношению ко всем запрещенным наборам
t7. Функция шести переменных задана восьмеричными кодами 56[26], для первого разряда запрещенные числа
(1): 2 (2): 2, 5 (3): 0, 1
(4): нет запрещенных чисел
t8. Функция пяти переменных задана восьмеричными кодами 37, 22, 31 [00, 16, 10], для рабочего числа 37 для первого разряда запрещенные числа
(1): 2, 5 (2): 0, 1
90