Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3838456
А
Аноним
7 часов назад · публичный вопрос
А
Аноним

610 Автоматическая обработка информации В качестве примера автомата, выполняющего обработку информации, рассмотрим машину Э. Поста. Алгоритм, по которому работает машина Поста,…

Запрос пользователя

610 Автоматическая обработка информации В качестве примера автомата, выполняющего обработку информации, рассмотрим машину Э. Поста. Алгоритм, по которому работает машина Поста, будем называть программой. Договоримся о терминологии: под словом «программа» мы всегда будем понимать алгоритм, записанный ‘по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя. Опишем архитектуру машины Поста (рис. 2.3). Имеется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо стоять метка (некоторый знак), либо отсутствовать ’ (пусто). у У м у у } Рис, 2.3. Модель машины Поста Вдоль ленты движется каретка — считывающее устройство, На рисунке 2.3 она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей. Каретка является еще и процессором машины. С ее помощью машина может: » распознать, пустая клетка или помеченная знаком; ® стереть знак в текущей клетке; * записать знак в пустую текущую клетку. Если произвести замену меток на единицы, а пустых клеток — на нули, то информацию на ленте можно будет рассматривать как аналог двоичного кода телеграфного сообщения или данных в памяти компьютера. Существенное отличие кареткипроцессора машины Поста от процессора компьютера состоит в том, что в компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке, а в машине Носта — только последовательно. Назначение машины Поста — производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — как результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки. Теперь рассмотрим систему команд машины Поста (табл. 2.1). Запись всякой команды начинается с ее порядкового номера в программе — п. Затем следует код операции и после него — номер следующей выполняемой команды программы — т. Рассмотрим пример программы решения задачи на машине Поста, Исходное состояние показано на рис. 2.3. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. Программа приведена В табл. 2.2. а . № ? т,й Команда _буб : 6}! _ © номером & `Пе о за если куш исимости от содержимого текущей клетки: взяться ко ая клетка пустая, то следующей будет выполманда с номером т, если непустая — команда Таблица 2.2 Программа для машины Поста + Действие Стирание метки; переход к следующей команде Сдвиг вправо на один шаг Если клетка пустая, то переход к команде 2, иначе — к ко манде 4 Сдвиг влево на шаг (команда выполнится, когда каретка ‚ выйдет на первый знак группы) Занись метки в пустую клетку Остановка машины В процессе выполнения приведенной программы многократно ° повторяется выполнение команд с номерами 2 и 3. Такая ситу‹. ация называется циклом. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ‚`. ватвлением. ’ ‚А теперь научим машину Поста играть в интеллектуальную игру, которая называется «Игра Баше». Опишем правила игры. ы % у“ 2 информационные процессы Играют дрое. Перед ними 21 (или 16. или 11 ит. д.) Фишка, Нгрокв берут фишки по очереди. За один ход можно взять от 1 ло 4 фишек. Проигрывает тот, кто забирает последнюю фишку. Имеется выигрышная тактика для игрока, берущего фишки вторым. Она заключается в том, чтобы брать такое количество Фишек, которое дополняет число фишек, взятых соперником ва предыдущем ходе, до пяти. Роль фишек на информационной ленте машины Поста будуъ выполнять метки (знаки). Машина играет с человеком. Человеку предоставляется возможность стирать метки (брать фишки) первым. Машина будет вступать в игру второй. Исходная обстановка: на ленте массив из 21 клетки содержит метки. Каретка установлена на крайней слева клетке этого массива. Стирать метки можно только подряд. Выигрышным результатом должна быть одна оставшаяся метка перед очередным ходом человека. Еще раз напомним принцип выигрышной тактики: стирать столько меток, чтобы в сумме с метками, стертыми противником за предыдущий ход, их было пять. Программа управления машиной Поста в игре Баше против человека приведена в табл. 2.3. Таблица 2.3 Программа игры Баше Комвида Действие 122,1 Машина ждет появления пустой клетки над кареткой. После очередного хода человека машина делает свой ход. Если человек видит всего одну метку на ленте, он прекращает игру, признав свое поражение 2—3 8>4 Эта серия команд выведет каретку на пятую (десятую, пятнадцатую и т. д.) позицию. Какой бы ход ни сделал со45 перник, в ней обязательно будет стоять метка 5>6 617 Стирается метка в текущей клетке 74-8 Шаг влево '. ‚ 829,6 Если клетка не пустая, то возврат к команде 6 9 -+ 10 Каретка перемещается к первой помеченной клетке. После этого машина возвращается к команде 1 и ждет хода 1079,1 человека (или признания им своего поражения) ‹ = . ` Автоматическая обработка информации р 51. ‚ Действуя по данной программе и начиная стирать метки второй после человека, машина всегда будет выигрывать, если правильно задано. начальное число меток, которое должно быть равно | машина может проиграть. Подведем итог. . Автоматическая обработка информации воз - можна, есни: ‚2. .. . °5в + Ъ где п — любое натуральное число. В противном случае 1) информация представлена В формализованном виде — в ко_нечном алфавите некоторой знаковой системы; #) реализован исполнитель, обладающий конечной системой команд, достаточной для построения алгоритмов решения ‘определенного класса задач обработки информации; 3) реализовано. программное управление работой исполнителя. ‚Маптина Носта — пример автоматического исполнителя обра ’ботки информации с ограниченными возможностями. Компьютер `’. удовлетворяет всем вышеперечисленным свойствам. Он является {” универсальным автоматическим исполнителем обработки инфор ‚``: мани. ``’, , р Система основных понятий , аа . да = -* = 3 и: 77" 5-я это” ^ ря = ЗА Автоматическая обработка информации .” р И м . - ‚ Свойства алгоритмической машины ‚ `. Дискретное, сим: Достаточная конечная Автоматическое —ис.“_ вольное представ‘ система команд для реполнение процессором ^ Левие данных знаемого класса задач программы, изменя‚ {информации)’ в у т = \ Двончное ; с аление инфор{1 > ® и .` у. г предг ` замяти машины ии на беско-, =. “.. * .^ Чно . Е й п ленте па. Ю * У ы ы ; ` 7 х ; ‹. > “ ющей содержимое памяти `Алгоритмическая машина Поста Гы - ст зе — команды ‘выставления. `й Удаления метки; $ ‚= команды смещения каретки влево и вправо; `> безусловный и услов ‚ ный переходы `. { “ остановка машины <. . че он а < Исполнение Начинается с первой команды и заканИВается к командой осТанов ‚ Процессор Чосле о %озательно вый, лняет ‚ команды прогу “мы 4 =. $; восстановить текст

