💯 Высшая математика [Модуль 1-5] — ответы на тесты Синергия / МОИ / МТИ / МосАП

Высшая математика > Тест 2 / Тест 3 / Тест 4 / Тест 5 / Тест 6 / Тест 7 / Тест 8 / Тест 9 / Тест 10 / Тест 11 / Тест 12 / Тест 13 / Тест 14 / Тест 15 / Тест 16 / Тест 17 / Итоговый тест

• правильные ответы на вопросы из тестов по данной дисциплине
• вопросы отсортированы в лексикографическом порядке

Высшая математика

• Модуль 1. Интро
• Модуль 2. Начала теории множеств
• Модуль 3. Логика и алгоритмы
• Модуль 4. Введение в теорию чисел
• Модуль 5. Графы и деревья
• Итоговая аттестация
• Анкета обратной связи

... Гамеля - это максимальное линейно независимое подмножество векторного пространства

Тип ответа: Текcтовый ответ

... обладает носителем и значениями для символов предикатов и функций.

Тип ответа: Текcтовый ответ

Аксиома выбора необходима для доказательства существования:

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

• Наименьшего элемента в любом множестве
• Базиса Гамеля в векторном пространстве
• Наибольшего общего делителя двух чисел
• Предела последовательности

Аксиома выбора необходима для доказательства:

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

• Теоремы о существовании предела последовательности
• Теоремы о существовании базиса в любом векторном пространстве
• Теоремы Пифагора
• Основной теоремы алгебры

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

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

• Верно только для конечных множеств
• Верно для любых множеств
• Неверно
• Верно только для счетных множеств

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

Тип ответа: Текcтовый ответ

Алгоритм Дейкстры можно интерпретировать как модифицированный алгоритм поиска в ..., где взешенное ребро заменяется на путь из нескольких ребер.

Тип ответа: Текcтовый ответ

Алгоритм Евклида основан на использовании деления с ...

Тип ответа: Текcтовый ответ

Алгоритмом называется программа, написанная на ... Тьюринга

Тип ответа: Текcтовый ответ

Арифметика ординалов включает операции:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Сложение
• Умножение
• Возведение в степень
• Вычитание

Базис Гамеля - это максимальное линейно ... независимое подмножество векторного пространства

Тип ответа: Текcтовый ответ

Бинарное отношение, которое является рефлексивным, симметричным и транзитивным, называется отношением ...

Тип ответа: Текcтовый ответ

В графе G с 7 вершинами каждая вершина соединена с двумя другими вершинами. Сколько ребер содержит этот граф?

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

• 5
• 6
• 7
• 8

В графе G с 8 вершинами каждая вершина соединена с каждой другой вершиной. Сколько ребер содержит этот граф?

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

• 28
• 30
• 32
• 34

В графе, представленном матрицей смежности, элемент aij равен 0, если между вершинами i и j ...

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

• существует путь
• существует ребро
• не существует пути
• не существует ребра

В интервале от 1 до 1000 найдите количество чисел, которые делятся на 4 или 6, но не делятся на 12.

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

• 150
• 250
• 333
• 427

В языках первого порядка, формула ∃x (P(x) ∧ Q(x)) означает, что

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

• существует такой x, что P(x) и Q(x) оба истинны.
• для каждого x, P(x) и Q(x) оба истинны.
• существует такой x, что P(x) истинно, но Q(x) ложно.
• ни одно из вышеуказанных.

Выберете все свойства, верные для отношения "сравнимы по модулю n":

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Рефлектсивность
• Симметричность
• Антисимметричность
• Транзитивность

Выберите все верные утверждения о алгоритме Евклида:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Алгоритм эффективен для больших чисел
• Алгоритм требует, чтобы числа были взаимно простыми
• Алгоритм завершается, когда остаток становится равным нулю
• Алгоритм не применим к отрицательным числам

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

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

Выберите все верные утверждения о свойствах графов:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• В дереве с n вершинами ровно n-1 ребро
• В полном графе с n вершинами ровно n рёбер
• В связном графе между любыми двумя вершинами существует путь
• В ациклическом графе каждая вершина соединена ребром с каждой другой вершиной

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

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

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Функциональные символы используются для построения термов.
• Функциональные символы не могут принимать аргументы.
• Функциональные символы могут представлять конкретные объекты или операции над объектами.
• Функциональные символы используются для представления логических операций.

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Он разбивает вершины по уровням
• Он является ускоренной версией алгоритма поиска в глубину
• Он завершает свою работу на любом входе
• Он работает только для неориентированных графов

