Выбранный для просмотра документ изучение машины Поста.pptx
Скачать материал "Изучение машины Поста в школьном курсе информатики"
Рабочие листы
к вашим урокам
Скачать
1 слайд
Изучение машины Поста в школьном курсе информатики
2 слайд
В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста
3 слайд
«Тезис Поста»: всякий алгоритм представим в форме машины Поста. Этот тезис является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.
4 слайд
Теоретическая часть. Состав машины Поста
Бесконечная лента
каретка
5 слайд
Команды машины Поста
6 слайд
Пример программы, которая неприменима к любому состоянию машины Поста
1 → 1
2 !
7 слайд
Пояснения к условиям задач
1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.
2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n.
3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: n подряд идущих меток будем обозначать 1n, а m пустых ячеек — 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно.
К примеру, запись “12012” будет соответствовать записи “11011” на ленте.
4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.
8 слайд
Применимость программ. Определение результата выполнения программ
Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.
Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.
3. Написать программы для машины Поста, которые обладают следующими свойствами:
программа применима к любому состоянию машины Поста;
программа не применима ни к какому состоянию машины Поста, и зона работы для любого начального состояния — бесконечная;
9 слайд
Арифметические задачи
На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.
10 слайд
Ориентация на ленте
На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
Решение. Этот алгоритм решения заимствован из замечательной книги В.А. Успенского “Машина Поста”. Мы не знаем, в какую сторону нам надо двигаться, но, в какую бы сторону мы ни пошли, может случиться, что метка стоит в другой стороне. Очевидно, что нам надо двигаться попеременно, то в одну сторону, то в другую, постоянно увеличивая размах своих колебаний. Но как определить момент, когда надо поворачивать, т.е. менять направление? Выход из положения есть. Вначале работы выставим метки слева и справа от исходного положения каретки, а затем будем ходить между ними и передвигать их.
Рабочие листы
к вашим урокам
Скачать
Выбранный для просмотра документ Изучение машины Поста в школьном курсе информатики.docx
Скачать материал "Изучение машины Поста в школьном курсе информатики"
Рабочие листы
к вашим урокам
Скачать
Рабочие листы
к вашим урокам
Скачать
В данном материале рассмотрено изучение темы "Автоматическая обработка информации" на примере машины Поста. Здесь рассмотрен как теоретический так и практический материал, представлено подробное описание программы и работа с ней. Для удобства теоретический материал представлен в виде презентации, которую можно использовать для объяснения материала на уроке. Также рассмотрены несколько задач с решениями в порядке увеличения их сложности.
6 664 963 материала в базе
Настоящий материал опубликован пользователем Дунаева Екатерина Николаевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс повышения квалификации
36/72 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
3 ч.
Мини-курс
5 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.