ВойтиПопробовать бесплатно

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

Машина Тьюринга

Информатика10 класс10 заданий
Краткий ответСоединениеПоследовательностьЗаполни пропускиМножественный выбор

Типы заданий

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

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

Ф.И.
Класс

Разберитесь, как машина Тьюринга хранит информацию, перемещает головку и выполняет алгоритм шаг за шагом. В конце попробуйте проследить работу машины на нетривиальных примерах.

№1 · ОПРЕДЕЛЕНИЕ

1 ТЕРМИН · 1 БАЛЛ

1. Назначение ленты

Как называется бесконечная или потенциально бесконечная последовательность ячеек, на которой машина Тьюринга хранит символы?

№2 · СООТВЕТСТВИЕ

4 ПАРЫ · 2 БАЛЛА

2. Элементы машины и их функции

Соедините каждый элемент машины Тьюринга с его функцией.

№3 · АЛГОРИТМ

5 ШАГОВ · 2 БАЛЛА

3. Порядок выполнения перехода

Расположите действия одного шага машины Тьюринга в правильном порядке: от чтения текущей ячейки до перехода к следующему состоянию.

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

№4 · ТЕРМИНЫ

4 ПРОПУСКА · 2 БАЛЛА

4. Состав конфигурации машины

Заполните пропуски в определении конфигурации машины Тьюринга.

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

№5 · ПРАВИЛА ПЕРЕХОДОВ

1 ВЕРНЫЙ ОТВЕТ · 2 БАЛЛА

5. Чтение правила перехода

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

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

№6 · УСТРОЙСТВО

1 ТЕРМИН · 1 БАЛЛ

6. Действие головки

Как называется устройство машины Тьюринга, которое считывает символ текущей ячейки и может записать в неё новый символ?

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

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

№7 · СООТВЕТСТВИЕ

5 ПАР · 3 БАЛЛА

7. Переходы для обработки цепочки

Соедините запись перехода с результатом его выполнения. Обозначения: q0 и q1 — состояния, □ — пустой символ; формат перехода: прочитать → записать, движение, новое состояние.

№8 · ТРАССИРОВКА

6 ШАГОВ · 3 БАЛЛА

8. Пошаговая обработка двоичной записи

Расположите конфигурации машины в правильном порядке. Машина начинает в состоянии q0, головка стоит на первой цифре строки 101, символы слева и справа обозначены как □, а правила таковы: в q0 машина заменяет 0 на 1 и движется вправо; встретив 1, заменяет её на 0 и переходит в q1; в q1 движется влево, пока не встретит □, затем завершает работу. Конфигурация записана как лента с состоянием и положением головки в квадратных скобках.

  1. □ 1 [q0] 0 1 □
  2. □ 1 0 [q1] 1 □
  3. □ 0 [q1] 1 □
  4. [qhalt] □ 0 1 1 □
  5. □ [q1] 1 0 1 □
  6. □ [q0] 1 0 1 □

№9 · ПРОЕКТИРОВАНИЕ

4 ПРОПУСКА · 3 БАЛЛА

9. Инвертирование двоичной строки

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

В состоянии q0 при чтении 0 машина должна записать , сдвинуться и остаться в состоянии q0. При чтении 1 она записывает , также сдвигается вправо и остаётся в q0. При чтении пустого символа она оставляет его без изменения и переходит в состояние.

№10 · КОМАНДА

1 ТЕРМИН · 1 БАЛЛ

10. Завершение работы

Как называется состояние машины Тьюринга, при достижении которого выполнение алгоритма прекращается?

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

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

Похожие рабочие листы

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

Обработка информации в текстовых процессорахЛогические операции и операции над множествамиПеревод чисел из одной позиционной системы счисления в другую. Таблицы триад и тетрадПредставление информации в компьютереСоздание и форматирование текстового документа в МойОфис ТекстАлфавитный (объёмный) подход к измерению информации; Единицы измерения информации: бит, байт, Кбайт, Мбайт, Гбайт; Хранение информации, объём памятиРабота с массивами. СортировкаАлгоритмыАлфавитный (объёмный) подход к измерению информации; Связь размера алфавита и информационного веса символа; Единицы измерения информации: бит, байт, Кбайт, Мбайт, ГбайтЛицензионные и свободно распространяемые программные продуктыТаблицы истинности дизъюнкции, конъюнкции, инверсии, импликации, эквиваленции; Логические выражения и их таблицы истинностиСодержательный и алфавитный подход к измерению информации

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

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

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

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

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

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

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

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

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

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

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