Теория алгоритмов (стр. 2 )

D) класс алгоритмически частичных числовых функций совпадает с классом рекурсивных функций

E) класс алгоритмически вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций

*****

Укажите примитивно рекурсивную функцию:

A)

B)

C)

D)

E)

*****

Определите значение терма :

A) неопределенно

B)

C)

D)

E)

*****

Укажите, что означает детерминированность алгоритма:

A) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени

B) Закон получения последующей системы величин из предшествующей должен быть простым и локальным

C) Закон получения последующей системы величин из предшествующей должен быть детерминированным

D) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется начальной системой величин

E) Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма

*****

Дайте определение вычислимых функций:

A) Вычислимыми функциями называются числовые функции, значения которых можно вычислять посредством некоторой программы

B) Вычислимыми функциями называются числовые функции, значения которых можно вычислять посредством некоторого (единого для данной функции) алгоритма

C) Вычислимыми функциями называются числовые функции, значения которых можно вычислять конечным числом операций подстановки и примитивной рекурсии

D) Функция f называется вычислимой функцией если f можно получить из функций системы и простейших функций конечным числом операций подстановки и примитивной рекурсии

E) Вычислимыми функциями называются числовые функции, значения которых можно вычислять

*****

Определите значение терма :

A) неопределенно

B)

C)

D)

E)

*****

Укажите, что означает направленность алгоритма:

A) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени

B) Закон получения последующей системы величин из предшествующей должен быть простым и локальным

C) Закон получения последующей системы величин из предшествующей должен быть детерминированным

D) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется начальной системой величин

E) Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма

*****

Дайте определение частичной функции:

A) Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция из X в Y

B) Пусть задана система каких-то частичных функций. Функция f называется частичной относительно , если f можно получить из функций системы и простейших функций , , конечным числом операций подстановки, примитивной рекурсии и минимизации

C) Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частично рекурсивная функция из X в Y

D) Если элементам множества X поставлены в соответствие элементы множества Y, то говорят, что задана частичная функция из X в Y

E) Если некоторым элементам множества Y поставлены в соответствие однозначно определенные элементы множества X, то говорят, что задана частичная функция из X в Y

*****

Дайте определение элементарных функций:

A) Частичные функции, которые можно получить операциями подстановок из функций , , …, называются элементарными относительно , , …,

B) Частичные функции, которые можно получить операциями подстановок из функций , , …, и функций (m, n = 1,2,…) называются элементарными относительно , , …,

C) Частичные функции, которые можно получить операциями подстановок и примитивной рекурсии из функций , , …, и функций (m, n = 1,2,…) называются элементарными относительно , , …,

D) Частичные функции, которые можно получить операциями подстановок из функций (m, n = 1,2,…) называются элементарными

E) Частичные функции, которые можно получить из функций , , …, и функций (m, n = 1,2,…) называются элементарными относительно , , …,

*****

Укажите, что означает массовость алгоритма:

A) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени

B) Начальная система величин может выбираться из некоторого потенциально бесконечного множества

C) Закон получения последующей системы величин из предшествующей должен быть детерминированным

D) Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется начальной системой величин

E) Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма

*****

Дайте определение всюду определенной функции:

A) Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана всюду определенная функция из X в Y

B) Пусть задана система каких-то частичных функций. Функция f называется всюду определенной относительно , если f можно получить из функций системы и простейших функций , , конечным числом операций подстановки, примитивной рекурсии и минимизации

C) Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана всюду определенная функция из X в Y

D) Если элементам множества X поставлены в соответствие элементы множества Y, то говорят, что задана всюду определенная функция из X в Y

E) Если область определения функции из X в Y совпадает с множеством X, то функция называется всюду определенной

*****

Укажите связь между примитивной рекурсивностью и всюду определенностью:

A) примитивно рекурсивные функции не являются всюду определенными

B) всюду определенные функции примитивно рекурсивны

C) все примитивно рекурсивные функции всюду определены

D) частичная числовая функция примитивно рекурсивна тогда и только тогда, когда она всюду определена

E) примитивная рекурсивность равносильна всюду определенности.

*****

Алгоритм - это процесс последовательного построения величин, идущий в дискретном времени таким образом, в начальный момент времени задается исходная конечная система величия, а в каждый следующий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыдущий момент времени. Как называют это свойство алгоритма?

A) детерминированность алгоритма

B) дискретность алгоритма

C) направленность алгоритма

D) массовость алгоритма

E) элементарность шагов алгоритма

*****

Закон получения последующей системы величии из предшествующей должен быть простым и локальным. Как называют это свойство алгоритма?

A) детерминированность алгоритма

B) дискретность алгоритма

C) направленность алгоритма

D) массовость алгоритма

E) элементарность шагов алгоритма

*****

Система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени. Как называют это свойство алгоритма?

A) детерминированность алгоритма

B) дискретность алгоритма

C) направленность алгоритма

D) массовость алгоритма

E) элементарность шагов алгоритма

*****

Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма. Как называют это свойство алгоритма?

A) детерминированность алгоритма