Выберите все верные утверждения относительно арифметики остатков:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Если a ≡ b (mod m) и c ≡ d (mod m), то a+c ≡ b+d (mod m)
• Если a ≡ b (mod m), то a^k ≡ b^k (mod m) для любого натурального k
• Если a ≡ b (mod m), то a^k ≡ b^(k+1) (mod m) для любого натурального k
• Если a ≡ b (mod m) и c ≡ d (mod m), то ac ≡ bd  (mod m)

Выберите все верные утверждения относительно арифметики остатков:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Если a ≡ b (mod m), то -a ≡ -b (mod m)
• Если a ≡ b (mod m) и c ≡ d (mod m), то ac ≡ bd (mod m)
• Если a ≡ b (mod m), то a^k ≡ b^(k-1) (mod m) для любого натурального k
• Если a ≡ b (mod m) и c ≡ d (mod m), то a+c ≡ b+d (mod m+1)

Выберите все верные утверждения относительно импликации:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• p → q эквивалентно ¬p ∨ q
• p → q эквивалентно p ∧ ¬q
• p → q эквивалентно ¬q → ¬p
• p → q эквивалентно q → p

Выберите все верные утверждения, связанные с малой теоремой Ферма:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Если p - простое число, то для любого целого a, a^p ≡ a (mod p)
• Если p - простое число и a не делится на p, то a^p ≡ 0 (mod p)
• Если p - простое число и a не делится на p, то a^(p-1) ≡ 1 (mod p)
• Если p - простое число, то для любого целого a, a^(p+1) ≡ a (mod p)

Выберите все верные утверждения:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Каждое разрешимое множество является перечислимым.
• Каждое перечислимое множество является разрешимым.
• Существуют перечислимые множества, которые не являются разрешимыми.
• Все подмножества натуральных чисел являются разрешимыми.

Выберите все верные утверждения:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Принцип Дирихле гласит, что если n + 1 объектов размещены в n ячейках, то по крайней мере одна ячейка содержит более одного объекта
• Принцип Дирихле применим только к бесконечным множествам
• Множество всех подмножеств данного множества имеет большую мощность, чем само множество
• Мощность множества всех подмножеств натуральных чисел равна мощности множества натуральных чисел

Выберите все верные утверждения:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Трансфинитная индукция применяется к вполне упорядоченным множествам
• Все частично упорядоченные множества являются вполне упорядоченными
• Отношение эквивалентности разбивает множество на классы эквивалентности
• Все фундированные множества имеют наибольший элемент

Выберите все утверждения, верные для любых множеств

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• A (B ∪ C) = (A B) ∪ (A C)
• A B = B A
• A ∩ B = B ∩ A

Высказывание "Если сегодня идет дождь, то я возьму зонт" является примером логической операции ...

Тип ответа: Текcтовый ответ

Вычислимая функция - это функция, для которой существует ... , вычисляющий её значение для любого входа.

Тип ответа: Текcтовый ответ

Говорят, что множество A содержится в множестве B, если каждый элемент A … B.

Тип ответа: Текcтовый ответ

Говорят, что множество A является … множества B, если каждый элемент A принадлежит B.

Тип ответа: Текcтовый ответ

Диаграмма Венна используется для

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

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

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

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

• Значения в нуле
• Старшие коэффициенты
• Свободные члены
• Степени

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

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

• математической индукции
• построения биекции (взаимно однозначного соответствия)
• использования принципа Дирихле
• применения теоремы Кантора-Бернштейна

Для чисел 1920 и 1080 НОД равен ...

Тип ответа: Текcтовый ответ

Если a ≡ b (mod m), то числа a и b имеют одинаковый ... при делении на m. Это утверждение является определением сравнения по модулю m

Тип ответа: Текcтовый ответ

Если a ≡ b (mod m), то числа a и b имеют одинаковый остаток при делении на m. Это утверждение является определением сравнения по ... m

Тип ответа: Текcтовый ответ

Из скольких элементов состоит множество {1, 2, {3, 4}}?

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

• 1
• 2
• 3
• 4

Индуктивные определения используются для:

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

• Определения мощности множеств
• Построения ординалов
• Доказательства теорем в линейной алгебре
• Решения дифференциальных уравнений

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

Тип ответа: Текcтовый ответ

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

Тип ответа: Текcтовый ответ

