Элементы комбинаторики. Теория графов и сетей. Теория кодирования. Конечные автоматы. Теория алгоритмов и вычислимых функций. Часть 1

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

• 24
• 42
• A24
• A42

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

• 44
• 24
• 4!
• 42

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

• {a: 00, b: 10, c: 11, d: 01}
• {a: 01, b: 001, c: 111, d: 11}
• {a: 000, b: 01, c: 101, d: 11}
• {a: 010, b: 101, c: 111}

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

• 0
• 36
• 72
• 343

Стоимость S кода алфавита с заданными частотами букв a: 01 0.4 b: 10 0.3 c: 1101 0.3 равна

• 3.0
• 2.8
• 2.5
• 2.6

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

• A53
• C53

Исходная конфигурация машины Тьюринга (М/Т): Установите соответствие между командой М/Т и конфигурацией, полученной из исходной за один шаг действием этой команды:

• q3c ® q2aL
• q3c ® L
• q3c ® q2bR

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

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

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

• 3
• 2
• 5
• 4

Цикломатическое число остова полного двудольного графа К4, 7 равно _____ .

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

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

• 4х7
• 2х4
• 7х2
• 7х4

Остов графа образуют ребра

• {a, b, c, d}
• {a, b, e}
• {a, d}
• {a, d, c}

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

• 55
• С55
• 5!
• 55

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

• слова длины 4 из всех букв алфавита {a, б, в, г}
• 58
• трехэлементные подмножества множества {a, b, c, d, e, f}
• С63
• слова длины 8 в алфавите {a, b, c, d, e}
• Р4

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

• 7
• 6
• 9
• 8

Кратчайшим путем [a, b] в сети является путь

• [a, C, D, b]
• [a, A, D, b]
• [a, A, B, b]
• [a, C, B, b]

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

• 120
• 90000
• 125
• 25

Канонические уравнения автомата выражают текущее выходное значение через

• текущее значение на входе и предыдущее внутреннее состояние
• предыдущее значение на входе и текущее внутреннее состояние
• предыдущее значение на входе и предыдущее внутреннее состояние
• текущее значение на входе и текущее внутреннее состояние

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

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

• 24
• 12
• 81
• 64

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

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

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

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

• 18
• 24
• 12
• 6

Исходная конфигурация машины Тьюринга (М/Т): Установите соответствие между командой М/Т и конфигурацией, полученной из исходной за один шаг действием этой команды:

• невозможно
• q3c ® q2aR
• q3c ® aL

Максимальное число абонентов, которых можно обеспечить 6-значными телефонными номерами, составляет __________ .

Требуется кодировать равномерным двоичным кодом 190 различных объектов. Код должен иметь длину не менее _____ .

Канонические уравнения автомата выражают внутреннее состояние автомата в следующий момент через

• предыдущее значение на входе и предыдущее внутреннее состояние
• текущее значение на входе и текущее внутреннее состояние
• предыдущее значение на входе и текущее внутреннее состояние
• текущее значение на входе и предыдущее внутреннее состояние

Без разделителей можно использовать код алфавита

• {a: 01, b: 11, c: 100}
• {a: 01, b: 001, c: 011}
• {a: 10, b: 01, c: 101}
• {a: 1, b: 01, c: 001}

Кратчайший путь между вершинами вершинами А и В в графе с заданными длинами ребер:

• [AEB]
• [ACEDB]
• [ACEB]
• [ACDB]

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

• 11
• 6
• 2
• 5

Если кодовое расстояние для двоичных кодов передаваемых сообщений равно 12, то возможно исправление до ____ ошибок замещения.

Число дуг (без склеивания) в графе переходов автомата с входным алфавитом {a, b, c, d, e}, выходным алфавитом {d, е} и 5 состояниями равно

• 5
• 25
• 10
• 50

Число ребер в 5-мерном единичном кубе Е5 равно _____ .

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

• 1
• 0
• 3

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

Исходными функциями при построении примитивно рекурсивных функций являются

• N(X) = X + 1
• S(X, Y) = X Y
• P(X, Y) = X + Y
• Z(X) = 0

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

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

Связный граф без циклов есть

Матрица представляет собой матрицу соседства вершин ориентированного графа

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

• I2(3, 2, 1, 10)
• 10
• I1(3, 2, 1, 10)
• 1
• I3(3, 2, 1, 10)
• 3
• I4(3, 2, 1, 10)
• 2

Число размещений без повторений из 3 элементов по 5 равно

• 125
• 120
• 0
• 243

Исходная конфигурация машины Тьюринга (М/Т): Установите соответствие между командой М/Т и конфигурацией, полученной из исходной за один шаг действием этой команды:

• q3c ® bL
• невозможно
• q3c ® q2a

Остов графа образуют ребра

• {a, b, c, d, e}
• {a, b, f, d}
• {b, c, d, g}
• {a, f, c, g}

Цикломатическое число графа

• 25
• 24
• 7
• 0

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

• I1(4, 2, 5, 3)
• 5
• I2(4, 2, 5, 3)
• 3
• I4(4, 2, 5, 3)
• 2
• I3(4, 2, 5, 3)
• 4

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

• 48
• 24
• 72
• 60

Вычисление попарных расстояний Хэмминга для кодовых слов алфавита V = {a, b, c} a: 10101, b: 10110, c: 10011 b: 00110, c: 11011, a: 01101 (второй ряд записан под первым для удобства вычислений) показывает, что кодовое расстояние данного кода равно

• 2
• 3
• 5
• 4

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

• C53
• A53