Ответ нейросети
7 часов назад

Краткий ответ: перед нами параграф учебника (Босова, информатика) про машину Поста — пример автоматического исполнителя обработки информации. Ниже — его связный пересказ с восстановленными ключевыми определениями, чтобы понятен был принцип.

Что такое машина Поста

Это абстрактный исполнитель для обработки информации. Алгоритм, записанный по строгим правилам языка команд этого исполнителя, называется программой (программа — всегда запись по правилам языка исполнителя).

Устройство (архитектура)

  • Информационная лента — бесконечная, разбита на клетки. В каждой клетке либо стоит метка (знак), либо пусто.
  • Каретка — считывающее устройство, обозначается стрелкой. Она может смещаться на одну клетку влево или вправо. Клетка под кареткой — текущая.
  • Каретка одновременно является процессором и умеет:
    1. распознать, пустая клетка или помеченная;
    2. стереть знак в текущей клетке;
    3. записать знак в пустую текущую клетку.

Если метки заменить на 1, а пустые клетки — на 0, лента становится аналогом двоичного кода сообщения. Отличие от компьютера: процессор ЭВМ обращается к памяти в произвольном порядке, а каретка — только последовательно (шаг за шагом).

Исходное состояние ленты — это исходные данные задачи, конечное — результат. В исходные данные входит и начальное положение каретки.

