Тезис Черча:
класс алгоритмически вычислимых функций совпадает с классом всех частично рекурсивных функций Как называется метод, сущность которого заключается в том, чтобы угадать ответ и доказать его по индукции?
Метод замены подстановки
Основная гипотеза Теории алгоритмов:
Всякий алгоритм может быть задан посредством Тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга
Что не является причиной останова машины Поста
Некорректно задан внешний алфавит
Класс алгоритмически вычислимых функций совпадает с классом всех частично рекурсивных функций - это ...
Тезис Черча
Последовательность слов P1,P2, ... ,Pn называется дедуктивной цепочкой, ведущей от слова P1 к P2 и т.д. , если...
если каждые из двух соседних слов - смежные
Алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа (например, алгоритм умножения матриц) относятся к классу...
N (количественно-зависимых по трудоемкости)
К свойствам алгоритма не относится...
вариативность
Функция f(x1,..,xn) называется примитивно рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи:
операций суперпозиции и схемы примитивной рекурсии
Машины Поста и Тьюринга были созданы...
1936 г.
Как соотносятся между собой классы вычислимых функций с классом всех частично рекурсивных функций
классы совпадают
Что не относится к операциям над функциями?
Оператор проектирования
Алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, иксирована), а конкретными значениями всех или некоторых элементов для входного множества D (например, алгоритм вычисления стандартных функций с заданной точностью).
PR (параметрически-зависимых)
Что входит в Нормальный Алгоритм Маркова?
Алфавит и список подстановок
Какую команду не умеет выполнять машина Поста?
Переход в новое состояние
Что представляет собой программа на машине Поста?
последовательность пронумерованных команд
Это достаточно широкий класс алгоритмов, так как в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от их значений.
NPR (количественно-параметрические по трудоемкости)
Система счисления, в которой значения каждой цифры в изображении числа определяется ее положением называется...
Позиционной
Какое свойство алгоритма пропущено:дискретность,определенность, результативность,массовость?
Понятность
Что не относится к основным алгоритмическим конструкциям?
ввод
Какая из нижеперечисленых функций не является простейшей:
оператор соединения
Что не является формальным описанием алгоритма, использующего строго определенные
модели вычислений?
Алгоритм Евклида
Теорема: Если существует задача принадлежащая классу NPC, для которой существует полиномиальный алгоритм решения, то классы...
P = NP
Если некоторый алгоритм содержит явную ссылку на самого себя, то его называют...
Пряморекурсивным
Что из себя представляет Машина Поста?
Бесконечная лента, разделенная на клетки, каждая из которых может быть либо пустой, либо помеченной галочкой и управляющая каретка
Указать неверное направление формализации в Теории алгоритмов
направление связано с разработкой структур ПО, позволяющих реализовать разработанные алгоритмы
Если функция f(x1,..,xn)частично рекурсивна и всюду определена, то она называется..
Общерекурсивной
К основным направлениям формализации понятия алгоритма не относится направление, вязанное ...
с определением скорости роста алгоритмов
Что представляет собой программа на машине Тьюринга?
Таблицу букв алфавита и состояний перехода
Для любой ли задачи можно составить алгоритм?
нет
Что понимается под массовой проблемой?
множество однотипных задач
Алгоритмом в алфавите А называется...
Понятное точное предписание, определяющее процесс над словами из А и допускающее любое слово в качестве исходного
Два слова эквивалентны, если...
существует дидактическая цепочка, ведущая от первого слова ко второму и обратно
Класс параметрически зависимых по трудоемкости алгоритмов, это класс...
PR
Ассоциативное исчисление - это:
Совокупность всех слов в алфавите вместе с системой подстановок
Если функция f(x1,...,xn) может быть получена за конечное число шагов из простейших функций при помощи операции суперпозиции,схемы примитивной рекурсии и m-оператора, то она называется...
Частично рекурсивной
Если существует дедуктивная цепочка, ведущая от одного слова ко второму и обратно, то эти
слова называются...
эквивалентными
Какое утверждение, из перечисленных, неверно
Проблема распознавания самоприменимости алгоритма разрешима
Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют...
Ассоциативным исчислением
У какого метода идея состоит в разделении задачи на части меньшей размерности, получении решений для выделенных частей и объединении решений при возврате рекурсивных вызовов?
Метод декомпозиции
Укажите верное продолжение тезиса Черча:"Класс алгоритмически вычислимых функций совпадает с классом всех..."
Частично рекурсивных функций
Дана функция f(x1,...,xn). Если существует алгоритм, позволяющй вычислить ее значения, то она является...
Эффективно вычислимой
Указать вариант, в котором перечислены все основные алгоритмические структуры:
следование, ветвление, цикл
Если алгоритм А1 ссылается на алгоритм А2, содержащий ссылку на А1, то рекурсия называется...
косвенной
С помощью композиции основных алгоритмических конструкций можно построить любой лгоритм - это ...
Структурная теорема Бена-Джакопини
С помощью композиции каких алгоритмических конструкций можно построить любой алгоритм?
следование, ветвление, цикл
Какой метод не является методом анализа сложности функции:
метод исключения
Первые фундаментальные работы по Теории алгоритмов были опубликованы...
А. Тьюрингом, А.Черчем, Э.Постом
Как соотносятся между собой классы примитивно рекурсивных функций с классом частично рекурсивных функций
класс примитивно рекурсивных функций уже, чем класс частично рекурсивных функций
Что не является свойством алгоритма?
непрерывность
Осуществите перевод 43210->X8. Укажите значение X.
660
Задача принадлежит классу P, то есть...
Называется полиномиальной и решается за время О(n^k), где k=const
Массовая проблема называется алгоритмически разрешимой, если...
Существует алгоритм, позволяющий решить каждую задачу этой массовой проблемы
Какой метод не используется при нахождении асимптотической оценки для рекуррентных соотношений?
метод декомпозиции
Какая операция над функциями указана Q(x1, x2,..., xn) = R(U1(x1, x2,..., xn), U2(x1, x2,..., xn),..., Um(x1, x2,..., xn))
супрпозиция функций
Ассоциативное исчисление используется в
Нормальных алгоритмах Маркова
Для какого вида рекуррентных соотношений можно применять основную теорему о рекуррентных соотношениях?
T(n) = aT(n/b) + f(n)
Что будет делать машина Поста по команде: 2. ->4
сдвинет каретку вправо на 1 позицию и приступит к выполнению команды №4
Независимо друг от друга сложностной класс Р (полиномиальный) ввели
Кобмен и Эдмондс
Структурная теорема (Бена-Джакопини):
С помощью композиции основных алгоритмических конструкций можно построить любой алгоритм
Функция f(x1,x2, … ,xn) - общерекурсивна, если...
она частично рекурсивна и всюду определена
Осуществите перевод 3325->X10. Укажите значение X.
92
Если существует алгоритм, позволяющий вычислить каждое значение функции, то такая функция называется
Эффективно вычислимой
Что не относится к простейшим функциям?
оператор суперпозиция
n K m <, m1> - это команда:
Машины Поста
К формализации понятия "алгоритм" не относится...
Алгоритм Евклида
Субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий
исполнитель
Функция g пренадлежит классу ?(f), если при всех значениях n>n0 , значение ...
g(n) >= c*f(n) , где c > 0 , c = const
Добавлено (2009-05-25, 8:15 Pm)
---------------------------------------------
Основная гипотеза теории алгоритмов:
Всякий алгоритм может быть реализован с помощью машины Поста
Всякий алгоритм может быть реализован посредством ЭВМ
Всякий алгоритм может быть задан посредством машин Тьюринга и Поста
Дан некоторый алфавит. Любая конечная последовательность букв данного алфавита называется...
словом
Что не входит в состав машины Поста?
алфавит
Понятие NP-полноты (класс NPC) ввели...
Левин и Кук
Как называется задача , если существует константа k и алгоритм, решающий эту задачу за время O(nk), где n - есть длина входа алгоритма?
Полиномиальный (класс P)
Функция f(x1,x2, … ,xn) - эфективно вычислима, если...
Существует алгоритм, позволяющий вычислить её значение
Функция является примитивно рекурсивной, если...
она представима за конечное число шагов из простейших функций с помощью операции суперпозиции и схемы примитивной рекурсии
Класс NP был впервые введен в работах...
Эдмондса
Если функция f(x1,..,xn) может быть получена за конечное число шагов из простейших функций при помощи операции суперпозиции и схемы примитивной рекурсии, то она называется...
Примитивно рекурсивной
Какая система счисления используется в Машине Поста?
унарная
Теоретический аспект теории алгоритмов позволяет:
Ответить на вопрос: является ли задача в принципе алгоритмически разрешимой
К целям формализации не относится...
Реализация алгоритмов с помощью абстрактных машин
