Машина Поста

Машина Поста

Цель работы: ввести понятие о машине Поста, показать принцип её работы, разобрать решение задачи по теме.

Вы уже знаете о суперспособностях современного учителя?

Тратить минимум сил на подготовку и проведение уроков.

Быстро и объективно проверять знания учащихся.

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

Избавить себя от подбора заданий и их проверки после уроков.

Наладить дисциплину на своих уроках.

Получить возможность работать творчески.

=> ПОЛУЧИТЬ СУПЕРСПОСОБНОСТИ УЧИТЕЛЯ <=

Просмотр содержимого документа
«Машина Поста»

«Машина Поста» автор: Камалова Татьяна Ивановна учитель высшей категории МАОУ СОШ№10 город Березники Пермский край

2014 г.

В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

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

Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

Машина Поста

Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой.

Машина Поста

Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд

Устройство машины:

Лента

Метка

Каретка

Типы команд:

Шаг вправо

Шаг влево

V Записать отметку

Х Стереть отметку

? a;b Просмотреть ячейку; если в ячейке находится 0, то перейти на команду с номером а , иначе на команду с номером b

! Остановка

Пример

Известно, что на ленте Машины Поста записан массив из 3 меток. Необходимо увеличить массив еще на одну метку. Так же известно, что каретка стоит слева от меток и обозревает пустую ячейку.

Решение:

1. 2

2. ? 1; 3

3. 4

4. V5

5. !

? Проверяем
Пусто
Возвращаемся к действию 1

? Проверяем
Есть запись
Переходим к действию 3

Задача 1

На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

Задача 2

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

Задача 3

На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.

Задача 4

Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.

Задача 5

Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

n . Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива." width="640"

Задача 6

На ленте заданы два массива — m и n , m n . Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

Задача 7

На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.

Задача 8

Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.

Задача 9

Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.

Задача 10

На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов

Предмет: Информатика

Категория: Презентации

Целевая аудитория: 9 класс.
Урок соответствует ФГОС

Скачать
Машина Поста

Автор: Камалова Татьяна Ивановна

Дата: 24.12.2014

Номер свидетельства: 147492

Похожие файлы

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

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(56) "Алгоритмическая машина Поста. "
    ["seo_title"] => string(33) "alghoritmichieskaia-mashina-posta"
    ["file_id"] => string(6) "117556"
    ["category_seo"] => string(11) "informatika"
    ["subcategory_seo"] => string(11) "presentacii"
    ["date"] => string(10) "1412837074"
  }
}

Конспект урока по информатике для учащихся 10 класса. Тема урока: "Автоматическая обработка данных".

object(ArrayObject)#885 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(182) "Конспект урока по информатике для учащихся 10 класса. Тема урока: "Автоматическая обработка данных". "
    ["seo_title"] => string(109) "konspiekt-uroka-po-informatikie-dlia-uchashchikhsia-10-klassa-tiema-uroka-avtomatichieskaia-obrabotka-dannykh"
    ["file_id"] => string(6) "206863"
    ["category_seo"] => string(11) "informatika"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1430294777"
  }
}

Разработка интегрированного урока, тема "Электрический ток. Оборудование сварочного поста"

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(168) "Разработка интегрированного урока, тема "Электрический ток. Оборудование сварочного поста""
    ["seo_title"] => string(96) "razrabotka-intieghrirovannogho-uroka-tiema-eliektrichieskii-tok-oborudovaniie-svarochnogho-posta"
    ["file_id"] => string(6) "339577"
    ["category_seo"] => string(7) "prochee"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1471356899"
  }
}

Конспект по информатике

object(ArrayObject)#885 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(45) "Конспект по информатике "
    ["seo_title"] => string(25) "konspiekt-po-informatikie"
    ["file_id"] => string(6) "195539"
    ["category_seo"] => string(11) "informatika"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1427913166"
  }
}

Тест 10 класс "Информационные процессы"

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(70) "Тест 10 класс "Информационные процессы""
    ["seo_title"] => string(38) "tiest10klassinformatsionnyieprotsiessy"
    ["file_id"] => string(6) "270211"
    ["category_seo"] => string(11) "informatika"
    ["subcategory_seo"] => string(5) "testi"
    ["date"] => string(10) "1451038101"
  }
}

Просмотр содержимого документа «Машина Поста»

Похожие файлы

Полезное для учителя

Просмотр содержимого документа
«Машина Поста»