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

Теория алгоритмов

Укажите, какими требованиями определяется интуитивное понятие алгоритма:

A) дискретность, детерминированность, элементарность шагов алгоритма, направленность, массовость, локальность

B) дискретность, детерминированность, элементарность шагов алгоритма, направленность, массовость

C) дискретность, детерминированносгь, элементарность шагов алгоритма, направленность, массовость, конечность

D) непрерывность, детерминированность, элементарность шагов алгоритма, направленность, массовость

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

*****

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

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

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

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

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

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

*****

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

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

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

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

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

E) закон получения системы величин должен быть элементарным

*****

Укажите простейшие функции:

A)

B)

C)

D)

E)

*****

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

A) Пусть заданы какие-нибудь числовые частичные функции: (n+1)-местная g и (n + 2) - местная h. Говорят, что (n + 1) - местная частичная функция возникает из функций g и h прими­тивной рекурсией, если для всех натуральных значений

B) Пусть заданы какие-нибудь числовые частичные функции: n-местная g и (n + 2) - местная h. Говорят, что (n + 1) - местная частичная функция возникает из функций g и h прими­тивной рекурсией, если для всех натуральных значений

C) Пусть заданы какие-нибудь числовые частичные функции: n-местная g и (n + 2) - местная h. Говорят, что (n + 1) - местная частичная функция возникает из функций g и h прими­тивной рекурсией, если для всех натуральных значений

D) Пусть заданы какие-нибудь числовые частичные функции: n-местная g и (n + 2) - местная h. Говорят, что (n + 1) - местная частичная функция возникает из функций g и h прими­тивной рекурсией, если для всех натуральных значений

E) Пусть заданы какие-нибудь числовые частичные функции: n-местная g и n - местная h. Говорят, что (n + 1) - местная частичная функция возникает из функций g и h прими­тивной рекурсией, если для всех натуральных значений

*****

Определите операцию суперпозиции или подстановки:

A) Пусть заданы какие-нибудь числовые частичные функции: n-местная g и (n + 2) - местная h. Говорят, что (n + 1) - местная частичная функция возникает из функций g и h суперпозицией, если для всех натуральных значений

B) Пусть заданы n каких-либо частичных функций от одного и того же числа m переменных, определенных на каком-то множестве А со значениями в множестве В, и пусть на множестве В определена частичная функция от n пере­менных, значения которой принадлежат некоторому треть­ему множеству С. Вводим теперь частичную функцию g от m переменных, определенную на А со значениями в С, полагая по определению для произвольных из А. Говорят, что функция g получается операцией суперпозиции или под­становки из функций

C) Пусть заданы n каких-либо частичных функций от одного и того же числа n переменных, определенных на каком-то множестве А со значениями в множестве В, и пусть на множестве В определена частичная функция от n пере­менных, значения которой принадлежат некоторому треть­ему множеству С. Вводим теперь частичную функцию g от n переменных, определенную на А со значениями в С, полагая по определению для произвольных из А. Говорят, что функция g получается операцией суперпозиции или под­становки из функций

D) Пусть заданы n каких-либо частичных функций от одного и того же числа m переменных, определенных на каком-то множестве А со значениями в множестве В, и пусть на множестве В определена частичная функция от n пере­менных, значения которой принадлежат некоторому треть­ему множеству С. Вводим теперь частичную функцию g от n переменных, определенную на А со значениями в С, полагая по определению для произвольных из А. Говорят, что функция g получается операцией суперпозиции или под­становки из функций

E) Пусть заданы n каких-либо частичных функций от одного и того же числа m переменных, определенных на каком-то множестве А со значениями в множестве В, и пусть на множестве В определена частичная функция от n пере­менных, значения которой принадлежат некоторому треть­ему множеству С. Вводим теперь частичную функцию g от m переменных, определенную на А со значениями в С, полагая по определению для произвольных из А. Говорят, что функция g получается операцией суперпозиции или под­становки из функций

*****

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

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

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

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

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

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

*****

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

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

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

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

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

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

*****

Сформулируйте тезис Чёрча:

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

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

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