Элементы комбинаторики. Теория графов и сетей. Теория кодирования. Конечные автоматы. Теория алгоритмов и вычислимых функций
Функция, получаемая применением оператора примитивной рекурсии 
k
x, y, k, f
x, y
x, y, k
В коде алфавита {a: 100, b: 01, c: 11} кодом сообщения cbac служит
110001110
111001101
110110011
110111011
Выход функционального элемента логической сети может быть присоединен к
выходу другого функционального элемента.
выходу элемента задержки
входу другого функционального элемента
выходу сети
Укажите соответствие между примерами кодов алфавита и их свойствами:
A: 01, b: 001, c: 1101, d: 111
равномерный
A: 0, b: 00, c: 000, d: 01
неразделимый
A: 001, b: 010, c: 110, d: 111
префиксный
Число различных 4-значных нечетных чисел, которые можно составить из всех цифр числа 8346, равно
12
18
24
6
Остов графа образуют ребра 
{a, b, f, d}
{b, c, d, g}
{a, b, c, d, e}
{a, b, g, e}
Число слов длины 3 в алфавите {p, q, r, s} равно
64
81
12
24
Цикломатическое число графа 
25
6
7
0
Число размещений с повторениями из 3 элементов по 5 равно
120
243
125
0
В графе G последовательность ребер представляет собой 
[a d c]
цикл
[b e d]
путь
[c d e]
цепь
Число различных 4-значных нечетных чисел, которые можно составить из всех цифр числа 4836, равно
18
24
12
6
Pасстояние между вершинами А и В в графе с заданными длинами ребер равно 
19
25
23
17
Кодовый замок имеет 10 клавиш с цифрами 0, 1, 2,..., 9. Для открывания двери нужно последовательно нажать 3 клавиши. Число всевозможных кодов такого замка равно
1000
720
300
120
Стоимость S кода алфавита с заданными частотами букв a: 01 0.4 b: 101 0.5 c: 1100 0.1 равна
2.7
2.6
3.0
1.5
Число сочетаний с повторениями из 5 элементов по 2 вычисляется по формуле
C52
A52
Укажите соответствие между примерами кодов алфавита и их свойствами:
A: 00, b: 01, c: 10, d: 11
префиксный
A: 0, b: 01, c: 1, d: 11
неразделимый
A: 001, b: 010, c: 011, d: 11
равномерный
При передаче сообщения 1011001 произошла ошибка вида L ® 1 между 3-м и 4-м разрядами. На приемнике получено сообщение ___________.
Цикломатическое число остова полного графа К6 равно _____ .
Остов графа образуют ребра 
{a, b, f, e}
{a, b, c, h}
{a, b, c, d, e}
{b, c, d, e, f}
Число размещений без повторений из 4 элементов по 2 равно _____ .
Число слов длины 2 в алфавите {a, b, c, d, e} равно
20
10
5
25
Число дуг (без склеивания) в графе переходов автомата с входным алфавитом {a, b}, выходным алфавитом {a, b, c, d} и 5 состояниями равно
5
10
20
40
Число сочетаний без повторений из 7 элементов по 3 равно _____ .
Требуется кодировать равномерным двоичным кодом 120 различных объектов. Код должен иметь длину не менее _____ .
Укажите соответствие между комбинаторными числами и их обозначениями:
(n, k)-размещения без повторений
nk(n, k)-сочетания без повторений
Сnk
(n, k)-размещения с повторениями
Аnk
Число ребер в полном двудольном графе К6,6 равно
12
36
15
24
Число различных 4-значных чисел, которые можно составить из всех цифр числа 3694, вычисляется по формуле
44Р4
4!
С44
Матрица 
представляет собой матрицу соседства вершин ориентированного графа
представляет собой матрицу соседства вершин ориентированного графа
Кодовый замок имеет 10 клавиш с цифрами 0, 1, 2,..., 9. Для открывания двери нужно одновременно нажать 4 клавиши. Число всевозможных кодов такого замка равно
А104
104410С104
Число различных 4-значных чисел, которые можно составить из всех цифр числа 7218, равно
64
256
9000
24
Если кодовое расстояние для двоичных кодов передаваемых сообщений равно 10, то возможно обнаружение до ____ ошибок замещения.
В графе Е3 (трехмерном единичном кубе) ___ различных элементарных цепей длины 3 связывают вершины (1 0 1) и (0 1 0) (ответ – целое число). 
Число слов длины 4 в алфавите {a, b, c, d} вычисляется по формуле
P4
A44
Укажите соответствие между сообщениями в алфавите {А, В, С} и их кодами при побуквенном кодировании [А: 1, В: 00, С: 01]
CВА
00101
AСВ
10100
BАС
01001
Число вершин в графе переходов автомата с входным алфавитом {a, b, c}, выходным алфавитом {d, е} и 7 состояниями равно
6
7
12
42
Число переменных функции, получаемой применением оператора примитивной рекурсии 
2
4
3
1
В данной сети из полюса α в полюс γ ведут ___ различных элементарных путей (ответ – целое число). 
Число различных 5-значных нечетных чисел, которые можно составить из всех цифр числа 25634, равно
6
24
48
60
Число сочетаний без повторений из 8 элементов по 2 равно
56
30
28
36
Число размещений без повторений из 5 элементов по 3 вычисляется по формуле
C53
Число ребер в полном двудольном графе К4,4 равно _____ .
Число сочетаний с повторениями из 8 элементов по 2 равно
64
56
28
36
При передаче сообщения 10101011 произошла ошибка типа {1 ® 0, 0 ® 1} во 2-м и 7-м разрядах. На приемнике получено сообщение _________.
Число размещений с повторениями из 7 элементов по 3 равно
35
343
210
0
Число слов длины 5 в алфавите {a, b, d}, если b не может находиться с краю, равно
241
54
243
108
Если кодовое расстояние для двоичных кодов передаваемых сообщений равно 14, то возможно исправление до ____ ошибок замещения.
Если кодовое расстояние для двоичных кодов передаваемых сообщений равно 7, то возможно обнаружение до ____ ошибок замещения.
Число размещений без повторений из 7 элементов по 3 равно
343
35
0
210
Стоимость S кода алфавита с заданными частотами букв a: 011 0.3 b: 10 0.6 c: 110 0.1 равна
2.4
2.2
3.0
2.5
Граф переходов представляет машину Тьюринга с ___ состояниями (ответ – целое число) . [Замечание: символы, приписываемые вершинам и дугам графа, отсутствуют, поскольку не требуются для решения] 