Дискретная математика

Что такое граф?

• A. Набор чисел
• B. Система уравнений
• C. Математическая структура, состоящая из вершин и рёбер
• D. Алгоритм поиска

Что такое комбинаторика?

• A. Раздел математики, изучающий последовательности чисел
• B. Раздел математики, изучающий способы выбора и расстановки объектов
• C. Теория вероятностей
• D. Исследование функций

Какое из следующих утверждений верно для пустого множества?

• A. Оно содержит хотя бы один элемент
• B. Оно является подмножеством любого множества
• C. Оно равно всем другим множествам
• D. Оно имеет бесконечное количество элементов

Каково количество способов выбрать 3 элемента из 5?

• A. 5
• B. 10
• C. 15
• D. 20

Что такое диаграмма Венна?

• A. Способ для нахождения корней уравнения
• B. Графическое представление множеств и их отношений
• C. Ряд чисел
• D. Метод визуализации алгоритмов

Какое из следующих утверждений о деревьях верно?

• A. Дерево обязательно имеет цикл
• B. Количество рёбер в дереве на 1 меньше количества вершин
• C. Все вершины дерева имеют одинаковую степень
• D. Дерево не может быть пустым

Что такое рёбра графа?

• A. Набор чисел
• B. Связи между вершинами графа
• C. Алгоритмы поиска
• D. Элементы целочисленного множества

Какое из следующих утверждений относится к булевой алгебре?

• A. Операции И, ИЛИ, НЕ
• B. Операции сложения и умножения
• C. Дифференцирование и интегрирование
• D. Все вышеперечисленное

Что такое функция хеширования?

• A. Алгоритм шифрования
• B. Функция, преобразующая входные данные в фиксированную длину
• C. Способ сортировки данных
• D. Математическая операция

Какой из примеров является рекурсивной последовательностью?

• A. Простые числа
• B. Фибоначчи
• C. Четные числа
• D. Нечётные числа

Что означает логический оператор «И»?

• A. В true, если хотя бы одно из выражений true
• B. В true, если оба выражения true
• C. Никогда не возвращает true
• D. Алгоритм сортировки данных

Какое из следующих утверждений соответствует теореме о графах?

• A. Графы всегда связаны
• B. В любом графе количество рёбер меньше, чем количество вершин
• C. Графы не могут иметь отрицательные веса
• D. Все графы являются деревьями

Что такое «перестановка»?

• A. Набор элементов без учета порядка
• B. Упорядоченный набор элементов
• C. Множество чисел
• D. Список функций

В чем разница между множеством и классом?

• A. Класс всегда меньше по размеру
• B. Класс может быть слишком большим, чтобы быть множеством
• C. Множество всегда имеет конечное количество элементов
• D. Множество имеет бесконечное количество элементов

Что такое бит в дискретной математике?

• A. Единица информации, которую можно представить в двоичном формате
• B. Набор чисел
• C. Способ сортировки данных
• D. Процесс вычисления

Что такое изоморфизм графов?

• A. Соответствие между графами, сохраняющее их структуру
• B. Граф, имеющий один и тот же вес
• C. Процесс упрощения графа
• D. Граф с одинаковым количеством рёбер и вершин

Какую задачу решает алгоритм Дейкстры?

• A. Нахождение кратчайшего пути в несвязанном графе
• B. Нахождение кратчайшего пути в связном графе
• C. Сортировка узлов графа
• D. Определение веса графа

Что такое подмножество?

• A. Множество, которое содержит все элементы другого множества
• B. Множество, которое содержит некоторые или все элементы другого множества
• C. Множество с одинаковыми элементами
• D. Множество, не содержащее элементов

Что такое пересечение множеств?

• A. Множество идей
• B. Элементы, которые принадлежат обоим множествам
• C. Множество всех элементов
• D. Множество, состоящее из различных элементов

В чем заключается принцип индукции?

• A. Метод случайного выбора
• B. Метод доказательства, который используется для утверждений о натуральных числах
• C. Метод проб и ошибок
• D. Алгоритмическое решение задач

Какой из следующих объектов является множеством?

• Натуральные числа
• Число 5
• Множество всех четных чисел
• Квадратный корень из 9

Что из следующего является эквивалентным выражением для логического высказывания: «P AND Q»?

• Равенство P и Q
• Оба P и Q истины
• Равенство P или Q
• Ни одно из выше перечисленных

Какое из следующих утверждений является тождественно ложным?

• P AND NOT P
• P OR NOT P
• P AND Q
• NOT (P AND Q)

Какое множество является подмножеством множества {1, 2, 3}?

• {1, 2}
• {4, 5}
• {1, 2, 3, 4}
• {}

Что из следующего является операцией на множествах?

• Сложение
• Пересечение
• Умножение
• Деление

Какое из выражений представляет собой индуктивное доказательство?

• База индукции и шаг индукции
• База индукции и шаг индукции с предположением о некотором элементе
• Рассмотрение всех возможных случаев
• Графическое доказательство

Какое из следующих утверждений верно для операции объединения множества?

• A ∪ B = B ∪ A
• A ∪ B = B — A
• A ∪ B = A — B
• A ∪ B = A ∩ B

Что из следующего является бинарной операцией?

• Сложение чисел
• Равенство
• Умножение матриц
• Все выше перечисленные

Что такое кардинальное число множества?

• Множество, состоящее из всех возможных подмножеств
• Количество элементов в множестве
• Число, выражающее количество элементов в множестве
• Объединение всех элементов множества

Какое из следующих утверждений верно для формулы логического высказывания?

• Она всегда истинна
• Она может быть либо истинной, либо ложной
• Она всегда ложна
• Она зависит от значений переменных

Что из следующего является примером рекурсии?

• Функция, которая вызывает сама себя
• Цикл for
• Операция умножения
• Цикл while

Что такое отношение в теории множеств?

• Набор всех подмножеств множества
• Множество элементов с одинаковым значением
• Множество упорядоченных пар
• Набор всех элементов множества

Что означает обозначение |A|?

• Множество элементов A
• Число элементов множества A
• Объединение всех элементов множества A
• Пересечение всех элементов множества A

Что такое диаграмма Венна?

• Графическое представление операций на множествах
• Графическое представление множества и их отношений
• Математическая модель для решения задач
• Математическое доказательство

Что такое булевы алгебры?

• Операции над множествами
• Алгебраические структуры для работы с логическими значениями
• Группы математических операций
• Операции над числами

Что такое граф в теории графов?

• Множество чисел, связанных операцией
• Множество объектов, связанных рёбрами
• Множество вершин и рёбер, соединяющих эти вершины
• Множество элементов, упорядоченных по важности

Что из следующего является примером замкнутой функции в теории графов?

• Функция, которая не может быть определена
• Функция, которая приводит к зацикливанию
• Функция, которая всегда возвращает одно значение
• Функция, которая не изменяет значения элементов

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

• P AND NOT P
• P OR P
• P AND Q
• P OR NOT P

Как называется минимальная функция в теории графов?

• Функция, которая минимизирует количество рёбер
• Функция, которая ограничивает количество вершин
• Функция, которая решает все задачи
• Функция, которая добавляет рёбра

Какое множество называется множества ограничений?

• Множество всех чисел
• Множество чисел, соответствующих определённым ограничениям
• Множество чисел от 1 до 10
• Множество всех переменных