Как расшифровывается аббревиатура RSA?

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

• Rivest, Shamir, Adleman
• Rickert, Shaviro, Agamben
• Rousseau, Spinoza, Aquinas
• Russell, Sartre, Arendt

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Множество всех простых чисел
• Множество всех четных чисел
• Множество всех непрерывных функций на отрезке [0, 1]
• Множество всех иррациональных чисел

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• p → q, ¬q → ¬p
• p ∧ q, p ∨ q
• p ∨ q, ¬p → q
• p ∧ q, ¬p ∨ ¬q

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Она необходима для доказательства теоремы Пифагора
• Она противоречит аксиоме выбора
• Она эквивалентна теореме Цермело
• Она используется для доказательства существования базиса Гамеля

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Основная теорема арифметики выполняется для многочленов с вещественными коэффициентами
• Любое натуральное число, большее 1, можно представить в виде произведения простых чисел
• Лемма о разложении единицы не может быть использована для доказательства ОТА
• Любое натуральное число можно представить в виде произведения составных чисел

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Не все элементы множества обязательно сравнимы между собой
• Существует единственный наименьший элемент множества
• Каждый элемент множества сравним сам с собой
• Существует единственный наибольший элемент множества

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

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

• Дерево - это граф, в котором любые две вершины соединены ровно одним путем
• Дерево - это связный граф без циклов
• Дерево - это граф, содержащий хотя бы один цикл
• Дерево - это граф, в котором есть хотя бы одна изолированная вершина

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

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

• В ориентированном графе рёбра не имеют направления
• В ориентированном графе рёбра имеют направление
• В ориентированном графе не может быть циклов
• В ориентированном графе каждая вершина соединена ребром с каждой другой вершиной

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

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

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Она эквивалентна лемме Цорна
• Она эквивалентна теореме Цермело
• Она противоречит теореме Цермело
• Она не следует из леммы Цорна

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Если a делится на b, то a = b·k, где k - целое число
• Если a делится на b, то b делится на a
• Если a и b взаимно простые числа, то НОД(a, b) = 1
• Если a делится на b, то a + b делится на b

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Любое простое число делится на 3
• Если a и b взаимно простые, то НОД(a, b) = 1
• Любое составное число делится на простое число
• Если a делится на b и b делится на c, то a делится на c

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

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

• Мощность множества натуральных чисел больше мощности множества целых чисел
• Мощность множества рациональных чисел равна мощности множества натуральных чисел
• Мощность множества действительных чисел меньше мощности множества натуральных чисел
• Мощность множества всех подмножеств натуральных чисел равна мощности множества натуральных чисел

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

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

• Алгоритм требует, чтобы оба числа были простыми
• Алгоритм использует последовательное деление с остатком
• Алгоритм не может быть применен, если одно из чисел отрицательное
• Алгоритм завершается, когда остаток от деления равен 1

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

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

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

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

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

• В дереве может быть цикл
• В дереве с n вершинами ровно n-1 ребро
• В дереве каждая вершина соединена ребром с каждой другой вершиной
• В дереве не может быть изолированных вершин

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

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

• Интерпретация - синоним понятия тавтология.
• Интерпретация обладает носителем и значениями для символов предикатов и функций.
• Интерпретация позволяет изменять значения логических переменных.
• Интерпретация используется для определения синтаксиса языка.

Какое из следующих утверждений верно для любых целых чисел a и b, где b ≠ 0?

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

• НОД(a, b) = a·b
• НОД(a, b) = НОД(b, a mod b)
• НОД(a, b) = a + b
• НОД(a, b) = a - b

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

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

• В ориентированном графе не может быть циклов
• В ориентированном графе рёбра имеют направление
• В ориентированном графе каждая вершина соединена ребром с каждой другой вершиной
• В ориентированном графе не может быть петель

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

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

• Отношение эквивалентности всегда антисимметрично
• Отношение эквивалентности всегда рефлексивно
• Отношение эквивалентности не требует симметричности
• Отношение эквивалентности не может быть транзитивным

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

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

• Никакое конечное множество не является перечислимым.
• Любое бесконечное множество, элементы которого можно перечислить алгоритмически, является перечислимым.
• Все подмножества действительных чисел являются перечислимыми.
• Перечислимые множества не могут содержать бесконечное количество элементов.

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

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

