Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Машина Поста
Содержание
- 1. Машина Поста
- 2. В 30-х годах XX века возникает новая
- 3. Машина Тьюринга Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная
- 4. Машина Поста Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой.
- 5. Машина Поста
- 6. Обе машины «эквивалентны» и были созданы для
- 7. Принцип работы Машина Поста состоит из каретки (или
- 8. Устройство машины: МеткаКареткаЛента
- 9. Типы команд:Шаг вправоШаг влево V
- 10. Пример Известно, что на ленте Машины Поста записан
- 11. Решение:1. 22. ? 1;
- 12. Задача 1 На ленте задан массив меток. Увеличить
- 13. Задача 2 На ленте заданы два массива. Найти
- 14. Задача 3 На ленте имеется некоторое множество меток
- 15. Задача 4 Дан массив меток. Каретка располагается где-то
- 16. Задача 5 Даны два массива меток, которые находятся
- 17. Задача 6 На ленте заданы два массива — m и n, m > n.
- 18. Задача 7 На ленте имеется массив из n отмеченных ячеек.
- 19. Задача 8 Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
- 20. Задача 9 Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
- 21. Задача 10 На ленте машины Поста расположено n массивов меток,
- 22. Скачать презентанцию
В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы
Слайды и текст этой презентации
Слайд 1«Машина Поста» автор: Камалова Татьяна Ивановна учитель высшей категории МАОУ СОШ№10 город
Березники Пермский край
Слайд 2 В 30-х годах XX века возникает новая наука — теория
алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой
ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
Слайд 3Машина Тьюринга
Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом
Тьюрингом в 1936 году для формализации понятия алгоритма.
Художественное представление машины Тьюринга
Слайд 4Машина Поста
Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом,
которая отличается от машины Тьюринга большей простотой.
Слайд 6 Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».В
1936 г. американский математик Эмиль Пост в статье описал систему,
обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Слайд 7Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей
головки) и разбитой на секции бесконечной в обе стороны ленты.
Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд
Слайд 9Типы команд:
Шаг вправо
Шаг влево
V
Записать отметку
Х
Стереть отметку ? a;b Просмотреть ячейку; если в ячейке находится 0, то перейти на команду с номером а, иначе на команду с номером b
! Остановка
Слайд 10Пример
Известно, что на ленте Машины Поста записан массив из 3
меток. Необходимо увеличить массив еще на одну метку. Так же известно,
что каретка стоит слева от меток и обозревает пустую ячейку.
Слайд 11Решение:
1. 2
2. ? 1; 3
3.
4
4. V5
5. !
?
? Проверяем
Пусто
Возвращаемся к действию 1
?
ПроверяемЕсть запись
Переходим к действию 3
?
Слайд 12Задача 1
На ленте задан массив меток. Увеличить длину массива на
2 метки. Каретка находится либо слева от массива, либо над
одной из ячеек самого массива.
Слайд 13Задача 2
На ленте заданы два массива. Найти модуль разности длин
массивов. Каретка располагается над первой ячейкой левого массива.
Слайд 14Задача 3
На ленте имеется некоторое множество меток (общее количество меток
не менее 1). Между метками множества могут быть пропуски, длина
которых составляет одну ячейку. Заполнить все пропуски метками.
Слайд 15Задача 4
Дан массив меток. Каретка располагается где-то над массивом, но
не над крайними метками. Стереть все метки, кроме крайних, и
поставить каретку в исходное положение.
Слайд 16Задача 5
Даны два массива меток, которые находятся на некотором расстоянии
друг от друга. Требуется соединить их в один массив. Каретка
находится над крайней левой меткой первого массива.
Слайд 17Задача 6
На ленте заданы два массива — m и n, m > n. Вычислить разность этих
массивов. Каретка располагается над левой ячейкой правого массива.
Слайд 18Задача 7
На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю
левую метку. Справа от данного массива на расстоянии в m ячеек находится
еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
Слайд 19Задача 8
Известно, что на ленте машины Поста находится метка. Напишите
программу, которая находит ее.
Слайд 20Задача 9
Дано несколько массивов меток. Удалить четные массивы. Каретка находится
над первым массивом.
Слайд 21Задача 10
На ленте машины Поста расположено n массивов меток, отделенных друг от
друга свободной ячейкой. Каретка находится над крайней левой меткой первого
массива. Определить количество массивов
