Ответы на модуль 2 (ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ) по предмету математическая логика.
1) Какая из перечисленных записей называется формулой подстановки (P, Q)? P -> Q.
2) Как называется функция f, заданная на некотором множестве слов алфавита A? нормально вычислимой функцией.
3) Какое свойство алгоритма означает, что описываемый алгоритмом процесс и сам алгоритм не могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнения? дискретность.
4) Какой символ, используемый в схемах алгоритмов, отображает выход во внешнюю среду и вход из внешней среды? терминатор.
5) Какое свойство алгоритма предполагает, что алгоритм может быть пригоден для решения всех задач данного типа? массовость.
6) Какое свойство алгоритма обеспечивает однозначность результата вычислительного процесса при заданных исходных данных? определенность.
7) Сколько входных и выходных лент имеет многоленточная машина Тьюринга? несколько входных лент и одну выходную.
8) Какой символ, используемый в схемах алгоритмов, отображает альтернативную связь между двумя и более символами? пунктирная линия.
9) Как называется операция получения новой функции по имеющимся функциям: по правилу ? суперпозицией.
10) Как называется правило построения последовательности слов в алфавите A, исходя из данного слова V в этом алфавите? нормальным алгоритмом (Маркова) в этом алфавите.
11) Что записывается на ленте машины Тьюринга? исходные данные и затем — результат.
12) Как называются свойства текстов, описывающих алгоритм? синтаксические свойства.
13) Какая из перечисленных операций называется минимизацией? операция построения новой функции по известной функции по правилу.
14) Какие из перечисленных классов функций (заданных на натуральных числах и принимающих натуральные значения) совпадают? класс всех функций, вычислимых по Тьюрингу, класс всех частично рекурсивных функций и класс всех нормально вычислимых функций.
15) Если A и B — два алфавита, причем , то: алфавит B называется расширением алфавита A.
16) В чем состоит смысл теоремы Райса? в том, что по описанию алгоритма, вычисляющего функцию, ничего нельзя узнать о свойствах функции, которую он вычисляет.
17) Кто является автором тезиса: «Класс интуитивно вычислимых функций совпадает с классом частично рекурсивных функций»? А. Чёрч.
18) Какой символ в схемах алгоритмов может быть использован для обозначения заголовка цикла? подготовка.
19) Какой схемой не может быть представлено предписание о последовательности действий алгоритма? эквивалентной схемой.
20) Какой фигурой обозначается вершина граф-схемы алгоритма операторного типа? прямоугольником.
21) Что из перечисленного является внутренней памятью машины Тьюринга? конечное множество состояний.
22) Для чего в схемах алгоритмов используется символ «процесс»? для обозначения операции присваивания.
23) Какой фигурой в схемах алгоритмов обозначается символ «решение»? ромбом.
24) Чем определяется каждая машина Тьюринга? своим алфавитом, состоянием внутренней памяти и программой.
25) Какая теорема устанавливает алгоритмическую неразрешимость вообще всякого нетривиального свойства вычислимых функций? теорема Райса.