• Формулы могут содержать только константы и переменные.
• Формулы могут содержать переменные, кванторы, предикаты и функциональные символы.
• Формулы не могут содержать кванторы.
• Формулы ограничены использованием только логических операций.

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

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

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

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

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

• Мощность множества всех подмножеств данного множества всегда больше мощности самого множества
• Все бесконечные множества имеют одинаковую мощность
• Мощность множества действительных чисел равна мощности множества натуральных чисел
• Мощность множества целых чисел меньше мощности множества натуральных чисел

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

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

• Простое число больше 2 всегда нечетно
• Все четные числа являются составными
• Все составные числа делятся на простые числа без остатка
• Все простые числа делятся на 2 без остатка

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

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

• 15
• 17
• 21
• 27

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

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

• 4
• 2
• 3
• 5

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

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

• рефлексивность
• симметричность
• транзитивность
• антисимметричность

Какое из этих свойств не присуще отношению эквивалентности?

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

• рефлексивность
• симметричность
• транзитивность
• антисимметричность

Какое свойство базиса Гамеля делает его особенно полезным для линейной алгебры?

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

• Все векторы базиса Гамеля имеют одинаковую длину.
• Базис Гамеля всегда образует ортонормированную систему.
• Векторы базиса Гамеля могут быть умножены только на скаляры.
• Базис Гамеля всегда содержит нулевой вектор.

Какое утверждение верно для схемы шифрования RSA?

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

• Открытый и закрытый ключи идентичны
• Открытый ключ используется для шифрования, а закрытый — для дешифрования
• Закрытый ключ используется для шифрования и дешифрования
• Открытый ключ используется для дешифрования, а закрытый — для шифрования

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

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• Алгоритм Косарайю
• Алгоритм поиска в глубину
• Алгоритм Дейкстры
• Алгоритм Прима

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

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

• Алгоритм Краскала
• Алгоритм Дейкстры
• Алгоритм Беллмана-Форда
• Алгоритм Флойда-Уоршелла

Какой алгоритм используется для нахождения наибольшего общего делителя (НОД) двух чисел?

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

• Алгоритм Дейкстры
• Алгоритм Флойда-Уоршелла
• Алгоритм Евклида
• Алгоритм Кнута-Морриса-Пратта

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

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

• Алгоритм Евклида
• Алгоритм быстрой сортировки
• Алгоритм RSA
• Алгоритм Диффи–Хеллмана

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

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

• Алгоритм Флойда-Уоршелла
• Алгоритм поиска в глубину
• Алгоритм Беллмана-Форда
• Алгоритм Косарайю

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

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

• Поиск кратчайшего пути
• Определение обратных ребер
• Использование внешнего стека для хранения вершин
• Сортировка вершин по времени завершения

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

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

• Граф, содержащий хотя бы один цикл
• Граф, не содержащий циклов
• Граф, в котором каждая вершина соединена ребром с каждой другой вершиной
• Граф, содержащий хотя бы одну изолированную вершину

Какой граф называется полным?

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

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

Какой из следующих вариантов лучше всего описывает принцип работы алгоритма поиска в глубину?

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

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

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

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

• Метод математической индукции
• Построение взаимно однозначного соответствия
• Принцип Дирихле
• Метод диагонали Кантора

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

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

• Метод наименьших квадратов
• Трансфинитная индукция
• Принцип Дирихле
• Диагональный метод Кантора

Какой метод является основой для генерации ключей в схеме Диффи–Хеллмана?

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

• Факторизация
• Возведение в степень
• Хеширование
• Симметричное шифрование

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

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

• 0
• 1
• ω
• ω + 1

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

Тип ответа: Текcтовый ответ

Квантор ... обозначается символом ∀ и означает, что утверждение верно для всех элементов.

Тип ответа: Текcтовый ответ

Квантор всеобщности в языках первого порядка обозначается символом ... и используется для указания, что утверждение верно для всех объектов домена.

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

• ∃
• ∑
• ∀
• ω

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

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

• ∃
• ω
• ∀
• ∑

Классическая теория алгоритмов описывает так называемые … функции.

Тип ответа: Текcтовый ответ

Компактные … часто рассматриваются в контексте леммы Цорна

Тип ответа: Текcтовый ответ

Лемма Цорна утверждает, что если в частично упорядоченном множестве каждая цепь имеет верхнюю грань, то существует максимальный … элемент.

Тип ответа: Текcтовый ответ

Логическая операция, подразумевающая логическое ИЛИ, называется ...

Тип ответа: Текcтовый ответ

Малая теорема ... утверждает, что для любого целого числа a и простого числа p, если a не делится на p, то ap-1 ≡ 1 (mod p).

Тип ответа: Текcтовый ответ

Малая теорема Ферма гласит, что если p - простое число и a не делится на p, то ap-1 ≡ ... (mod p).

Тип ответа: Текcтовый ответ

Множества A и B равномощны, если существует … между их элементами.

Тип ответа: Текcтовый ответ

Множество называется ..., если существует алгоритм, который для любого элемента может определить, принадлежит ли он этому множеству

Тип ответа: Текcтовый ответ

Множество называется ..., если существует алгоритм, который по очереди выдает все его элементы и только их

Тип ответа: Текcтовый ответ

Множество, состоящее из всех элементов, принадлежащих A и B, называется … этих двух множеств.

Тип ответа: Текcтовый ответ

Множество, состоящее из пар (a, b), где a∈A, b∈B, называется … произведением множеств A и B.

Тип ответа: Текcтовый ответ

Мощность множества определяется числом … в нем.

Тип ответа: Текcтовый ответ

Наибольший общий делитель (НОД) чисел 36 и 48 равен...

Тип ответа: Текcтовый ответ

Наибольший общий делитель чисел 2560 и 1440, равен ...

Тип ответа: Текcтовый ответ

Найдите количество решений системы уравнений: ¬x1+x2=1 ¬x2+x3=1 … ¬x9+x10=1, где x1,…,x10 – неизвестные логические величины

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

• 10
• 13
• 11
• 15

Найдите наименьшее общее кратное (НОК) для чисел 234 и 221.

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

• 3891
• 3978
• 3913
• 3984

Обозначение ∅ используется для … множества.

Тип ответа: Текcтовый ответ

Операция, обозначаемая символом ¬, называется ...

Тип ответа: Текcтовый ответ

Операция, обозначаемая символом ∧, называется ...

Тип ответа: Текcтовый ответ

Ординал ω + 1 обозначает:

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

• Сумму первого предельного ординала и единицы
• Наименьший ординал, больший всех натуральных чисел
• Произведение первого предельного ординала и единицы
• Множество всех натуральных чисел

Ординалы - это:

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

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

Основной вывод из проблемы остановки состоит в том, что:

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

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

Отношение "делится на" является примером отношения:

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

• Эквивалентности
• Частичного порядка
• Линейного порядка
• Полного порядка

Отношение "сравнимы по модулю n" является примером отношения:

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

• Эквивалентности
• Частичного порядка
• Линейного порядка
• Полного порядка

Отношение R на множестве A называется ..., если для любого a из A, aRa.

Тип ответа: Текcтовый ответ

Отношение R на множестве A называется ..., если для любых a, b из A, таких что aRb и bRa, следует, что a = b.

Тип ответа: Текcтовый ответ

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

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

• Соответствуют несчетным множествам
• Не имеют непосредственного предшественника
• Равны нулю
• Являются конечными

При поиске в глубину, если граф содержит циклы, какое утверждение верно?

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

• Алгоритм завершится с ошибкой
• Алгоритм может посетить некоторые вершины более одного раза
• Алгоритм посетит каждую вершину ровно один раз
• Алгоритм не сможет обойти все вершины

Принцип работы алгоритма Евклида основан на свойстве, что НОД(a, b) = НОД(b, r), где r обозначает ... от деления a на b.

Тип ответа: Текcтовый ответ

Проблема остановки важна потому, что она:

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

• позволяет оптимизировать программы
• показывает существование пределов алгоритмической вычислимости
• демонстрирует, как исправлять ошибки в программном коде
• обеспечивает основу для создания искусственного интеллекта

Проблема остановки демонстрирует, что:

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

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

Проблема остановки иллюстрирует, что:

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

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

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

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

• Может ли программа решить любую математическую задачу?
• Может ли программа выполниться за конечное время?
• Можно ли определить, завершится ли программа или будет выполняться бесконечно, используя другую программу?
• Можно ли создать программу, которая исправляет ошибки в других программах?

Разность множеств A и B (A B) состоит из элементов,

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

• принадлежащих и A, и B
• принадлежащих A или B
• принадлежащих A, но не B
• принадлежащих B, но не A

Рассмотрим граф G с 15 вершинами и 8 ребрами. Какое максимальное количество ребер может быть добавлено в граф G, чтобы он не содержал циклов?

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

• 6
• 7
• 8
• 9

Рассмотрим граф G с 8 вершинами. Каждая вершина имеет степень 4. Сколько компонент связности содержит граф G?

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

• 1
• 2
• 4
• 8

Рассмотрим числа от 1 до 100. Сколько существует чисел, которые не делятся на 2, 3 и 5?

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

• 26
• 28
• 30
• 32

Рома хочет узнать, какая погода будет завтра. В прогнозе погоды он услышал несколько высказываний: Если не будет ветра, то будет пасмурная погода без дождя. Если будет дождь, то будет пасмурно и без ветра. Если будет пасмурная погода, то будет дождь и не будет ветра. Определите, какая погода будет завтра.

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

• Пасмурно, дождь, без ветра
• Ясно, без дождя, ветер
• Ясно, дождь, без ветра
• Пасмурно, без дождя, ветер

Сколько компонент сильной связности у данного графа? @13.jpg

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

• 1
• 2
• 3
• 4

Сколько компонент сильной связности у данного графа? @3.jpg 

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

• 1
• 2
• 3
• 4

Структура данных, используемая для хранения вершин, еще не успевших получить свой уровень в алгоритме поиска в ширину, называется ...

Тип ответа: Текcтовый ответ

Существует ... функция, принимающая только значения 0 и 1 и не имеющая всюду определённого вычислимого продолжения.

Тип ответа: Текcтовый ответ

Теорема … гласит, что мощность множества всех подмножеств любого множества A больше мощности самого множества A.

Тип ответа: Текcтовый ответ

Теорема Кантора утверждает, что множество всех подмножеств множества A имеет … мощность, чем само множество A.

Тип ответа: Текcтовый ответ

Теорема Цермело утверждает, что любое множество может быть вполне ….

Тип ответа: Текcтовый ответ

Теорема Цермело утверждает, что:

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

• Любое множество счетно
• Любое множество может быть вполне упорядочено
• Любое множество имеет максимальный элемент
• Любое множество имеет минимальный элемент

Теорему о том, что любое множество можно вполне упорядочить, можно доказать с помощью леммы ...

Тип ответа: Текcтовый ответ

Трансфинитная ... может быть использована для алгоритмического построения множеств с любым порядковым типом.

Тип ответа: Текcтовый ответ

Тьюринг доказал, что проблема остановки:

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

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

Укажите наименьшее натуральное число, которое дает остаток 3 при делении на 4, остаток 4 при делении на 5 и остаток 5 при делении на 6.

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

• 41
• 51
• 59
• 63

Установите соответствие между выражениями и их значениями по модулю 10:

Тип ответа: Сопоставление

• A. 5·99
• B. 9600
• C. 100000
• D. НОД(123456, 654321)
• E. 5
• F. 1
• G. 0
• H. 3

Установите соответствие между криптографическими понятиями и их описаниями:

Тип ответа: Сопоставление

• A. Шифр Цезаря
• B. Симметричное шифрование
• C. Асимметричное шифрование
• D. Хеш-функция
• E. Простейший метод шифрования путем сдвига букв алфавита
• F. Использует один и тот же ключ для шифрования и дешифрования
• G. Использует разные ключи для шифрования и дешифрования
• H. Преобразует произвольный объем данных в строку фиксированной длины

Установите соответствие между логическими операциями и их обозначениями:

Тип ответа: Сопоставление

• A. Конъюнкция
• B. Дизъюнкция
• C. Импликация
• D. Эквивалентность
• E. ∧
• F. ∨
• G. →
• H. ↔

Установите соответствие между понятиями и их описаниями:

Тип ответа: Сопоставление

• A. Проблема остановки
• B. Вычислимая функция
• C. Неразрешимая задача
• D. Алгоритм
• E. Вопрос о возможности определения, завершится ли выполнение программы на любых входных данных.
• F. Функция, для которой существует алгоритм, вычисляющий её значение для любого входного значения.
• G. Задача, для которой невозможно создать алгоритм, решающий её для всех возможных входных данных.
• H. Описание последовательности действий для решения задачи.

Установите соответствие между понятиями и их определениями:

Тип ответа: Сопоставление

• A. Вычислимая функция
• B. Перечислимое множество
• C. Разрешимое множество
• D. Функция, для которой существует алгоритм, вычисляющий её значение для любого аргумента из области определения
• E. Множество, элементы которого можно перечислить алгоритмически
• F. Множество, для которого существует алгоритм, определяющий принадлежность любого элемента этому множеству

