Главная /
Алгоритмы и дискретные структуры /
Дискретный анализ
Дискретный анализ - ответы на тесты Интуит
Правильные ответы выделены зелёным цветом.
Все ответы: Дискретный анализ содержит материал, излагаемый в первом семестре курса дискретного анализа: комбинаторика, элементы алгебры логики, начальные сведения теории графов. В курс включены как основополагающие понятия и результаты перечисленных разделов, так и материал повышенной трудности, часто в лекциях не излагаемый. Курс предназначен для изучения студентами соответствующих разделов программы основ дискретного анализа.
Все ответы: Дискретный анализ содержит материал, излагаемый в первом семестре курса дискретного анализа: комбинаторика, элементы алгебры логики, начальные сведения теории графов. В курс включены как основополагающие понятия и результаты перечисленных разделов, так и материал повышенной трудности, часто в лекциях не излагаемый. Курс предназначен для изучения студентами соответствующих разделов программы основ дискретного анализа.
Укажите верные равенства о количестве разбиений множества из ![math]()
элементов на ![math]()
классов:
элементов на 
классов:
(1) ![math]()
(2) ![math]()
, где ![math]()
, где 
(3) ![math]()
, где ![math]()
, где 
(4) ![math]()
(5) ![math]()
Появление теории графов как математической дисциплины связывают с датой этого события:
(1) появление задач о структуре молекул
(2) появление статьи Эйлера о Кенигсбергских мостах
(3) формулировка задач об электрических сетях
(4) постановка проблемы четырех красок
Укажите множество, с которым у множества деревьев с ![math]()
вершинами имеется взаимнооднозначное соответствие:
вершинами имеется взаимнооднозначное соответствие:
(1) множество слов длины ![math]()
в алфавите из ![math]()
символов
в алфавите из символов
(2) множество слов длины ![math]()
в алфавите из ![math]()
символов
в алфавите из символов
(3) множество слов длины ![math]()
в алфавите из ![math]()
символов
в алфавите из символов
(4) множество слов длины ![math]()
в алфавите из ![math]()
символов
в алфавите из символов Некоторая функция алгебры логики зависит от 64 аргументов. Областью определения данной функции алгебры логики является множество с количеством элементов:
(1) 2
(2) 64
(3) 642
(4) 264
Любая функция алгебры логики представима единственным образом в виде:
(1) полинома Жегалкина
(2) конъюнктивной нормальной формы
(3) дизъюнктивной нормальной формы
(4) суперпозиции немонотонной и несамодвойственной функции
Для двух способов упорядоченного размещения ![math]()
различных объектов по ![math]()
различным ящикам верно следующее:
различных объектов по 
различным ящикам верно следующее:
(1) способы размещения различаются только на основании того, какой объект попал в какой ящик
(2) если в одном и том же ящике одни и те же объекты стоят в разном порядке, то способы упорядоченного размещения различны
(3) упорядоченные размещения различаются по тому, в каком порядке стоят ящики
Сколько существует разбиений ![math]()
объектов на ![math]()
классов, таких что объект с номером ![math]()
не является единственным в своем классе:
объектов на классов, таких что объект с номером не является единственным в своем классе:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Что соответствует вершинам и ребрам графа, который описывает "Задачу о четырех красках":
(1) страны изображаются в виде вершин, ребра соединяют вершины, если между соответствующими им странами имеется граница, отличная от точки
(2) страны изображаются в виде вершин, ребра соединяют вершины, если соответствующие им страны окрашены на карте в одинаковый цвет
(3) вершины изображают точки, где пересекаются границы трех и более государств, ребра соответствуют линиям границы между государствами
Количество слов длины ![math]()
в алфавите из ![math]()
символов, причем каждый символ входит в это слово, равно:
в алфавите из 
символов, причем каждый символ входит в это слово, равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Какие из перечисленных утверждений верны:
(1) в логике любое высказывание либо истинно, либо ложно; третьего не дано.
(2) в алгебре высказываний каждая из переменных принимает одно из двух значений, истина или ложь. Третьего не дано.
(3) в рамках любой математической теории, содержащей хотя бы арифметику, всегда можно сформулировать утверждение, которое нельзя ни опровергнуть, ни доказать.
Сколько существует различных многочленов Жегалкина от ![math]()
переменных:
переменных:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Выражение ![math]()
еще называют так:
еще называют так:
(1) ![math]()
в верхней степени ![math]()
в верхней степени
(2) ![math]()
в нижней степени ![math]()
в нижней степени
(3) ![math]()
-факториал от ![math]()
вверх
-факториал от вверх
(4) ![math]()
-факториал от ![math]()
вниз
-факториал от вниз Для любого сюръективного отображения верно, что:
(1) у каждого элемента образа существует единственный прообраз
(2) у каждого элемента образа существует хотя бы один прообраз
(3) сюръективное отображение является взаимнооднозначным соответствием
(4) каждому элементу множества, на котором задано сюрьективное отношение, соответствует не более одного образа
Как формально определяется граф:
(1) множество ориентированных и неориентированных отрезков
(2) множество точек и соединяющих их отрезков
(3) совокупность из двух множеств: множества вершин и множества ребер (дуг)
Сколько существует деревьев на 3 вершинах с 2 концевыми вершинами:
(1) 1
(2) 2
(3) 3
(4) 4
Что из перечисленного ниже вводится как функция алгебры логики:
(1) дизъюнкция
(2) конъюнкция
(3) сумма
(4) эквивалентность
(5) импликация
(6) ассоциативность
(7) стрелка
(8) штрих
Укажите системы функций, не являщихся полными:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Сколько существует способов закупить 5 компьютеров из имеющихся 3 типов:
(1) 15
(2) 21
(3) 35
(4) 45
Сколько существует сюръективных отображений из множества, состоящего из ![math]()
элементов на множество из ![math]()
элементов:
элементов на множество из элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Как называется граф, в котором есть и ориентированные, и неориентированные ребра:
(1) ориентированный граф
(2) неориентированный граф
(3) смешанный граф
(4) для такого графа не вводится отдельного понятия, так как всегда можно свести граф к ориентированному графу или к неориентированному графу
Какова первоначальная формулировка задачи о кенигсбергских мостах:
(1) обойти все части города, разделенные рекой и соединенные мостами так, чтобы побывать в каждой части города ровно по 1 разу
(2) обойти все части города, разделенные рекой и соединенные мостами так, чтобы пройти по каждому мосту ровно 1 раз, и вернуться в исходную точку путешествия
(3) обойти все части города, разделенные рекой и соединенные мостами так, чтобы пройти по каждому мосту ровно 1 раз
Какие из функций алгебры логики принимают значение ![math]()
при значениях аргументов ![math]()
при значениях аргументов 
(1) дизъюнкция
(2) конъюнкция
(3) сумма
(4) эквивалентность
(5) импликация ![math]()
(6) штрих
(7) стрелка
Укажите полные системы функций:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Сколько существует монотонных слов длины 6 в алфавите из 2 символов:
(1) 4
(2) 5
(3) 6
(4) 7
(5) 8
(6) 12
Базис в пространстве многочленов образуют:
(1) степени переменной
(2) нижние степени переменной
(3) числа Стирлинга I рода
(4) числа Стирлинга II рода
Укажите выражения, описывающие количество ребер в полном неориентированном графе с количеством вершин ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
По определению, эйлеров путь для конечного неориентированного графа -это:
(1) путь, проходящий через каждое ребро графа в точности один раз
(2) путь, проходящий через каждую вершину графа в точности один раз
(3) цикл, проходящий через каждое ребро графа в точности один раз
Какие из записей являтся формулами:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Многочлен Жегалкина для функции ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Алфавит - это:
(1) множество символов
(2) конечное множество символов
(3) конечное упорядоченное множество символов
Сколько существует всевозможных отображений множества, состоящего из ![math]()
элементов, в множество, состоящее из ![math]()
элементов:
элементов, в множество, состоящее из элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Неориентированный граф называют простым графом, если этот граф:
(1) не имеет петель и кратных ребер
(2) не является полным
(3) не имеет кратных ребер, но может иметь петли
(4) не имеет петель и кратных ребер, степень каждой вершины графа равна единице
В конечном неориентированном графе эйлеров путь существует тогда и только тогда, когда:
(1) граф связен
(2) граф связен и имеет четное количество вершин нечетной степени
(3) граф связен и имеет не более 2 вершин нечетной степени
Какие из записей являтся формулами, если ![math]()
и ![math]()
- формулы:
и 
- формулы:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
(5) ![math]()
Многочлен Жегалкина для функции ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Количество монотонных слов длины ![math]()
в алфавите из ![math]()
символов равно:
в алфавите из символов равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Числа Белла обозначают:
(1) количество упорядоченных разбиений множества из ![math]()
элементов на произвольное число классов
элементов на произвольное число классов
(2) количество разбиений множества из ![math]()
элементов на фиксированное число классов
элементов на фиксированное число классов
(3) динамику и направленность развития индустриального общества
(4) количество разбиений ![math]()
-множества на произвольное число классов
-множества на произвольное число классов В неориентированном графе количество вершин нечетной степени:
(1) нечетно
(2) четно
(3) может быть как четным, так и нечетным
Как соотносятся между собой эйлеровы пути и эйлеровы циклы в графе:
(1) эйлеровых путей в графе больше, чем эйлеровых циклов
(2) эйлеровы пути и эйлеровы циклы в графе находятся во взаимнооднозначном соответствии
(3) в некоторых графах есть эйлеровы пути, но нет эйлеровых циклов
В каких случаях имеет место указанная равносильность формул:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Основная лемма критерия полноты обосновывает возможность, при определенных условиях, получения функций:
(1) константа 0, константа 1, тождество
(2) константа 0, константа 1, отрицание
(3) константа 0, константа 1, конъюнкция
(4) константа 0, константа 1, дизъюнкция
Сколько существует способов инвестировать 5 миллионов рублей в какие-то из 3 проектов так, чтобы проекты получали по целому число миллионов и все деньги были инвестированы:
(1) 15
(2) 20
(3) 21
(4) 42
(5) 63
(6) 125
Чему равно число Белла для множества из 3 элементов:
(1) 1
(2) 3
(3) 5
(4) 7
(5) 9
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:
(1) (1,1,1,1,1)
(2) (10,10,3,2)
(3) (4,5,4,5,4)
(4) (11,1,2,2,3)
Чем замечательны эйлеровы пути и эйлеровы циклы на практике:
(1) существуют необходимые и достаточные условия их существования
(2) существуют эффективные алгоритмы
В каких случаях имеет место указанная равносильность формул:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите необходимое свойство системы функций, из которых можно получить набор функций ![math]()
:
:
(1) наличие самодвойственной функции
(2) отсутствие самодвойственной функции
(3) отсутствие несамодвойственной функции
(4) наличие несамодвойственной функции
Сколько существует способов инвестировать 3 миллиона рублей в какие-то из 10 проектов так, чтобы проекты получали целое число миллионов и все деньги были инвестированы:
(1) 30
(2) 33
(3) 55
(4) 300
(5) 1000
Основная задача метода включений-исключений - это:
(1) подсчет количества объектов, которые обладают всеми указанными свойствами
(2) подсчет количества объектов, которые обладают ровно ![math]()
из ![math]()
указанными свойствами
из указанными свойствами
(3) подсчет количества объектов, которые обладают не менее, чем ![math]()
из ![math]()
указанных свойств
из указанных свойств
(4) подсчет количества объектов, которые не обладают ни одним из указанных свойств
Способ представления графа в виде матрицы, в которой строки соответствуют вершинам графа, а столбцы - ребрам, называется:
(1) список смежности
(2) список инцидентности
(3) матрица смежности
(4) матрица инциденций
Некоторый простой путь называется полным, если:
(1) этот путь нельзя продолжить добавлением вершин к его концам
(2) множество вершин этого пути порождает подграф, имеющий гамильтонов путь
(3) этот путь проходит через все вершины графа
Разложение функции алгебры логики в дизъюнктивную форму по одной переменной:
(1) существует для любой функции алгебры логики
(2) не существует для функций алгебры логики, заданных табличным образом
(3) существует для всех функций алгебры логики, но только для первой переменной
С помощью каких операций можно получить конъюнкцию из любой нелинейной функции алгебры логики:
(1) замена переменных и суперпозиция с функциями ![math]()
(2) замена переменных и суперпозиция с функциями ![math]()
(3) замена переменных и суперпозиция с функциями ![math]()
(4) только суперпозиция с функциями ![math]()
Укажите числа сочетаний, равные единице:
(1) ![math]()
, ![math]()
, 
(2) ![math]()
(3) ![math]()
(4) ![math]()
Задача о подсчете количества элементов ![math]()
в объединении трех множеств ![math]()
решается методом включений-исключений. Укажите возможные списки свойств объектов:
в объединении трех множеств 
решается методом включений-исключений. Укажите возможные списки свойств объектов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите самый неудобный способ машинного представления графа:
(1) матрица смежности
(2) списки инциденций
(3) матрица инциденций
Максимальный полный путь в связном графе имеет тип цикла тогда и только тогда, когда:
(1) граф имеет эйлеров цикл
(2) граф имеет гамильтонов цикл
(3) этот путь проходит через все вершины графа
Что является разложением функции алгебры логики ![math]()
в дизъюнктивную форму по переменной ![math]()
в дизъюнктивную форму по переменной 
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Для того, чтобы система функций ![math]()
была полна, необходимо и достаточно, чтобы:
была полна, необходимо и достаточно, чтобы:
(1) ![math]()
целиком не содержалась ни в одном из замкнутых классов ![math]()
целиком не содержалась ни в одном из замкнутых классов 
(2) ![math]()
целиком содержалась хотя бы в одном из замкнутых классов ![math]()
целиком содержалась хотя бы в одном из замкнутых классов
(3) ![math]()
целиком содержалась во всех замкнутых классах ![math]()
целиком содержалась во всех замкнутых классах Укажите выражения, равные числу сочетаний из ![math]()
элементов по ![math]()
элементов:
элементов по элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
В комбинаторике беспорядком называют:
(1) уличный беспорядок
(2) беспорядок в комнате
(3) перестановку, где элементы перечислены в произвольном порядке
(4) перестановку, где ни один элемент не стоит на своем месте
Длина пути в графе - это:
(1) количество ребер, входящих в путь
(2) количество вершин, входящих в путь
(3) сумма количества ребер и количества вершин, входящих в путь
Укажите достаточное условие существования гамильтонова пути в графе с ![math]()
вершинами:
вершинами:
(1) для любой пары вершин сумма степеней этих вершин не менее чем ![math]()
(2) для любой пары вершин сумма степеней этих вершин более чем ![math]()
(3) для любой пары вершин сумма степеней этих вершин не менее чем ![math]()
Совершенная дизъюнктивная нормальная форма функции алгебры логики:
(1) существует для всех функций алгебры логики, кроме тождественного нуля
(2) определена для константы ![math]()
(3) определена для константы ![math]()
Объект ![math]()
может быть выбран ![math]()
различными способами, после этого объект ![math]()
может быть выбран ![math]()
различными способами. Тогда:
может быть выбран различными способами, после этого объект может быть выбран различными способами. Тогда:
(1) объект ![math]()
может быть выбран ![math]()
различными способами
может быть выбран 
различными способами
(2) объект ![math]()
может быть выбран ![math]()
различными способами
может быть выбран 
различными способами
(3) объект ![math]()
может быть выбран ![math]()
различными способами
может быть выбран 
различными способами
(4) объект ![math]()
может быть выбран ![math]()
различными способами
может быть выбран различными способами Определите производящую функцию для последовательности ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Сколько существует перестановок элементов множества ![math]()
, состоящего из ![math]()
элементов, таких, что ровно ![math]()
, ![math]()
, элементов стоят на своих местах, а остальные ![math]()
элементов расположены случайно:
, состоящего из элементов, таких, что ровно , 
, элементов стоят на своих местах, а остальные элементов расположены случайно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Цикл, по определению, - это:
(1) любой путь, у которого начальная и конечная вершины совпадают
(2) простой путь, у которого начальная и конечная вершины совпадают
(3) проходящий через все вершины графа простой путь, у которого начальная и конечная вершины совпадают
Если степень каждой из вершин графа строго больше половины количества вершин графа, то:
(1) граф имеет эйлеров путь
(2) граф имеет эйлеров цикл
(3) граф имеет гамильтонов путь
(4) граф имеет гамильтонов цикл
Совершенная конъюнктивная нормальная форма функции алгебры логики:
(1) определена для константы ![math]()
(2) наиболее удобна для представления функции алгебры логики, в табличном представлении которой много нулей и мало единиц
(3) определена для константы ![math]()
Имеется 5 путевок на Байкал и 8 путевок на Родос. Сколько существует способов выбрать одну поездку?
(1) 5
(2) 8
(3) 13
(4) 40
Сверткой в комбинаторике называют:
(1) произведение Коши
(2) формулу для коэффициента перед переменной в степени ![math]()
для произведения производящих функций
для произведения производящих функций
(3) формулу для ![math]()
-го члена последовательности, производящая функция которой есть произведение двух других производящих функций
-го члена последовательности, производящая функция которой есть произведение двух других производящих функций
(4) выражение для числа сочетаний по ![math]()
из ![math]()
из Укажите верное рекуррентное соотношение для числа беспорядков:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Как соотносятся между собой графы ![math]()
и ![math]()
, если множество вершин графа ![math]()
является подмножеством вершин графа ![math]()
и все ребра графа ![math]()
яаляются ребрами графа ![math]()
:
и 
, если множество вершин графа является подмножеством вершин графа и все ребра графа яаляются ребрами графа :
(1) граф ![math]()
является изоморфным графу ![math]()
является изоморфным графу
(2) граф ![math]()
является циклом в графе ![math]()
является циклом в графе
(3) граф ![math]()
является подграфом графа ![math]()
является подграфом графа
(4) граф ![math]()
является частью графа ![math]()
является частью графа Укажите верные утверждения:
(1) в тета-графе может быть гамильтонов цикл
(2) в тета-графе может быть гамильтонов путь
Примерами полных систем функции алгебры логики являются:
(1) ![math]()
(2) ![math]()
(3) ![math]()
К модельным задачам комбинаторики относятся:
(1) задача о числе функций (отображений)
(2) задача о размещении объектов по ящикам
(3) задача о числе слов в алфавите
(4) задача линейной фильтрации
Что является производящей функцией последовательности ![math]()
![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Сколько существует беспорядков для множества, состоящего из ![math]()
элемента, таких, что элемент ![math]()
стоит на ![math]()
-ом месте, а элемент ![math]()
НЕ стоит на ![math]()
-ом месте:
элемента, таких, что элемент 
стоит на -ом месте, а элемент НЕ стоит на -ом месте:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
По определению, две вершины называются связанными, если:
(1) эти вершины смежные
(2) существует путь, для которого одна из двух рассматриваемых вершин является начальной вершиной, а вторая - конечной вершиной
(3) существуют кратные ребра, соединяющие эти вершины
(4) степени этих двух вершин численно равны друг другу
Граф называется негамильтоновым, если он:
(1) не имеет гамильтонова пути
(2) не имеет гамильтонова цикла
(3) является тэта-графом
Образ ямы, из которой нельзя вылезти с помощью операции суперпозиции и замены переменных, на поле всех функций алгебры логики от n переменных иллюстрирует понятие:
(1) полной системы
(2) замкнутого класса
Упорядоченное размещение объектов по ящикам предполагает, что:
(1) каждый ящик содержит упорядоченную последовательность объектов
(2) каждый ящик содержит не упорядоченную последовательность объектов
Выражение ![math]()
равно:
равно:
(1) 0
(2) 1
(3) ![math]()
(4) ![math]()
Формула явного вида для чисел Стирлинга II рода может быть записана как:
(1) ![math]()
=![math]()
=
(2) ![math]()
=![math]()
=
(3) ![math]()
=![math]()
=
(4) ![math]()
=![math]()
=
Единственные вершины нечетной степени в простом графе:
(1) всегда связанные
(2) всегда не связанные
(3) могут быть как связанными, так и не связанными
Какой граф называют плоским:
(1) граф, представимый в виде матрицы
(2) граф, который можно на плоскости изобразить без пересечения ребер
(3) двусвязный граф
К классу функций алгебры логики, сохраняющих ноль, относятся:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите количество всевозможных отображений из множества ![math]()
в множество ![math]()
, где ![math]()
- конечное множество из ![math]()
элементов, ![math]()
- конечное множество из ![math]()
элементов:
в множество 
, где - конечное множество из элементов, - конечное множество из элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Чему равна сумма коэффициентов при нечетных степенях ![math]()
бинома ![math]()
:
бинома 
:
(1) 0
(2) 1
(3) 4
(4) 16
(5) 60
Укажите количество сюръективных отображений ![math]()
из множества ![math]()
, на множество ![math]()
:
из множества 
, на множество 
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Максимальное количество ребер в простом графе с 3 вершинами и 2 компонентами связности равно:
(1) 0
(2) 1
(3) 2
(4) 3
Вес ребра - это:
(1) количество кратных ребер между заданными вершинами
(2) вещественное число, поставленное в соответствие каждому ребру ориентированного графа
(3) сумма степеней вершин, которые это ребро соединяет
Инструментами для получения новых функций из уже имеющихся являются:
(1) замена переменной
(2) импликация
(3) суперпозиция
Укажите количество способов поставить четырем студентам оценки "удовлетворительно", "хорошо", "отлично":
(1) 12
(2) 64
(3) 81
(4) 128
Чему равна сумма квадратов чисел сочетаний ![math]()
:
:
(1) 0
(2) ![math]()
(3) ![math]()
(4) ![math]()
Система различных представителей:
(1) способ организации исполнительной власти
(2) подход к характеризации структуры конечных множеств
(3) подход, определяющий условия существования некоторых конфигураций
(4) то же самое, что система общих представителей
Укажите свойство простого графа с количеством вершин ![math]()
и количеством ребер большим ![math]()
:
и количеством ребер большим 
:
(1) полный
(2) связный
(3) имеющий петли или кратные ребра
(4) содержащий ![math]()
компонент связности
компонент связности Расстояние от одной вершины графа до другой - это:
(1) длина кратчайшего пути от начальной вершины к конечной
(2) длина некоторого пути от начальной вершины к конечной
(3) измеренное линейкой расстояние между вершинами графа
К классу функций алгебры логики, сохраняющих единицу, относятся:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите выражения, равные количеству инъективный отображений из множества ![math]()
в множество ![math]()
, где ![math]()
- конечное множество из ![math]()
элементов, ![math]()
- конечное множество из ![math]()
элементов:
в множество , где - конечное множество из элементов, - конечное множество из элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Чему равно количество размещений n различных объектов по ![math]()
различным ящикам при условии, что в каждом ящике находится ![math]()
объектов соответственно, ![math]()
:
различным ящикам при условии, что в каждом ящике находится 
объектов соответственно, 
:
(1) 0
(2) ![math]()
(3) ![math]()
(4) ![math]()
Что из перечисленного ниже есть система различных представителей для системы подмножеств ![math]()
, ![math]()
, ![math]()
, ![math]()
исходного множества ![math]()
:
, 
, 
, 
исходного множества 
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 5 вершинами:
(1) 4
(2) 5
(3) 6
(4) 7
Определите сложность решения задачи поиска кратчайших путей в графе с неотрицательными весами ребер ![math]()
- количество вершин графа:
- количество вершин графа:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) эта задача неразрешима
Количество линейных функций алгебры логики от n переменных равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) науке не известно точное количество таких функций
Укажите количество способов поставить четырем студентам оценки "удовлетворительно", "хорошо", "отлично", чтобы все студенты получили разные оценки:
(1) 0
(2) 1
(3) 3
(4) 4
Укажите комбинаторный смысл полиномиальных коэффициентов ![math]()
, где ![math]()
, в терминах слов в алфавите:
, где , в терминах слов в алфавите:
(1) количество слов длины ![math]()
в алфавите из ![math]()
символов, в которых символ ![math]()
встречается ![math]()
раз, ..., символ ![math]()
встречается ![math]()
раз
в алфавите из символов, в которых символ 
встречается 
раз, ..., символ 
встречается 
раз
(2) количество слов длины ![math]()
в алфавите из ![math]()
символов, в которых символ ![math]()
встречается ![math]()
раз, ..., символ ![math]()
встречается ![math]()
раз
в алфавите из символов, в которых символ встречается раз, ..., символ встречается раз
(3) количество монотонных слов длины ![math]()
в алфавите из ![math]()
символов, в которых символ ![math]()
встречается ![math]()
раз, ..., символ ![math]()
встречается ![math]()
раз
в алфавите из символов, в которых символ встречается раз, ..., символ встречается раз Система различных представителей для совокупности из ![math]()
множеств ![math]()
существует тогда и только тогда, когда:
множеств 
существует тогда и только тогда, когда:
(1) пересечение любых ![math]()
множеств из ![math]()
содержит не менее ![math]()
различных элементов, для всех ![math]()
множеств из 
содержит не менее различных элементов, для всех 
(2) объединение любых ![math]()
множеств из ![math]()
содержит не менее ![math]()
различных элементов, для всех ![math]()
множеств из содержит не менее различных элементов, для всех
(3) пересечение любых ![math]()
множеств из ![math]()
содержит более ![math]()
различных элементов, для всех ![math]()
множеств из содержит более различных элементов, для всех
(4) объединение любых ![math]()
множеств из ![math]()
содержит более ![math]()
различных элементов, для всех ![math]()
множеств из содержит более различных элементов, для всех Какой неориентированный граф по определению называется деревом:
(1) связный граф, имеющий циклы
(2) связный граф, не имеющий циклов
(3) граф, все имеющиеся пути в котором простые
Функцией, двойственной к ![math]()
, является:
, является:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите выражения, равные количеству взаимнооднозначных отображений из множества ![math]()
на себя, где ![math]()
- конечное множество из ![math]()
элементов:
на себя, где - конечное множество из элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Какая функция является производящей для полиномиальных коэффициентов ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Для совокупности из ![math]()
множеств ![math]()
для каждого ![math]()
последовательно выбрали ![math]()
. Тогда выбранный набор ![math]()
:
множеств для каждого 
последовательно выбрали 
. Тогда выбранный набор 
:
(1) является системой различных представителей
(2) является системой общих представителей
(3) состоит из различных элементов
(4) является единственной системой различных представителей по построению
Вершина дерева называется концевой вершиной, если:
(1) степень данной вершины равна 0
(2) степень данной вершины равна 1
(3) данной вершине инцидентно концевое ребро
Количество самодвойственных функций алгебры логики от n переменных равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите количество способов поставить трем студентам оценки "удовлетворительно", "хорошо", "отлично", чтобы все студенты получили разные оценки::
(1) 1
(2) 3
(3) 6
(4) 9
Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения ![math]()
:
:
(1) 15
(2) 75
(3) 125
(4) 243
Система общих представителей - это:
(1) система одновременных представителей
(2) любая система различных представителей
(3) система региональных представителей
(4) система полномочных представителей
Количество деревьев, которое можно построить на ![math]()
заданный вершинах, равно:
заданный вершинах, равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Для определения монотонной функции алгебры логики:
(1) требуется определить отношение полного порядка наборов
(2) требуется определить отношение частичного порядка наборов
(3) достаточно определить отношение порядка в смысле сравнения чисел
Числа Стирлинга первого рода - это:
(1) коэффициенты при разложении любого полинома степени n виде суммы степеней переменной
(2) коэффициенты при разложении полинома вида ![math]()
виде суммы степеней переменной
виде суммы степеней переменной Разбиение - это:
(1) упорядоченная последовательность непустых непересекающихся подмножеств
(2) неупорядоченная последовательность непустых непересекающихся подмножеств
(3) неупорядоченная последовательность непустых пересекающихся подмножеств
(4) упорядоченная непоследовательность непустых непересекающихся подмножеств
Для системы общих представителей ![math]()
при разбиениях множества ![math]()
![math]()
и ![math]()
справедливо, для ![math]()
:
при разбиениях множества 
и 
справедливо, для 
:
(1) ![math]()
, ![math]()
, 
(2) ![math]()
, ![math]()
, где ![math]()
- перестановка
, 
, где 
- перестановка
(3) ![math]()
, ![math]()
, 
(4) ![math]()
, ![math]()
, где ![math]()
- путь
, , где - путь Количество деревьев, которое можно построить на 4 заданных вершинах, равно:
(1) 2
(2) 4
(3) 8
(4) 16
Какие из перечисленных функций является монотонными?
(1) ![math]()
(2) ![math]()
(3) ![math]()
Чему равно число Стирлинга первого рода ![math]()
:
:
(1) 0
(2) 1
(3) 10
Числами Стирлинга II рода называют:
(1) количество любых неупорядоченных разбиений
(2) числа Белла
(3) коэффициенты многочлена ![math]()
(4) количество различных разбиений множества из ![math]()
элементов на ![math]()
классов
элементов на классов К каким классам функций алгебры логики относится функция ![math]()
:
:
(1) класс функций, сохраняющих единицу
(2) класс линейных функций
(3) класс монотонных функций
Укажите верное рекуррентное соотношение для числа разбиений:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите название известной головоломки: "Можно ли произвольную географическую карту раскрасить в 4 цвета так, чтобы ни одни 2 государства, граница которых имеется и отлична от точки, не были окрашены в один и тот же цвет".
(1) выбор цветовой модели
(2) задача о карте Европы
(3) проблема четырех красок
(4) задача коммивояжера
Какой способ наиболее эффективен при подсчете количества деревьев:
(1) метод полного перебора
(2) построение изоморфизма между множеством деревьев и некоторым другим множеством
(3) рассуждение по индукции
Некоторая функция алгебры логики зависит от 64 аргументов. Количество элементов в множестве значений данной функции алгебры логики равно:
(1) 2
(2) 64
(3) 642
(4) 264
Функция алгебры логики, зависящая от ![math]()
переменных, представима в виде полинома Жегалкина:
переменных, представима в виде полинома Жегалкина:
(1) единственным образом
(2) ![math]()
способами
способами
(3) ![math]()
способами
способами
(4) ![math]()
способами
способами Укажите, где способы упорядоченного размещения семи различных цифр ![math]()
по 3 различным ящикам различны:
по 3 различным ящикам различны:
(1) ![math]()
и ![math]()
и 
(2) ![math]()
и ![math]()
и
(3) ![math]()
и ![math]()
и 
(4) ![math]()
и ![math]()
и 
Сколько существует разбиений из 4 элементов на 2 класса:
(1) 4
(2) 7
(3) 8
(4) 9
Для графов с каким количеством вершин удобно их графическое представление в виде точек и соединяющих их линий:
(1) 5
(2) 50
(3) 500
Множество деревьев на ![math]()
вершинах с ![math]()
концевыми вершинами имеет взаимнооднозначное соответствие с этим множеством:
вершинах с концевыми вершинами имеет взаимнооднозначное соответствие с этим множеством:
(1) множество слов длины ![math]()
в алфавите из ![math]()
символов
в алфавите из символов
(2) множество слов длины ![math]()
в алфавите из ![math]()
символов, причем каждый символ в это слово входит
в алфавите из символов, причем каждый символ в это слово входит
(3) множество слов длины ![math]()
в алфавите из ![math]()
символов, причем каждый символ в это слово входит
в алфавите из символов, причем каждый символ в это слово входит
(4) множество слов длины ![math]()
в алфавите из ![math]()
символов
в алфавите из символов Функция алгебры логики задана на двух аргументах. Количество элементов в множестве значений данной функции алгебры логики равно:
(1) 1
(2) 2
(3) 3
(4) 4
Сколько коэффициентов в многочлене Жегалкина от трех переменных:
(1) 1
(2) 2
(3) 3
(4) 4
(5) 5
(6) 6
(7) 7
(8) 8
(9) 9
(10) 10
Сколько существует различных способов расставить 2 разные книги по 10 книжным полкам:
(1) 20
(2) 100
(3) 110
(4) 120
Что соответствует понятию сюръективного отображения в терминах слов длины ![math]()
в алфавите из ![math]()
символов:
в алфавите из символов:
(1) всевозможные слова длины ![math]()
, в которых присутствует каждый символ в алфавите
, в которых присутствует каждый символ в алфавите
(2) всевозможные монотонные слова длины ![math]()
, в которых присутствует каждый символ в алфавите
, в которых присутствует каждый символ в алфавите
(3) всевозможные слова длины ![math]()
, в которых каждый символ алфавита присутствует не более ![math]()
раз
, в которых каждый символ алфавита присутствует не более раз
(4) всевозможные слова длины ![math]()
Как формально определяется множество ребер неориентированного графа:
(1) ![math]()
, где ![math]()
- упорядоченная пара вершин
, где 
- упорядоченная пара вершин
(2) ![math]()
, где ![math]()
- неупорядоченная пара вершин
, где 
- неупорядоченная пара вершин
(3) набор ненаправленных отрезков
Сколько существует деревьев на 4 вершинах с 2 концевыми вершинами:
(1) 4
(2) 8
(3) 12
(4) 16
Какие из функций алгебры логики принимают значение ![math]()
при значениях аргументов ![math]()
при значениях аргументов 
(1) дизъюнкция
(2) конъюнкция
(3) сумма
(4) эквивалентность
(5) импликация ![math]()
(6) штрих
(7) стрелка
Укажите системы функций, не являющихся полными:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Сколько существует способов закупить 4 компьютера из имеющихся 3 типов:
(1) 15
(2) 21
(3) 24
(4) 120
Сколько сюръективных отображений соответствует каждому разбиению множества ![math]()
из ![math]()
элементов на ![math]()
классов:
из элементов на классов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите, где понятие "инцидентность" использовано верно:
(1) ребро ![math]()
инцидентно вершинам ![math]()
и ![math]()
инцидентно вершинам и 
(2) два ребра инцидентны
(3) две вершины индидентны
В формулировке задачи о кенигсбергских мостах в терминах теории графов:
(1) части города обозначают вершинами, мосты - ребрами графа
(2) части города изображают ребрами графа, острова - вершинами графа
(3) мосты изображают вершинами графа, части города - ребрами
Какие из функций алгебры логики принимают значение ![math]()
при значениях аргументов ![math]()
при значениях аргументов 
(1) дизъюнкция
(2) конъюнкция
(3) сумма
(4) эквивалентность
(5) импликация ![math]()
(6) штрих
(7) стрелка
Укажите полную систему функций:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Сколько существует монотонных слов длины 7 в алфавите из 2 символов:
(1) 4
(2) 5
(3) 6
(4) 7
(5) 8
(6) 14
Укажите верный способ выразить степень переменной через нижние степени переменной:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите выражение, описывающие количество ребер в полном ориентированном графе с количеством вершин ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
В каких задачах встречаются эйлеровы пути
(1) головоломки: рисование фигур не отрывая карандаша от бумаги
(2) проектирование последовательности технологических операций для управления качеством изделия
(3) задачи проектирования печатных плат
Определите взаимосвязь между формулой и функцией алгебры логики:
(1) формула реализует функцию алгебры логики
(2) для каждой функции алгебры логики существует единственная формула, которая реализует эту функцию алгебры логики
(3) одну и ту же функцию алгебры логики могут реализовывать несколько формул разного вида
Многочлен Жегалкина для функции ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Слово длины ![math]()
- это:
- это:
(1) любая последовательность длины ![math]()
элементарных подмножеств (символов) алфавита
элементарных подмножеств (символов) алфавита
(2) последовательность длины ![math]()
символов алфавита, в которой каждый следующий символ не меньше предыдущего в терминах порядка символов в алфавите
символов алфавита, в которой каждый следующий символ не меньше предыдущего в терминах порядка символов в алфавите Довод, согласно которому из равенства нулю полинома конечной степени в бесконечном множестве целых значений переменной следует равенство полинома нулю для всех вещественных чисел, называют в комбинаторике:
(1) полиномиальная теорема
(2) полиномиальная аргументация
(3) полиномиальная аппроксимация
(4) полиномиальная регрессия
Вершине неориентированного графа инцидентны три ребра, петель и кратных ребер в графе нет. Определите степень вершины:
(1) 0
(2) 1
(3) 2
(4) 3
Началом и концом эйлерова пути могут быть вершины:
(1) только четной степени
(2) только нечетной степени
(3) вершины как четной, так и нечетной степени
Какие из формул равносильны формуле ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Многочлен Жегалкина для функции ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Количество монотонных слов длины ![math]()
в алфавите из ![math]()
символов:
в алфавите из символов:
(1) равно количеству упорядоченных размещений ![math]()
различных объектов по ![math]()
различным ящикам
различных объектов по различным ящикам
(2) больше в ![math]()
раз количества упорядоченных размещений ![math]()
различных объектов по ![math]()
различным ящикам
раз количества упорядоченных размещений различных объектов по различным ящикам
(3) меньше в ![math]()
раз количества упорядоченных размещений ![math]()
различных объектов по ![math]()
различным ящикам
раз количества упорядоченных размещений различных объектов по различным ящикам
(4) никак не связано соотношением с количеством упорядоченных размещений ![math]()
различных объектов по ![math]()
различным ящикам
различных объектов по различным ящикам Рекуррентное соотношение для чисел Белла имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:
(1) (4,3,3,3)
(2) (4,4,3,3)
(3) (4,3,3,3,3)
(4) (1,2,3,4,5)
Конечный неориентрованный граф имеет эйлеров цикл тогда и тольо тогда, когда:
(1) граф связен
(2) все вершины имеют четную степень
(3) граф связен и все вершины имеют четную степень
В каких случаях имеет место указанная равносильность формул:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите необходимое свойство системы функций, из которых можно получить набор функций ![math]()
:
:
(1) наличие функции, сохраняющей ноль
(2) отсутствие функции, сохраняющей ноль
(3) наличие функции, не сохраняющей ноль
Сколько существует способов инвестировать 4 миллиона рублей в какие-то из 3 проектов так, чтобы проекты получали целое число миллионов и все деньги были инвестированы:
(1) 12
(2) 15
(3) 24
(4) 42
(5) 63
Укажите выражения, равные количеству размещений ![math]()
одинаковых объектов по ![math]()
различным ящикам:
одинаковых объектов по различным ящикам:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:
(1) (1,2,3,4,5,6)
(2) (4,4,3,2)
(3) (4,3,4,3,4)
(4) (1,1,2,2,3)
Гамильтонов путь на простом неориентрованном графе - это:
(1) простой путь, проходящий через каждое ребро и каждую вершину графа
(2) простой путь, проходящий через каждое ребро графа
(3) простой путь, проходящий через каждую вершину графа
В каких случаях имеет место указанная равносильность формул:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите необходимое свойство системы функций, из которых можно получить набор функций ![math]()
:
:
(1) наличие монотонной функции
(2) отсутствие монотонной функции
(3) наличие немонотонной функции
(4) отсутствие немонотонной функции
Сколько существует способов представить целое число 3 в виде суммы целых неотрицательных слагаемых:
(1) 9
(2) 10
(3) 12
(4) 15
(5) 27
Основная польза метода включений-исключений состоит в следущем:
(1) метод позволяет подсчитывать количество интересующих нас объектов, обладающих теми или иными свойствами, в достаточно сложных конфигурациях
(2) метод позволяет вычислить значение числа ![math]()
(3) метод позволяет вычислить количество объектов в объединении трех множеств
(4) метод позволяет вычислить числа Стирлинга I, II и III рода
Укажите способы машинного представления графа:
(1) графический способ
(2) матрица смежности
(3) матрица инциденций
(4) списки инциденций
(5) списки смежности
Полный простой путь длины ![math]()
имеет тип цикла, если выполняется условие:
имеет тип цикла, если выполняется условие:
(1) сумма степеней начальной и конечной вершин этого пути менее длины этого пути
(2) сумма степеней начальной и конечной вершин этого пути не менее увеличенной на единицу длины пути
(3) сумма степеней начальной и конечной вершин этого пути равна длине пути
Что является разложением функции алгебры логики ![math]()
в дизъюнктивную форму по переменной ![math]()
в дизъюнктивную форму по переменной
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
С помощью каких операций можно получить отрицание из любой немонотонной функции алгебры логики:
(1) только замена переменных
(2) замена переменных и суперпозиция с функциями ![math]()
(3) замена переменных и суперпозиция с функциями ![math]()
(4) только суперпозиция с функциями ![math]()
Укажите числа сочетаний, равные нулю:
(1) ![math]()
, ![math]()
, 
(2) ![math]()
, ![math]()
,
(3) ![math]()
(4) ![math]()
Запишите формулу включений-исключений для трех свойств:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Способ представления графа в виде матрицы, в которой столбцы и строки соответствуют вершинам графа, называется:
(1) матрица смежности
(2) списки инциденций
(3) матрица инциденций
Продолжите утверждение: "В связном графе либо имеется гамильтонов цикл, либо:
(1) длина его максимального пути не меньше суммы степеней начальной и конечной вершин
(2) длина его максимального пути меньше суммы степеней начальной и конечной вершин
(3) длина его максимального пути строго больше суммы степеней начальной и конечной вершин
Что является разложением функции алгебры логики ![math]()
в дизъюнктивную форму по переменной ![math]()
в дизъюнктивную форму по переменной
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Для того, чтобы система функций ![math]()
была полна, необходимо и достаточно, чтобы:
была полна, необходимо и достаточно, чтобы:
(1) для хотя бы одного класса из ![math]()
среди функций системы ![math]()
нашлась функция, этому классу принадлежащая
среди функций системы нашлась функция, этому классу принадлежащая
(2) для любого класса из ![math]()
среди функций системы ![math]()
нашлась функция, этому классу принадлежащая
среди функций системы нашлась функция, этому классу принадлежащая
(3) для любого класса из ![math]()
среди функций системы ![math]()
нашлась функция, этому классу не принадлежащая
среди функций системы нашлась функция, этому классу не принадлежащая
(4) для хотя бы одного класса из ![math]()
среди функций системы ![math]()
нашлась функция, этому классу не принадлежащая
среди функций системы нашлась функция, этому классу не принадлежащая Чему равно ![math]()
:
:
(1) 0
(2) 1
(3) 2
(4) 4
(5) 6
(6) 8
Как в комбинаторике называют задачу, шутливая формулировка которой такова: "В лондонском клубе швейцар выдает шляпы наобум. Какова вероятность того, что ни один посетитель не получит свою шляпу?"
(1) задача о числе шляп
(2) задача о числе драк
(3) задача о числе беспорядков
(4) задача о лондонских мостах
Путь в графе - это:
(1) любая последовательность вершин графа
(2) такая последовательность вершин графа, в которой любые две последовательно перечисленные вершины соединены ребром
(3) последовательность всех вершин графа
Укажите достаточное условие существования гамильтонова цикла в графе с ![math]()
вершинами:
вершинами:
(1) для любой пары вершин сумма степеней этих вершин не более чем длина полного максимального пути
(2) для любой пары вершин сумма степеней этих вершин не менее чем ![math]()
(3) для любой пары вершин сумма степеней этих вершин более чем ![math]()
Совершенная дизъюнктивная нормальная форма функции алгебры логики:
(1) позволяет представить любую заданную таблично функцию алгебры логики в виде формулы
(2) определена для константы ![math]()
(3) наиболее удобна для представления функции алгебры логики, в табличном представлении которой много нулей и мало единиц
(4) позволяет задать любую функцию алгебры логики в виде формулы, содержащей операции только следующих видов: конъюнкцию, дизъюнкцию, отрицание
Объект ![math]()
может быть выбран ![math]()
различными способами, объект ![math]()
может быть выбран ![math]()
различными способами, одновременный выбор объектов ![math]()
и ![math]()
невозможен. Тогда:
может быть выбран различными способами, объект может быть выбран различными способами, одновременный выбор объектов и невозможен. Тогда:
(1) выбор объекта ![math]()
может быть осуществлен ![math]()
различными способами
может быть осуществлен 
различными способами
(2) выбор объекта ![math]()
может быть осуществлен ![math]()
различными способами
может быть осуществлен различными способами
(3) выбор объекта ![math]()
может быть осуществлен ![math]()
различными способами
может быть осуществлен различными способами
(4) выбор объекта ![math]()
может быть осуществлен ![math]()
различными способами
может быть осуществлен 
различными способами Определите производящую функцию для последовательности ![math]()
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Приближенное значение доли беспорядков ко всем перестановкам конечного множества ![math]()
, состоящего из ![math]()
элементов, равно:
, состоящего из элементов, равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) некоторое выражение, зависящее от ![math]()
- количества элементов множества ![math]()
- количества элементов множества Какова минимальная длина цикла в простом графе:
(1) 1
(2) 2
(3) 3
Степенной последовательностью графа называют:
(1) записанные в порядке возрастания степени вершин графа
(2) записанные в порядке убывания степени вершин графа
(3) перечисление в любом порядке степеней вершин графа
(4) разложение графа в ряд Тейлора
Cовершенная конъюнктивная нормальная форма для импликации ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
К основным задачам комбинаторики относятся:
(1) вопрос о существовании конфигурации заданных объектов
(2) подсчет числа конфигураций
(3) приближенный подсчет числа конфигураций
(4) перечисление конфигураций
В формуле свертки ![math]()
значение коэффициента ![math]()
равно:
значение коэффициента 
равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите верное рекуррентное соотношение для числа беспорядков:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Как соотносятся между собой графы ![math]()
и ![math]()
, если множество вершин графа ![math]()
является подмножеством вершин графа ![math]()
и множество ребер графа ![math]()
состоит из всех ребер графа ![math]()
, соединяющих вершины графа ![math]()
:
и , если множество вершин графа является подмножеством вершин графа и множество ребер графа состоит из всех ребер графа , соединяющих вершины графа :
(1) граф ![math]()
является циклом в графе ![math]()
является циклом в графе
(2) граф ![math]()
является изоморфным графу ![math]()
является изоморфным графу
(3) граф ![math]()
является подграфом графа ![math]()
является подграфом графа
(4) граф ![math]()
является частью графа ![math]()
является частью графа Для какого графа наименьшее количество вершин, удаление которых приводит к несвязному или одновершинному графу, равно двум:
(1) односвязный граф
(2) двусвязный граф
(3) трехсвязный граф
Если операциями суперпозиции и замены переменных из функций данной системы функций алгебры логики можно получить только функции, ей принадлежащие, и никаких других функций, то такая система функций:
(1) полная система
(2) замкнутый класс
Задача о числе функций (отображений) и задача о размещении объектов по ящикам
(1) находятся во взаимнооднозначном отношении
(2) описывают принципиально различные конфигурации объектов
Бином Ньютона - это бином вида:
(1) ![math]()
, где ![math]()
- любое натуральное число
, где - любое натуральное число
(2) ![math]()
, где ![math]()
- любое целое число
, где 
- любое целое число
(3) ![math]()
, где ![math]()
- любое действительное число
, где 
- любое действительное число
(4) ![math]()
, где ![math]()
- любое комплексное число
, где 
- любое комплексное число Укажите точное значение числа беспорядков на множестве из ![math]()
элементов:
элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
По определению, граф называется связным, если:
(1) все вершины графа попарно связаны
(2) некоторые вершины графа попарно связаны
(3) все вершины графа связаны только простыми путями
(4) через каждую вершину графа проходит более двух простоых путей
Двухсвязный негамильтонов граф:
(1) является тэта-графом
(2) содержит тэта-подграф
(3) не имеет гамильтонова цикла
Сколько существует функций алгебры логики от ![math]()
переменных:
переменных:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Для двух чисел Стирлинга 1 рода, не равных нулю, ![math]()
и ![math]()
:
и 
:
(1) их знаки будут совпадать
(2) их знаки будут противоположными
Выражение ![math]()
равно:
равно:
(1) 0
(2) 1
(3) ![math]()
(4) ![math]()
Укажите взимосвязь чисел Стирлинга II рода ![math]()
и количества сюръективных отображений ![math]()
:
и количества сюръективных отображений :
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите последовательность степеней вершин существующего графа, которая требует связности первой и второй вершины:
(1) (1,1,1,1)
(2) (1,1,2,2)
(3) (1,2,3,4,5)
(4) (4,4,4,4)
Любой четырехсвязный планарный граф:
(1) имеет гамильтонов цикл
(2) имеет тэта-подграф
(3) не имеет гамильтонова цикла
К классу функций алгебры логики, сохраняющих ноль, относятся:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите количество всевозможных размещений ![math]()
различных объектов по ![math]()
различным ящикам:
различных объектов по различным ящикам:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Чему равна сумма коэффициентов при четных степенях ![math]()
бинома ![math]()
:
бинома 
:
(1) 0
(2) 1
(3) 16
(4) 32
(5) 60
Количество разбиений ![math]()
объектов на ![math]()
непустых класса равно ![math]()
. Вычислите количество сюръективных отображений из множества, содержащего ![math]()
элементов, на множество, содержащее ![math]()
элемента:
объектов на 
непустых класса равно 
. Вычислите количество сюръективных отображений из множества, содержащего элементов, на множество, содержащее элемента:
(1) 5
(2) 25
(3) 75
(4) 150
Максимальное количество ребер в простом графе с 4 вершинами и 2 компонентами связности равно:
(1) 1
(2) 2
(3) 3
(4) 4
Длина пути в ориентированном графе с весами ребер - это:
(1) количество ребер входящих в путь
(2) сумма весов всех входящих в путь ребер
(3) произведение весов всех входящих в путь ребер
Какие равенства представляют собой правила поглощения:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите количество способов разместить 4 шарика по 5 лункам:
(1) 20
(2) 512
(3) 625
(4) 1024
Чему равна сумма квадратов коэффициентов при степенях бинома ![math]()
:
:
(1) 0
(2) 10
(3) 252
(4) 525
При построении системы различных представителей:
(1) для совокупности некоторых множеств каждое из этих множеств заменяется любым одним из его элементов, и этот элемент называется представителем
(2) для совокупности подмножеств некоторого множества каждое из этих подмножеств заменяется любым одним из его элементов, и этот элемент называется представителем
(3) для совокупности подмножеств некоторого множества каждое из этих подмножеств заменяется одним из его элементов, и этот элемент называется представителем, при этом все выбранные представители различны
Укажите нижнюю границу количества ребер простого графа с ![math]()
вершинами, превышение которой означает связность графа:
вершинами, превышение которой означает связность графа:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
В каких задачах применяются ориентированные графы с весами ребер:
(1) транспортные задачи о минимизации стоимости перевозок
(2) задачи проектирования печатных плат
Количество функций алгебры логики от n переменных, сохранящих единицу, равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) науке не известно точное количество таких функций
Укажите выражения, равные количеству всевозможных размещений ![math]()
различных объектов по ![math]()
различным ящикам при условии, что в каждом ящике не более 1 объекта:
различных объектов по различным ящикам при условии, что в каждом ящике не более 1 объекта:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Выпишите числа сочетаний для ![math]()
в факториальной форме::
в факториальной форме::
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Что из перечисленного ниже есть система различных представителей для системы подмножеств ![math]()
, ![math]()
, ![math]()
, ![math]()
исходного множества ![math]()
, 
, 
, 
исходного множества 
(1) ![math]()
(2) ![math]()
(3) не существует системы различных представителей для данной системы подмножеств
Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 3 вершинами:
(1) 0
(2) 1
(3) 2
(4) 3
Определите сложность решения задачи поиска кратчайших путей в графе без циклов, ![math]()
- количество вершин графа:
- количество вершин графа:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) эта задача неразрешима
С помощью каких операций над функциями можно получить из самодвойственной функции константу:
(1) с помощью суперпозиции с функциями ![math]()
и ![math]()
и
(2) с помощью суперпозиции с функциями ![math]()
и ![math]()
и
(3) с помощью суперпозиции с функциями ![math]()
и ![math]()
и Укажите количество способов разместить 4 шарика по 5 лункам при условии, что в каждой лунке не более 1 шарика:
(1) 12
(2) 20
(3) 120
(4) 128
Чему равно количество размещений 6 различных объектов по 3 различным ящикам при условии, что в первом ящике находится 1 объект, во втором - 2 объекта, в третьем - 3 объекта:
(1) 6
(2) 60
(3) 120
(4) 720
В каких случаях нельзя построить систему различных представителей для ![math]()
множеств:
множеств:
(1) среди рассматриваемых ![math]()
множеств существуют пустые множества
множеств существуют пустые множества
(2) среди рассматриваемых ![math]()
множеств нет пустых множеств, при этом среди них найдутся два множества, объединение которых состоит из одного элемента
множеств нет пустых множеств, при этом среди них найдутся два множества, объединение которых состоит из одного элемента
(3) объединение всех ![math]()
множеств состоит из ![math]()
элемента
множеств состоит из элемента Укажите верные утверждения:
(1) в дереве любые две вершины связаны простым путем
(2) дерево не имеет петель и кратных ребер
(3) дерево не имеет кратных ребер, но может иметь петли
Какое значение принимает самодвойственная функция на наборе ![math]()
, если на наборе ![math]()
эта функция принимает значение ![math]()
:
, если на наборе 
эта функция принимает значение :
(1) 1
(2) 0
(3) для ответа недостаточно информации
Укажите выражения, равные количеству всевозможных размещений ![math]()
различных объектов по ![math]()
различным ящикам при условии, что в каждом ящике не более 1 объекта:
различных объектов по различным ящикам при условии, что в каждом ящике не более 1 объекта:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Замена представителей - это:
(1) этап построения системы различных представителей
(2) замена множества его представителем
(3) увольнение представителей
(4) ситуация, означающая, что не существует системы различных представителей
Сколько ребер содержит дерево с ![math]()
вершинами?
вершинами?
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Какие из перечисленных функций являются самодвойственными:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите количество способов разместить 4 шарика по 4 лункам при условии, что в каждой лунке не более 1 шарика:
(1) 4
(2) 16
(3) 24
(4) 64
Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения ![math]()
:
:
(1) 3
(2) 9
(3) 27
(4) 81
Укажите условие существования системы общих представителей для разбиений ![math]()
и ![math]()
:
и 
:
(1) множества ![math]()
попарно не пересекаются и множества ![math]()
попарно не пересекаются
попарно не пересекаются и множества 
попарно не пересекаются
(2) каждое из множеств ![math]()
и ![math]()
непусто
и непусто
(3) любые ![math]()
множеств ![math]()
содержатся не менее, чем в ![math]()
множествах ![math]()
:
множеств содержатся не менее, чем в множествах : Количество деревьев, которое можно построить на 2 заданный вершинах, равно:
(1) 0
(2) 1
(3) 2
(4) 3
Количество монотонных функций алгебры логики от
n переменных:
(1) равно ![math]()
(2) больше числа ![math]()
(3) равно ![math]()
Чему равно число Стирлинга первого рода ![math]()
при ![math]()
:
при :
(1) 0
(2) 1
Разбиение в терминах размещения объектов по ящикам - это:
(1) размещение ![math]()
одинаковых объектов по ![math]()
различным ящикам при условии, что каждый ящик не пуст
одинаковых объектов по различным ящикам при условии, что каждый ящик не пуст
(2) размещение ![math]()
различных объектов по ![math]()
одинаковым ящикам при условии, что некоторые ящики могут быть пустыми
различных объектов по одинаковым ящикам при условии, что некоторые ящики могут быть пустыми
(3) размещение ![math]()
различных объектов по ![math]()
одинаковым ящикам при условии, что каждый ящик не пуст
различных объектов по одинаковым ящикам при условии, что каждый ящик не пуст
(4) размещение ![math]()
одинаковых объектов по ![math]()
одинаковым ящикам
одинаковых объектов по одинаковым ящикам Количество деревьев, которое можно построить на 10 заданный вершинах, равно:
(1) 100
(2) 10000
(3) 1000000
(4) 100000000
К каким классам функций алгебры логики относится функция ![math]()
:
:
(1) класс монотонных функций
(2) класс самодвойственных функций
(3) класс линейных функций
Чему равно число Стирлинга первого рода ![math]()
:
:
(1) 0
(2) 1
Сколько существует различных разбиений множества из 4 элементов на 2 класса:
(1) 6
(2) 7
(3) 8
(4) 12
К каким классам функций алгебры логики относится функция ![math]()
:
:
(1) класс функций, сохраняющих ноль
(2) класс линейных функций
(3) класс монотонных функций
Сколько существует разбиений ![math]()
объектов на ![math]()
классов, таких что объект с номером ![math]()
- единственный в своем классе:
объектов на классов, таких что объект с номером - единственный в своем классе:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите приложения теории графов:
(1) задачи изучения электричеких цепей
(2) задача коммивояжера
(3) минимизация булевых функций
(4) задачи о существовании эфективных алгоритмов
Количество слов длины ![math]()
в алфавите из ![math]()
символов равно:
в алфавите из символов равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Функция алгебры логики - это:
(1) функция
(2) алгебра
(3) логика
(4) ничто из перечисленного
Укажите, какие функции алгебры логики могут быть представлены в виде полинома Жегалкина:
(1) все функции алгебры логики
(2) все несамодвойственные функции алгебры логики
(3) все функции алгебры логики, за исключением тождественного нуля и тождественной единицы
(4) все функции алгебры логики, существенно зависящие не менее, чем от трех переменных
Число различных упорядоченных размещений ![math]()
различных объектов по ![math]()
различным ящикам равно:
различных объектов по различным ящикам равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Сколько существует разбиений из 5 элементов на 2 класса:
(1) 10
(2) 14
(3) 25
(4) 15
Какая задача в терминах теории графов решалась в связи с проблемой неплатежей после начала перестройки, при наличии списка должников:
(1) задача поиска простого пути
(2) задача поиска циклов с целью устранения их
(3) задача о четырех красках
Какие из методов доказательства применяются при подсчете количества деревьев на ![math]()
вершинах с ![math]()
концевыми вершинами:
вершинах с концевыми вершинами:
(1) метод включений-исключений
(2) метод разбиений
(3) построение изоморфизма между множеством деревьев и некоторым другим множеством
Некоторая функция алгебры логики зависит от одного аргумента. Областью определения данной функции алгебры логики является множество с количеством элементов:
(1) 1
(2) 2
(3) 3
Укажите функцию, представление которой в виде полинома Жегалкина содержит конъюнкцию с двумя или более переменными:
(1) немонотонная
(2) нелинейная
(3) не самодвойственная
(4) не сохраняющая единицу
Сколько существует различных способов расставить 10 разных книг по 2 книжным полкам:
(1) 120
(2) 720
(3) 5040
(4) 39916800
Что соответствует понятию сюръективного отображения в терминах размещения объектов по ящикам:
(1) размещения одинаковых объектов по различным ящикам при условии, что каждый ящик не пуст
(2) размещения различных объектов по различным ящикам
(3) размещения различных объектов по различным ящикам при условии, что каждый ящик не пуст
(4) размещения одинаковых объектов по одинаковым ящикам при условии, что каждый ящик не пуст
Как формально определяется множество ребер ориентированного графа:
(1) ![math]()
, где ![math]()
- упорядоченная пара вершин
, где - упорядоченная пара вершин
(2) ![math]()
, где ![math]()
- неупорядоченная пара вершин
, где - неупорядоченная пара вершин
(3) набор отрезков, некоторые из которых являются направленными
Сколько существует деревьев на 6 вершинах с 4 концевыми вершинами:
(1) 24
(2) 48
(3) 96
(4) 840
Какие из функций алгебры логики принимают значение ![math]()
при значениях аргументов ![math]()
при значениях аргументов 
(1) дизъюнкция
(2) конъюнкция
(3) сумма
(4) эквивалентность
(5) импликация ![math]()
(6) штрих
(7) стрелка
Укажите полные системы функций:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Сколько существует способов закупить 3 компьютера из имеющихся 3 типов:
(1) 1
(2) 3
(3) 9
(4) 10
Сколько существует сюръективных отображений из множества, состоящего из 4 элементов на множество из 2 элементов:
(1) 8
(2) 16
(3) 48
(4) 168
Укажите, где понятие "смежность" использовано верно:
(1) ребро ![math]()
смежно с вершинами ![math]()
и ![math]()
смежно с вершинами и
(2) два ребра смежные
(3) две вершины смежные
Формулировка задачи о кенигсбергских мостах в терминах теории графов выглядит так:
(1) построить цикл так, чтобы он проходил через каждое ребро в точности один раз
(2) построить путь так, чтобы он проходил через каждое ребро в точности один раз
(3) построить цикл так, чтобы он проходил через каждую вершину в точности один раз
Как связаны между собой элементарные функции алгебры логики:
(1) штрих Шеффера представим как отрицание стрелки Пирса
(2) штрих Шеффера представим как отрицание конънкции
(3) штрих Шеффера представим как отрицание дизъюнкции
(4) стрелка Пирса представима как отрицание конънкции
(5) стрелка Пирса представима как отрицание дизъюнкции
Укажите полную систему функций:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Сколько существует монотонных слов длины 4 в алфавите из 3 символов:
(1) 4
(2) 12
(3) 15
(4) 16
(5) 24
(6) 81
Укажите верные способы выразить нижнюю степень переменной через степени переменной:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите соотношение между количество ребер в полном ориентированном графе и количеством ребер в полном неориентированном графе, оба графа с количеством вершин ![math]()
:
:
(1) количество ребер в этих графах одинаково
(2) количество ребер полного ориентированного графа в два раза больше, чем количество ребер полного неориентированного графа
(3) количество ребер полного ориентированного графа в два раза меньше, чем количество ребер полного неориентированного графа
(4) в силу разнообразия полных графов невозможно вывести точное соотношение
Конечный граф - это граф, у которого:
(1) конечное число вершин
(2) конечное число ребер
(3) конечное число вершин и конечное число ребер
Две формулы называются равносильными, если они:
(1) реализуют одну и ту же функцию алгебры логики
(2) реализуют двойственные функции
(3) реализуют самодвойственные функции
Многочлен Жегалкина для функции ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Монотонное слово длины ![math]()
- это:
- это:
(1) любая последовательность длины ![math]()
элементарных подмножеств (символов) алфавита
элементарных подмножеств (символов) алфавита
(2) последовательность длины ![math]()
символов алфавита, в которой каждый следующий символ не меньше предыдущего в терминах порядка символов в алфавите
символов алфавита, в которой каждый следующий символ не меньше предыдущего в терминах порядка символов в алфавите Укажите верное рекуррентное соотношение для чисел Стирлинга II рода:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите вершины графа, степень которых равна нулю:
(1) изолированная вершина
(2) вершина, которой инцидентно два ребра и не имеющая петель
(3) любая вершина полного графа
(4) любая вершина простого графа
Эйлеров путь может существовать в графе, количество вершин нечетной степени в котором:
(1) 0
(2) 2
(3) 4
В каких случаях формулы ![math]()
и ![math]()
равносильны:
и равносильны:
(1) ![math]()
, ![math]()
, 
(2) ![math]()
, ![math]()
, 
(3) ![math]()
, ![math]()
, 
Многочлен Жегалкина для функции ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Для целых положительных чисел ![math]()
и ![math]()
выражение ![math]()
делится нацело на ![math]()
:
и выражение делится нацело на :
(1) никогда
(2) иногда
(3) всегда
Числа Белла выражаются через числа Стирлинга так:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Для доказательства изоморфности двух графов:
(1) достаточно определить взаимнооднозначное соответствие между вершинами этих графов
(2) необходимо установить взаимноознозначное соответствие между вершинами этих графов
(3) достаточно установить взаимноознозначное соответствие между вершинами этих графов, сохраняющее свойство "быть связанным ребром"
Оцените сложность алгоритма построения эйлерова цикла в графе с количеством вершин ![math]()
и количеством ребер ![math]()
:
и количеством ребер :
(1) O(m)
(2) O(n2)
(3) o(m)
(4) o(n)
В каких случаях имеет место указанная равносильность формул:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите необходимое свойство системы функций, из которых можно получить набор функций ![math]()
:
:
(1) отсутствие функции, сохраняющей единицу
(2) наличие функции, не сохраняющей единицу
(3) отсутствие функции, не сохраняющей единицу
(4) наличие функции, сохраняющей единицу
Сколько существует способов инвестировать 3 миллиона рублей в какие-то из 3 проектов так, чтобы проекты получали целое число миллионов и все деньги были инвестированы:
(1) 9
(2) 10
(3) 12
(4) 15
(5) 27
Выразите задачу размещения ![math]()
одинаковых объектов по ![math]()
различным ящикам в терминах задачи Муавра:
одинаковых объектов по различным ящикам в терминах задачи Муавра:
(1) представить целое положительное число ![math]()
в виде суммы ![math]()
неотрицательных слагаемых
в виде суммы неотрицательных слагаемых
(2) представить целое положительное число ![math]()
в виде суммы ![math]()
неотрицательных слагаемых
в виде суммы 
неотрицательных слагаемых
(3) представить целое положительное число ![math]()
в виде суммы ![math]()
слагаемых
в виде суммы слагаемых
(4) представить целое положительное число ![math]()
в виде суммы ![math]()
неотрицательных слагаемых
в виде суммы неотрицательных слагаемых Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:
(1) (1,3,3,3)
(2) (2,3,3,3)
(3) (2,3,2,3,2)
(4) (1,2,3,4)
Путь имеет тип цикла, если:
(1) этот путь является эйлеровым циклом
(2) этот путь является гамильтоновым циклом
(3) порожденный множеством вершин пути подграф имеет гамильтонов цикл
В каких случаях имеет место указанная равносильность формул:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите необходимые свойства системы функций, из которых можно получить набор функций ![math]()
:
:
(1) наличие линейной функции
(2) отсутствие линейной функции
(3) наличие нелинейной функции
(4) отсутствие нелинейной функции
Сколько существует способов представить целое число 4 в виде суммы целых неотрицательных слагаемых:
(1) 8
(2) 16
(3) 20
(4) 35
(5) 210
Формула включений-исключений имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
При котором из способов представления графа матрица для его представления всегда квадратная:
(1) матрица смежности
(2) матрица инциденций
(3) списки инциденций
Полным максимальным путем называют:
(1) полный путь, проходящий через все вершины графа
(2) полный путь, который имеет максимально возможную длину
(3) полный путь, проходящий через все ребра графа
Что является разложением функции алгебры логики ![math]()
в дизъюнктивную форму по переменной ![math]()
в дизъюнктивную форму по переменной
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
С помощью каких операций можно получить константу из любой несамодвойственной функции алгебры логики:
(1) только замена переменных
(2) замена переменных и суперпозиция с функциями ![math]()
(3) только суперпозиция с функциями ![math]()
(4) замена переменных и суперпозиция с функциями ![math]()
Укажите обозначения для числа сочетаний из ![math]()
элементов по ![math]()
элементов:
элементов по элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Решение задачи о подсчете количества элементов в объединении трех множеств ![math]()
с применением метода включений-исключений имеет вид:
с применением метода включений-исключений имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите достоинства списков инциденций как способа машинного представления графа:
(1) свобода модификации этого списка
(2) абсолютная экономия места
(3) список используется в программном смысле этого слова
(4) необходимость регулярно чистить память машины
Каким свойством обладает длина максимальных путей в графе без гамильтоновых циклов:
(1) длина максимальных путей больше суммы двух наименьших степеней вершин графа
(2) длина максимальных путей не меньше суммы двух наименьших степеней вершин графа
(3) длина максимального пути не меньше суммы степеней начальной и конечной вершин графа
Какие из формул равносильны формуле ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Критерий полноты - это:
(1) необходимое условие полноты системы функций алгебры логики
(2) достаточное условие полноты системы функций алгебры логики
(3) необходимое и достаточное условие полноты системы функций алгебры логики
(4) индекс массы тела
Чему равно ![math]()
:
:
(1) 0
(2) 1
(3) 2
(4) 4
(5) 6
(6) 8
В комбинаторике перестановкой элементов конечного множества ![math]()
называют:
называют:
(1) запись, где элементы ![math]()
перечислены в произвольном порядке по одному разу
перечислены в произвольном порядке по одному разу
(2) взаимнооднозначное отображение множества ![math]()
на себя
на себя
(3) взаимнооднозначное отображение множества ![math]()
на себя, при котором ни один образ элемента не равен своему прообразу
на себя, при котором ни один образ элемента не равен своему прообразу Путь назвается простым, если:
(1) начальная и конечная вершины пути различны
(2) путь проходит через все вершины пути
(3) все вершины пути, кроме, быть может, первой и последней, различны
Какова максимальная длина простого пути в графе с ![math]()
вершинами:
вершинами:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Совершенная конъюнктивная нормальная форма функции алгебры логики:
(1) определена для константы ![math]()
(2) позволяет представить любую заданную таблично функцию алгебры логики в виде формулы
(3) наиболее удобна для представления функции алгебры логики, в табличном представлении которой мало нулей и много единиц
Имеется 4 конверта и 5 марок. Сколько существует способов выбрать конверт и марку для одного письма:
(1) 4
(2) 5
(3) 9
(4) 20
Определите производящую функцию для последовательности ![math]()
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Приближенное значение выражения ![math]()
равно:
равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите верные утверждения:
(1) некоторые пути являются циклами
(2) все циклы являются путями
(3) все простые пути являются циклами
(4) все циклы являются простыми путями
Простой граф, имещий две вершины степени 3, соединенные тремя непересекающимися путями длины не менее 2, называется:
(1) полный граф
(2) тэта-граф
(3) трехсвязный граф
(4) гамильтонов граф
Cовершенная дизъюнктивная нормальная форма для импликации ![math]()
имеет вид:
имеет вид:
(1) ![math]()
(2) ![math]()
(3) ![math]()
К задачам комбинаторики относятся:
(1) перечисление конфигураций
(2) оптимизация перечисления конфигураций
(3) оптимизация построения конфигураций
Производящая функция - это:
(1) произведение двух степенных функций
(2) функция, разложение которой в степенной ряд имеет в качестве коэффициентов при степенях переменной элементы некоторой заданной последовательности
Сколько существует беспорядков для множества, состоящего из ![math]()
элемента, таких, что элемент ![math]()
стоит на ![math]()
-ом месте, а элемент ![math]()
- на ![math]()
-ом месте:
элемента, таких, что элемент стоит на -ом месте, а элемент - на -ом месте:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите верные утверждения:
(1) любая часть графа является подграфом исходного графа
(2) любой подграф является частью исходного графа
(3) некоторые части графа являются его подграфами
(4) подграф некоторого графа может содержать вершины, которые не содержатся в исходном графе
Граф называется гамильтоновым, если он:
(1) имеет гамильтонов путь
(2) имеет гамильтонов цикл
(3) является двухсвязным тэта-графом
Если операциями суперпозиции и замены переменных из функций данной системы функций алгебры логики можно получить произвольную функцию алгебры логики, то такая система функций:
(1) полная система
(2) замкнутый класс
Сколько существует упорядоченных размещений 2 объектов по 2 ящикам:
(1) 2
(2) 4
(3) 6
(4) 8
Чему равна сумма всех чисел сочетаний из ![math]()
по ![math]()
:
по :
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите точное значение числа беспорядков на множестве из ![math]()
элементов:
элементов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Представление графа в виде объединения связанных компонент - это:
(1) графическое представление графа в виде точек, связанных дугами
(2) представление графа в виде объединения связных непересекающихся подграфов
(3) построение взаимнооднозначного соответствия между вершинами изоморфных графов
(4) представление графа в виде объединения полных графов
Для какого графа наименьшее количество вершин, удаление которых приводит к несвязному или одновершинному графу, равно трем:
(1) двусвязный граф
(2) трехсвязный граф
(3) четырехсвязный граф
Получить функцию алгебры логики от двух переменных, применяя операции суперпозиции и замены переменной над классом функций алгебры логики одной переменной:
(1) можно
(2) нельзя
Для двух чисел Стирлинга 1 рода, не равных нулю, ![math]()
и ![math]()
:
и 
:
(1) их знаки будут совпадать
(2) их знаки будут противоположными
(3) эти числа равны нулю
Выражение ![math]()
равно:
равно:
(1) 0
(2) 1
(3) ![math]()
(4) ![math]()
Укажите количество произвольных отображений из множества ![math]()
, в множество ![math]()
:
, в множество 
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Максимальное количество ребер в простом графе с ![math]()
вершинами и ![math]()
компонентами связности равно:
вершинами и компонентами связности равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Любой планарный граф:
(1) является гамильтоновым
(2) не является гамильтоновым
(3) может быть как гамильтоновым, так и негамильтоновым
Количество функций от ![math]()
переменных в классе функций, сохраняющих ноль, равно:
переменных в классе функций, сохраняющих ноль, равно:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите количество различных слов длины ![math]()
в алфавите из ![math]()
символов:
в алфавите из символов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Чему равно число сочетаний ![math]()
:
:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Количество разбиений ![math]()
объектов на ![math]()
непустых класса равно ![math]()
. Вычислите количество сюръективных отображений из множества, содержащего ![math]()
элементов, на множество, содержащее ![math]()
элемента:
объектов на 
непустых класса равно 
. Вычислите количество сюръективных отображений из множества, содержащего элементов, на множество, содержащее элемента:
(1) 24
(2) 260
(3) 654
(4) 1560
Максимальное количество ребер в простом графе с 5 вершинами и 2 компонентами связности равно:
(1) 4
(2) 5
(3) 6
(4) 7
Кратчайший путь - это:
(1) путь, проходящий через минимальное количество ребер из всех путей из начальной вершины в конечную
(2) путь, имеющий минимальную длину из всех путей из начальной вершины в конечную
(3) путь, проложенный по методу ближайшего соседа
Класс функций заданный как ![math]()
является
является
(1) примером замкнутого класса
(2) классом функций, сохраняющих ноль
(3) классом функций, сохраняющих единицу
Укажите количество различных слов длиной в 3 символа в алфавите из 5 символов:
(1) 15
(2) 125
(3) 243
(4) 256
Чему равна сумма квадратов коэффициентов при степенях бинома ![math]()
:
:
(1) 0
(2) 16
(3) 70![math]()
(4) 120![math]()
Система различных представителей:
(1) состоит из элементов, среди которых нет двух одинаковых
(2) строится для совокупности множеств, среди которых нет двух одинаковых
(3) строится для совокупности множеств, которые не пересекаются
(4) строится для совокупности множеств, некоторые из которых могут совпадать
Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 4 вершинами:
(1) 2
(2) 3
(3) 4
(4) 5
Определите сложность решения задачи поиска кратчайших путей в орграфе без циклов отрицательной длины, ![math]()
- количество вершин графа
- количество вершин графа
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) эта задача неразрешима
К классу линейных функций алгебры логики относятся:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите выражения, равные количеству различных слов длины ![math]()
, в которых все символы различны, в алфавите из ![math]()
символов:
, в которых все символы различны, в алфавите из символов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Укажите эквивалентные записи для полиномиальных коэффициентов ![math]()
через числа сочетаний:
через числа сочетаний:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Что из перечисленного ниже есть система различных представителей для системы подмножеств ![math]()
, ![math]()
, ![math]()
, ![math]()
исходного множества ![math]()
, 
, , исходного множества
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) не существует системы различных представителей для данной системы подмножеств
Для простого графа с ![math]()
вершинами укажите количества ребер, обеспечивающие связность графа:
вершинами укажите количества ребер, обеспечивающие связность графа:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Процедура перенумерации вершин графа так, чтобы номер вершины, куда ведет ребро, был больше, чем номер вершины-предшественника, называется:
(1) топологическая сортировка
(2) поиск кратчайшего пути
(3) поиск гамильтонова пути
Укажите функции, наличие которых требуется в системе функций для получения из них операциями суперпозиции и замены переменных функций ![math]()
:
:
(1) функция, не сохраняющая ноль
(2) функция, не сохраняющая единицу
(3) функция, не являющаяся двойственной
(4) функция, не являющаяся самодвойственной
(5) функция, не являющаяся монотонной
Укажите количество различных слов длиной в 3 символа, в которых все символы различны, в алфавите из 5 символов:
(1) 15
(2) 30
(3) 60
(4) 125
Чему равно количество размещений 5 различных объектов по 3 различным ящикам при условии, что в первом ящике находится 1 объект, во втором - 2 объекта, в третьем - 2 объекта:
(1) 15
(2) 30
(3) 60
(4) 120
Если система различных представителей для совокупности из ![math]()
множеств существует, то:
множеств существует, то:
(1) среди рассматриваемых ![math]()
множеств нет пустых множеств
множеств нет пустых множеств
(2) среди рассматриваемых ![math]()
множеств не более ![math]()
пустых множеств
множеств не более 
пустых множеств
(3) различные представители любых ![math]()
множеств из ![math]()
дают не менее ![math]()
различных элементов объединения этих ![math]()
множеств, для всех ![math]()
множеств из дают не менее различных элементов объединения этих множеств, для всех 
Что из перечисленного есть термины теории графов:
(1) корень дерева
(2) листья
(3) лес
Функцией, двойственной к ![math]()
, является:
, является:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Укажите выражения, равные количеству различных слов длины ![math]()
, в которых все символы различны, в алфавите из ![math]()
символов:
, в которых все символы различны, в алфавите из символов:
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
Сколько существует способов разместить ![math]()
различных объектов по ![math]()
различным ящикам, при условии, что в каждом ящике находится ![math]()
объектов соответственно, ![math]()
, и один из размещаемых объектов уже лежит в ящике ![math]()
:
различных объектов по различным ящикам, при условии, что в каждом ящике находится объектов соответственно, , и один из размещаемых объектов уже лежит в ящике :
(1) ![math]()
(2) ![math]()
(3) ![math]()
(4) ![math]()
При построении С.Р.П. для совокупности из ![math]()
множеств ![math]()
для первых ![math]()
множеств, ![math]()
, удалось выбрать различных представителей, но все элементы множества ![math]()
уже использованы в качестве представителей предыдущих множеств. Тогда:
множеств для первых 
множеств, 
, удалось выбрать различных представителей, но все элементы множества 
уже использованы в качестве представителей предыдущих множеств. Тогда:
(1) не существует С.Р.П. для исходной совокупности из ![math]()
множеств
множеств
(2) существует С.Р.П. для исходной совокупности из ![math]()
множеств
множеств
(3) С.Р.П. для исходной совокупности из ![math]()
множеств может существовать, а может и не существовать
множеств может существовать, а может и не существовать Сколько ребер содержит дерево со 100 вершинами?
(1) 100
(2) 10000
(3) 10
(4) 99
Какое значение принимает самодвойственная функция на наборе ![math]()
, если на наборе ![math]()
эта функция принимает значение ![math]()
?
, если на наборе 
эта функция принимает значение ?
(1) 1
(2) 0
(3) для ответа недостаточно информации
Укажите количество различных слов длиной в 5 символов, в которых все символы различны, в алфавите из 5 символов:
(1) 5
(2) 25
(3) 60
(4) 120
Чему равна сумма полиномиальных коэффициентов разложения по степеням выражения ![math]()
:
:
(1) 12
(2) 24
(3) 64
(4) 81
Понятие системы общих представителей формулируется для:
(1) множества ![math]()
, представленного в виде разбиений на множества ![math]()
, представленного в виде разбиений на множества
(2) множества ![math]()
, представленного в виде разбиений на множества ![math]()
, и того же самого множества ![math]()
, представленного в виде разбиений на множества ![math]()
, представленного в виде разбиений на множества , и того же самого множества , представленного в виде разбиений на множества
(3) множества ![math]()
, представленного в виде разбиений на множества ![math]()
, и того же самого множества ![math]()
, представленного в виде разбиений на множества ![math]()
, ![math]()
, представленного в виде разбиений на множества , и того же самого множества , представленного в виде разбиений на множества , 
(4) множества ![math]()
, представленного в виде разбиений на множества ![math]()
, и множества ![math]()
, представленного в виде разбиений на множества ![math]()
, представленного в виде разбиений на множества , и множества 
, представленного в виде разбиений на множества Количество деревьев, которое можно построить на 3 заданный вершинах, равно:
(1) 1
(2) 2
(3) 3
(4) 4
Какая из перечисленных функций является монотонной:
(1) ![math]()
(2) ![math]()
(3) ![math]()
Чему равно число Стирлинга первого рода ![math]()
при ![math]()
:
при 
:
(1) 0
(2) 1
Блоки разбиения - это:
(1) непустые непересекающиеся подмножества, на которые разбивается некоторое конечное множество
(2) непустые упорядоченные подмножества, на которые разбивается некоторое конечное множество
(3) невозможность разбить некоторое конечное множество на непустые классы
(4) упорядоченный набор кеглей
Как можно доказать существование системы общих представителей в общем случае:
(1) путем сведения к доказательству существования системы различных представителей
(2) путем полного перебора
(3) невозмножно в общем случае доказать существование системы общих представителей
Любое нетривиальное дерево содержит::
(1) хотя бы одно концевую вершину
(2) хотя бы две концевых вершины и одно концевое ребро
(3) хотя бы три концевых вершины и два концевых ребра
К каким классам функций алгебры логики относится функция ![math]()
:
:
(1) класс монотонных функций
(2) класс самодвойственных функций
(3) класс линейных функций
В записи числа Стирлинга первого рода ![math]()
индекс ![math]()
означает, что:
индекс означает, что:
(1) ![math]()
это коэффициент при переменной в степени ![math]()
это коэффициент при переменной в степени
(2) ![math]()
это коэффициент при переменной в степени ![math]()
это коэффициент при переменной в степени Сколько существует различных разбиений множества из 4 элементов на 3 класса:
(1) 6
(2) 7
(3) 8
(4) 12
К каким классам функций алгебры логики относится функция ![math]()
:
:
(1) класс самодвойственных функций
(2) класс линейных функций
(3) класс функций, сохраняющих ноль
Укажите возможные ситуации для системы общих представителей ![math]()
при разбиениях множества ![math]()
![math]()
и ![math]()
, для ![math]()
, ![math]()
:
при разбиениях множества и , для , 
:
(1) для каждого из множеств ![math]()
найдется множество ![math]()
такое, что их пересечение не пусто
найдется множество такое, что их пересечение не пусто
(2) некоторые из множеств ![math]()
попарно пересекаются
попарно пересекаются
(3) некоторые из множеств ![math]()
попарно пересекаются
попарно пересекаются