🧮 Математика · 30 вопросов · ~60 мин · ⏱ Таймер 10:00 · Средний · 👥 1 прошёл

Дискретная математика: кругозор в мире графов, комбинаций и логики

Дискретная математика — это математика цифровой эпохи. Именно здесь живут алгоритмы, шифрование, базы данных и нейросети. Но это и красивая наука сама по себе: задача о коммивояжёре, раскраска карт, семь мостов Кёнигсберга — задачи, которые легко формулировать и трудно решать. Тест проверяет кругозор в комбинаторике (сколькими способами?), теории графов (как связаны вершины?), логике (истина или ложь?), теории множеств (что входит в пересечение?) и основах теории алгоритмов. Вопросы смешаны по сложности: часть вспомните сразу, часть потребует думать.

Отвечено: 0 из 30

⏱ --:--

💡 Инструкция: Выберите один вариант ответа. Дискретная математика редко встречается в школе — не переживайте, если что-то видите впервые. Кругозор важнее зубрёжки.

Вопрос 1 из 30

Сколькими способами можно расставить 3 разных книги на полке?

9 6 3 27

Вопрос 2 из 30

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

Множество вершин и рёбер между ними Диаграмма в системе координат Таблица значений функции Сеть из одинаковых ячеек

Вопрос 3 из 30

Что такое «дизъюнкция» в логике?

Логическое НЕ (отрицание) Логическое И (конъюнкция) Логическое ИЛИ Логическое исключение

Вопрос 4 из 30

Что такое «пересечение» двух множеств A ∩ B?

Декартово произведение множеств Все элементы, принадлежащие обоим множествам одновременно Элементы A, не входящие в B Все элементы, принадлежащие хотя бы одному из множеств

Вопрос 5 из 30

Чему равно число 13 в двоичной системе счисления?

1001 1110 1011 1101

Вопрос 6 из 30

Сколькими способами можно выбрать 2 человека из группы 5 для выполнения задания (порядок не важен)?

25 10 20 5

Вопрос 7 из 30

Задача о «семи мостах Кёнигсберга» привела к открытию...

Теории графов Теории чисел Теории вероятностей Алгебраической топологии

Вопрос 8 из 30

Что такое «эйлеров путь» в графе?

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

Вопрос 9 из 30

Что означает «O(n²)» в анализе алгоритмов?

Алгоритм работает за O(n) шагов с вложенным O(n) вызовом Алгоритм выполняется ровно n² операций Алгоритм использует n² байт памяти Число операций растёт пропорционально квадрату входного размера

Вопрос 10 из 30

Что такое «принцип включений и исключений»?

Формула для подсчёта элементов объединения множеств через пересечения Алгоритм удаления дубликатов из множества Правило: если A истинно, а B ложно, то A ∧ B ложно Метод доказательства от противного

Вопрос 11 из 30

Что такое «контрапозиция» в логике?

Отрицание обоих частей импликации Замена импликации «A ⇒ B» на эквивалентную «¬B ⇒ ¬A» Замена «или» на «и» в логическом выражении Утверждение, противоположное исходному

Вопрос 12 из 30

Что такое «планарный граф»?

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

Вопрос 13 из 30

Что такое «транзитивное замыкание» отношения?

Минимальное транзитивное расширение отношения Рефлексивное расширение отношения Объединение двух отношений Отношение, обратное к данному

Вопрос 14 из 30

Что такое «задача коммивояжёра» (TSP)?

Найти максимальный поток в сети Разложить граф на дерево минимального веса Кратчайший обход всех городов с возвратом в начало Покрасить граф минимальным числом цветов

Вопрос 15 из 30

Что такое «лемма о рукопожатиях» в теории графов?

Количество рёбер не превышает числа вершин в квадрате Сумма степеней всех вершин равна удвоенному числу рёбер В любом графе есть вершина, связанная со всеми остальными Любой связный граф содержит эйлеров путь

Вопрос 16 из 30

Что такое «бинарное дерево» в информатике?

