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

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

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

Я готовлюсь к

Список задач

id 830631 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $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}$ .
Выполните задание
На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:

$λ$
$0$
$1$
$q_0$
$λ, L, q_1$
$0, L, q_1$
$0, L, q_1$
$q_1$
$λ, S, q_1$
$0, L, q_0$
$1, L, q_0$
После выполнения программы на ленте осталось ровно 101 единица. Определите максимально возможное число единиц в исходной последовательности.
id 830641 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $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}$ .
Выполните задание
На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, которые могут включать только нули, единицы и тройки. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:

$λ$
$3$
$1$
$0$
$q_0$
$λ, L, q_1$

$q_1$
$λ, S, q_1$
$0, L, q_1$
$1, L, q_1$
$3, L, q_1$
После выполнения программы сумма цифр на ленте оказалась ровно 100. Определите, сколько было троек, при максимально возможном числе единиц в исходной последовательности.

	$λ$	$0$	$1$
$q_0$	$λ, L, q_1$	$0, L, q_1$	$0, L, q_1$
$q_1$	$λ, S, q_1$	$0, L, q_0$	$1, L, q_0$

	$λ$	$3$	$1$	$0$
$q_0$	$λ, L, q_1$
$q_1$	$λ, S, q_1$	$0, L, q_1$	$1, L, q_1$	$3, L, q_1$

id 830651 балл

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

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $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}$ .

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

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

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

	$λ$	$0$	$1$	$2$
$q_0$	$λ, R, q_1$
$q_1$	$λ, L, q_2$	$2, R, q_1$	$X, R, q_1$	$1, R, q_1$
$q_2$	$λ, S, q_2$	$1, L, q_2$	$2, L, q_2$	$0, L, q_2$

Символом $X$ в программе обозначена цифра из алфавита МТ. Известно, что количество символов 0 и 1 в исходной строке было одинаково, а сумма значений в исходной строке больше суммы значений в конечной строке на 363.

В качестве ответа укажите количество цифр $X$ в конечной строке.

id 830661 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $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}$ .
Выполните задание
На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.
Программа работы исполнителя:

$λ$
$0$
$1$
$2$
$q_0$
$λ, R, q_1$

$q_1$
$λ, S, q_1$
$2, R, q_1$
$0, R, q_1$
$1, R, q_1$
Известно, что количество символов 0 в конечной строке было в 2 раза больше, по сравнению с количеством символов 2 в исходной строке, а сумма значений в исходной строке меньше суммы значений в конечной строке на 1640. Определите количество цифр 0 в исходной строке.
id 830671 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $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}$ .
Выполните задание
На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.
Программа работы исполнителя:

$λ$
$0$
$1$
$2$
$q_0$
$λ, R, q_1$

$q_1$
$λ, S, q_1$
$2, R, q_1$
$0, R, q_1$
$1, R, q_1$
Известно, что количество символов 1 и 2 в исходной строке было одинаково, а сумма значений в исходной строке больше суммы значений в конечной строке на 178. Определите количество цифр 2 в исходной строке.