Тест по теории алгоритмов
Тест предназначен для студентов ССУЗов, изучающих дисциплину "Теория алгоритмов"
Задание 1
Подберите каждому названию функции его формулу
Задание 2
Из чего состоит Базис Клини?
Задание 3
Сопоставьте верное продолжение:
Задание 4
Выберите пропущенное слово(-а): Рассмотрим равенство f(х)=g(x), где f(х) и g(x) некоторые функции. Когда говорят, что это равенство есть …, то это означает, что равенство рассматривается как неопределенное высказывание, при одних значениях x истинное, при других ложное.
Задание 5
Машина … эквивалентна машине … , если в соответствующие такты их работы лента машины … содержит всю информацию о ленте машины …. Машина … работает гораздо медленнее, т.к. каждый такт … она моделирует несколькими тактами, поэтому мы говорим о соответствующих тактах. Если … остановится, то … тоже остановится и будет содержать всю информацию о машине …. Выберите верную последовательность названий машин Тьюринга , подходящих в данное определение
Задание 6
Рассчитайте степени, в которые были возведены простые числа, произведение которых образует число 540: 540=2x • 3y • 5z
Задание 7
Какого вида доказательств не существует
Задание 8
Пусть имеются две вычислимые арифметические функции f1(x) и f2(x). Построим функцию g(x) = |f1(x) - f2(x)|. Данная функция является арифметической т.к.:
Задание 9
Основная операция при работе алгоритмов Маркова –
Задание 10
Что принято понимать под определением “Эффективно перечислимое множество”
Задание 11
Функция , определенная в одной точке будет иметь данное уравнение. Выберите верное
Задание 12
Из приведенных определений тезиса Черча выберите верное