💯Высшая математика Модуль 1- 5

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

Выберите все утверждения, верные для любых множеств
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A (B ∪ C) = (A B) ∪ (A C)
A B = B A
A ∩ B = B ∩ A

Какие из следующих множеств являются перечислимыми?
Множество всех простых чисел
Множество всех четных чисел
Множество всех непрерывных функций на отрезке [0, 1]
Множество всех иррациональных чисел

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

Установите соответствие между уравнениями на множествах и выводами,
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 пустые

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

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

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

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

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

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

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

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

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

В языках первого порядка, формула ∃x (P(x) ∧ Q(x)) означает, что
существует такой x, что P(x) и Q(x) оба истинны.
для каждого x, P(x) и Q(x) оба истинны.
существует такой x, что P(x) истинно, но Q(x) ложно.
ни одно из вышеуказанных.

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

Какие из следующих пар высказываний являются эквивалентными?
p → q, ¬q → ¬p
p ∧ q, p ∨ q
p ∨ q, ¬p → q
p ∧ q, ¬p ∨ ¬q

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

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

Как расшифровывается аббревиатура RSA?
Rivest, Shamir, Adleman
Rickert, Shaviro, Agamben
Rousseau, Spinoza, Aquinas
Russell, Sartre, Arendt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выберете все свойства, верные для отношения "сравнимы по модулю n":
Рефлектсивность
Симметричность
Антисимметричность
Транзитивность

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

Какое из следующих утверждений верно для любых целых чисел a и b, где b ≠ 0?
НОД(a, b) = a·b
НОД(a, b) = НОД(b, a mod b)
НОД(a, b) = a + b
НОД(a, b) = a - b

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

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

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

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

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

Какой алгоритм позволяет определить, есть ли в ориентированном графе цикл?
Алгоритм Флойда-Уоршелла
Алгоритм поиска в глубину
Алгоритм Беллмана-Форда
Алгоритм Косарайю

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

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

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

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

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

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

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

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

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

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

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

Выберите все верные утверждения относительно импликации:
p → q эквивалентно ¬p ∨ q
p → q эквивалентно p ∧ ¬q
p → q эквивалентно ¬q → ¬p
p → q эквивалентно q → p

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

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

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

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

Отношение "делится на" является примером отношения:
Эквивалентности
Частичного порядка
Линейного порядка
Полного порядка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Какие из следующих утверждений верны?
Любое простое число делится на 3
Если a и b взаимно простые, то НОД(a, b) = 1
Любое составное число делится на простое число
Если a делится на b и b делится на c, то a делится на c

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

Отношение "сравнимы по модулю n" является примером отношения:
Эквивалентности
Частичного порядка
Линейного порядка
Полного порядка

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

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

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

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

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

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

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

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

Арифметика ординалов включает операции:
Сложение
Умножение
Возведение в степень
Вычитание

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

Выберите все верные утверждения, связанные с малой теоремой Ферма:
Если 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)

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

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

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

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

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

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

Установите соответствие между логическими операциями и их обозначениями:
A. Конъюнкция
B. Дизъюнкция
C. Импликация
D. Эквивалентность
E. ∧
F. ∨
G. →
H. ↔

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

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

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

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

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

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

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

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

Выберите все верные утверждения относительно арифметики остатков:
Если 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 имеют одинаковый остаток при делении на m. Это утверждение является определением сравнения по ... m

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

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

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

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

Понятие "предельный ординал" используется для описания ординалов, которые:
Соответствуют несчетным множествам
Не имеют непосредственного предшественника
Равны нулю
Являются конечными

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

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

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

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

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

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

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

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

Установите соответствие между выражениями и их значениями по модулю 10:
A. 5·99
B. 9600
C. 100000
D. НОД(123456, 654321)
E. 5
F. 1
G. 0
H. 3

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

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

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

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

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

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

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

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

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

Выберите все верные утверждения относительно арифметики остатков:
Если 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

Какие из следующих утверждений верны?
Если a делится на b, то a = b·k, где k - целое число
Если a делится на b, то b делится на a
Если a и b взаимно простые числа, то НОД(a, b) = 1
Если a делится на b, то a + b делится на b

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

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

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

Какой метод является основой для генерации ключей в схеме Диффи–Хеллмана?
Факторизация
Возведение в степень
Хеширование
Симметричное шифрование

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

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

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

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

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

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

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

Какое утверждение верно для схемы шифрования RSA?
Открытый и закрытый ключи идентичны
Открытый ключ используется для шифрования, а закрытый — для дешифрования
Закрытый ключ используется для шифрования и дешифрования
Открытый ключ используется для дешифрования, а закрытый — для шифрования

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

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

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

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

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

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