Тест по теории алгоритмов

Тест предназначен для студентов ССУЗов, изучающих дисциплину "Теория алгоритмов"

Задание 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

Из приведенных определений тезиса Черча выберите верное