1. На входе размера n алгоритм со сложностью f не может выполнить более f(n) "элементарных" операций 1 балл

Верно

Неверно

2. f(n) — это сложность некоторого алгоритма F. Тогда... 1 балл

На любом входе размера n алгоритм F выполнит в точности f(n) "элементарных" операций.

На любом входе размера n алгоритм F выполнит менее f(n) "элементарных" операций.

Существует некоторый вход размера n, на котором алгоритм F выполнит в точности f(n) "элементарных" операций.

Существует некоторый вход размера n, на котором алгоритм F выполнит менее f(n) "элементарных" операций.

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

Нет, только алгоритмы работы со строками

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

4. Алгоритм принимает на вход два числа N и M. Какой размер его входа согласно теории алгоритмов? 1 балл

N+M

N \times M

\log_{10} N + \log_{10} M

Зависит от выбранного алфавита и способа кодирования входа