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

1 Автоматическая обработка информации

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

3 Английский ученый Алан Тьюринг предложил модель такого исполни­ теля, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем об­работки любых символьных последовательностей в лю­бом алфавите.

4 Практически одновременно с Тьюрингом ( гг.) другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным слу­чаем машины Тьюринга. Однако именно работа с двоич­ ным алфавитом представляет наибольший интерес, по­скольку, как вы знаете, современный компьютер тоже ра­ботает с двоичным алфавитом.

5 Ал­горитм, по которому работает машина Поста, будем на­зывать программой. Договоримся о терминологии: под словом «програм­ма» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя на языке программирования для данного исполнителя.

6 Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента, разделенная на позиции клетки. В каждой клетке может либо сто­ять метка (некоторый знак), либо отсутствовать (пусто). vvvvv Вдоль ленты движется каретка считывающее устройство. На рисун­ке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей. Каретка является еще и процессором машины. С ее помощью машина может: распознать, пустая клетка или помеченная знаком; стереть знак в текущей клетке; записать знак в пустую текущую клетку.

7 Если произвести замену меток на единицы, а пустых клеток на нули, то информацию на ленте можно будет рассматривать как аналог двоично­го кода телеграфного сообщения или данных в памяти компьютера. Существенное отличие каретки-процессора машины Поста от процессора компьютера состоит в том, что в компьютере возможен доступ процессора к ячейкам памяти в произвольном порядке, а в машине Поста только последовательно.

8 Назначение машины Поста производить преобразования на инфор­мационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки.

9 Система команд машины Поста КомандаДействие n mСдвиг каретки на шаг влево и переход к выполнению команды с номером m n mСдвиг каретки на шаг вправо и переход к выполнению команды с номером m n v mЗапись метки в текущую пустую клетку и переход к выполнению команды с номером m n mСтирание метки в текущей клетке и переход к выполнению команды с номером m n !Остановка выполнения программы n ? m,kПереход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m, если непустая – команда с номером k

10 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

11 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины vvvv

12 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

13 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

14 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

15 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

16 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

17 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

18 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

19 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

20 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины v

21 Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. vvvvv КомандаДействие 1 2Стирание метки; переход к следующей команде 2 3Сдвиг вправо на один шаг 3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 4 4 5Сдвиг влево на шаг (команда выполнится, когда каретка выйдет на первый знак группы) 5 v 6Запись метки в пустую клетку 6 !Остановка машины

22 В процессе выполнения приведенной программы многократно повторя­ется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом. Напомним, что цикл относится к числу основных алгоритмичес­ ких структур вместе со следованием и ветвлением.

23 Источники ed=1&text=%D0%90%D0%BB%D0%B0%D0%BD%20%D 0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0 %B3&p=11&img_url= Fturing2012%2FImages%2FTuring7.jpg ed=1&text=%D0%90%D0%BB%D0%B0%D0%BD%20%D 0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0 %B3&p=11&img_url= Fturing2012%2FImages%2FTuring7.jpg g g Семакин И.Г., Хеннер Е.К., Информатика и ИКТ Издательство БИНОМ Лаборатория знаний, 2009