Введение в алгоритмы

Упражнение 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

Если исходная машина произвела t шагов, то универсальная произведёт не более

Ответ:

(1) clogt

(2) ct²

(3) ce^t

Номер 2

Доказательство теоремы об универсальной машине Тьюринга является

Ответ:

(1) конструктивным

(2) деструктивным

(3) модификативным

Номер 3

Является ли доказательство теоремы об универсальной машине Тьюринга конструктивным?

Ответ:

(1) да, является

(2) нет, не является

(3) только в комплексном пространстве

Введение в алгоритмы - тест 2