Система команд

Запись команды: \(\;n.\ \text{операция}\ ;\ m\;\), где \(n\) — номер команды в программе, \(m\) — номер следующей команды. Основные операции: стереть метку, записать метку, сдвиг вправо, сдвиг влево, остановка. Есть условный переход: в зависимости от содержимого текущей клетки выполняется команда с номером \(m\) (одно значение) или с другим номером. Исполнение идёт с команды №1 до команды «остановка».

Пример и цикл

В примере программа должна стереть знак в текущей клетке и присоединить его слева к группе знаков справа. Команды 2 и 3 (сдвиг вправо, проверка клетки, сдвиг влево) многократно повторяются — это цикл. Цикл — одна из основных алгоритмических структур наряду со следованием и ветвлением.

Игра Баше

Правила: 21 (или 16, 11 …) фишка, игроки берут по очереди от 1 до 4 фишек, проигрывает взявший последнюю. Выигрышная тактика у второго игрока: брать столько фишек, чтобы сумма с ходом соперника (за предыдущий ход) была равна 5.

Машина играет второй, метки на ленте — фишки; человек стирает метки первым. Стирать можно только подряд. Программа (таблица 2.3) в цикле: машина ждёт появления пустой клетки (ход человека), выводит каретку на 5-ю (10-ю, 15-ю…) позицию — там при любом ходе соперника стоит метка, стирает её, шагает влево и возвращается к первой помеченной клетке, затем снова ждёт хода человека. Выигрыш: перед ходом человека остаётся одна метка.

Условие безошибочной игры

Машина всегда выигрывает, если начальное число меток имеет вид \[ N = 5n + 1, \] где \(n\) — натуральное число (то есть 1, 6, 11, 16, 21 …). Иначе машина может проиграть.

Итог: когда возможна автоматическая обработка информации

  1. информация представлена в формализованном виде — в конечном алфавите знаковой системы;
  2. есть исполнитель с конечной системой команд, достаточной для алгоритмов нужного класса задач;
  3. реализовано программное управление работой исполнителя (процессор автоматически выполняет программу, меняющую содержимое памяти).

Машина Поста — пример автоматического исполнителя с ограниченными возможностями; компьютер — универсальный автоматический исполнитель обработки информации.

Проверка понимания: возьми \(N = 21\). Тогда \(21 = 5\cdot 4 + 1\), \(n = 4\) — целое натуральное, значит машина гарантированно выигрывает. А при \(N = 20\): \(20 = 5\cdot 4\), остаток не 1, так что выигрыш не гарантирован.

Обсуждение

2 сообщения
А
Аноним

Мне нужен просто восстановленный текст

Нейросеть7 часов назад

Вот восстановленный текст параграфа (по смыслу и структуре оригинала):


§. Автоматическая обработка информации

В качестве примера автомата, выполняющего обработку информации, рассмотрим машину Э. Поста. Алгоритм, по которому работает машина Поста, будем называть программой. Договоримся о терминологии: под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.

Опишем архитектуру машины Поста (рис. 2.3). Имеется бесконечная информационная лента, разделённая на позиции — клетки. В каждой клетке может либо стоять метка (некоторый знак), либо отсутствовать (пусто).

Рис. 2.3. Модель машины Поста

Вдоль ленты движется каретка — считывающее устройство. На рисунке 2.3 она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей.

Каретка является ещё и процессором машины. С её помощью машина может:

  • распознать, пустая клетка или помеченная знаком;
  • стереть знак в текущей клетке;
  • записать знак в пустую текущую клетку.

Если произвести замену меток на единицы, а пустых клеток — на нули, то информацию на ленте можно будет рассматривать как аналог двоичного кода телеграфного сообщения или данных в памяти компьютера. Существенное отличие каретки-процессора машины Поста от процессора компьютера состоит в том, что в компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке, а в машине Поста — только последовательно. Назначение машины Поста — производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — как результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.

