Введение в теория алгоритмов//ИРНИТУ//72 балла
Ответы находятся в купленной работе на скринах. Рез-т теста 72 балла, скрин прилагается. Ответы выделены желтым на след. вопросы:
Вопрос 1
Для n-местной функции выбора справедливо равенство:
Выберите один ответ:
Вопрос 2
Проблема останова в машине Тьюринга:
Выберите один ответ:
a.Не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.
b.По двум произвольным заданным алгоритмам (например, по двум ма-шинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
Очистить мой выбор
Вопрос 2
Проблема останова в машине Тьюринга:
Выберите один ответ:
a.Не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.
b.По двум произвольным заданным алгоритмам (например, по двум ма-шинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
Вопрос 3
Пока нет ответа
Балл: 1,00
Текст вопроса
Говорят, что n-местная функция F(x1 ,...,xn) получена с помощью оператора суперпозиции из функции f (у1,..., ym) и функций g1(x1,...,xn), g2(x1, ...,xn), ..., gm(x1, ...,xn), если
Вопрос 4
Пока нет ответа
Примерами примитивно рекурсивных функций являются:
Выберите один или несколько ответов:
a. cos(x)
b.(x+y)n
c. число простых чисел, не превосходящих Х
d. | x+y|/|x-y|
e. sin(x)
Вопрос 5
Говорят, что (n + 1)-местная функция f получена из n-местной функции g и (n + 2)-местной функции h с помощью оператора примитивной рекурсии, если для любвых x1, x2,..., xn, у справедливы равенства:
Вопрос 6
Говорят, что одноместная функция f (x) получена из нульместной функции g и двуместной функции h(x, у) с помощью оператора примитивной рекурсии, если для любого y справедливы равенства:
Вопрос 7
Машина Тьюринга полностью определяется:
Выберите один ответ:
a.программой, бесконечным алфавитом внутренних состояний.
b.бесконечным внешним алфавитом, программой, нумерацией команд.
c.конечным внешним алфавитом и бесконечным алфавитом внутренних состояний.
d.конечным внешним алфавитом, конечным алфавитом внутренних состояний, программой.
Очистить мой выбор
Вопрос 8
Для n-местной функции проекции справедливо равенство:
Вопрос 9
Тезис Тьюринга - это
Выберите один ответ:
a.теорема, доказанная Тьюрингом о существовании алгоритма.
b.гипотеза, высказанная Тьюрингом о том, что функция является алгоритмически вычислимой тогда и только тогда, когда она является вычислимой по Тьюрингу.
c.теорема, доказанная Тьюрингом о том, что все функции вычислимые по Тьюрингу являются частично рекурсивными.
Вопрос 10
Функция называется общерекурсивной, если она является
a.всюду определенной и примитивно рекурсивной.
b.всюду определенной и частично рекурсивной.
c.частично определенной и примитивно рекурсивной.
Первой фундаментальной теоретической работой, связанной с доказа-тельством алгоритмической неразрешимости, была работа
Выберите один ответ:
a.Поста
b.Геделя
c.Тьюринга
Очистить мой выбор
Вопрос 12
Функция называется примитивно рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений
Выберите один ответ:
a.операторов суперпозиции и примитивной рекурсии.
b.оператора суперпозиции.
c.оператора примитивной рекурсии.
Очистить мой выбор
Выберите один ответ:
a.1024.
b.16;
c.∞
d.4096;
Очистить мой выбор
Вопрос 14
Как может передвигаться считывающее устройство машины Тьюринга?
Выберите один ответ:
a.вдоль ленты влево и вправо.
b.вверх или вниз;
c.по диагонали;
Очистить мой выбор
Вопрос 15
Сколько лент имеет машина Тьюринга?
Выберите один ответ:
a.одну;
b.две.
c.четыре;
Очистить мой выбор
Вопрос 16
Функция называется частично рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений
Выберите один ответ:
a.операторов суперпозиции и минимизации.
b.операторов суперпозиции, примитивной рекурсии и минимизации.
c.операторов примитивной рекурсии и минимизации.
Очистить мой выбор
Вопрос 17
Функция следования - это
Выберите один ответ:
a.двуместная функция, которая каждой паре (x,y) ставит в соответствие элемент x + у.
b.одноместная функция, которая каждому элементу x ставит в соответствие элемент x — 1.
c.одноместная функция, которая каждому элементу x ставит в соответствие элемент x + 1.
Очистить мой выбор
Вопрос 18
Функция проекции (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) принимает значение, равное:
Выберите один ответ:
Вопрос 19
Говорят, что двуместная функция f (x,у) получена из одноместной функции g(x) и трехместной функции h(x,y,z) с помощью оператора примитивной рекурсии, если для любых x,y справедливы равенства:
Вопрос 20
Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.Это определение
Выберите один ответ:
a.Колмагорова
b.Маркова
Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.Это определение
Выберите один ответ:
a.Маркова
b.Колмагорова
Очистить мой выбор
Вопрос 22
Команда giaj →gkalL означает, что
Выберите один ответ:
a.машина Тьюринга находится в состоянии gi и обозревает ячейку, в которой записана буква аj машина переходит в со стояние gk, в обозреваемой ячейке стирает букву аj и заносит туда букву аl.
b.машина Тьюринга находится в состоянии gi и обозревает ячейку, в которой записана буква аj, машина переходит к обозреванию ячейки, следующей слева от предыдущей, затем переходит в состояниеgk, в обозреваемую ячейку заносит букву аl.
c.машина Тьюринга находится в состоянии gi и обозревает ячейку, в которой записана буква аj машина переходит в со стояние gk, в обозреваемой ячейке стирает букву аjи заносит туда букву аl, затем переходит к обозреванию ячейки, следующей слева от предыдущей.
Очистить мой выбор
Вопрос 23
Текст вопросаИз функций f (x,y) = x2 + 4y f1 (x) = 3x, f2(x) = 2x + 2 с помощью операции суперпозиции получена функция
