игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 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], то  math  будет:

Ответ:

 (1) числовой функцией 

 (2) множеством 

 (3) отображением 


Номер 2
Если X=[0;3], Y=[3;0], то  math  будет:

Ответ:

 (1) числом 

 (2) отображением 

 (3) множеством 


Номер 3
Соответствие - это:

Ответ:

 (1) порядок 

 (2) отображение 

 (3) множество 


Упражнение 8:
Номер 1
Отношение "math" является:

Ответ:

 (1) симметричным, рефлексивным, транзитивным 

 (2) симметричным, нерефлексивным, транзитивным 

 (3) несимметричным, нерефлексивным, транзитивным 


Номер 2
Отношение "math" является:

Ответ:

 (1) симметричным, рефлексивным, транзитивным 

 (2) симметричным, нерефлексивным, транзитивным 

 (3) несимметричным, рефлексивным, транзитивным 


Номер 3
Отношение "math" является:

Ответ:

 (1) рефлексивным 

 (2) симметричным 

 (3) антисимметричным 




Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 5