Рабочий лист на тему:

Машина Тьюринга и машина Поста

Информатика11 класс15 заданий
Заполни пропускиСоединениеМножественный выборИстина / ЛожьТаблицаПоследовательность

Типы заданий

Заполни пропускиСоединениеМножественный выборИстина / ЛожьТаблицаПоследовательность
Машина Тьюринга и машина Поста

11 класс · дифференцированный

Ф.И.
Класс


Разберём, как абстрактные машины выполняют алгоритмы шаг за шагом, и научимся читать их команды, состояния и изменения на ленте.

№1 · Понятия

1 пропуск · 1 балл

1. Основные элементы машины Тьюринга

Заполните пропуск в определении.

Машина Тьюринга работает с бесконечной лентой, разделённой на отдельные .

№2 · Команды

3 связки · 1 балл

2. Команды машины Тьюринга

Соедините каждую команду машины Тьюринга с её действием.

№3 · Сравнение

1 вопрос · 1 балл

3. Алфавит машины Тьюринга

Выберите верное утверждение о рабочем алфавите машины Тьюринга.

  • Рабочий алфавит состоит только из цифр от 0 до 9.
  • Рабочий алфавит содержит только команды движения головки.
  • Рабочий алфавит содержит символы, которые машина может читать и записывать на ленте.
  • Рабочий алфавит задаёт только количество состояний машины.

№4 · Команды

4 связки · 2 балла

4. Команды машины Поста

Соедините команды машины Поста с их назначением.

№5 · Понятия

1 пропуск · 1 балл

5. Программа машины Поста

Заполните пропуск в определении.

В машине Поста команды программы обращаются с символами на ленте и перемещают рабочий .

№6 · Алгоритмы

1 вопрос · 2 балла

6. Остановка машины Поста

Прочитайте последовательность команд машины Поста: «Поставить 1; Вправо; Стереть 1; Стоп». Какое действие выполнит машина последним?

  • Переместится ещё на одну ячейку вправо.
  • Поставит метку в исходной ячейке.
  • Начнёт выполнение программы сначала.
  • Остановится после стирания метки в новой ячейке.

№7 · Состояния

3 пропуска · 2 балла

7. Команда машины Тьюринга

Заполните пропуски в записи команды машины Тьюринга. Команда должна: если прочитан символ 0, записать 1, перейти вправо и остаться в состоянии q1.

Запись команды: q0, 0 → , , .

№8 · Трассировка

3 связки · 2 балла

8. Изменение ленты после выполнения команд

Соедините начальную конфигурацию с результатом выполнения указанной последовательности команд машины Тьюринга. Головка в начале находится над первой ячейкой.

+8 заданий в этом листе

Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.

№9 · Алгоритмы

1 вопрос · 3 балла

9. Пошаговая работа машины Поста

На ленте машины Поста записана последовательность 111, курсор находится над первой меткой. Программа повторяет цикл: «Вправо; если клетка пуста — поставить 1 и перейти к команде Стоп; иначе повторить цикл». Что произойдёт после выполнения программы?

  • Машина сотрёт все три исходные метки и остановится.
  • Машина будет бесконечно двигаться вправо по занятым клеткам.
  • Машина добавит одну метку справа от исходной последовательности и остановится.
  • Машина добавит метку слева от исходной последовательности и остановится.

№10 · Сравнение моделей

4 пропуска · 3 балла

10. Сопоставление машин Тьюринга и Поста

Заполните пропуски, сравнивая две модели алгоритмов.

У машины Тьюринга есть управляющие , а машина Поста использует последовательность команд с переходами по . Обе модели работают с и предназначены для формального описания .

№1 · Основные понятия

4 варианта · 1 балл

1. Устройство машины Тьюринга

Выберите одно верное утверждение о машине Тьюринга.

  • В машине Тьюринга головка всегда движется только вправо.
  • Машина Тьюринга состоит из ленты, головки и управляющего устройства.
  • Машина Тьюринга работает только с десятичными числами.
  • Машина Тьюринга не может изменять символы на ленте.

№2 · Верно или ложно

4 утверждения · 1 балл

2. Свойства моделей вычислений

Определите истинность каждого утверждения, опираясь на определения машины Тьюринга и машины Поста.

  1. Лента машины Тьюринга разбита на ячейки.
  2. Машина Поста использует только команды рисования картинок.
  3. В машине Тьюринга головка может читать символ и записывать символ.
  4. Машина Поста не использует ленту с ячейками.

№3 · Сопоставление

4 пары · 2 балла

3. Команды машин и их назначение

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

№4 · Схема работы

3 строки · 2 балла

4. Сравнение машин Тьюринга и Поста

Заполните пропуски в таблице, используя определения двух моделей. В каждой строке первый столбец уже содержит признак сравнения.

ПризнакМашина ТьюрингаМашина Поста
Рабочая область
Основной элемент управления
Действие с текущей ячейкой

№5 · Алгоритм

5 шагов · 2 балла

5. Порядок выполнения команды машины Тьюринга

Расположите действия машины Тьюринга в правильной последовательности для одного шага работы.

  1. Записать новый символ в ячейку
  2. Перейти в новое состояние
  3. Считать символ в текущей ячейке
  4. Получить команду для текущего состояния и символа
  5. Переместить головку влево, вправо или оставить на месте

Создайте уникальный лист по своей теме

  • Любая тема, любой уровень
  • 20+ типов заданий
  • 100% уникальный контент
  • Со страницей ответов
  • Защита от списывания
  • Готово за 1 минуту

Другие темы по информатике для 11 класса

Обновление драйверов, конфигурирование системы, управление ресурсами локальной сетиОптимизация контента и индексирование сайта поисковыми системамиОбработка текстовой информацииСоздание и форматирование документа с помощью текстового редактора MS Word. Создание структурированного документаСредства искусственного интеллектаФункции в Python: основные встроенные и создание собственныхВиды деятельности в сети Интернет, сервисы Интернета, сетевой этикет, проблема подлинности полученной информации, государственные электронные сервисы и услуги, открытые образовательные ресурсыАнализ правильности скобочного выраженияСетевое хранение данных и цифрового контента. Облачные сервисы. Цифровые сервисы государственных услуг. Разделение прав доступа в облачных хранилищах. Соблюдение мер безопасности, предотвращающих незаконное распространение персональных данныхДискретные игры двух игроков с полной информациейОсновные сведения об алгоритмахЦиклы с условием. Циклы по переменной; Язык программирования. Основные конструкции языка; Типы данных: целочисленные, вещественные, символьные, логические; Ветвления. Составные условия; Этапы решения

Чем удобны рабочие листы Нейрум

  • По действующей программеТемы и задания совпадают со школьной программой 1–11 классов. Открыли — дали классу, без правок.
  • Готово к печати, с ответамиPDF в формате A4 и ключ ответов на отдельной странице. Скачали, распечатали, раздали — без правок в Word.
  • Свой лист за минутуНе нашли нужный? ИИ-конструктор соберёт лист по вашей теме, классу и типам заданий.

Вопросы и ответы

Как скачать рабочий лист «Машина Тьюринга и машина Поста»?

Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.

Сколько заданий в листе и какие они?

В листе 15 заданий: заполни пропуски, соединение, множественный выбор, истина / Ложь, таблица, последовательность.

Соответствует ли лист ФГОС?

Да, задания ориентированы на школьную программу по информатике для 11 класса по ФГОС.

Можно ли изменить задания под свой класс?

Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.