Дискретная математика (курс 2). Часть 1

В коде алфавита {a: 100, b: 01, c: 11} кодом сообщения bacb служит

• 111001101
• 010110011
• 011001101
• 011000111

В графе G последовательность ребер представляет собой

• [b e a]
• Путь
• [d a b]
• Цепь
• [b e d]
• Контур

Дерево представляет код алфавита

• a: 00, b: 011, c: 101, d: 110, e:111
• a: 000, b: 0011, c: 1101, d: 1110, e:1111
• a: 00, b: 011, c: 0101, d: 0110, e: 0111
• a: 00, b: 110, c: 101, d: 011, e:111

Префиксными кодами являются

• {a: 01, b: 011, c: 110, d: 11}
• {a: 001, b: 01, c: 101, d: 10}
• {a: 00, b: 100, c: 11, d: 01}
• {a: 01, b: 101, c: 110}

Булевы функции и задаются столбцами значений и . Столбцом значений функции является [ ____ ]T.

Если кодовое расстояние для двоичных кодов передаваемых сообщений равно 8, то возможно обнаружение до ____ ошибок замещения (ответ дать числом)

Стоимость S кода алфавита с заданными частотами букв равна

• 2.6
• 2.5
• 3.6
• 1.0

На координатной плоскости изображено декартово произведение А ∙ В множеств (отрезков) А = [2, 6] и B = [1, 4].

• А и B – множества целых чисел
• A — множество целых чисел, В — множество действительных чисел
• A и В – множества действительных чисел
• А — множество действительных чисел, В — множество целых чисел

Предикатная формула $X,Y (X + Y = Z – X) представляет собой

• трехместный предикат P(X, Y, Z)
• высказывание
• двуместный предикат P(X, Y)
• одноместный предикат P(Z)

Число различных 5-значных чисел, которые можно составить из всех цифр числа 53674, вычисляется по формуле

• Р5
• 5!
• 55
• С55

Функция, получаемая применением оператора примитивной рекурсии

• x, y, k, f
• k
• x, y, k
• x, y

Число различных 4-значных нечетных чисел, которые можно составить из всех цифр числа 2874, вычисляется по формуле

• 4! / 3
• 3 ∙ 3!
• 3!
• 4!

Число сочетаний с повторениями из 3 элементов по 5 равно _____

Значение суперпозиции I1(Z(2), N(4)) исходных п/р функций и констант 2, 4 равно ____ .

Для функции f(X) = X3 суперпозиция f(f(X)) равна

• Х9
• Х8
• Х6

Число внешних символов машины Тьюринга, представленной графом переходов, равно ___ (ответ – целое число). [Указание: символы, приписываемые вершинам и дугам графа, отсутствуют, поскольку не требуются для решения]

Сопоставьте свойства операций сложения и умножения с тождествами, выражающими эти свойства:

• (X + Y) + Z = X + (Y + Z)
• дистрибутивность умножения относительно сложения
• X + Y = Y + X
• коммутативность
• (X + Y) ∙ Z = X ∙ Y + X ∙ Z
• ассоциативность

Алфавитное упорядочение слов в русском алфавите

• транзитивно
• симметрично
• нетранзитивно
• антисимметрично

Кодовый замок имеет 10 клавиш с цифрами 0, 1, 2,…, 9. Для открывания двери нужно одновременно нажать 3 клавиши. Число всевозможных кодов такого замка равно

• 120
• 720
• 310
• 100

В данной сети из полюса a в полюс g ведут ____ различных элементарных цепей (ответ – целое число).

Число различных 5-значных чисел, которые можно составить из всех цифр числа 53674, равно

• 90000
• 25
• 120
• 125

Функционально полную систему булевых функций, состоящую из одной функции, образует

• дизъюнкция
• отрицание
• конъюнкция
• штрих Шеффера

Матрица переходов автомата с входным алфавитом {a, b}, выходным алфавитом {a, b, d} и 5-тью состояниями имеет размерность

• 5х2
• 5х5
• 2х5
• 5х3

Функция, заданная на трехмерном единичном кубе , имеет СДНФ

• Ú
• Ú
• Ú
• Ú

Схема из функциональных элементов реализует функцию

• (Y-X) ∙ X
• (Y- X) ∙ Y
• (X-Y) ∙ Y
• (X-Y) ∙ X

