Алгоритмы и теория вычислений

Упражнение 1:

Номер 1

Некоторая процедура, состоящая из конечного числа шагов, строго определенных на конкретном наборе данных, называется:

Ответ:

(1) функцией

(2) алгоритмом

(3) графом переходов

Номер 2

Основными свойствами алгоритма являются:

Ответ:

(1) массовость

(2) результативность

(3) однозначность результата

Номер 3

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

Ответ:

(1) результативностью

(2) массовостью

(3) однозначностью результата

Упражнение 2:

Номер 1

Свойство алгоритма, заключающееся в том, что при одних и тех же данных получается один и тот же результат, называется:

Ответ:

(1) результативностью

(2) массовостью

(3) однозначностью результата

Номер 2

Схема определения понятия "Алгоритм" включает:

Ответ:

(1) данные

(2) память

(3) элементарный шаг

Номер 3

Детерминированность в теории алгоритма означает:

Ответ:

(1) правило инициации

(2) определение следующего шага

(3) правило окончания

Упражнение 3:

Номер 1

Классификация алгоритмических моделей включает следующие группы:

Ответ:

(1) абстрактные машины

(2) вычислимые функции

(3) комбинаторные модели

Номер 2

Представителями класса моделей "Абстрактные машины" являются:

Ответ:

(1) машина Тьюринга

(2) машина Поста

(3) машина Джексона

Номер 3

Машина Тьюринга состоит из:

Ответ:

(1) бесконечной в обе стороны ленты

(2) управляющего устройства

(3) головки, которая может считывать символы с ленты и записывать их на ленту

Упражнение 4:

Номер 1

Если машина Тьюринга зацикливается на некотором слове, это означает, что:

Ответ:

(1) машина не имеет точки останова для этого слова

(2) машина работает с ошибками

(3) функция, вычисляемая машиной Тьюринга, на данном слове не определена

Номер 2

Машина Тьюринга может быть задана:

Ответ:

(1) списком команд

(2) таблицей

(3) графом переходов

Номер 3

Граф,задающий машину Тьюринга, обладает следующими свойствами::

Ответ:

(1) это ориентированный граф

(2) это мультиграф

(3) на ребрах графа записывается формула перехода машины из состояния в состояние

Упражнение 5:

Номер 1

К операциям над машинами Тьюринга относятся:

Ответ:

(1) суперпозиция машин Тьюринга

(2) операция условного перехода

(3) извлечение корня из машины Тьюринга

Номер 2

К особенностям программирования машин Тьюринга относятся:

Ответ:

(1) отсутствие доступа по адресу

(2) ограниченные возможности запоминания

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

Номер 3

Характерными свойствами головки машины Тьюринга являются:

Ответ:

(1) возможность перемещения в обе стороны

(2) элементарное перемещение головки равно одной ячейке

(3) элементарное перемещение головки равно задаваемому оператором числу ячеек

Упражнение 6:

Номер 1

Головка машины Тьюринга имеет возможность:

Ответ:

(1) чтения информации с ленты

(2) записи информации на ленту

(3) перемещения по ленте только в одном направлении

Номер 2

Машина Тьюринга и машина Поста относятся к классу:

Ответ:

(1) легковых машин

(2) абстрактных машин

(3) комбинаторных моделей

Номер 3

Говоря об абстрактных машинах, чаще всего имеют в виду машины Тьюринга, потому что:

Ответ:

(1) работы по ним были раньше других опубликованы

(2) у них благозвучное название

(3) других абстрактных машин не существует

Упражнение 7:

Номер 1

Примером примитивно-рекурсивной функции является:

Ответ:

(1) константа ноль

(2) функция прибавления единицы

(3) функция тождества

Номер 2

Оператор суперпозиции функций является примером:

Ответ:

(1) оператора языка программирования

(2) примитивно-рекурсивной функции

(3) алфавита языка программирования

Номер 3

Суперпозиция - это

Ответ:

(1) общий случай рекурсии

(2) частный случай рекурсии

(3) то же самое, что и рекурсия

Упражнение 8:

Номер 1

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

Ответ:

(1) выводу о несостоятельности теории рекурсивных функций

(2) образованию класса частично-рекурсивных функций

(3) выводу о тождественности операций суперпозиции и рекурсии

Номер 2

Класс частично-рекурсивных функций образуют функции, которые

Ответ:

(1) определены во всех точках

(2) определены не во всех точках

(3) невычислимы в рамках теории рекурсивных функций

Номер 3

Тезис Чорча гласит:

Ответ:

(1) всякая частично-рекурсивная функция является вычислимой

(2) всякая вычислимая функция является частично-рекурсивной

(3) никакая вычислимая функция не является частично-рекурсивной

Упражнение 9:

Номер 1

Тезис Тьюринга гласит:

Ответ:

(1) ни для одной вычислимой функции не существует машины Тьюринга, ее вычисляющей

(2) для каждой вычислимой функции существует машина Тьюринга, ее вычисляющая

(3) для любой произвольной функции существует машина Тьюринга, ее вычисляющая

Номер 2

Отличие тезиса от теоремы заключается в

Ответ:

(1) том, что теорема доказывается, а тезис - нет

(2) том, что в теореме все используемые понятия и термины строго определены, а в тезисе - нет

(3) написании - по сути это идентичные понятия

Номер 3

Выберите верное:

Ответ:

(1) любая частично-рекурсивная функция вычислима по Тьюрингу

(2) всякая вычислимая по Тьюрингу функция является частично-рекурсивной

(3) определения понятия алгоритма по Тьюрингу и в терминах теории рекурсивных функций эквивалентны

Упражнение 10:

Номер 1

Выберите верное:

Ответ:

(1) всякая функция, вычислимая по Тьюрингу, вычислима по Маркову

(2) всякая функция, вычислимая по Маркову, вычислима по Тьюрингу

(3) всякое произвольно взятое уравнение вычислимо по Тьюрингу

Номер 2

Если для любого произвольно взятого элемента можно определить, принадлежит он некоторому множеству или нет, то такое множество называется:

Ответ:

(1) определимым

(2) элементарным

(3) разрешимым

Номер 3

Множество, которое может быть порождено некоторой вычислимой функцией, называется:

Ответ:

(1) вычислимым

(2) перечислимым

(3) определимым

Упражнение 11:

Номер 1

Множество корней некоторого уравнения является примером

Ответ:

(1) перечислимого множества

(2) разрешимого множества

(3) рекурсивного множества

Номер 2

Множество степеней тройки является примером

Ответ:

(1) перечислимого множества

(2) рекурсивного множества

(3) разрешимого множества

Номер 3

Множество называется перечислимым, если

Ответ:

(1) оно является областью значений некоторой всюду определенной вычислимой функции

(2) оно является областью определения некоторой вычислимой функции

(3) существует алгоритм, определяющий для каждого произвольного элемента признак принадлежность данному множеству

Упражнение 12:

Номер 1

Выберите верное:

Ответ:

(1) всякое разрешимое множество перечислимо

(2) всякое перечислимое множество разрешимо

(3) существует множество, которое перечислимо, но неразрешимо

Номер 2

Свойствами алгоритма не являются:

Ответ:

(1) узкая специализация

(2) неоднозначность результата

(3) нерезультативность

Номер 3

Сходимость алгоритма означает, что

Ответ:

(1) алгоритм завершит работу через конечное число шагов

(2) алгоритм не завершит работу через конечное число шагов

(3) алгоритм применим для решения широкого круга задач

Алгоритмы и теория вычислений - тест 4