Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…
Пусть машина Тьюринга M
построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн
и Пуст
, описанных в задаче 4, и машин
Выбin
– выбирает i
-ый аргумент из n
аргументов: x1*…*xi*…*xn ⇐ xi
,Большеij
- выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn
i
-ый аргумент xi
больше j
-ого аргумента xj
, иначе выдает 1,
с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:
M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );
if Больше21 then par#( Пуст, Умн ) else par#( Пуст, Сум ) endif;
Зам(#, *); Выб33.
Какие результаты она получит на входных данных вида |x1 * |x2
при x1 = 4, x2 = 8
и при x1 = 1, x2 = 5
, соответственно?
вопрос
Выбin
– выбирает i
-ый аргумент из n
аргументов: x1*…*xi*…*xn ⇐ xi
,Большеij
- выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn
i
-ый аргумент xi
больше j
-ого аргумента xj
, иначе выдает 1,Правильный ответ:
12 и 5
12 и 6
32 и 5
32 и 6
ни один из предыдущих ответов не подходит
Сложность вопроса
72
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
спасибо за пятёрку
28 окт 2018
Аноним
Кто находит эти тесты интуит? Это же очень простые ответы
27 фев 2016
Аноним
спасибо за ответ
25 ноя 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)} ( для каждого ребра третий параметр после ; - его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.
- # Какой язык L является конкатенацией двух языков: L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?
- # Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {R}, ΦA > с программой ΦA: { Q a → P, Q b → Q, P b → P, P a → R, R a → Q, R b → S, S a → S, S b → S} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = aba, h(1) = aa, h(2) = ε Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)? С1 = < {0, 1}, { Q, P, R, S }, 0, F1={ R }, Φ1>, С2 = < {0, 1}, { Q, P, R, S }, 0, F2={ R }, Φ2>, С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ R }, Φ3>, где программы заданы в следующих таблицах. [Большая Картинка]
- # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2 ?
- # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа x, отличных от 1 и самого x?