Рабочие листы
к вашим урокам
Скачать
1 слайд
Автоматическая обработка информации Информатика 11 класс Учитель информатики МБОУСОШ №61 г.Тулы Слепцова Н.Ю.
2 слайд
В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
3 слайд
Английский ученый Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите.
4 слайд
Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным случаем машины Тьюринга. Однако именно работа с двоичным алфавитом представляет наибольший интерес, поскольку, как вы знаете, современный компьютер тоже работает с двоичным алфавитом.
5 слайд
Алгоритм, по которому работает машина Поста, будем называть программой. Договоримся о терминологии: под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.
6 слайд
Опишем архитектуру машины Поста. Имеется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо стоять метка (некоторый знак), либо отсутствовать (пусто). Вдоль ленты движется каретка — считывающее устройство. На рисунке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей. Каретка является еще и процессором машины. С ее помощью машина может: •распознать, пустая клетка или помеченная знаком; •стереть знак в текущей клетке; •записать знак в пустую текущую клетку. vvvvv
7 слайд
Если произвести замену меток на единицы, а пустых клеток — на нули, то информацию на ленте можно будет рассматривать как аналог двоичного кода телеграфного сообщения или данных в памяти компьютера. Существенное отличие каретки-процессора машины Поста от процессора компьютера состоит в том, что в компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке, а в машине Поста — только последовательно.
8 слайд
Назначение машины Поста — производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
9 слайд
Система команд машины Поста КомандаДействие n ← mСдвиг каретки на шаг влево и переход к выполнению команды с номером m n → mСдвиг каретки на шаг вправо и переход к выполнению команды с номером m n v mЗапись метки в текущую пустую клетку и переход к выполнению команды с номером m n ↕ mСтирание метки в текущей клетке и переход к выполнению команды с номером m n !Остановка выполнения программы n ? m,kПереход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m, если непустая – команда с номером k
10 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
11 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины vvvv
12 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
13 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
14 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
15 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
16 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
17 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
18 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
19 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
20 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. v vvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
21 слайд
Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. vvvvv КомандаДействие 1 ↕ 2Стирание метки; переход к следующей команде 2 → 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины
22 слайд
В процессе выполнения приведенной программы многократно повторяется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.
23 слайд
Задание: На информационной ленте машины Поста расположен массив из N меток. Каретка расположена под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы? 1 → 2 2 ↕ 3 3 → 4 4? 5, 2 5 ← 6 6 V 7 7 !
24 слайд
Задание: На ленте поставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.
25 слайд
Составить программу перевода информационной ленты из начального состояния в конечное: Начальное состояние: Конечное состояние: …۷۷۷ ۷ ۷ ۷… …۷۷۷ ۷۷ ۷۷…
26 слайд
Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно. Начальное состояние: Конечное состояние: …۷ ۷… …۷ ۷…
27 слайд
Составить программу для заполнения всех клеток от левой метки до правой. Количество пустых клеток между метками неизвестно. Начальное состояние: Конечное состояние: …۷ ۷… …۷۷۷۷۷۷۷۷۷…
Рабочие листы
к вашим урокам
Скачать
Цель урока - сформировать и закрепить знания учащихся по теме "Автоматическая обработка информации. Машина Поста" В презентации рассматривается модель машины Поста, а также содержатся задания для самостоятельной работы учащихся.Литература: Семакин И.Г. Информатика и ИКТ. Базовый уровень: учебник для 10-11 классов / И.Г. Семакин, Е.К. Хеннер. – 8-е изд. - М.: БИНОМ. Лаборатория знаний, 2012. Семакин И.Г. Информатика и ИКТ. Базовый уровень: практикум для 10-11 классов / И.Г. Семакин, Е.К. Хеннер, Т.Ю. Шеина. – 7-е изд.– М.: БИНОМ. Лаборатория знаний, 2012.
6 671 666 материалов в базе
Настоящий материал опубликован пользователем Слепцова Наталия Юрьевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
600 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Курс профессиональной переподготовки
500/1000 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.