МОИБ неделя №3

Что такое машина Тьюринга?

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

• Настоящий компьютер, созданный Тьюрингом

• Устройство для шифрования

• Программа для работы с числами

Что описывает класс P?

• Множество задач, решаемых за экспоненциальное время

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

• Множество неразрешимых задач

• Множество задач, решаемых вероятностными методами

Класс NP включает:

• Только задачи, которые нельзя проверить

• Только неразрешимые задачи

• Задачи, решение которых можно проверить за полиномиальное время

• Только задачи линейной сложности

Что значит NP-полная (NPC) задача?

• Ее решение невозможно

• Она проще всех NP-задач

• Она не проверяется алгоритмически

• Она сводима ко всем NP-задачам и является самой сложной в классе NP

Какой пример NP-полной задачи?

• Умножение чисел

• Задача коммивояжера

• Сложение чисел

• Сортировка массива

Что такое простое число?

• Число, делящееся только на 2

• Число, не имеющее делителей, кроме 1 и самого себя

• Любое нечетное число

• Число, у которого четная сумма цифр

Составное число — это:

• Число, не имеющее делителей

• Число, делящееся на 1 и себя

• Число, имеющее более двух делителей

• Число, равное квадрату простого

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

• 4

• 6

• 12

• 18

Как называется алгоритм нахождения НОД?

• Алгоритм Флойда

• Алгоритм Евклида

• Алгоритм Кнута

• Алгоритм Дейкстры

В чем суть алгоритма Евклида?

• В нахождении суммы чисел

• В последовательном вычитании/делении с остатком

• В разложении числа на простые множители

• В сортировке массива чисел