Теперь рассмотрим систему команд машины Поста (табл. 2.1). Запись всякой команды начинается с её порядкового номера в программе — \(n\). Затем следует код операции и после него — номер следующей выполняемой команды программы — \(m\).

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

Таблица 2.1

Команда с номером \(n\): если текущая клетка пустая, то следующей будет выполняться команда с номером \(m\), если непустая — другая команда.

Таблица 2.2. Программа для машины Поста

Команда Действие
1 Стирание метки; переход к следующей команде
2 Сдвиг вправо на один шаг
3 Если клетка пустая, то переход к команде 2, иначе — к команде 4
4 Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы)
5 Запись метки в пустую клетку
6 Остановка машины

В процессе выполнения приведённой программы многократно повторяется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.

А теперь научим машину Поста играть в интеллектуальную игру, которая называется «Игра Баше». Опишем правила игры.

Играют двое. Перед ними 21 (или 16, или 11 и т. д.) фишка. Игроки берут фишки по очереди. За один ход можно взять от 1 до 4 фишек. Проигрывает тот, кто забирает последнюю фишку.

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

Роль фишек на информационной ленте машины Поста будут выполнять метки (знаки). Машина играет с человеком. Человеку предоставляется возможность стирать метки (брать фишки) первым. Машина будет вступать в игру второй. Исходная обстановка: на ленте массив из 21 клетки содержит метки. Каретка установлена на крайней слева клетке этого массива. Стирать метки можно только подряд. Выигрышным результатом должна быть одна оставшаяся метка перед очередным ходом человека.

Ещё раз напомним принцип выигрышной тактики: стирать столько меток, чтобы в сумме с метками, стёртыми противником за предыдущий ход, их было пять.

Программа управления машиной Поста в игре Баше против человека приведена в табл. 2.3.

Таблица 2.3. Программа игры Баше

Команда Действие
1 → 2, 1 Машина ждёт появления пустой клетки над кареткой. После очередного хода человека машина делает свой ход. Если человек видит всего одну метку на ленте, он прекращает игру, признав своё поражение
2 → 3 \(8 \to 4\). Эта серия команд выведет каретку на пятую (десятую, пятнадцатую и т. д.) позицию. Какой бы ход ни сделал соперник, в ней обязательно будет стоять метка
5 → 6 Стирается метка в текущей клетке
6 → 7 Шаг влево
7 → 8 \(8 \to 9, 6\). Если клетка не пустая, то возврат к команде 6
9 → 10 Каретка перемещается к первой помеченной клетке. После этого машина возвращается к команде 1 и ждёт хода человека (или признания им своего поражения)
10 → 1

Действуя по данной программе и начиная стирать метки второй после человека, машина всегда будет выигрывать, если правильно задано начальное число меток, которое должно быть равно \[ 5n + 1, \] где \(n\) — любое натуральное число. В противном случае машина может проиграть.

Подведём итог.

Автоматическая обработка информации возможна, если:

  1. информация представлена в формализованном виде — в конечном алфавите некоторой знаковой системы;
  2. реализован исполнитель, обладающий конечной системой команд, достаточной для построения алгоритмов решения определённого класса задач обработки информации;
  3. реализовано программное управление работой исполнителя.

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

Система основных понятий

Автоматическая обработка информации — свойства алгоритмической машины:

  • дискретное, символьное представление информации (данных);
  • достаточная конечная система команд для решаемого класса задач;
  • автоматическое исполнение процессором программы, изменяющей содержимое памяти.

Алгоритмическая машина Поста:

  • двоичное представление информации в памяти машины на бесконечной ленте;
  • команды выставления и удаления метки;
  • команды смещения каретки влево и вправо;
  • безусловный и условный переходы;
  • остановка машины.

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