Онлайн тесты на тему "Росдистант. Массовая и индивидуальная задачи. Сложность алгоритма. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP. NP-трудные и NP-полные задачи."

Тестовое задание на тему: Массовая и индивидуальная задачи. Сложность алгоритма. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP. NP-трудные и NP-полные задачи.
Тест выполнен на 100%. В тесте 10 вопросов. После оплаты вы сможете скачать готовые ответы по тесту. Так же могу выполнять данную работу индивидуально. Делайте индивидуальный заказ.

Описание работы

1. Массовая и индивидуальная задачи. Сложность алгоритма. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP. NP-трудные и NP-полные задачи.

Укажите два наилучших алгоритма по критерию трудоемкости.
Алгоритм с логарифмической скоростью роста
Алгоритм с линейной скоростью роста
Алгоритм с линейно-логарифмической скоростью роста
Алгоритм с квадратичной скоростью роста

Пусть X — задача из NP. Какое утверждение справедливо для задачи X?
X может быть неразрешима
Если X можно решить за полиномиальное время на ДМТ, то P = NP
Нет полиномиального алгоритма для X
X — NP-трудная задача
Если X — NP-трудная задача, то она NP-полная

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

Алгоритм некоторым образом обрабатывает массив (см. рисунок). Алгоритм состоит из двух вложенных циклов. Как асимптотическая сложность зависит от переменной n?
O(4 * n)
Не зависит от n
O(n)
O((i + j)n)

Какова сложность алгоритма?
O(n)
O(k + n)
O(k(n – 1))
O(k)

Что понимается под временной сложностью алгоритма?
Минимальное количество машинного кода для представления алгоритма в ЭВМ
Функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи данного размера
Максимальное количество машинного кода для представления алгоритма в ЭВМ
Нет верного ответа

Алгоритм F имеет оценку сложности O(n2), а алгоритм G — O(n). Тогда
F может быть быстрее G на любом входе
F может быть медленнее G на любом входе
F может быть таким, что для любого n он делает n2 операций на некотором входе размера n
G может быть таким, что для любого n он делает n2 операций на некотором входе размера n

Алгоритм обрабатывает массив (см. рисунок). Входные данные алгоритма — k, t, n. От каких из перечисленных входных данных зависит время работы алгоритма?
От k, t, n
От k и t
От t и n
От n
Не зависит от входных данных

Рассмотрите программу ниже и определите её сложность.
void function(int n) {
int i, j, count=0;
for (i=n/2; i <= n; i++)
for (j = 1; j <= n; j = j*2)
count++;}
O(log n)
O(n?)
O(n? log n)
O(n log n)

Если f(n) = O(n), то какие оценки верны?
f(n) = O(10n)
f(n) = O(0.001n)
f(n) = O(n + 1000 / n)
f(n) = o(2n + 5)
f(n) = o(n2)
f(n) = o(0.001n3 + 1000)
f(n) = ?(n + 10 / n)
f(n) = ?(n)