Элементы комбинаторики. Теория графов и сетей. Теория кодирования. Конечные автоматы. Теория алгоритмов и вычислимых функций
Число слов длины 2 в алфавите {a, b, c, d} вычисляется по формуле
2442A24
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
