Скрытый текст
*
Укажите верные утверждения:
1. Универсальный алгоритм (относительно нормальных алгоритмов) -
нормальный алгоритм, который выполняет работу любого нормального
алгоритма, если на вход поступает изображение этого последнего
алгоритма вместе с изображением определенного входного слова.
2. Изображение любого нормального алгоритма строится только в
двоичном алфавите.
3. Универсальный алгоритм всегда применен к слову, которое есть
изображением любого нормального алгоритма с приписанным
по правую сторону изображением любого входного слова, независимо от
того входит это входное слово в область определения последнего
алгоритма или нет.
A. 1 B. 2 C. 3 D. 1,2 E. 1,3 F. 2,3 G. 1,2,3
*
Укажите ошибочные утверждения:
1. Нормальный алгоритм, который может быть примененным к любому
слова, называется универсальным нормальным алгоритмом.
2. Невозможно построить такую машину, которая могла бы выполнять работу
любого алгоритма (не только нормального).
3. Соответственно принципу нормализации, машина, которая реализует роботу
любого алгоритма, может быть построенной лишь на системе
нормальных алгоритмов.
A. 1 B. 2 C. 3 D. 1,2 E. 1,3 F. 2,3 G. 1,2,3
*
Укажите ошибочные утверждения:
1. Нормальный алгоритм, который может быть примененным к любому
слова, называется универсальным нормальным алгоритмом тогда
i только тогда, когда это слово является изображением любого другого
нормального алгоритма.
2. Не существуют такие слова (в двоичном алфавите), к которым не может
быть примененный универсальный нормальный алгоритм.
3. Если универсальный нормальный алгоритм не применен к определенному
слова, то это слово - не в двоичном алфавите.
A. 1 B. 2 C. 3 D. 1,2 E. 1,3 F. 2,3 G. 1,2,3
*
Укажите верные утверждения:
1. Любая арифметическая функция f(x) определяется для всех
целочисельных значений аргумента.
2. Любая арифметическая функция f(x) определяется для всех
Неотъемлемых целочисельных значений своего аргумента.
3. Любая арифметическая функция f(x) может быть не определенной
для некоторых значений своего аргумента.
A. 1 B. 2 C. 3 D. 1,3 E. 2,3
*
Укажите верные утверждения:
1. Если в определенном нормальном алгоритме первой подстановкой
есть подстановка, которая заменяет пустое слово на любое другое, то
этот алгоритм никогда не завершится.
2. Если в определенном нормальном алгоритме последней подстановкой
есть подстановка, которая заменяет пустое слово на любое другое, то
эта подстановка, хотя раз, но выполнится.
A. 1 B. 2 C. 1,2 D. Верных утверждений нет
*
Укажите ошибочные утверждения:
1. Если в определенном нормальном алгоритме нет конечных подстановок,
он никогда не завершит свою работу.
2. Если в определенном нормальном алгоритме существует хотя бы одна
конечная подстановка, он всегда завершит свою работу.
3. Если определенный нормальный алгоритм состоит лишь из конечных
подстановок то результатом его работы всегда будет осуществление
только одной подстановки, не обязательно первой.
A. 1 B. 2 C. 3 D. 1,2 E. 1,3 F. 2,3 G. 1,2,3
*
Укажите ошибочные утверждения:
1. Существуют нормальные алгоритмы, которые могут быть не реализованными
универсальным нормальным алгоритмом.
2. Алфавитный оператор A(p)=pp невозможно реализовать нормальным
алгоритмом потому, что заведомо неизвестная длина слова p.
A. 1 B. 2 C. 1,2 E. Все утверждения верные
*
Укажите ошибочные утверждения:
1. Существует такая подстановка, которая выполнится для любого
слова.
2. Существует такая подстановка, для которой невозможно подобрать
слово, чтобы эта подстановка выполнилась.
A. 1 B. 2 C. 1,2 E. Все утверждения верные
*
Минимальное количество подстановок в нормальном алгоритме, который
реализует алфавитный оператор A(p)=*p*, где p=aa...a (n букв a):
A. Две B. Три C. Четыре D. Зависит от значения n
*
Минимальное количество подстановок в нормальном алгоритме, который
реализует алфавитный оператор A(p)=p*, где p=aa...a (n букв a):
A. Одна B. Две C. Три D. Зависит от значения n
*
Минимальное количество подстановок в нормальном алгоритме, который
реализует алфавитный оператор A(p)=*, где p=aa...a (n букв a):
A. Одна B. Две C. Три D. Зависит от значения n
*
В каких алгоритмических системах порядок команд не влияет на
результат работы алгоритма ?
1. Нормальные алгоритмы Маркова
2. Машина Тюринга
3. Алгоритмическая система Поста
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3
*
Укажите количество категорий (типов) команд в алгоритмической
системе Поста:
A. 4 B. 5 C. 6 D. 7 E. 8
*
ЗАДАЧА I. Создать алгоритм, который бы для заданного слова
(или массива меток) дописал бы справа один символ (или одну метку).
ЗАДАЧА II. Создать алгоритм, который бы для заданного слова (или
массива меток) дописал бы справа два символ (или две метки).
В какой алгоритмической системе как задача I, так i задача II
реализуются одинаковым количеством команд ?
1. Нормальные алгоритмы Маркова
2. Машина Тюринга
3. Алгоритмическая система Поста
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3 G. Ни в одной
*
Минимальное количество команд в нормальном алгоритме, который
любое слово длины 5 в алфавите {a,b,c} превращает в
"ерунды" слово:
A. 1 B. 2 C. 3 D. 4 E. 5 F. Больше пяти
*
Минимальное количество команд в нормальном алгоритме, который
любое слово длины 3 в алфавите {a,b,c,d,f} превращает в
"ерунды" слово:
A. 1 B. 2 C. 3 D. Больше трех
*
Что можно сказать о приведенных ниже нормальных алгоритмах
(где e - "ерунды" слово) ?
I) a -> d II) a -> d III) d -> e
d -> e d -> e a -> d
b -> c c -> e c -> e
c -> e b -> c b -> c
A. Они эквивалентные.
B. Они не эквивалентные.
C. Они эквивалентные только для входных слов из алфавита {a,b}
*
Минимальное количество состояний (без учета начального и
конечного состояния Halt) программы для машины Тюринга, которая просто
"просматривает" все слова длины 4 в двоичном алфавите, например:
Начало работы программы Конец работы программы
*0110* *0110*
A. 1 B. 2 C. 3 D. 4 E. Больше четырех
*
Минимальное количество состояний (без учета начального и
конечного состояния Halt) программы для машины Тюринга, которая просто
"просматривает" все слова длины 2 в алфавите {0,1,2,3}, например:
Начало работы программы Конец работы программы
*13* *13*
A. 1 B. 2 C. 3 D. 4 E. Больше четырех
*
Минимальное количество состояний (без учета начального и
конечного состояния Halt) программы для машины Тюринга, которая реализует
инверсию (0 заменяет на 1, а 1 заменяет на 0) любого слова
в двоичном алфавите:
A. 1 B. 2 C. Совпадает с длиной слова D. Больше длины слова
*
Завершите правильно утверждение:
В алгоритмической системе Поста допустим использование ...
A. ... любого количества разных меток.
B. ... только единого символ для обозначения всех меток.
C. ... не больше двух разных символов для обозначения всех меток.
*
Количество слов длины 3 в алфавите {a,b}, для которых примененный
нормальный алгоритм (где e - "ерунды" слово):
a ->.b
e -> a
A. 0 B. 4 C. 8
*
Количество слов длины 3 в алфавите {a,b}, для которых не примененный
нормальный алгоритм (где e - "ерунды" слово):
a ->.b
e -> a
A. 0 B. 4 C. 8
*
К элементарным арифметическим функциям принадлежат:
1. Функция f(x)=0
2. Функция f(x)=1
3. Функция f(x)=x
4. Функция f(x)=x+1
5. Функция f(x)=x-1
A. 1,2 B. 1,3 C. 3,4 D. 1,3,4 E. 1,2,3 F. 3,4,5 G. Все
*
Укажите верные утверждения
1. Однозначные алфавитные операторы ставят в соответствие каждому
входному слову одно i только одно исходное слово.
2. Однозначные алфавитные операторы ставят в соответствие каждому
входному слову не больше одного исходного слова.
3. Алфавитным оператором называется любая функция, которая ставит
в соответствие словам в определенном алфавите слова в тому самому
алфавите.
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3
*
Укажите ошибочные утверждения
1. Кодируя отображение всегда будет обратным, если коды всех букв
входного алфавита имеют одинаковую длину.
2. Кодируя отображение всегда будет обратным, если коды разных
букв входного алфавита разные.
3. Кодируя отображение всегда будет обратным, если коды всех
букв входного алфавита строятся на основе двоичного алфавита.
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3 G. 1,2,3
*
Укажите верные утверждения
1. Любой алфавитный оператор может быть задан таблицей
соответствия.
2. Любой алфавитный оператор, область определения которого
составляется со слов в двоичном алфавите может быть заданный
таблицей соответствия.
3. Любой алфавитный оператор, область определения которого
есть оконченной, может быть заданный таблицей соответствия.
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3
*
Укажите верные утверждения
1. Если алфавитный оператор есть многозначным, то область его
определение неконченая.
2. Любые процессы преобразования информации фактически могут
сводиться к алфавитным операторам.
3. Возвратность кодирования не обеспечивается лишь одним условием о
несовпадении кодов разных букв.
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3
*
Укажите ошибочные утверждения
1. Все алгоритмы можно нормализовать.
2. Строгого математического доведения принципа нормализации не существует.
3. Алфавитный оператор A(p)=pp может быть реализованный нормальным
алгоритмом, который состоит лишь из заключительных подстановок.
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3
*
Укажите верные утверждения
1. Разветвление алгоритмов является композицией двух алгоритмов.
2. Повторение (итерация) является композицией трех алгоритмов.
3. Суперпозиция алгоритмов - один из видов композиции
любого оконченного количества алгоритмов.
A. 1 B. 2 C. 3 D. 2,3 E. 1,2 F. 1,3
*
Завершите правильно утверждение:
Если слова в алфавите А кодируются словами в алфавите В, то ...
A. ... в алфавите У больше литер, чем в алфавите А.
B. ... в алфавите В одинаковое количество букв с алфавитом А.
C. ... в алфавите В может быть любое количество букв, кроме одной.
D. Правильных утверждения не приведены.
*
Если Вы склонны к риску, то нажмите в ответ на любую
с трех клавиша - "A", "B", "C". Только одна из них есть верной.
*
Нахабству нашему немає меж.
Ваши права
