Машина Поста и алгорифмы Маркова
11 класс, углублённый уровень. Обзорный практикум к тринадцатой паре: шесть задач — от выполнения чужой программы до своего алгорифма.
- Что нужно сделать
- Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными. Времени нужно минут двадцать пять: шаги машины и подстановки удобно выписывать на черновике столбиком.
- Свой алгорифм
- Последний вопрос — алгорифм Маркова пишешь сам. Его не сверяют с ответом, а выполняют на всех коротких словах. Не прошёл — страница покажет слово, на котором он ошибся, и что у него вышло; исправляй и проверяй ещё раз, сколько нужно.
- Отметка
- Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не засчитывается — за ошибку приходит новая, без ограничений: добирать можно до пятёрки. В своём алгорифме ошибкой считается только первая неудачная проверка: дальше это отладка, а не ошибка. Описка в записи формулы (нет стрелки, русская буква) ошибкой не считается вовсе. Кнопка «Получить код» появляется, как только закрыто три вопроса.
- Короткий ответ — знак в знак
- В первых пяти вопросах — число (
13, а не13 шагов) или слово латинскими буквами подряд (abca, без кавычек и пробелов). На КЕГЭ ответ читает машина, и здесь так же. - Как сдать
- В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
- Не успел на уроке
- Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.
Вопросы темы
Подсказка: машина Поста и алгорифмы Маркова
Ещё два уточнения понятия алгоритма
Машина Тьюринга — не единственная попытка строго сказать, что такое алгоритм. В том же 1936 году Эмиль Пост описал машину ещё проще, а в конце 1940-х — начале 1950-х А. А. Марков предложил нормальные алгорифмы — преобразования слов по формулам. Все эти модели равносильны: что вычисляет одна, вычисляют и другие.
Машина Поста
- Лента из клеток; клетка либо пуста, либо отмечена меткой V. Над одной клеткой стоит каретка.
- Программа — пронумерованный список команд; в каждой, кроме «стоп», сказано, к какой команде перейти дальше.
| команда | что делает |
|---|---|
| V j | поставить метку, перейти к j |
| X j | стереть метку, перейти к j |
| → j / ← j | каретку на клетку вправо / влево, перейти к j |
| ? i; j | клетка пуста — к i, отмечена — к j |
| ! | стоп |
Метка в уже отмеченную клетку и стирание пустой — аварийная
остановка, результата нет. Пример: 
,
, 
, 
— каретка
идёт вправо по ряду меток до первой пустой клетки и ставит в неё метку:
ряд стал на одну метку длиннее.
Как выполнять вручную
Пиши столбиком: номер команды, номер клетки, пуста она или отмечена. Шаг — одна выполненная команда, «!» тоже считается. Лента перерисовывается после каждого V и X.
Нормальный алгорифм Маркова
Работает со словом — строкой символов. Схема — упорядоченный список формул P → Q («заменить P на Q») и заключительных P →· Q. λ — пустое слово. Один шаг:
- просмотреть формулы сверху вниз и взять первую, левая часть которой входит в слово;
- заменить её самое левое вхождение на правую часть;
- если формула заключительная — стоп, иначе снова к пункту 1.
Ни одна формула не подходит — тоже стоп. Пример: схема 
на слове 
: bab ⇒ abb, больше 
нет — стоп.
Алгорифм сортирует буквы.
Свой алгорифм на странице
По одной формуле в строке, по порядку; заключительная — с точкой после стрелки, пустое слово — λ или ничего:
Эта схема меняет a на b и b на a. Приём бегунка: формула с пустой
левой частью ставит служебную метку * в начало слова, формулы вида
проводят её по слову, а заключительная стирает в
конце. Формула 
подходит к любому слову — поэтому её
пишут последней. Порядок формул — часть алгорифма.