База ответов ИНТУИТ

Дискретный анализ - ответы

Количество вопросов - 387

Количество слов длины n-2 в алфавите из n символов равно:

Что из перечисленного ниже есть система различных представителей для системы подмножеств S_1 =\{ 1,2,3,4 \}, S_2 =\{ 1,2 \}, S_3 =\{ 2 \}, S_4 =\{ 2 \} исходного множества S=\{ 1,2,3,4 \}

С помощью каких операций можно получить отрицание из любой немонотонной функции алгебры логики:

Укажите полную систему функций:

К каким классам функций алгебры логики относится функция x \cdot y:

Как формально определяется множество ребер неориентированного графа:

Определите сложность решения задачи поиска кратчайших путей в графе с неотрицательными весами ребер n - количество вершин графа:

Что соответствует понятию сюръективного отображения в терминах слов длины n в алфавите из m символов:

Какой граф называют плоским:

Для простого графа с n вершинами укажите количества ребер, обеспечивающие связность графа:

Многочлен Жегалкина для функции x \vee y \vee z имеет вид:

Укажите количество произвольных отображений из множества X,|X|=n, в множество Y\setminus \{ Y_{i_1},..., Y_{i_k}, \;\;\; |Y \setminus \{ Y_{i_1},..., Y_{i_k} \} |=m-k:

Сколько существует способов закупить 5 компьютеров из имеющихся 3 типов:

К классу линейных функций алгебры логики относятся:

Определите производящую функцию для последовательности (1,1,1,1,...):

К каким классам функций алгебры логики относится функция x:

Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения (x_1 + x_2 +...+ x_p)^n:

Полный простой путь длины l имеет тип цикла, если выполняется условие:

Определите взаимосвязь между формулой и функцией алгебры логики:

Класс функций заданный как T_0= \{ f(x_1, x_2, ...,x_n)|f(0,...0)\} =0 является

Укажите верные способы выразить нижнюю степень переменной через степени переменной:

Количество деревьев, которое можно построить на n заданный вершинах, равно:

Для двух чисел Стирлинга 1 рода, не равных нулю, s(n,k) и s(n+1,k+1):

Как называется граф, в котором есть и ориентированные, и неориентированные ребра:

Укажите функции, наличие которых требуется в системе функций для получения из них операциями суперпозиции и замены переменных функций \{ 0,1,\overline {x} \}:

Какие из формул равносильны формуле xy:

Слово длины n- это:

Какова первоначальная формулировка задачи о кенигсбергских мостах:

Максимальное количество ребер в простом графе с n вершинами и k компонентами связности равно:

Чему равно число Белла для множества из 3 элементов:

Некоторая функция алгебры логики зависит от 64 аргументов. Областью определения данной функции алгебры логики является множество с количеством элементов:

Некоторая функция алгебры логики зависит от одного аргумента. Областью определения данной функции алгебры логики является множество с количеством элементов:

Какие из функций алгебры логики принимают значение
истина
при значениях аргументов x=ложь, y=ложь

Какие из функций алгебры логики принимают значение
истина
при значениях аргументов x=ложь, y=истина

Какие из записей являтся формулами:

Какие из записей являтся формулами, если A и B - формулы:

В каких случаях имеет место указанная равносильность формул:

В каких случаях имеет место указанная равносильность формул:

Что является разложением функции алгебры логики x_1 \cdot x_2 в дизъюнктивную форму по переменной x_1

Совершенная дизъюнктивная нормальная форма функции алгебры логики:

Cовершенная дизъюнктивная нормальная форма для импликации x \to y имеет вид:

Если операциями суперпозиции и замены переменных из функций данной системы функций алгебры логики можно получить произвольную функцию алгебры логики, то такая система функций:

Сколько существует функций алгебры логики от n переменных:

К классу функций алгебры логики, сохраняющих ноль, относятся:

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

Количество линейных функций алгебры логики от n переменных равно:

Какое значение принимает самодвойственная функция на наборе (0,1,0,1), если на наборе (1,0,1,0) эта функция принимает значение 1:

Количество самодвойственных функций алгебры логики от n переменных равно:

Для определения монотонной функции алгебры логики:

К каким классам функций алгебры логики относится функция 0:

Любая функция алгебры логики представима единственным образом в виде:

Сколько коэффициентов в многочлене Жегалкина от трех переменных:

Укажите системы функций, не являющихся полными:

Многочлен Жегалкина для функции x \vee y имеет вид:

Многочлен Жегалкина для функции x \to y имеет вид:

Укажите необходимое свойство системы функций, из которых можно получить набор функций \{0,1, \overline{x} \}:

С помощью каких операций можно получить конъюнкцию из любой нелинейной функции алгебры логики:

Для того, чтобы система функций F была полна, необходимо и достаточно, чтобы:

Объект A может быть выбран m различными способами, после этого объект B может быть выбран n различными способами. Тогда:

Имеется 5 путевок на Байкал и 8 путевок на Родос. Сколько существует способов выбрать одну поездку?

Задача о числе функций (отображений) и задача о размещении объектов по ящикам

Упорядоченное размещение объектов по ящикам предполагает, что:

Укажите количество различных слов длины n в алфавите из m символов:

Укажите количество способов разместить 4 шарика по 5 лункам:

Укажите выражения, равные количеству всевозможных размещений n различных объектов по m различным ящикам при условии, что в каждом ящике не более 1 объекта:

Укажите количество способов поставить четырем студентам оценки "удовлетворительно", "хорошо", "отлично", чтобы все студенты получили разные оценки:

Укажите выражения, равные количеству взаимнооднозначных отображений из множества X на себя, где X - конечное множество из n элементов:

Укажите количество различных слов длиной в 5 символов, в которых все символы различны, в алфавите из 5 символов:

Числа Стирлинга первого рода - это:

Чему равно число Стирлинга первого рода s(n,0):

Укажите, где способы упорядоченного размещения семи различных цифр \{ 1,2,3,4,5,6,7 \} по 3 различным ящикам различны:

Выражение m(m+1)(m+2)...(m+n-1) еще называют так:

Сколько существует способов закупить 3 компьютера из имеющихся 3 типов:

Сколько существует монотонных слов длины 6 в алфавите из 2 символов:

Количество монотонных слов длины n в алфавите из m символов:

Сколько существует способов инвестировать 3 миллиона рублей в какие-то из 3 проектов так, чтобы проекты получали целое число миллионов и все деньги были инвестированы:

Сколько существует способов представить целое число 4 в виде суммы целых неотрицательных слагаемых:

Укажите числа сочетаний, равные единице:

Чему равно C_2^4:

Определите производящую функцию для последовательности (1,2,3,4,...)

В формуле свертки c_k=\sum_{i=0}^k{a_i b_{k-i}} значение коэффициента c_2 равно:

Бином Ньютона - это бином вида:

Выражение \sum_{k=0}^{[\frac{n}{2}]} (-1)^k \binom{n}{2k+1} равно:

Чему равна сумма коэффициентов при четных степенях x бинома (1+x)^6:

Чему равна сумма квадратов коэффициентов при степенях бинома (1+x)^{4}:

Укажите эквивалентные записи для полиномиальных коэффициентов \binom{n}{k,n-k} через числа сочетаний:

Чему равно количество размещений 5 различных объектов по 3 различным ящикам при условии, что в первом ящике находится 1 объект, во втором - 2 объекта, в третьем - 2 объекта:

Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения (x_1 + x_2 +x_3)^3:

Блоки разбиения - это:

Сколько существует различных разбиений множества из 4 элементов на 2 класса:

Сколько существует разбиений n+1 объектов на k классов, таких что объект с номером n+1 - единственный в своем классе:

Сколько существует разбиений n+1 объектов на k классов, таких что объект с номером n+1 не является единственным в своем классе:

Сколько существует сюръективных отображений из множества, состоящего из n элементов на множество из m элементов:

Укажите верный способ выразить степень переменной через нижние степени переменной:

Сколько существует всевозможных отображений множества, состоящего из n элементов, в множество, состоящее из m элементов:

Числа Белла выражаются через числа Стирлинга так:

Основная польза метода включений-исключений состоит в следущем:

Решение задачи о подсчете количества элементов в объединении трех множеств A,B,C с применением метода включений-исключений имеет вид:

Как в комбинаторике называют задачу, шутливая формулировка которой такова: "В лондонском клубе швейцар выдает шляпы наобум. Какова вероятность того, что ни один посетитель не получит свою шляпу?"

Приближенное значение выражения n! \{1-1+ \frac{1}{2!} - \frac{1}{3!} +...+(-1)^n \frac{1}{n!} \} равно:

Укажите верное рекуррентное соотношение для числа беспорядков:

Укажите точное значение числа беспорядков на множестве из n элементов:

Формула явного вида для чисел Стирлинга II рода может быть записана как:

Количество разбиений 5 объектов на 3 непустых класса равно 25. Вычислите количество сюръективных отображений из множества, содержащего 5 элементов, на множество, содержащее 3 элемента:

Система различных представителей:

Что из перечисленного ниже есть система различных представителей для системы подмножеств S_1 =\{ 1,2,3,4 \}, S_2 =\{ 2,5 \}, S_3 =\{ 2,5 \}, S_4 =\{ 2,5 \} исходного множества S=\{ 1,2,3,4,5 \}

Система различных представителей для совокупности из n множеств M(S)= \{ S_1, ..., S_n \} существует тогда и только тогда, когда:

Замена представителей - это:

Система общих представителей - это:

Укажите возможные ситуации для системы общих представителей (c_1,с_2,...,c_m) при разбиениях множества S S=A_1 \cup A_2 \cup ... \cup A_m и S=B_1 \cup B_2 \cup ... \cup B_n, для i=1,2,...,m, j=1,2,...,m:

Укажите название известной головоломки: "Можно ли произвольную географическую карту раскрасить в 4 цвета так, чтобы ни одни 2 государства, граница которых имеется и отлична от точки, не были окрашены в один и тот же цвет".

Для графов с каким количеством вершин удобно их графическое представление в виде точек и соединяющих их линий:

Как формально определяется граф:

Укажите, где понятие "инцидентность" использовано верно:

Укажите выражения, описывающие количество ребер в полном неориентированном графе с количеством вершин n:

Вершине неориентированного графа инцидентны три ребра, петель и кратных ребер в графе нет. Определите степень вершины:

В неориентированном графе количество вершин нечетной степени:

Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

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

Укажите достоинства списков инциденций как способа машинного представления графа:

Длина пути в графе - это:

Какова минимальная длина цикла в простом графе:

Как соотносятся между собой графы G и H, если множество вершин графа H является подмножеством вершин графа G и все ребра графа H яаляются ребрами графа G:

Представление графа в виде объединения связанных компонент - это:

Укажите последовательность степеней вершин существующего графа, которая требует связности первой и второй вершины:

Максимальное количество ребер в простом графе с 4 вершинами и 2 компонентами связности равно:

Укажите нижнюю границу количества ребер простого графа с n вершинами, превышение которой означает связность графа:

Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 5 вершинами:

Какой неориентированный граф по определению называется деревом:

Вершина дерева называется концевой вершиной, если:

Количество деревьев, которое можно построить на 10 заданный вершинах, равно:

Какие из методов доказательства применяются при подсчете количества деревьев на n вершинах с k концевыми вершинами:

Сколько существует деревьев на 6 вершинах с 4 концевыми вершинами:

Формулировка задачи о кенигсбергских мостах в терминах теории графов выглядит так:

В каких задачах встречаются эйлеровы пути

В конечном неориентированном графе эйлеров путь существует тогда и только тогда, когда:

Конечный неориентрованный граф имеет эйлеров цикл тогда и тольо тогда, когда:

Путь имеет тип цикла, если:

Некоторый простой путь называется полным, если:

Каким свойством обладает длина максимальных путей в графе без гамильтоновых циклов:

Укажите достаточное условие существования гамильтонова пути в графе с n вершинами:

Степенной последовательностью графа называют:

Для какого графа наименьшее количество вершин, удаление которых приводит к несвязному или одновершинному графу, равно двум:

Для какого графа наименьшее количество вершин, удаление которых приводит к несвязному или одновершинному графу, равно трем:

Любой четырехсвязный планарный граф:

Кратчайший путь - это:

Расстояние от одной вершины графа до другой - это:

Чему равно количество размещений n различных объектов по p различным ящикам при условии, что в каждом ящике находится n_1,n_2,...,n_p объектов соответственно, n_1+n_2+...+n_p=n:

Количество деревьев, которое можно построить на 3 заданный вершинах, равно:

Многочлен Жегалкина для функции x \downarrow y имеет вид:

Сколько сюръективных отображений соответствует каждому разбиению множества X из n элементов на m классов:

Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 3 вершинами:

В каких случаях имеет место указанная равносильность формул:

Укажите выражения, равные количеству размещений n одинаковых объектов по m различным ящикам:

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

Основная лемма критерия полноты обосновывает возможность, при определенных условиях, получения функций:

Укажите функцию, представление которой в виде полинома Жегалкина содержит конъюнкцию с двумя или более переменными:

Сколько существует перестановок элементов множества X, состоящего из n элементов, таких, что ровно k, k \le n, элементов стоят на своих местах, а остальные n-k элементов расположены случайно:

Разложение функции алгебры логики в дизъюнктивную форму по одной переменной:

Какие из перечисленных функций является монотонными?

Укажите необходимые свойства системы функций, из которых можно получить набор функций \{0,1, \overline{x} \}:

Какие равенства представляют собой правила поглощения:

Что является разложением функции алгебры логики x_1 \downarrow x_2 в дизъюнктивную форму по переменной x_1

К основным задачам комбинаторики относятся:

Количество деревьев, которое можно построить на 4 заданных вершинах, равно:

Разбиение - это:

Чему равна сумма всех чисел сочетаний из n по k:

Чему равна сумма квадратов коэффициентов при степенях бинома (1+x)^{5}:

Цикл, по определению, - это:

Путь назвается простым, если:

Укажите количество сюръективных отображений F(n,m) из множества X,|X|=n, на множество Y, \;\; |Y |=m:

В каких случаях формулы A и B равносильны:

Какова максимальная длина простого пути в графе с n вершинами:

Имеется 4 конверта и 5 марок. Сколько существует способов выбрать конверт и марку для одного письма:

Укажите полные системы функций:

Продолжите утверждение: "В связном графе либо имеется гамильтонов цикл, либо:

Процедура перенумерации вершин графа так, чтобы номер вершины, куда ведет ребро, был больше, чем номер вершины-предшественника, называется:

Сколько существует способов представить целое число 3 в виде суммы целых неотрицательных слагаемых:

Что является разложением функции алгебры логики x_1 +x_2 в дизъюнктивную форму по переменной x_1

Производящая функция - это:

Функция алгебры логики - это:

Какие из перечисленных утверждений верны:

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

Как связаны между собой элементарные функции алгебры логики:

В каких случаях имеет место указанная равносильность формул:

Совершенная конъюнктивная нормальная форма функции алгебры логики:

Совершенная конъюнктивная нормальная форма функции алгебры логики:

Примерами полных систем функции алгебры логики являются:

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

Количество функций от n переменных в классе функций, сохраняющих ноль, равно:

К классу функций алгебры логики, сохраняющих единицу, относятся:

Какая из перечисленных функций является монотонной:

Функция алгебры логики, зависящая от n переменных, представима в виде полинома Жегалкина:

Сколько существует различных многочленов Жегалкина от n переменных:

Укажите полные системы функций:

Укажите необходимое свойство системы функций, из которых можно получить набор функций \{0,1, \overline{x} \}:

С помощью каких операций можно получить константу из любой несамодвойственной функции алгебры логики:

Для того, чтобы система функций F была полна, необходимо и достаточно, чтобы:

К модельным задачам комбинаторики относятся:

Укажите количество всевозможных размещений n различных объектов по m различным ящикам:

Укажите количество различных слов длиной в 3 символа, в которых все символы различны, в алфавите из 5 символов:

Укажите выражения, равные количеству всевозможных размещений n различных объектов по n различным ящикам при условии, что в каждом ящике не более 1 объекта:

Чему равно число Стирлинга первого рода s(n,k) при k<0:

Чему равно число Стирлинга первого рода s(n,n):

Сколько существует различных способов расставить 2 разные книги по 10 книжным полкам:

Сколько существует способов закупить 4 компьютера из имеющихся 3 типов:

Монотонное слово длины n- это:

Для целых положительных чисел n и m выражение [m]^n делится нацело на n!:

Укажите числа сочетаний, равные нулю:

Выражение \sum_{k=0}^n (-1)^k \binom{n}k равно:

Чему равно число сочетаний \binom{m+n}{k}:

Какая функция является производящей для полиномиальных коэффициентов \binom{n}{n_1,...,n_p}:

Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения (x_1 + x_2 +x_3)^5:

Сколько существует различных разбиений множества из 4 элементов на 3 класса:

Укажите верные равенства о количестве разбиений множества из n элементов на k классов:

Сколько существует сюръективных отображений из множества, состоящего из 4 элементов на множество из 2 элементов:

Укажите верное рекуррентное соотношение для чисел Стирлинга II рода:

Числа Белла обозначают:

Основная задача метода включений-исключений - это:

Задача о подсчете количества элементов x в объединении трех множеств A,B,C решается методом включений-исключений. Укажите возможные списки свойств объектов:

В комбинаторике беспорядком называют:

Приближенное значение доли беспорядков ко всем перестановкам конечного множества X, состоящего из n элементов, равно:

Сколько существует беспорядков для множества, состоящего из n+1 элемента, таких, что элемент i стоит на 1-ом месте, а элемент 1 НЕ стоит на i-ом месте:

Система различных представителей:

В каких случаях нельзя построить систему различных представителей для n множеств:

Укажите условие существования системы общих представителей для разбиений S=A_1 \cup A_2 \cup ... \cup A_m и S=B_1 \cup B_2 \cup ... \cup B_m:

Как можно доказать существование системы общих представителей в общем случае:

Формула включений-исключений имеет вид:

Какие из формул равносильны формуле x:

Укажите обозначения для числа сочетаний из n элементов по k элементов:

Сколько ребер содержит дерево с n вершинами?

Укажите верные утверждения:

Какой способ наиболее эффективен при подсчете количества деревьев:

Некоторая функция алгебры логики зависит от 64 аргументов. Количество элементов в множестве значений данной функции алгебры логики равно:

По определению, эйлеров путь для конечного неориентированного графа -это:

Укажите комбинаторный смысл полиномиальных коэффициентов \frac{n!}{n_1!n_2!...n_p!}, где n_1+n_2+...+n_p=n, в терминах слов в алфавите:

Функция алгебры логики задана на двух аргументах. Количество элементов в множестве значений данной функции алгебры логики равно:

В каких случаях имеет место указанная равносильность формул:

Совершенная дизъюнктивная нормальная форма функции алгебры логики:

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

Какое значение принимает самодвойственная функция на наборе (0,1,0,1), если на наборе (1,0,0,0) эта функция принимает значение 1?

Количество монотонных функций алгебры логики от n переменных:

Укажите, какие функции алгебры логики могут быть представлены в виде полинома Жегалкина:

Укажите полную систему функций:

Многочлен Жегалкина для функции x|y имеет вид:

Укажите необходимое свойство системы функций, из которых можно получить набор функций \{0,1, \overline{x} \}:

Критерий полноты - это:

Укажите количество способов поставить четырем студентам оценки "удовлетворительно", "хорошо", "отлично":

Укажите выражения, равные количеству различных слов длины n, в которых все символы различны, в алфавите из m символов:

Укажите количество способов разместить 4 шарика по 4 лункам при условии, что в каждой лунке не более 1 шарика:

Чему равно число Стирлинга первого рода s(n,k) при k>n:

В записи числа Стирлинга первого рода s(n,k) индекс k означает, что:

Для двух способов упорядоченного размещения n различных объектов по m различным ящикам верно следующее:

Сколько существует монотонных слов длины 4 в алфавите из 3 символов:

Алфавит - это:

Количество монотонных слов длины n в алфавите из m символов равно:

Укажите выражения, равные числу сочетаний из n элементов по k элементов:

Выражение \sum_{k=0}^{[\frac{n}{2}]} (-1)^k \binom{n}{2k} равно:

Выпишите числа сочетаний для \binom{n}{n_1} \binom{n-n_1}{n2} \binom{n-n_1-n_2}{n_3}... \binom{n_p}{n_p} в факториальной форме::

Сколько существует способов разместить n различных объектов по p различным ящикам, при условии, что в каждом ящике находится n_1,n_2,...,n_p объектов соответственно, n_1+n_2+...+n_p=n, и один из размещаемых объектов уже лежит в ящике i:

Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения (x_1 + x_2 +x_3+ x_4)^3:

Числами Стирлинга II рода называют:

Укажите верное рекуррентное соотношение для числа разбиений:

Сколько существует разбиений из 4 элементов на 2 класса:

Для любого сюръективного отображения верно, что:

Довод, согласно которому из равенства нулю полинома конечной степени в бесконечном множестве целых значений переменной следует равенство полинома нулю для всех вещественных чисел, называют в комбинаторике:

Выразите задачу размещения n одинаковых объектов по m различным ящикам в терминах задачи Муавра:

Укажите верное рекуррентное соотношение для числа беспорядков:

Количество разбиений 6 объектов на 4 непустых класса равно 65. Вычислите количество сюръективных отображений из множества, содержащего 6 элементов, на множество, содержащее 4 элемента:

Что из перечисленного ниже есть система различных представителей для системы подмножеств S_1 =\{ 1,2,3,4 \}, S_2 =\{ 1,2,5 \}, S_3 =\{ 2,5 \}, S_4 =\{ 2,5 \} исходного множества S=\{ 1,2,3,4,5 \}:

Укажите приложения теории графов:

Какая задача в терминах теории графов решалась в связи с проблемой неплатежей после начала перестройки, при наличии списка должников:

Укажите, где понятие "смежность" использовано верно:

Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

Способ представления графа в виде матрицы, в которой строки соответствуют вершинам графа, а столбцы - ребрам, называется:

Способ представления графа в виде матрицы, в которой столбцы и строки соответствуют вершинам графа, называется:

Единственные вершины нечетной степени в простом графе:

Максимальное количество ребер в простом графе с 3 вершинами и 2 компонентами связности равно:

Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 4 вершинами:

Количество деревьев, которое можно построить на 2 заданный вершинах, равно:

Сколько существует деревьев на 3 вершинах с 2 концевыми вершинами:

Началом и концом эйлерова пути могут быть вершины:

Как соотносятся между собой эйлеровы пути и эйлеровы циклы в графе:

Гамильтонов путь на простом неориентрованном графе - это:

Если степень каждой из вершин графа строго больше половины количества вершин графа, то:

Граф называется гамильтоновым, если он:

Двухсвязный негамильтонов граф:

Длина пути в ориентированном графе с весами ребер - это:

Укажите количество различных слов длиной в 3 символа в алфавите из 5 символов:

Максимальный полный путь в связном графе имеет тип цикла тогда и только тогда, когда:

Сколько ребер содержит дерево со 100 вершинами?

Множество деревьев на n вершинах с k концевыми вершинами имеет взаимнооднозначное соответствие с этим множеством:

Эйлеров путь может существовать в графе, количество вершин нечетной степени в котором:

Неориентированный граф называют простым графом, если этот граф:

Что соответствует вершинам и ребрам графа, который описывает "Задачу о четырех красках":

Многочлен Жегалкина для функции (x \cdot \overline{y}) \vee (\overline{x} \cdot y \cdot \overline{z}) имеет вид:

Сколько существует способов инвестировать 4 миллиона рублей в какие-то из 3 проектов так, чтобы проекты получали целое число миллионов и все деньги были инвестированы:

Укажите множество, с которым у множества деревьев с n вершинами имеется взаимнооднозначное соответствие:

Две формулы называются равносильными, если они:

Что является разложением функции алгебры логики x_1 \mid x_2 в дизъюнктивную форму по переменной x_1

Если операциями суперпозиции и замены переменных из функций данной системы функций алгебры логики можно получить только функции, ей принадлежащие, и никаких других функций, то такая система функций:

Количество функций алгебры логики от n переменных, сохранящих единицу, равно:

Функцией, двойственной к x \vee y, является:

Объект A может быть выбран m различными способами, объект B может быть выбран n различными способами, одновременный выбор объектов A и B невозможен. Тогда:

Для двух чисел Стирлинга 1 рода, не равных нулю, s(n,k) и s(n+1,k):

Укажите выражения, равные количеству инъективный отображений из множества X в множество Y, где X - конечное множество из n элементов, Y - конечное множество из m элементов:

Сколько существует способов инвестировать 5 миллионов рублей в какие-то из 3 проектов так, чтобы проекты получали по целому число миллионов и все деньги были инвестированы:

Сверткой в комбинаторике называют:

Что является производящей функцией последовательности \binom{n}k, k=0,1,...,n:

Сколько существует разбиений из 5 элементов на 2 класса:

Что соответствует понятию сюръективного отображения в терминах размещения объектов по ящикам:

В комбинаторике перестановкой элементов конечного множества X называют:

Если система различных представителей для совокупности из n множеств существует, то:

Для совокупности из n множеств M(S)= \{ S_1, ..., S_n \} для каждого i=1,2...,nпоследовательно выбрали a_i \in S_i, \ a_i \ne a_j \ j<i. Тогда выбранный набор \{ a_1, a_2, ... a_n \}:

Укажите выражение, описывающие количество ребер в полном ориентированном графе с количеством вершин n:

Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

При котором из способов представления графа матрица для его представления всегда квадратная:

Как соотносятся между собой графы G и H, если множество вершин графа H является подмножеством вершин графа G и множество ребер графа H состоит из всех ребер графа G, соединяющих вершины графа H:

По определению, граф называется связным, если:

Что из перечисленного есть термины теории графов:

Любое нетривиальное дерево содержит::

Количество слов длины n-2 в алфавите из n-k символов, причем каждый символ входит в это слово, равно:

Чем замечательны эйлеровы пути и эйлеровы циклы на практике:

Полным максимальным путем называют:

В каких задачах применяются ориентированные графы с весами ребер:

К задачам комбинаторики относятся:

Сколько существует монотонных слов длины 7 в алфавите из 2 символов:

Какие из перечисленных функций являются самодвойственными:

Определите сложность решения задачи поиска кратчайших путей в орграфе без циклов отрицательной длины, n - количество вершин графа

Чему равна сумма квадратов чисел сочетаний \sum_{k=0}^n {\binom{n}k}^2:

К классу функций алгебры логики, сохраняющих ноль, относятся:

С помощью каких операций над функциями можно получить из самодвойственной функции константу:

Укажите необходимое свойство системы функций, из которых можно получить набор функций \{0,1, \overline{x} \}:

Укажите количество способов поставить трем студентам оценки "удовлетворительно", "хорошо", "отлично", чтобы все студенты получили разные оценки::

Число различных упорядоченных размещений n различных объектов по m различным ящикам равно:

Определите производящую функцию для последовательности (1,-1,1,-1,...)

Чему равно количество размещений 6 различных объектов по 3 различным ящикам при условии, что в первом ящике находится 1 объект, во втором - 2 объекта, в третьем - 3 объекта:

Рекуррентное соотношение для чисел Белла имеет вид:

Запишите формулу включений-исключений для трех свойств:

Укажите точное значение числа беспорядков на множестве из n элементов:

Как формально определяется множество ребер ориентированного графа:

Укажите вершины графа, степень которых равна нулю:

Для доказательства изоморфности двух графов:

Путь в графе - это:

В формулировке задачи о кенигсбергских мостах в терминах теории графов:

Укажите верные утверждения:

Укажите достаточное условие существования гамильтонова цикла в графе с n вершинами:

В каких случаях имеет место указанная равносильность формул:

Укажите количество всевозможных отображений из множества X в множество Y, где X - конечное множество из n элементов, Y - конечное множество из m элементов:

Укажите количество способов разместить 4 шарика по 5 лункам при условии, что в каждой лунке не более 1 шарика:

Для системы общих представителей (c_1,с_2,...,c_m) при разбиениях множества S S=A_1 \cup A_2 \cup ... \cup A_m и S=B_1 \cup B_2 \cup ... \cup B_n справедливо, для i=1,2,...,m:

Какие из функций алгебры логики принимают значение
истина
при значениях аргументов x=истина, y=ложь

Функцией, двойственной к x \cdot y, является:

К каким классам функций алгебры логики относится функция 1:

Сколько существует упорядоченных размещений 2 объектов по 2 ящикам:

Сколько существует способов инвестировать 3 миллиона рублей в какие-то из 10 проектов так, чтобы проекты получали целое число миллионов и все деньги были инвестированы:

Базис в пространстве многочленов образуют:

Сколько существует беспорядков для множества, состоящего из n+1 элемента, таких, что элемент 1 стоит на i-ом месте, а элемент i - на 1-ом месте:

При построении системы различных представителей:

При построении С.Р.П. для совокупности из n множеств M(S)= \{ S_1, ..., S_n \} для первых r-1 множеств, r<n, удалось выбрать различных представителей, но все элементы множества S_r уже использованы в качестве представителей предыдущих множеств. Тогда:

Появление теории графов как математической дисциплины связывают с датой этого события:

Укажите соотношение между количество ребер в полном ориентированном графе и количеством ребер в полном неориентированном графе, оба графа с количеством вершин n:

Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

Укажите верные утверждения:

По определению, две вершины называются связанными, если:

Максимальное количество ребер в простом графе с 5 вершинами и 2 компонентами связности равно:

Простой граф, имещий две вершины степени 3, соединенные тремя непересекающимися путями длины не менее 2, называется:

Оцените сложность алгоритма построения эйлерова цикла в графе с количеством вершин n и количеством ребер m:

Какие из функций алгебры логики принимают значение
истина
при значениях аргументов x=истина, y=истина

Укажите системы функций, не являщихся полными:

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

Конечный граф - это граф, у которого:

Граф называется негамильтоновым, если он:

Любой планарный граф:

Вес ребра - это:

Определите сложность решения задачи поиска кратчайших путей в графе без циклов, n - количество вершин графа:

Cовершенная конъюнктивная нормальная форма для импликации x \to y имеет вид:

Сколько существует различных способов расставить 10 разных книг по 2 книжным полкам:

Чему равна сумма коэффициентов при нечетных степенях x бинома (1+x)^5:

Укажите взимосвязь чисел Стирлинга II рода S(n,m) и количества сюръективных отображений F(n,m):

Понятие системы общих представителей формулируется для:

Укажите верные утверждения:

Укажите свойство простого графа с количеством вершин n и количеством ребер большим {\frac{1}{2}}(n-1)(n-2):

Чему равно C_4^2:

К каким классам функций алгебры логики относится функция x \vee y:

Разбиение в терминах размещения объектов по ящикам - это:

Сколько существует деревьев на 4 вершинах с 2 концевыми вершинами: