- Модуль 1. Интро
- Модуль 2. Начала теории множеств
- Модуль 3. Логика и алгоритмы
- Модуль 4. Введение в теорию чисел
- Модуль 5. Графы и деревья
- Итоговая аттестация
- Анкета обратной связи
... обладает носителем и значениями для символов предикатов и функций.
Тип ответа: Текcтовый ответ
Аксиома выбора необходима для доказательства существования:
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Наименьшего элемента в любом множестве
- Базиса Гамеля в векторном пространстве
- Наибольшего общего делителя двух чисел
- Предела последовательности
Аксиома выбора необходима для доказательства:
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Теоремы о существовании предела последовательности
- Теоремы о существовании базиса в любом векторном пространстве
- Теоремы Пифагора
- Основной теоремы алгебры
Аксиома выбора утверждает, что для любого семейства непустых множеств существует такая функция выбора, что она выбирает ровно один элемент из каждого множества. Это утверждение:
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Верно только для конечных множеств
- Верно для любых множеств
- Неверно
- Верно только для счетных множеств
Алгоритм ... можно интерпретировать как модифицированный алгоритм поиска в ширину, где взешенное ребро заменяется на путь из нескольких ребер.
Тип ответа: Текcтовый ответ
Алгоритм Дейкстры можно интерпретировать как модифицированный алгоритм поиска в ..., где взешенное ребро заменяется на путь из нескольких ребер.
Тип ответа: Текcтовый ответ
Алгоритм Евклида основан на использовании деления с ...
Тип ответа: Текcтовый ответ
Арифметика ординалов включает операции:
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Сложение
- Умножение
- Возведение в степень
- Вычитание
Базис Гамеля - это максимальное линейно ... независимое подмножество векторного пространства
Тип ответа: Текcтовый ответ
Бинарное отношение, которое является рефлексивным, симметричным и транзитивным, называется отношением ...
Тип ответа: Текcтовый ответ
В графе G с 7 вершинами каждая вершина соединена с двумя другими вершинами. Сколько ребер содержит этот граф?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
В графе, представленном матрицей смежности, элемент aij равен 0, если между вершинами i и j ...
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- существует путь
- существует ребро
- не существует пути
- не существует ребра
В интервале от 1 до 1000 найдите количество чисел, которые делятся на 4 или 6, но не делятся на 12.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
В языках первого порядка, формула ∃x (P(x) ∧ Q(x)) означает, что
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- существует такой x, что P(x) и Q(x) оба истинны.
- для каждого x, P(x) и Q(x) оба истинны.
- существует такой x, что P(x) истинно, но Q(x) ложно.
- ни одно из вышеуказанных.
Выберете все свойства, верные для отношения "сравнимы по модулю 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 ячейках, то по крайней мере одна ячейка содержит более одного объекта
- Принцип Дирихле применим только к бесконечным множествам
- Множество всех подмножеств данного множества имеет большую мощность, чем само множество
- Мощность множества всех подмножеств натуральных чисел равна мощности множества натуральных чисел
Высказывание "Если сегодня идет дождь, то я возьму зонт" является примером логической операции ...
Тип ответа: Текcтовый ответ
Говорят, что множество A содержится в множестве B, если каждый элемент A … B.
Тип ответа: Текcтовый ответ
Диаграмма Венна используется для
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- решения систем линейных уравнений
- быстрого возведения числа в степень
- установления соответствия между множествами
- объединения множеств точек в геометрические фигуры
Для чисел 1920 и 1080 НОД равен ...
Тип ответа: Текcтовый ответ
Если a ≡ b (mod m), то числа a и b имеют одинаковый ... при делении на m. Это утверждение является определением сравнения по модулю m
Тип ответа: Текcтовый ответ
Индуктивные определения используются для:
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Определения мощности множеств
- Построения ординалов
- Доказательства теорем в линейной алгебре
- Решения дифференциальных уравнений
Как называется граф, в котором между любыми двумя вершинами существует не более одного пути?
Тип ответа: Текcтовый ответ
Какие из следующих утверждений верно относительно леммы Цорна?
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Она необходима для доказательства теоремы Пифагора
- Она противоречит аксиоме выбора
- Она эквивалентна теореме Цермело
- Она используется для доказательства существования базиса Гамеля
Какие из следующих утверждений верны в контексте основной теоремы арифметики?
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Основная теорема арифметики выполняется для многочленов с вещественными коэффициентами
- Любое натуральное число, большее 1, можно представить в виде произведения простых чисел
- Лемма о разложении единицы не может быть использована для доказательства ОТА
- Любое натуральное число можно представить в виде произведения составных чисел
Какие из следующих утверждений верны для всех частично упорядоченных множеств?
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Не все элементы множества обязательно сравнимы между собой
- Существует единственный наименьший элемент множества
- Каждый элемент множества сравним сам с собой
- Существует единственный наибольший элемент множества
Какие из следующих утверждений верны для деревьев?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Дерево - это граф, в котором любые две вершины соединены ровно одним путем
- Дерево - это связный граф без циклов
- Дерево - это граф, содержащий хотя бы один цикл
- Дерево - это граф, в котором есть хотя бы одна изолированная вершина
Какие из следующих утверждений верны для термов в языках первого порядка?
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Термы используются для представления объектов.
- Термы могут содержать только константы.
- Термы могут быть построены с использованием переменных и функциональных символов.
- Термы используются для представления логических операций.
Какие из следующих утверждений верны относительно аксиомы выбора?
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Она эквивалентна лемме Цорна
- Она эквивалентна теореме Цермело
- Она противоречит теореме Цермело
- Она не следует из леммы Цорна
Какие из следующих утверждений верны?
Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов
- Любое простое число делится на 3
- Если a и b взаимно простые, то НОД(a, b) = 1
- Любое составное число делится на простое число
- Если a делится на b и b делится на c, то a делится на c
Какое из следующих утверждений верно для вычислимых функций?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Все функции, определенные на множестве натуральных чисел, являются вычислимыми.
- Вычислимая функция может быть реализована алгоритмом.
- Любая вычислимая функция является непрерывной.
- Все вычислимые функции являются линейными.
Какое из следующих утверждений верно для интерпретаций в языках первого порядка?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Интерпретация - синоним понятия тавтология.
- Интерпретация обладает носителем и значениями для символов предикатов и функций.
- Интерпретация позволяет изменять значения логических переменных.
- Интерпретация используется для определения синтаксиса языка.
Какое из следующих утверждений верно для любых целых чисел a и b, где b ≠ 0?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- НОД(a, b) = a·b
- НОД(a, b) = НОД(b, a mod b)
- НОД(a, b) = a + b
- НОД(a, b) = a - b
Какое из следующих утверждений верно для ориентированных графов?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- В ориентированном графе не может быть циклов
- В ориентированном графе рёбра имеют направление
- В ориентированном графе каждая вершина соединена ребром с каждой другой вершиной
- В ориентированном графе не может быть петель
Какое из следующих утверждений верно для отношения эквивалентности?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Отношение эквивалентности всегда антисимметрично
- Отношение эквивалентности всегда рефлексивно
- Отношение эквивалентности не требует симметричности
- Отношение эквивалентности не может быть транзитивным
Какое из следующих утверждений верно для формул в языках первого порядка?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Формулы могут содержать только константы и переменные.
- Формулы могут содержать переменные, кванторы, предикаты и функциональные символы.
- Формулы не могут содержать кванторы.
- Формулы ограничены использованием только логических операций.
Какое из следующих утверждений верно?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Мощность множества всех подмножеств данного множества всегда больше мощности самого множества
- Все бесконечные множества имеют одинаковую мощность
- Мощность множества действительных чисел равна мощности множества натуральных чисел
- Мощность множества целых чисел меньше мощности множества натуральных чисел
Какое из следующих утверждений верно?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Простое число больше 2 всегда нечетно
- Все четные числа являются составными
- Все составные числа делятся на простые числа без остатка
- Все простые числа делятся на 2 без остатка
Какое из следующих чисел является простым?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Какое из этих свойств не присуще отношению линейного порядка?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- рефлексивность
- симметричность
- транзитивность
- антисимметричность
Какое из этих свойств не присуще отношению эквивалентности?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- рефлексивность
- симметричность
- транзитивность
- антисимметричность
Какое свойство базиса Гамеля делает его особенно полезным для линейной алгебры?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Все векторы базиса Гамеля имеют одинаковую длину.
- Базис Гамеля всегда образует ортонормированную систему.
- Векторы базиса Гамеля могут быть умножены только на скаляры.
- Базис Гамеля всегда содержит нулевой вектор.
Какой алгоритм не используется непосредственно в криптографии?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Алгоритм Евклида
- Алгоритм быстрой сортировки
- Алгоритм RSA
- Алгоритм Диффи–Хеллмана
Какой алгоритм позволяет определить, есть ли в ориентированном графе цикл?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Алгоритм Флойда-Уоршелла
- Алгоритм поиска в глубину
- Алгоритм Беллмана-Форда
- Алгоритм Косарайю
Какой аспект алгоритма поиска в глубину позволяет определить компоненты сильной связности в ориентированном графе?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Поиск кратчайшего пути
- Определение обратных ребер
- Использование внешнего стека для хранения вершин
- Сортировка вершин по времени завершения
Какой из следующих вариантов лучше всего описывает принцип работы алгоритма поиска в глубину?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Посещает соседнюю вершину, затем переходит к следующей соседней вершине на том же уровне
- Переходит к следующей вершине, достижимой из текущей, и продолжает так до тех пор, пока не достигнет тупика
- Посещает все вершины на одном уровне, прежде чем перейти на следующий уровень
- Использует случайный выбор следующей вершины для посещения
Какой метод используется для доказательства равномощности двух бесконечных множеств?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Метод математической индукции
- Построение взаимно однозначного соответствия
- Принцип Дирихле
- Метод диагонали Кантора
Какой метод может быть использован для доказательства свойств ординалов?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Метод наименьших квадратов
- Трансфинитная индукция
- Принцип Дирихле
- Диагональный метод Кантора
Какой метод является основой для генерации ключей в схеме Диффи–Хеллмана?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Факторизация
- Возведение в степень
- Хеширование
- Симметричное шифрование
Квантор ... обозначается символом ∀ и означает, что утверждение верно для всех элементов.
Тип ответа: Текcтовый ответ
Квантор всеобщности в языках первого порядка обозначается символом ... и используется для указания, что утверждение верно для всех объектов домена.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Квантор существования в языках первого порядка обозначается символом ... и используется для указания, что существует хотя бы один объект, удовлетворяющий условию.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Компактные … часто рассматриваются в контексте леммы Цорна
Тип ответа: Текcтовый ответ
Лемма Цорна утверждает, что если в частично упорядоченном множестве каждая цепь имеет верхнюю грань, то существует максимальный … элемент.
Тип ответа: Текcтовый ответ
Логическая операция, подразумевающая логическое ИЛИ, называется ...
Тип ответа: Тек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товый ответ
Найдите количество решений системы уравнений: ¬x1+x2=1 ¬x2+x3=1 … ¬x9+x10=1, где x1,…,x10 – неизвестные логические величины
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Обозначение ∅ используется для … множества.
Тип ответа: Тек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, чтобы он не содержал циклов?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Рассмотрим числа от 1 до 100. Сколько существует чисел, которые не делятся на 2, 3 и 5?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Рома хочет узнать, какая погода будет завтра. В прогнозе погоды он услышал несколько высказываний: Если не будет ветра, то будет пасмурная погода без дождя. Если будет дождь, то будет пасмурно и без ветра. Если будет пасмурная погода, то будет дождь и не будет ветра. Определите, какая погода будет завтра.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Пасмурно, дождь, без ветра
- Ясно, без дождя, ветер
- Ясно, дождь, без ветра
- Пасмурно, без дождя, ветер
Сколько компонент сильной связности у данного графа? @3.jpg
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Структура данных, используемая для хранения вершин, еще не успевших получить свой уровень в алгоритме поиска в ширину, называется ...
Тип ответа: Текcтовый ответ
Существует ... функция, принимающая только значения 0 и 1 и не имеющая всюду определённого вычислимого продолжения.
Тип ответа: Текcтовый ответ
Теорема … гласит, что мощность множества всех подмножеств любого множества A больше мощности самого множества A.
Тип ответа: Текcтовый ответ
Теорема Кантора утверждает, что множество всех подмножеств множества A имеет … мощность, чем само множество A.
Тип ответа: Текcтовый ответ
Теорема Цермело утверждает, что любое множество может быть вполне ….
Тип ответа: Текcтовый ответ
Теорема Цермело утверждает, что:
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Любое множество счетно
- Любое множество может быть вполне упорядочено
- Любое множество имеет максимальный элемент
- Любое множество имеет минимальный элемент
Теорему о том, что любое множество можно вполне упорядочить, можно доказать с помощью леммы ...
Тип ответа: Текcтовый ответ
Трансфинитная ... может быть использована для алгоритмического построения множеств с любым порядковым типом.
Тип ответа: Текcтовый ответ
Тьюринг доказал, что проблема остановки:
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- неразрешима
- разрешима для некоторых специальных случаев
- разрешима для всех возможных программ
- не была полностью исследована
Установите соответствие между выражениями и их значениями по модулю 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. Числа, имеющие только один натуральный общий делитель - единицу
Установите соответствие между понятиями и их определениями:
Тип ответа: Сопоставление
- 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. Используются для составления одной формулы из нескольких
Учащимся было необходимо написать 3 контрольные работы. Первую или вторую контрольные работы успешно написали 33 учащихся, первую или третью – 31 учащийся, вторую или третью – 32 учащихся. Не менее двух контрольных работ выполнили 20 учащихся. Сколько учащихся успешно решили только одну контрольную работу?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Функция называется вычислимой, если существует …, который ее вычисляет
Тип ответа: Текcтовый ответ
Чем малая теорема Ферма отличается от великой теоремы Ферма?
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Малая теорема утверждает, что для любого простого числа существует тройка целых чисел, удовлетворяющая уравнению a^n + b^n = c^n.
- Малая теорема Ферма формулирует свойство простых чисел, а великая теорема Ферма - обобщение на произвольные целые степени.
- Малая теорема Ферма доказывает, что существует бесконечно много простых чисел, а великая теорема Ферма - что все простые числа имеют особое свойство.
- Эти теоремы одинаковы, просто разные названия для одного и того же утверждения.
a … b - остаток при делении а на b
Тип ответа: Текcтовый ответ