Выражение булевой функции через &, Ú, ¬:

• Ú
• Ú X Y
• Ú X Y
• Ú

На координатной плоскости изображено декартово произведение А ∙ В множеств (отрезков) А = [2, 6] и B = [1, 4].

• А и B – множества целых чисел
• A и В – множества действительных чисел
• A — множество целых чисел, В — множество действительных чисел
• А — множество действительных чисел, В — множество целых чисел

Число слов длины 4 в алфавите {a, b, c} равно

• 81
• 12
• 24
• 64

Число различных элементарных цепей [a, d] в данной сети равно

• 3
• 5
• 2
• 4

X, Y – логические переменные. Тождество (X & Y) = (Y & X) означает, что

• операция & ассоциативна
• (X & Y) – тавтология
• операция & коммутативна
• (X & Y) = (Y & X) – тавтология

Булева функция, задаваемая таблицей выражается формулой

• ¬X & ¬Y
• X & ¬Y
• X & Y
• ¬X & Y

Число сочетаний без повторений из 6 элементов по 2 вычисляется по формуле

• C62
• 62
• A62
• 62

На координатной плоскости изображено декартово произведение А ∙ В множеств (отрезков) А = [2, 6] и B = [1, 4].

• А и B – множества действительных чисел
• А — множество действительных чисел, В — множество целых чисел
• A — множество целых чисел, В — множество действительных чисел
• A и В – множества целых чисел

В графе G последовательность ребер представляет собой

• [c d e]
• Путь
• [a e c]
• Цепь
• [c d a]
• Цикл

Значение суперпозиции Z(I1(4, N(2)))исходных п/р функций и констант 4, 2 равно ____ .

Значение суперпозиции N(I1(N(2), Z(4)))исходных п/р функцийи констант 2, 4 равно ____ .

Цикломатическое число остова полного графа К5 равно _____

Укажите соответствие между графами и их цикломатическими числами:

• 1
• 0
• 2

Число слов длины 4 в алфавите {a, b, c, d} вычисляется по формуле

• A44
• 44
• 44
• P4

Укажите соответствие между исходными п/р селекторными функциями и их значениями:

• I4(5, 2, 1, 17)
• 2
• I1(5, 2, 1, 17)
• 1
• I3(5, 2, 1, 17)
• 5
• I2(5, 2, 1, 17)
• 17

При правильной раскраске полного графа К6 минимальное число красок равно

• 15
• 6
• 2
• 5

Число слов длины 2 в алфавите {a, b, c, d} вычисляется по формуле

• A24
• 24
• A42
• 42

Критерий Поста – это критерий _______ системы булевых функций.

Для функции f(X) = X2 /(2Х-1) суперпозиция f(3-X) равна

• (3-X)2 / (5-2X)
• (3-Х)2 / (2Х –1)
• X2 / (5-2X)
• Х2 / (2Х –1)

Число различных 4-значных четных чисел, которые можно составить из всех цифр числа 2876, равно

• 6
• 24
• 18
• 12

Кодовый замок имеет 10 клавиш с цифрами 0, 1, 2,…, 9. Для открывания двери нужно последовательно нажать 3 клавиши. Число всевозможных кодов такого замка равно

• 120
• 720
• 300
• 1000

Булева функция, задаваемая таблицей выражается формулой

• ¬X & Y
• X & Y
• X & ¬Y
• ¬X & ¬Y

Бинарное отношение «правее» между точками на числовой прямой является

• антисимметричным
• симметричным
• транзитивным
• нетранзитивным

Укажите соответствие между комбинаторными конфигурациями и формулами для их пересчета:

• четырехэлементные подмножества множества из 7 элементов
• Р3
• слова длины 6 в алфавите {a, b, c, d}
• 46
• слова длины 3 из всех букв алфавита {a, b, c}
• С74

Множества А и В не образуют разбиения множества С = {0, 2, 4, 6, 8, 10, 12}, поскольку

• A = {0, 4, 6}, B = {2, 6, 10}
• не выполнена полнота разбиения
• A = {0, 4, 8, 12}, B = {2, 6, 10, 12}
• не выполнена чистота разбиения
• A = {0, 4, 8}, B = {2, 6, 12}
• не выполнены ни чистота, ни полнота разбиения