При использовании данной презентации при объяснении новой темы появляется возможность применять методы личностно-ориентированного обучения: проблемный метод, метод эвристической беседы и элементы исследования. Постановка проблемы ставит учащихся в условия, которые побуждают его решать учебную проблему, проводить анализ материала и оперировать им. Такая деятельность позволяет учащимся получить новую информацию, освоит новые способы применения знаний
Для уточнения понятия
алгоритма амер. математиком
Постом (1937 г.) было
предложено строгое
математическое построение,
которое было названо
«машиной», т. к. в нем
используются некоторые
понятия реальных машин –
память, команда и др.
Машина Поста (МП)
– бесконечная лента, в
ячейках которой можно
записывать всего два
знака: 1 (ставить метку)
или 0 (стирать метку) и
головка для
чтения/записи,
управляемая программой.
Обозначения
Система команд МП
V i
Записать 1 (отметку), перейти к i
той строке программы
Записать 0 (стереть отметку),
перейти к iтой строке
X i
i Шаг вправо, перейти к iтой строке
i Шаг влево, перейти к iтой строке
? i ; j Если в ячейке 0, то перейти к iтой
строке, иначе перейти к jтой
Недопустимые действия МП
Попытка записать 1
(отметку) в заполненную
ячейку
Попытка стереть отметку в
пустой ячейке
Уход головки в бесконечность
или зацикливание
Программа МП
состоит из
пронумерованных
строк, в каждой
строке записывается
только одна команда.
Пример
На ленте проставлена отметка в
одной единственной ячейке.
Головка стоит слева на некотором
расстоянии. Надо стереть отметку
и остановить головку слева от
ячейки.
Программа МП задачи
1
1. 2
2. ? 1 ; 3
3. X 4
4. 5
5. !
Тезис Поста
– всякий алгоритм
представим в форме
машины Поста.
Алгоритм (по Посту)
– программа для
машины Поста,
приводящая к решению
поставленной задачи.
Если для решения задачи можно
построить машину Поста, то она
алгоритмически разрешима.
В теории алгоритмов
доказано, что машина
Поста и машина Тьюринга
эквивалентны по своим
возможностям несмотря
на то, что МП проще, чем
МТ.
mashina_posta.ppt
