Элементы комбинаторики. Теория графов и сетей. Теория кодирования. Конечные автоматы. Теория алгоритмов и вычислимых функций
При передаче сообщения 01100100 произошла ошибка типа {1 ® 0, 0 ® 1} в 3-м и 5-м разрядах. На приемнике получено сообщение _________.
Число сочетаний с повторениями из 7 элементов по 3 равно _____ .
Укажите соответствие между комбинаторными конфигурациями и их наименованиями:
слова длины 8 в алфавите {a, b, c, d, e}
размещения без повторений
двухэлементные подмножества множества {a, b, c, d, e, f}
сочетания без повторений
слова длины 5 из всех букв алфавита {a, б, в, г, д}
размещения с повторениями
Число размещений без повторений из 3 элементов по 5 вычисляется по формуле
C35
A35
Префиксными кодами являются
{a: 00, b: 100, c: 11, d: 01}
{a: 001, b: 01, c: 101, d: 10}
{a: 01, b: 011, c: 110, d: 11}
{a: 01, b: 101, c: 110}
Значение суперпозиции I1 (Z(4), N(5)) исходных п/р функций и констант 4, 5 равно ____ .
Число различных элементарных циклов длины 3 в полном двудольном графе К6,4 равно
24
6
12
0
При правильной раскраске графа (т. е. соседние вершины – разного цвета) 
минимальное число красок равно
минимальное число красок равно4
3
7
2
Число сочетаний без повторений из 4 элементов по 7 равно _____ .
Связный граф с цикломатическим числом, равным 0, есть
Число различных 4-значных четных чисел, которые можно составить из всех цифр числа 5876, вычисляется по формуле
2 ∙ 2!
2 ∙ Р3
2 ∙ С42
2 ∙ 3!
Расстояние в графе между вершинами А и В равно 
4
2
0
8
Кодовый замок имеет 10 клавиш с цифрами 0, 1, 2,..., 9. Для открывания двери нужно последовательно нажать 4 клавиши. Число всевозможных кодов такого замка равно
А104
С104
Стоимость S кода алфавита с заданными частотами букв a: 011 0.3 b: 10 0.5 c: 1101 0.2 равна
1.0
3.0
2.7
2.8
Дерево 
представляет код алфавита
представляет код алфавитаa: 100, b: 10, c: 001, d: 101, e:11
a: 001, b: 01, c: 100, d: 101, e:11
a: 100, b: 01, c: 101, d: 110, e: 11
a: 001, b: 011, c: 101, d: 110, e:111
Тезис Тьюринга
устанавливает сводимость рекурсивных функций к машинам Тьюринга
декларирует связь интуитивного понятия алгоритма с машинами Тьюринга
перечисляет основные требования к точному понятию алгоритма
устанавливает сводимость машин Тьюринга к рекурсивным функциям
Число сочетаний с повторениями из 3 элементов по 4 равно _____ .
Число переменных функции, получаемой применением оператора примитивной рекурсии 
3
2
1
0
Вычисление попарных расстояний Хэмминга для кодовых слов алфавита V = {a, b, c} a: 00110, b: 01001, c: 11101 b: 01001, c: 11101, a: 01110 (второй ряд записан под первым для удобства вычислений) показывает, что кодовое расстояние данного кода равно
5
4
3
2
К основным операторам при построении примитивно рекурсивных функций относятся операторы
примитивной рекурсии
дифференциальный
линейный
суперпозиции
Pасстояние между вершинами А и В в графе с заданными длинами ребер равно 
13
14
10
12
Укажите соответствие между исходными п/р селекторными функциями и их значениями:
I1(6, 2, 11, 8)
2
I4(6, 2, 11, 8)
11
I3(6, 2, 11, 8)
8
I2(6, 2, 11, 8)
6
Остов графа образуют ребра 
{b, c, d}
{a, d, e}
{a, b, c, e}
{b, d}
Тезис Черча
перечисляет основные требования к точному понятию алгоритма
устанавливает сводимость рекурсивных функций к машинам Тьюринга
устанавливает сводимость машин Тьюринга к рекурсивным функциям
декларирует связь интуитивного понятия алгоритма с рекурсивными функциями
Цикломатическое число графа равно _____ . 
Матрица переходов автомата с входным алфавитом {a, b}, выходным алфавитом {a, b, d} и 10 состояниями имеет размерность
10х2
10х10
2х10
10х3
Число различных 5-значных чисел, которые можно составить из всех цифр числа 93871, равно
90000
125
120
25
Число внешних символов машины Тьюринга, представленной графом переходов, равно ___ (ответ – целое число). [Замечание: символы, приписываемые вершинам и дугам графа, отсутствуют, поскольку не требуются для решения] 
Вычисление попарных расстояний Хэмминга для кодовых слов алфавита V = {a, b, c} a: 01100, b: 00011, c: 11110 b: 00010, c: 10110, a: 00101 (второй ряд записан под первым для удобства вычислений) показывает, что кодовое расстояние данного кода равно
3
5
2
4
Если кодовое расстояние для двоичных кодов передаваемых сообщений равно 15, то возможно исправление до ____ ошибок замещения.
Число различных элементарных циклов длины 3 в полном двудольном графе К7,2?
6
49
0
36
Укажите соответствие между сообщениями в алфавите {А, В, С} и их кодами при побуквенном кодировании [А: 1, В: 00, С: 01]
CАВ
00011
AВС
10001
BСА
01100
Число различных 4-значных четных чисел, которые можно составить из всех цифр числа 6534, равно
18
12
6
24
Число слов длины 4 в алфавите {a, b, c, d} равно
256
24
12
64
Число ребер в полном графе K10 равно
90
81
45
100
Функция, получаемая применением оператора примитивной рекурсии 
x, k
x, k, f
x
k
При передаче сообщения 00110001 произошла ошибка вида 1 ® L в 4-м разряде и вида 0 ® 1 в 5-м разряде. На приемнике получено сообщение _________.
Число слов длины 4 в алфавите {a, b, c, d, e} равно
243
1024
60
625
Число слов длины 5 в алфавите {p, q, r, s} вычисляется по формуле
C54
45A45
54Число размещений с повторениями из 3 элементов по 5 вычисляется по формуле
C35
A35
Число сочетаний без повторений из 5 элементов по 2 вычисляется по формуле
A52
Цикломатическое число графа 
0
8
9
1
В коде алфавита {a: 101, b: 01, c: 11} последовательность 1011110101 служит кодом сообщения
acab
cacb
acbc
acba
Остов графа образуют ребра 
{b, c, d, e, f}
{a, f, g, e}
{a, b, h, d}
{a, b, c, g}
В графе Е3 (трехмерном единичном кубе) ___ различных элементарных цепей длины 3 связывают вершины (0 1 1) и (1 0 0) (ответ – целое число). 
Число внешних символов машины Тьюринга, представленной графом переходов, равно ___ (ответ – целое число). [Замечание: символы, приписываемые вершинам и дугам графа, отсутствуют, поскольку не требуются для решения] 
В логической сети выход элемента задержки может быть присоединен к
входу функционального элемента
входу другого элемента задержки
выходу функционального элемента.
своему входу
Число сочетаний без повторений из 3 элементов по 5 вычисляется по формуле
35A35
C35
35Равномерными кодами являются
{a: 100, b: 101, c: 11}
{a: 01, b: 101, c: 110}
{a: 001, b: 101, c: 110}
{a: 00, b: 01, c: 11}
Число сочетаний с повторениями из 3 элементов по 5 вычисляется по формуле
C35
A35