WorksheetsМОИБ неделя №3
Total questions: 25
Worksheet time: 13mins
Что такое машина Тьюринга?
Модель вычислительной машины, формализующая понятие алгоритма
Настоящий компьютер, созданный Тьюрингом
Устройство для шифрования
Программа для работы с числами
Что описывает класс P?
Множество задач, решаемых за экспоненциальное время
Множество задач, решаемых за полиномиальное время
Множество неразрешимых задач
Множество задач, решаемых вероятностными методами
Класс NP включает:
Только задачи, которые нельзя проверить
Только неразрешимые задачи
Задачи, решение которых можно проверить за полиномиальное время
Только задачи линейной сложности
Что значит NP-полная (NPC) задача?
Ее решение невозможно
Она проще всех NP-задач
Она не проверяется алгоритмически
Она сводима ко всем NP-задачам и является самой сложной в классе NP
Какой пример NP-полной задачи?
Умножение чисел
Задача коммивояжера
Сложение чисел
Сортировка массива
Что такое простое число?
Число, делящееся только на 2
Число, не имеющее делителей, кроме 1 и самого себя
Любое нечетное число
Число, у которого четная сумма цифр
Составное число — это:
Число, не имеющее делителей
Число, делящееся на 1 и себя
Число, имеющее более двух делителей
Число, равное квадрату простого
Наибольший общий делитель (НОД) чисел 24 и 36 равен:
4
6
12
18
Как называется алгоритм нахождения НОД?
Алгоритм Флойда
Алгоритм Евклида
Алгоритм Кнута
Алгоритм Дейкстры
В чем суть алгоритма Евклида?
В нахождении суммы чисел
В последовательном вычитании/делении с остатком
В разложении числа на простые множители
В сортировке массива чисел
Что означает операция a mod n?
Деление a на n с округлением
Нахождение остатка от деления a на n
Умножение a и n
Возведение a в степень n
Если 17 mod 5 = ?
2
3
4
1
Какое свойство верно для модульной арифметики?
(a + b) mod n = (a mod n + b mod n) mod n
(a + b) mod n = a + b
(a × b) mod n = a + b
Вычет не может быть равен 0
В криптографии модульная арифметика используется для:
Генерации случайных чисел
Шифрования и дешифрования сообщений
Ускорения работы процессора
Проверки четности чисел
Что такое открытый ключ в криптографии?
Секретный параметр, известный только владельцу
Параметр, доступный всем для шифрования
Случайная последовательность бит
Пароль пользователя
Что такое секретный параметр в криптографии?
Секретный параметр, известный только владельцу
Параметр, доступный всем для шифрования
Случайная последовательность бит
Пароль пользователя
Что такое закрытый ключ?
Ключ, известный всем
Ключ, используемый для шифрования
Ключ, известный только владельцу
Любое простое число
Какое из чисел простое? 21, 29, 33, 35
21
29
33
35
Если a ≡ b (mod n), то:
a и b равны
a и b дают одинаковый остаток при делении на n
a = b × n
a и b — простые
Какое число простое
39
45
41
49
Что означает "полиномиальная сложность алгоритма"?
Алгоритм работает за время, растущее как многочлен от размера входных данных
Алгоритм имеет случайный результат
Алгоритм работает за экспоненциальное время
Алгоритм не имеет конечного времени работы
Что значит "экспоненциальная сложность"?
Время работы растет медленно
Время растет как kⁿ
Алгоритм выполняется мгновенно
Сложность не зависит от входных данных
Что является примером задачи из класса P?
Сортировка массива
Задача раскраски графа
NP-полная задача
Доказательство теорем
Почему простые числа важны в криптографии?
Потому что они легко находятся
Потому что они позволяют строить трудные для подбора задачи
Потому что их бесконечно много
Потому что они нечётные
Наибольший общий делитель (НОД) чисел 120 и 236 равен
4
6
8
2
