Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 5
Основы теории вычислимых функций - тест 5
Упражнение 1:
Номер 1
Если U
- главная вычислимая универсальная функция для класса вычислимых одноместных функций, то существует для произвольной вычислимой одноместной функции h
:
Ответ:
 (1) Un=Uh(n)
 
 (2) Uh=Un(h)
 
 (3) U(h(n))n=U
 
Номер 2
Теорема Клини о неподвижной точке:
Ответ:
 (1) все программы эквивалентно преобразуемы друг к другу 
 (2) есть алгоритм преобразования программы к ней эквивалентной 
 (3) нет алгоритма преобразования программы к ней эквивалентной 
Номер 3
Программа, печатающая свой текст:
Ответ:
 (1) реализуема на всех современных процедурных языках 
 (2) нереализуема ни на одном процедурном языке 
 (3) реализуема только в "рекурсивных" языках (например, Рефал) 
Упражнение 2:
Номер 1
Если U(n,x)
- главная вычислимая универсальная функция для класса всех вычислимых одноместных функций, то тогда:
Ответ:
 (1) для всех x
существует p: U(p,x)=p
 
 (2) существует одно лишь x
и одно лишь p: U(p,x)=p
 
 (3) не для всех x
существует p: U(p,x)=p
 
Номер 2
Существует ли Паскаль-программа, инвертирующая свой текст?
Ответ:
 (1) да 
 (2) нет 
 (3) да, но только для задач обработки текстов 
Номер 3
Существуют ли Паскаль-программы А
и В
, печатающие, соответственно, тексты В
и А
?
Ответ:
 (1) да 
 (2) нет 
 (3) да, но только для задач обработки текстов 
Упражнение 3:
Номер 1
Какая программа печатает свой текст?
Ответ:
 (1) Паскаль: Writeln('Writeln');
 
 (2) Бейсик: 10 LIST
 
 (3) Паскаль: End.
 
Номер 2
Если программа на каждом входе зацикливается, то для неё:
Ответ:
 (1) справедлив принцип неподвижной точки 
 (2) не справедлив принцип неподвижной точки 
 (3) некорректен входной набор 
Номер 3
Теорема о неподвижной точке называется также теоремой:
Ответ:
 (1) о рекурсии 
 (2) об итерации 
 (3) стабильности 
Упражнение 4:
Номер 1
Теорема о неподвижной точке гарантирует существование:
Ответ:
 (1) хотя бы одной неподвижной точки 
 (2) единственной всегда неподвижной точки 
 (3) счетного множества неподвижных точек 
Номер 2
Если преобразователь программ вычислимо зависит от некоторого параметра, то:
Ответ:
 (1) неподвижная точка вычислимо зависима от параметра 
 (2) неподвижная точка вычислимо независима от параметра 
 (3) не вычислима неподвижная точка 
Номер 3
По любой вычислимой функции можно указать:
Ответ:
 (1) бесконечно много неподвижных точек 
 (2) лишь конечное множество неподвижных точек 
 (3) бесконечно много точек, где не определена функция 
Упражнение 5:
Номер 1
Два главных универсальных множества для класса перечислимых подмножеств N
:
Ответ:
 (1) вычислимо изоморфны 
 (2) вычислимо не изоморфны 
 (3) совпадают 
Номер 2
Множество А
является I
-соответствующей множеству В
, если:
Ответ:
 (1) В
- образ А
при биекции I
 
 (2) В
- прообраз А
при биекции I
 
 (3) биекция I
переводит любое подмножество А
в В
 
Номер 3
В языке Паскаль существует ряд программ Pi
, i=1,2,…,n
таких, что:
Ответ:
 (1) каждая предыдущая в ряде может печатать следующую 
 (2) каждая следующая в ряде печатает предыдущую 
 (3) каждая предыдущая не сможет напечатать предыдущую 
Упражнение 6:
Номер 1
Структура на множестве X
- это отношение типа:
Ответ:
 (1) упорядочивания. 
 (2) транзитивное 
 (3) рефлексивное 
Номер 2
Отношение эквивалентности - это отношение:
Ответ:
 (1) транзитивное, рефлексивное, симметричное 
 (2) не транзитивное, рефлексивное, симметричное 
 (3) транзитивное, не рефлексивное, симметричное 
Номер 3
Отношение эквивалентности - это всегда отношение:
Ответ:
 (1) классифицирующее 
 (2) не классифицирующее 
 (3) над декартовым произведением 
Упражнение 7:
Номер 1
Если X=[-2;5]
, Y=[0;2]
, то будет:
Ответ:
 (1) числовой функцией 
 (2) множеством 
 (3) отображением 
Номер 2
Если X=[0;3]
, Y=[3;0]
, то будет:
Ответ:
 (1) числом 
 (2) отображением 
 (3) множеством 
Номер 3
Соответствие - это:
Ответ:
 (1) порядок 
 (2) отображение 
 (3) множество 
Упражнение 8:
Номер 1
Отношение "" является:
Ответ:
 (1) симметричным, рефлексивным, транзитивным 
 (2) симметричным, нерефлексивным, транзитивным 
 (3) несимметричным, нерефлексивным, транзитивным 
Номер 2
Отношение "" является:
Ответ:
 (1) симметричным, рефлексивным, транзитивным 
 (2) симметричным, нерефлексивным, транзитивным 
 (3) несимметричным, рефлексивным, транзитивным 
Номер 3
Отношение "" является:
Ответ:
 (1) рефлексивным 
 (2) симметричным 
 (3) антисимметричным