Установите соответствие между понятиями и их определениями:

Тип ответа: Сопоставление

• A. Делимость
• B. Взаимно простые числа
• C. Простое число
• D. Свойство одного числа быть кратным другому без остатка
• E. Числа, имеющие только один общий делитель - единицу
• F. Число, имеющее ровно два различных натуральных делителя: единицу и само себя

Установите соответствие между понятиями и их определениями:

Тип ответа: Сопоставление

• A. Порядковый тип
• B. Предельный ординал
• C. Мощность множества
• D. Упорядоченное множество
• E. Класс эквивалентности вполне упорядоченных множеств по изоморфности
• F. Ординал, не имеющий непосредственного предшественника
• G. Класс эквивалентности множеств по биективности
• H. Множество, каждый элемент которого имеет следующий за ним элемент

Установите соответствие между понятиями и их определениями:

Тип ответа: Сопоставление

• A. Простое число
• B. Составное число
• C. Взаимно простые числа
• D. Число, имеющее ровно два различных натуральных делителя: единицу и само себя
• E. Число, имеющее более двух натуральных делителей
• F. Числа, имеющие только один натуральный общий делитель - единицу

Установите соответствие между понятиями и их определениями:

Тип ответа: Сопоставление

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

Установите соответствие между понятиями и их определениями:

Тип ответа: Сопоставление

• A. Универсальная функция
• B. Перечислимое множество
• C. Неразрешимое множество
• D. Перечислимые неотделимые множества
• E. Функция, способная симулировать работу любого алгоритма на основе его программного кода и входных данных.
• F. Множество, элементы которого могут быть перечислены алгоритмически.
• G. Множество, для которого не существует алгоритма, способного определить принадлежность любого элемента этому множеству.
• H. Множества, для которых не существует алгоритма, способного разделить их элементы на два непересекающихся подмножества.

Установите соответствие между типами графов и их характеристиками:

Тип ответа: Сопоставление

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

Установите соответствие между типами графов и их характеристиками:

Тип ответа: Сопоставление

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

Установите соответствие между типами множеств и их мощностями:

Тип ответа: Сопоставление

• A. Конечное множество
• B. Счетное множество
• C. Континуум
• D. Мощность множества, содержащего 10 элементов
• E. Мощность множества натуральных чисел
• F. Мощность множества действительных чисел

Установите соответствие между уравнениями на множествах и выводами,

Тип ответа: Сопоставление

• A. A ∪ B = B
• B. B ∩ A = ∅
• C. A B = A
• D. A ∩ B = B A
• E. A - подмножество B
• F. Все элементы A и B различны
• G. A - пустое множество
• H. Оба множества A и B пустые

Установите соответствие между элементами языка первого порядка и их ролями:

Тип ответа: Сопоставление

• A. Предикаты
• B. Функциональные символы
• C. Кванторы
• D. Логические операторы
• E. Описывают свойства объектов или отношения между объектами
• F. Используются для построения термов, представляющих объекты
• G. Определяют область значений переменных
• H. Используются для составления одной формулы из нескольких

Утверждение “Неразрешимость проблемы остановки эквивалентна существованию перечислимого множества с неперечислимым дополнением” является следствием из теоремы

Тип ответа: Текcтовый ответ

Учащимся было необходимо написать 3 контрольные работы. Первую или вторую контрольные работы успешно написали 33 учащихся, первую или третью – 31 учащийся, вторую или третью – 32 учащихся. Не менее двух контрольных работ выполнили 20 учащихся. Сколько учащихся успешно решили только одну контрольную работу?

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

• 10
• 28
• 18
• 22

Функция называется вычислимой, если существует …, который ее вычисляет

Тип ответа: Текcтовый ответ

Чем малая теорема Ферма отличается от великой теоремы Ферма?

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

• Малая теорема утверждает, что для любого простого числа существует тройка целых чисел, удовлетворяющая уравнению a^n + b^n = c^n.
• Малая теорема Ферма формулирует свойство простых чисел, а великая теорема Ферма - обобщение на произвольные целые степени.
• Малая теорема Ферма доказывает, что существует бесконечно много простых чисел, а великая теорема Ферма - что все простые числа имеют особое свойство.
• Эти теоремы одинаковы, просто разные названия для одного и того же утверждения.

a … b - остаток при делении а на b

Тип ответа: Текcтовый ответ