Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций



Скачать 118.08 Kb.
Дата07.11.2012
Размер118.08 Kb.
ТипДокументы

Ответы на экзаменационные вопросы интернет-курсов ИНТУИТ (INTUIT): 346. Основы теории вычислимых функций





  1. "Оракул" для множества X может быть реализован вызовом внешней:

  2. "Оракул" для множества X отвечает на вопрос:

  3. m-полное множество относительно m-сводимости - это множество:

  4. m-полнота - это отношение:

  5. m-сводящей X к X будет функция:

  6. Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:

  7. Ассоциативное исчисление - двустороннее, если оно содержит правила:

  8. Ассоциативное исчисление - это:

  9. Бесконечное множество, не содержащее бесконечных разрешимых подмножеств является:

  10. В алфавите X слово P выводимо из слова Q, если:

  11. В теореме Роджерса утверждается, что трансляторы, сводящие главные нумерации друг к другу выбираемы:

  12. В теореме Успенского - Райса утверждается, что в главной нумерации:

  13. В языке Паскаль существует ряд программ Pi, i=1,2,…,n таких, что:

  14. Верно утверждение для множества диафантовых уравнений:

  15. Верно утверждение:

  16. Верно утверждение:

  17. Верно утверждение:

  18. Верны утверждения:

  19. Всякая универсальная функция для класса вычислимых одноместных функций задает:

  20. Всякая функция, вычислимая программой с конечным числом переменных:

  21. Всякая частично рекурсивная функция:

  22. Всякое бесконечное перечислимое множество:

  23. Выводящие из класса примитивно рекурсивных функций схемы рекурсии:

  24. Вычислима функция:

  25. Вычислима функция:

  26. Вычислимая всюду определенная функция двух аргументов, универсальная для класса всех вычислимых функций одного аргумента:

  27. Вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента:

  28. Вычислимая функция со значением {0,1} и не имеющая всюду определенного вычислимого продолжения:

  29. Вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов:

  30. Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:

  31. Вычислимые универсальные функции, не являющиеся главными:

  32. Главная универсальная функция:

  33. Головка машины Тьюринга может передвигаться на:

  34. Гомоморфизм полугрупп - это отображение:

  35. График любой функции, вычислимой программой с конечным числом переменных:

  36. Два главных универсальных множества для класса перечислимых подмножеств N:

  37. Два образца - совместны, если:

  38. Два пересекающихся перечислимых множества, не отделимые разрешимым множеством:

  39. Две программы A, В доказуемо различны, если:

  40. Двухстороннее исчисление, для правил которого нет алгоритма, выясняющегося, можно ли получить одно слово из другого:

  41. Декартово произведение перечислимых множеств А и В перечислимо:

  42. Для \alpha - всюду определенной функции, \alpha-вычислимая функция двух аргументов являющаяся универсальной:

  43. Для m-сводящей X к Y функции f используют обозначение:

  44. Для доказательства неразрешимости множества X достаточно доказать, что:

  45. Для любого k и последовательности b+1, 2b+2, 3b+1, … (b<0 - некоторое целое):

  46. Для любого n в классе \Sigma_n:

  47. Для любого перечислимого множества X из декартового квадрата N существует вычислимая f\colon N \to N :

  48. Для любых х_0, х_1, \ldots , х_n \in N можно найти такие числа a и b, что:

  49. Для описания свойств вычислимых функций, из перечисленных ниже наиболее подходит язык:

  50. Для перечисляемых образцов и вычислимой универсальной функции, множество номеров всех функций, продолжающих хоть один образец:

  51. Для универсального перечислимого множества W-перечислимо множество:

  52. Дополнение к универсальному множеству \Pi_2 будет:

  53. Если B(x,y) - некоторое разрешимое свойство, то свойства вида A(x) \Leftrightarrow \forall y : B(x,y) определяют свойства:

  54. Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

  55. Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

  56. Если f сводит Х к Y, g - Y к Z, то:

  57. Если f сводит Х к Y, то она сводит:

  58. Если T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}, то это множество:

  59. Если T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}, то:

  60. Если U - главная вычислимая универсальная функция для класса вычислимых одноместных функций, то существует для произвольной вычислимой одноместной функции h:

  61. Если U - главная универсальная функция, а X - множество натуральных чисел n, где Un - нигде не определена, то Un:

  62. Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:

  63. Если U(n,x) - главная вычислимая универсальная функция для класса всех вычислимых одноместных функций, то тогда:

  64. Если V(m,x)=U(s(m),x), m, x - любые, то U называется:

  65. Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

  66. Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

  67. Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:

  68. Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:

  69. Если X \in \Sigma_n, то:

  70. Если X \le_m Y и X - эффективно неперечислимо, то:

  71. Если X \le_m Y и Y - перечислимо, то:

  72. Если X \le_m Y и Y - разрешимо, то:

  73. Если X \le_m Y и Y \le_m Z, то:

  74. Если X \le_m Y,Y \in \Pi_n, то:

  75. Если X \le_m Y,Y \in \Sigma_n, то:

  76. Если X \le_T Y, то:

  77. Если X,Y \in \Pi_n, то:

  78. Если X,Y \in \Pi_n, то:

  79. Если X,Y \in \Sigma_n, то:

  80. Если X,Y \in \Sigma_n, то:

  81. Если X=[0;3], Y=[3;0], то f\colon X\to Y будет:

  82. Если X=[-2;5], Y=[0;2], то f\colon X \to Y будет:

  83. Если Y - класс вычислимых одноместных функций, а X \subset Y, то множество \{n\colon U_n \in X\}:

  84. Если Y \le_m X, то:

  85. Если Y \le_m X, то:

  86. Если в одноместную формулу с номером n подставить значение n, то получим:

  87. Если входной алфавит машины Тьюринга состоит 0, 1 и пробела, то входным будет:

  88. Если два множества неотделимы разрешимыми множествами, то:

  89. Если дополнение неразрешимого множества перечислимо, то само множество:

  90. Если нумерация является вычислимой, то последовательность i \mapsto f_i

  91. Если преобразователь программ вычислимо зависит от некоторого параметра, то:

  92. Если программа на каждом входе зацикливается, то для неё:

  93. Если свойство R(x, y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:

  94. Если свойство R(x,y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:

  95. Если универсальное множество - главное, то его:

  96. Если функция f дает по номеру m функции другой номер s этой функции, то:

  97. Иммунное множество - это множество:

  98. Инструкции "находясь в состоянии s \in S и читая символ x \in X перейти в состояние для всех z \in X,p \in S, напечатать символ y \in X и сдвинуться влево" соответствует:

  99. Инструкция "находясь в состоянии s и читая символ x, перейти в состояние p, напечатать символ y и сдвинуться вправо" порождает правило:

  100. Каждая операция проектирования:

  101. Какая программа печатает свой текст?

  102. Класс \Pi_n является:

  103. Класс \Sigma_n является:

  104. Класс эквивалентных множеств называют:

  105. Классы \Sigma_n и \Pi_n:

  106. Композиция двух вычислимых функций является:

  107. Конкатенация - это операция:

  108. Конфигурация машины Тьюринга в каждый момент времени складывается из:

  109. Лента машины Тьюринга может быть:

  110. Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное время:

  111. Любое арифметичное множество может лежать в классе:

  112. Любое перечислимое свойство:

  113. Любые два множества:

  114. Любые две нумерации перечислимых множеств:

  115. Машина Тьюринга включает объект:

  116. Машина Тьюринга включает объект:

  117. Машина Тьюринга включает объект:

  118. Множества X и Y, для которых X\neg \le_T Y и Y\neg \le_T X:

  119. Множества с эффективно неперечислимыми дополнениями:

  120. Множество - 0' - разрешимо, если оно:

  121. Множество - простое, если:

  122. Множество X - \alpha-перечислимо тогда и только тогда, когда для некоторого перечислимого множества E:

  123. Множество X - корректно, если:

  124. Множество X - эффективно бесконечное, если алгоритм конструирования по любому n различных элементов из X:

  125. Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f:

  126. Множество X \subset N m-сводится к Y \subset N, если существует:

  127. Множество X \subset N перечислимо тогда и только тогда, когда:

  128. Множество X из N перечислимо тогда и только тогда, когда:

  129. Множество X из N разрешимо, если существует алгоритм:

  130. Множество X из N×N - универсальное, если:

  131. Множество X согласовано с фрагментом x, если:

  132. Множество А является I-соответствующей множеству В, если:

  133. Множество всех истинных арифметических формул без параметров:

  134. Множество всех истинных арифметических формул без параметров:

  135. Множество всех показателей n, для которых существует целое решение уравнения xn+yn=zn всегда:

  136. Множество всех программ, останавливающихся хотя бы на одном входе является:

  137. Множество всех самоприменимых программ:

  138. Множество доказательств:

  139. Множество натуральных чисел X перечислимо, если оно:

  140. Множество натуральных чисел X разрешимо, если:

  141. Множество номеров нигде не определенной функции:

  142. Множество перечислимо, если оно:

  143. Множество перечислимо, если:

  144. Множество является примитивно рекурсивной, если его характеристическая функция:

  145. Множеством, перечислимым относительно всюду определенной вычислимой функции f является множество:

  146. Не вычислима функция:

  147. Неверно для произвольных множеств:

  148. Неверно для произвольных множеств:

  149. Неверно для произвольных множеств:

  150. Непересекающиеся множества X и Y отделяются множеством Z, если:

  151. Непознаваемая программа:

  152. Непустое множество с ассоциативной операцией типа умножения и единичным элементом называется:

  153. Несравнимые по Тьюрингу перечислимые множества:

  154. Нумерация - вычислима, если вычислима:

  155. Нумерация - вычислимая, если:

  156. Нумерация множества X - это отображение:

  157. Нумерация, соответствующая главной универсальной функции называется:

  158. Область определения универсальной функции будет:

  159. Образ множества X для частичной функции f(n) - это:

  160. Образец - это функция из N в N, определенная:

  161. Образец - это:

  162. Образец является:

  163. Образцом не является (n - натуральное, x - вещественное число):

  164. Образцом является (n - натуральное, x - вещественное число):

  165. Образцом является:

  166. Образцом является:

  167. Объединение перечислимых множеств А и В всегда перечислимо:

  168. Операция:

  169. Определению главной универсальной функции адекватно утверждение:

  170. Отношение "x\mod y=0, x, y \in N" является:

  171. Отношение "xy, x, y \in N" является:

  172. Отношение "х+5=y, x,y \in N" является:

  173. Отношение эквивалентности - это всегда отношение:

  174. Отношение эквивалентности - это отношение:

  175. Отрицания свойств из класса \Pi_n:

  176. Отрицания свойств из класса \Sigma_n:

  177. Парадокс лжеца отражает утверждение:

  178. Пересечение перечислимых множеств - всегда:

  179. Перечислимо всякое множество, если оно:

  180. Перечислимое множество m-полно тогда и только тогда, когда его дополнение:

  181. Перечислимое множество с неперечислимым дополнением:

  182. Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:

  183. Перечислимое неразрешимое множество;

  184. По любой вычислимой функции можно указать:

  185. По любому номеру любого вычислимого действительного числа, номер вычислимой функции десятичного его разложения:

  186. По программам функций f и g получить их композицию:

  187. Последовательность i \mapsto f_i вычислима, если существует:

  188. Последовательность i \mapsto f_i вычислима, если:

  189. При любом n любое множество из класса \Pi_n:

  190. При любом n любое множество из класса \Sigma_n:

  191. Примитивно рекурсивно для примитивно рекурсивных операндов:

  192. Примитивно рекурсивно для примитивно рекурсивных операндов:

  193. Примитивно рекурсивно свойство:

  194. Примитивно рекурсивно свойство:

  195. Проблема остановки состоит в выяснении того, что:

  196. Программа, печатающая свой текст:

  197. Программу А со свойством "никакая программа В не является доказуемо различной с А":

  198. Прообраз множества X для частичной функции f(n) - это:

  199. Простое множество:

  200. Процедура замены вычислимых функции на функции, вычислимые относительно всюду определенной функции называется:

  201. Работу всякой машины Тьюринга промоделировать другой машиной Тьюринга:

  202. Равенство f(n)=d(n) может означать, что:

  203. Равенство f(n)=U(n,n) определяет:

  204. Различным операциям над множествами соответствуют:

  205. Рекурсия 0 mod n=0, (x+1) mod n=(x mod n)+1 mod n определяет:

  206. Самая трудная в мире задача разрешения:

  207. Свободная полугруппа - это полугруппа:

  208. Свойства класса \Pi_2 имеют вид:

  209. Свойство A принадлежит классу \Pi_n, если для некоторого разрешимого свойства В:

  210. Свойство A принадлежит классу \Sigma_n, если для некоторого разрешимого свойства В:

  211. Свойство A(x), x \in N перечислимо тогда и только тогда, когда:

  212. Сложение чисел x, y ((x,y) \to x+y) реализует рекурсия:

  213. Совокупность операндов алгебры A называется:

  214. Совокупность операций алгебры A называется:

  215. Совокупность элементов X и определённых над ними операции F, удовлетворяющих аксиомам, называется:

  216. Соответствие - это:

  217. Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:

  218. Стек - это:

  219. Структура на множестве X - это отношение типа:

  220. Существует ли Паскаль-программа, инвертирующая свой текст?

  221. Существуют ли Паскаль-программы А и В, печатающие, соответственно, тексты В и А?

  222. Счетное число непересекающихся перечислимых множеств попарно неотделимых разрешимым множеством:

  223. Счетное число непересекающихся перечислимых множеств, никакие два из которых неотделимы разрешимым множеством:

  224. Таблица переходов машины Тьюринга - функция:

  225. Таблица переходов машины Тьюринга - функция:

  226. Тезис Тьюринга:

  227. Теорема Геделя:

  228. Теорема Клини о неподвижной точке:

  229. Теорема о неподвижной точке гарантирует существование:

  230. Теорема о неподвижной точке называется также теоремой:

  231. Теорема Поста:

  232. Теорема Тарского:

  233. Термину "k - местная" удовлетворяет функция:

  234. Указание - это кортеж \langle A^+,A^-,B^+,B^- \rangle, в котором:

  235. Умножение чисел x, y ((x,y) \to x*y) реализует рекурсия:

  236. Универсальное \Pi_n множество:

  237. Универсальное \Sigma_n множество:

  238. Универсальное перечислимое множество из N × N:

  239. Универсальную вычислимую функцию, для которой каждая вычислимая функция имеет ровно один номер:

  240. Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:

  241. Утверждение "Любой алгоритм, перечисляющий множество формул арифметики порождает некоторую ложную формулу, либо не порождает некоторой истинной формулы" - это:

  242. Утверждение: "Средствами формальной системы нельзя доказать ее непротиворечивость" - это:

  243. Формула х+1 mod n = [if x+1=n then 0 else x+1] :

  244. Фрагмент - это всегда:

  245. Функции, вычисляемые программой с полным ветвлением и циклом "для", но без циклов "пока":

  246. Функции, получаемые с помощью операций подстановки и рекурсии из константы 0, операции прибавления единицы k штук k-местных функций (x_1,x_2, \ldots ,x_n) \to x_i называют:

  247. Функция f примитивна рекурсивна, если одновременно выполнено:

  248. Функция f(n,x)=\{\mbox{if } n \in K \mbox{ then } \xi (x) \mbox{ else неопределенно} \}, где K -перечислимое и неразрешимое, является:

  249. Функция f(x,0)=x, f(x,y+1)=f(x,y)+1:

  250. Функция f(xn)=f(xn-1)+x:

  251. Функция fn(x)=fn-1(x)+x:

  252. Функция m=f(n), m,n \in N вычислима, если существует алгоритм A(f):

  253. Функция m=f(n), m,n \in N вычислима, если существует алгоритм A(f):

  254. Функция m=f(n), m,n \in N вычислима, если существует алгоритм A(f):

  255. Функция U(n,m), n,m \in N - универсальна для класса вычислимых функций одного аргумента, если для каждого n:

  256. Функция перечислима тогда и только тогда, когда

  257. Характеристическая функция множества X:

  258. Частичная функция f вычислима относительно всюду определенной функции g тогда и только тогда, когда она:

  259. Частичная функция вычислима относительно всюду определенной функции тогда и только тогда, когда она:

  260. Частично рекурсивная и всюду определенная функция называется:

  261. Частично рекурсивны функции получаемые из базисных с помощью:

  262. Частично рекурсивны функции, получаемые из базисных с помощью:

  263. Элемент - это:

  264. Элемент \langle C,D \rangle продолжает элемент \langle A,B\rangle, если:




Актуальная информация по учебным программам ИНТУИТ расположена по адресу: http://www.intuit.ru/.

Повышение квалификации

(программ: 450)

Профессиональная переподготовка

(программ: 14)

Лицензия на образовательную деятельность и приложение











Developer Project предлагает поддержку при сдаче экзаменов учебных курсов Интернет-университета информационных технологий INTUIT (ИНТУИТ). Мы ответили на экзаменационные вопросы 380 курсов INTUIT (ИНТУИТ), всего 110 300 вопросов, 154 221 ответов (некоторые вопросы курсов INTUIT имеют несколько правильных ответов). Текущий каталог ответов на экзаменационные вопросы курсов ИНТУИТ опубликован на сайте объединения Developer Project по адресу: http://www.dp5.su/

Подтверждения правильности ответов можно найти в разделе «ГАЛЕРЕЯ», верхнее меню, там опубликованы результаты сдачи экзаменов по 100 курсам (удостоверения, сертификаты и приложения с оценками).

Более 21 000 вопросов по 70 курсам и ответы на них, опубликованы на сайте http://www.dp5.su/, и доступны зарегистрированным пользователям. По остальным экзаменационным вопросам курсов ИНТУИТ мы оказываем платные услуги (см. вкладку верхнего меню «ЗАКАЗАТЬ УСЛУГУ». Условия поддержки и помощи при сдаче экзаменов по учебным программам ИНТУИТ опубликованы по адресу: http://www.dp5.su/

Примечания:

- ошибки в текстах вопросов являются оригинальными (ошибки ИНТУИТ) и не исправляются нами по следующей причине - ответы легче подбирать на вопросы со специфическими ошибками в текстах;

- часть вопросов могла не войти в настоящий перечень, т.к. они представлены в графической форме. В перечне возможны неточности формулировок вопросов, что связано с дефектами распознавания графики, а так же коррекцией со стороны разработчиков курсов.


Похожие:

Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): Основы теории нечетких множеств
Алгоритм построения функции принадлежности косвенным методом Шера для группы экспертов заканчивает работу, когда
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 217. Основы информатики и программирования
Большинство предикатов в состоянии, в котором не определены некоторые из переменных, входящих в него
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): Алгоритмические основы современной компьютерной графики
Благодаря чему достигается быстрота алгоритма Брезенхема разложения отрезка в растр?
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 068. Основы работы в Adobe PageMaker
Атрибут форматирования, определяющий межсимвольное расстояние для всех символов текста, называется
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): Криптографические основы безопасности
В уравнениях эллиптических кривых бесконечно удаленная точка, в которой сходятся все вертикальные прямые, называется
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconОтветы на экзаменационные вопросы интернет-курсов интуит (intuit): 221. Основы объектно-ориентированного проектирования
В данной главе под многопанельной системой понимается интерактивная система, в которой?
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconОтветы на экзаменационные вопросы интернет-курсов интуит (intuit): 291. Основы функционального программирования
В каких из перечисленных форм необходимость вычислять те или иные подвыражения зависит от значений переменных?
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 290. Основы программирования на языке Пролог
В алгоритме сортировки перестановками предикат permutation выполняет перестановку двух соседних элементов в случае, если
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 314. Основы конфигурирования в системе "1С: Предприятие 0"
Бросают 10 симметричных игральных костей. Какое распределение имеет число костей, на которых выпало шесть очков?
Экзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций iconОтветы на экзаменационные вопросы интернет-курсов интуит (intuit): 102. Основы программирования на JavaScript
Будет ли выдано сообщение об ошибке JavaScript при вводе данных в поле формы и передаче их на сервер в следующем примере?
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org