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

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

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

Я готовлюсь к

Список задач

id 955391 балл

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

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

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

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

Алгоритм для Исполнителя:

	$λ$	$0$	$1$
$q_{0}$	$0, L, q_{1}$	$0, N, q_2$	$1, N, q_2$
$q_{1}$	$1, L, q_0$	$0, N, q_2$	$1, N, q_2$
$q_2$	$1, S, q_2$	$1, L, q_2$	$0, L, q_2$

После выполнения программы на ленте оказалась двоичная запись числа 682. Определите, на каком расстоянии от последовательности находилась головка в начальный момент времени (сколько шагов влево должна сделать каретка до того, как будет указывать на первый символ последовательности).

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

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

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

id 955461 балл

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

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

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

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

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

Алгоритм для Исполнителя:

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_{1}$
$q_{1}$	$λ, S, q_1$	$0, R, q_1$	$1, R, q_2$
$q_2$	$λ, S, q_2$	$0, R, q_1$	$1, R, q_3$
$q_3$	$λ, S, q_3$	$2, R, q_1$	$2, R, q_1$

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

id 955471 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955481 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

Определите максимально возможное число нулей в преобразованной последовательности.

id 955491 балл

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955501 балл

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955511 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955521 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955531 балл

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955541 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955551 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955561 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955571 балл

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

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

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

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

Алгоритм для Исполнителя:

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

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

id 955581 балл

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

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

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

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

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

Алгоритм для Исполнителя:

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

После выполнения программы в преобразованной строке оказалось поровну символов 0, 1 и 2. Определите максимально возможное число единиц в исходной последовательности.

id 955591 балл

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

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

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

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

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

Алгоритм для Исполнителя:

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_0$	$2, R, q_1$	$1, R, q_2$
$q_{1}$	$λ, S, q_1$	$0, R, q_1$	$1, R, q_2$
$q_2$	$λ, S, q_2$	$1, R, q_1$	$1, R, q_3$
$q_3$	$λ, S, q_3$	$2, R, q_1$	$1, R, q_2$

Определите максимально возможное число двоек в преобразованной последовательности.

id 955601 балл

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

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

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

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

Алгоритм для Исполнителя:

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_0$	$0, N, q_1$	$1, N, q_1$
$q_{1}$	$λ, S, q_0$	$0, R, q_1$	$1, R, q_2$
$q_2$	$λ, S, q_0$	$0, R, q_1$	$1, R, q_3$
$q_3$	$λ, S, q_0$	$0, R, q_3$	$0, R, q_1$

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

id 955611 балл

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

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

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

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

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

Алгоритм для Исполнителя:

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_0$	$0, N, q_1$	$1, N, q_1$
$q_{1}$	$λ, S, q_0$	$0, R, q_1$	$1, R, q_2$
$q_2$	$λ, S, q_0$	$0, R, q_2$	$1, R, q_3$
$q_3$	$λ, S, q_0$	$0, R, q_3$	$0, R, q_1$

В результате на ленте оказалось 60 единиц и 40 нулей. Определите максимальное число единиц в исходной последовательности.

id 955621 балл

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

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

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

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

Алгоритм для Исполнителя:

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

В результате на ленте оказалась последовательность с суммой цифр, превышающей 1200. Определите максимально возможное число единиц в исходной последовательности.

id 955631 балл

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

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

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

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

Алгоритм для Исполнителя:

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

В результате на ленте оказалась последовательность с суммой цифр, превышающей 1200. Определите минимально возможное число нулей в исходной последовательности.