Таблица из двух столбцов Граф без циклов, где у каждого узла не более двух потомков Граф, который можно раскрасить двумя цветами Список из нулей и единиц

Вопрос 17 из 30

Что такое «теорема Рамсея»?

Каждый конечный граф можно раскрасить не более чем пятью цветами Количество гамильтоновых циклов в полном графе равно (n−1)!/2 Хроматическое число плоского графа не превышает 4 В достаточно большом графе неизбежно найдётся клика или независимое множество заданного размера

Вопрос 18 из 30

Что такое «принцип Дирихле» (принцип ящиков)?

В любой конечной последовательности есть возрастающая или убывающая подпоследовательность Каждое рациональное число можно разложить в непрерывную дробь Число простых в арифметической прогрессии бесконечно Если n+1 предмет разложить по n ящикам, в хотя бы одном окажется не менее двух предметов

Вопрос 19 из 30

Что такое «класс P» в теории сложности?

Задачи, требующие параллельных вычислений Задачи, решаемые за полиномиальное время Задачи, решаемые за O(1) Задачи, которые нельзя решить за конечное время

Вопрос 20 из 30

Что такое «хроматическое число» графа?

Максимальная длина пути в графе Число связных компонент графа Минимум цветов для раскраски смежных вершин Количество рёбер в графе

Вопрос 21 из 30

Что такое «треугольное число»?

Простое число, записываемое тремя одинаковыми цифрами Число, равное сумме его цифр в кубе Число, равное сумме 1+2+3+...+n для некоторого натурального n Число сторон любого правильного многоугольника, делящееся на 3

Вопрос 22 из 30

Что означает «импликация» A ⇒ B в логике?

A или B истинно, но не оба одновременно «Если A, то B» — ложна только когда A истинно, а B ложно A и B — взаимоисключающие события A и B обычно одновременно истинны или ложны

Вопрос 23 из 30

Что такое «декартово произведение» множеств A × B?

Множество всех упорядоченных пар (a, b), где a ∈ A и b ∈ B Множество всех элементов, входящих в оба множества Произведение мощностей множеств Объединение множеств без повторений

Вопрос 24 из 30

Что такое «парадокс Рассела» в теории множеств?

Самопротиворечие множества всех множеств, не содержащих себя Любое бесконечное множество содержит подмножество той же мощности Некоторые высказывания ни истинны, ни ложны Пустое множество является подмножеством любого множества

Вопрос 25 из 30

Чему равно 2⁸ (два в восьмой степени)?

512 64 256 128

Вопрос 26 из 30

Что такое «метод математической индукции»?

Доказательство через перебор всех частных случаев Доказательство базы (n=1) и индукционного перехода (из n следует n+1) Метод нахождения паттерна на примерах и обобщения Доказательство от противного

Вопрос 27 из 30

Что такое «дерево остова» (минимальное остовное дерево) графа?

Граф без циклов с максимальным числом рёбер Дерево, в котором каждая вершина имеет ровно одного потомка Подграф, связывающий все вершины с минимальной суммой весов рёбер, без циклов Путь минимального веса между двумя заданными вершинами

Вопрос 28 из 30

Что такое «закон де Моргана» в логике?

A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) A ∨ ¬A ≡ истина ¬(A ⇒ B) ≡ A ∧ ¬B ¬(A ∧ B) ≡ ¬A ∨ ¬B и ¬(A ∨ B) ≡ ¬A ∧ ¬B

Вопрос 29 из 30

Что утверждает «теорема Кёнига» о двудольных графах?

Любой двудольный граф является планарным В двудольном графе максимальное паросочетание равно минимальному вершинному покрытию В двудольном графе с равными долями обычно есть гамильтонов цикл Хроматическое число двудольного графа равно 3

Вопрос 30 из 30

Что такое «инвариант» в задачах на доказательство?

Число, которое не меняется при разрешённых преобразованиях задачи Переменная, принимающая только целые значения Условие, которое обычно ложно Утверждение, которое нельзя ни доказать, ни опровергнуть

Ответьте на все 30 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу