Открытый Банк заданий ЕГЭ по информатике, стр. 347 с ответами и решениями

Каталог заданий

Найдите нужные задания по ЕГЭ, информатике, номеру или теме. Любое задание можно открыть в каталоге или решить в тренажёре.

Я готовлюсь к

Список задач

	$λ$	$0$	$1$
$q_{0}$	$λ, L, q_0$	$1, S, q_1$	$0, L, q_1$
$q_{1}$	$1, S, q_1$	$1, S, q_0$	$0, L, q_1$

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_1$
$q_{1}$	$λ, S, q_1$	$1, S, q_1$	$0, R, q_1$

id 830411 балл

Задания на машину Тьюринга

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A=\{a_{0},a_{1},…,a_{n–1}\}$ ), включая специальный пустой символ $a_{0}$ .

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q=\{q_{0},q_{1},…,q_{n–1}\}$ . В начальный момент времени головка находится в начальном состоянии $q_{0}$ .

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении $i$ -й строки и $j$ -го столбца находится команда, которую выполняет МТ, когда головка обозревает $j$ -й символ, находясь в $i$ -м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов $«L»$ , $«R»$ , $«N»$ , $«S»$ . Символы $«L»$ и $«R»$ означают сдвиг в левую или правую ячейки соответственно, $«N»$ – отсутствие сдвига, $«S»$ – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда $0, L, q_{3}$ выполняется следующим образом: в текущую ячейку записывается символ $«0»$ , затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_{3}$ .

Выполните задание

На ленте в соседних ячейках записана двоичная запись числа 32768, с неизвестным количеством ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.

Программа работы исполнителя:

	$λ$	$1$	$0$
$q_{0}$	$λ, L, q_{1}$
$q_{1}$	$λ, S, q_1$	$0, S, q_2$	$1, L, q_2$
$q_2$	$λ, S, q_1$	$1, L, q_1$	$0, L, q_1$

После выполнения программы на ленте осталось ровно 200 нулей. Определите максимально возможное число нулей в исходной последовательности.

id 830421 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A=\{a_{0},a_{1},…,a_{n–1}\}$ ), включая специальный пустой символ $a_{0}$ .
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q=\{q_{0},q_{1},…,q_{n–1}\}$ . В начальный момент времени головка находится в начальном состоянии $q_{0}$ .
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
$a_{0}$
$a_{1}$
...
$q_{0}$
команда
команда
...
$q_{1}$
команда
команда
...
...
...
...
...
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении $i$ -й строки и $j$ -го столбца находится команда, которую выполняет МТ, когда головка обозревает $j$ -й символ, находясь в $i$ -м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов $«L»$ , $«R»$ , $«N»$ , $«S»$ . Символы $«L»$ и $«R»$ означают сдвиг в левую или правую ячейки соответственно, $«N»$ – отсутствие сдвига, $«S»$ – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда $0, L, q_{3}$ выполняется следующим образом: в текущую ячейку записывается символ $«0»$ , затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_{3}$ .
Выполните задание
На ленте исполнителя МТ в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей слева к последовательности ячейке.
Программа работы исполнителя:
$λ$
$0$
$1$
$q_{0}$
$λ, R, q_{1}$
$q_{1}$
$λ, S, q_1$
$1, R, q_1$
$0, R, q_1$
После выполнения программы на ленте оказалось двоичная запись числа 415. Определите десятичное значение наибольшего числа, меньшего, чем 70000, которое могло быть записано на ленте до начала работы программы.