Ели функция определена не на всем множестве Х, то она называется:
частичной В каких задачах, обычно, не требуется математическая формулировка задачи?
обработка текстов
Как называется графическое представление алгоритма:
Блок-схема
Какая процедура изображается на блок-схеме в виде ромба?
Проверка условия
В машине Поста или Тьюринга останов будет результативным:
По команде СТОП
Что называют служебными словами в алгоритмическом языке:
слова, смысл и способ употребления которых задан раз и навсегда
Что необходимо сделать на начальном этапе решения задачи на ЭВМ?
Четко сформулировать условие и цели задачи
В чем состоит структурный подход при разработке алгоритмов?
в алгоритме должен использоваться только стандартизированные комбинации элементов
Если в алгоритме происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то сложность алгоритма можно представить в виде:
f(n)=af(n/b)+d(n)+U(n)
Какие операции можно производить на машиной Тьюринга?
Композиция, ветвление, зацикливание
Какой фигурой на блок-схеме изображается операция ввода-вывода?
параллелограмм
Класс функций, растущих по крайней мере так же быстро, как f:
класс ОМЕГА
К значимым операциям при анализе алгоритмов относятся:
арифметические операции и операции сравнения
Для чего нужна отладка программы?
для проверки правильности работы программы и исправления ошибок
Какая из приведенных ниже последовательностей этапов решения задачи на ЭВМ считается более рациональной?
Математическая постановка, выбор метода решения, разработка алгоритма, составление программы, отладка, счет по программе
Как называется свойство применимости алгоритма к разным наборам входных данных?
массовостью
Вычислимая функция - это
функция, для которой существует вычисляющий её значения алгоритм
В чем состоит отличие цикла "ДО" от цикла "ПОКА"?
в цикле “ДО” проверка условия выхода из цикла производится после выполнения тела цикла, а в цикле “ПОКА” перед его выполнением
В машине Тьюринга система {q0,q1,q2,q3,...qn}:
внутренний алфавит
Класс Р определяет класс задач:
полиномиальной сложности
Наилучшим случаем для алгоритма является:
набор данных, на котором алгоритм выполняется за минимальное время
Простейшая функция, определяющая оператор сдвига:
рекурсивная функция
S(x)=x+1
Как называется структура с последовательным размещением блоков и групп?
следование
Если функция может быть получена за конечное число шагов из простейших функций при помощи конечного числа операции суперпозиции, схемы примитивной рекурсии, то она называется:
примитивно рекурсивной
Из перечисленных характеристик выберите общую особенность всех стандартных основных
алгоритмических структур
имеют один вход и выход, их можно соединить в любой последовательности
В алгоритмах Маркова ана система подстановок в алфавите А={a,b,c}: abc-c, ba-cb, ca-ab. Преобразуйте с помощью этой системы слово bacaabc
ccbcbbc
В классе О функция f образует:
верхнюю границу класса
Тезис Черча:
класс алгоритмически вычислимых функций совпадает с классом всех частично рекурсивных функций
Команда машины Поста имеет структуру n K m, где
n - порядковый номер команды; К - действие выполняемое головкой; m - номер следующей команды, подлежащей выполнению
Словесный способ записи алгоритмов представляет собой
описание последовательных этапов обработки данных
Основными критериями анализа алгоритмов являются:
классы входных данных, используемый объем памяти, количество времени
Рекурсия - это:
Способ задания функции при котором значение определяемой функции для произвольных значений аргументов выражается известным образом через значения определяемой функции для меньших значений аргументов
Цель процесса формализации алгоритмов:
Сравнение алгоритмов по эффективности и поиск наиболее эффективных алгоритмов
Функция называется частично рекурсивной, если она:
может быть получена за конечное число шагов из простейших функций при помощи операции суперпозиции, схемы примитивной рекурсии и оператора минимизации
Скорость роста функции входных данных определяется:
На бесконечности
Стуктурная теорема Бома-Джакопини:
С помощью композиции основных алгоритмических конструкций можно построить любой алгоритм
Рекурсия в алгоритме будет прямой, если
команда обращения алгоритма к самому себе находится в самом алгоритме
Функция называется общерекурсивной, если она:
частично рекурсивна и всюду определена
В машине Тьюринга команда Л для ленты означает:
переместиь ленту влево
В алгоритмическом языке с помощью конструкции КЦ...НЦ обозначается
Начало и конец цикла
В машине Поста некорректным алгортм будет в следующем случае:
Машина не останавливается никогда
Рекурсия в алгоритме будет косвенной, если
Рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение
Элементарное преобразование в алгоритмах Маркова:
подстановка одного слова вместо другого
Сколько существует команд машины Поста?
6
Задача является NP-полной, если
Существует способ сведения к ней всех остальных задач класса NP
К классу ТЕТА относятся функции:
растущие с той же скоростью, что функция f
Что является основным преимуществом записи алгоритма в виде блок-схемы?
наглядность в изображении переходов между отдельными шагами алгоритма
В чем состоит свойство определенности алгоритма?
каждый шаг алгоритма должен быть понятным и однозначным для исполнителя
Класс N - это класс:
количественно-зависимых по трудоемкости алгоритмов
Свойство алгоритма записываться в виде упорядоченной совокупности отделенных друг от друга предписаний:
дискретность
