Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 1
Основы теории вычислимых функций - тест 1
Упражнение 1:
Номер 1
Функция m=f(n)
, вычислима, если существует алгоритм A(f)
:
Ответ:
 (1) останавливающийся и печатающий m=f(n)
 
 (2) преобразующий число n
в число n+1
для любого m
 
 (3) преобразующий число n
в число n+m
для любого m
 
Номер 2
Функция m=f(n)
, вычислима, если существует алгоритм A(f)
:
Ответ:
 (1) останавливающийся для неопределенного f(n)
 
 (2) не останавливающийся для неопределенного f(n)
 
 (3) не останавливающийся для определенного f(n)
 
Номер 3
Функция m=f(n)
, вычислима, если существует алгоритм A(f)
:
Ответ:
 (1) останавливающийся для определенного f(n)
 
 (2) не останавливающийся для неопределенного f(n)
 
 (3) вычисляющий цифры m
 
Упражнение 2:
Номер 1
Вычислима функция:
Ответ:
 (1) f(n)=sin(n)
 
 (2) f(n)=sign(x+n)
 
 (3) f(n)=n+1
 
Номер 2
Вычислима функция:
Ответ:
 (1) f(n)=cos(n)
 
 (2) f(n)=n sign(n+x)
 
 (3) f(n)=n-1
 
Номер 3
Не вычислима функция:
Ответ:
 (1) f(n)=1
 
 (2) f(n)=sign(n+1)
 
 (3) f(n)=n
 
Упражнение 3:
Номер 1
Множество X
из N
разрешимо, если существует алгоритм:
Ответ:
 
(1) определения, принадлежит ли
множеству
X
 
 
(2) вычисления
по заданному
 
 (3) поиска наибольшего n
 
Номер 2
Характеристическая функция множества X
:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Множество натуральных чисел X
разрешимо, если:
Ответ:
 
(1) вычислима
для
 
 
(2) вычислима
для
 
 (3) оно универсально 
Упражнение 4:
Номер 1
Множество натуральных чисел X
перечислимо, если оно:
Ответ:
 (1) перечисляется по некоторому алгоритму 
 (2) сортируемо алгоритмом обменами 
 (3) счетно 
Номер 2
Множество перечислимо, если:
Ответ:
 (1) оно есть область определения вычислимой функции 
 (2) оно состоит только из натуральных чисел 
 (3) его характеристическая функция имеет значение 0
 
Номер 3
Множество перечислимо, если оно:
Ответ:
 (1) есть область значений вычислимой функции 
 (2) содержит область значений вычислимой функции 
 (3) совершенно 
Упражнение 5:
Номер 1
Пересечение перечислимых множеств - всегда:
Ответ:
 (1) перечислимо 
 (2) перечислимо или неопределенно  
 (3) пусто 
Номер 2
Объединение перечислимых множеств А
и В
всегда перечислимо:
Ответ:
 (1) для конечных А
и В
 
 (2) для всех таких А
и В
 
 (3) или универсально 
Номер 3
Декартово произведение перечислимых множеств А
и В
перечислимо:
Ответ:
 
(1) если
 
 (2) всегда 
 (3) или неопределенно всегда  
Упражнение 6:
Номер 1
Перечислимо всякое множество, если оно:
Ответ:
 (1) разрешимо 
 (2) есть подмножество N
 
 (3) равномощно N
 
Номер 2
Теорема Поста:
Ответ:
 (1) разрешимые множества перечислимы со своими дополнениями 
 (2) перечислимые множества разрешимы со своими дополнениями 
 (3) либо само множество, либо его дополнение всегда перечислимо 
Номер 3
Множество X
из N
перечислимо тогда и только тогда, когда:
Ответ:
 (1) X
- проекция некоторого разрешимого множества 
 (2) Y
- множество натуральных чисел 
 (3) верно и а), и б) 
Упражнение 7:
Номер 1
Функция перечислима тогда и только тогда, когда
Ответ:
 (1) ее график перечислим 
 (2) ее график - множество изолированных точек 
 (3) ее график совпадает с проекцией графика на N
 
Номер 2
Образ множества X
для частичной функции f(n)
- это:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Прообраз множества X
для частичной функции f(n)
- это:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 8:
Номер 1
Верно утверждение для множества диафантовых уравнений:
Ответ:
 (1) перечислимо, если разрешимы уравнения  
 (2) перечислимо, если они неразрешимы 
 (3) всегда перечислимо 
Номер 2
Всякое бесконечное перечислимое множество:
Ответ:
 (1) содержит разрешимое множество 
 (2) разрешимо 
 (3) неразрешимо 
Номер 3
Множество всех показателей n
, для которых существует целое решение уравнения xn+yn=zn
всегда:
Ответ:
 (1) перечислимо 
 (2) пусто 
 (3) совпадает с N