Презентация на тему Автоматическая о бработка информации
АвтоматическаяобработкаинформацииВыполнил: Сорокин Дмитрий
В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
Английский ученый Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите.
Другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным случаем машины Тьюринга. Однако именно работа с двоичным алфавитом представляет наибольший интерес, поскольку, как вы знаете, современный компьютер тоже работает с двоичным алфавитом.
Алгоритм, по которому работает машина Поста, будем называть программой.Договоримся о терминологии: под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.
Назначение машины Поста — производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
Система команд машины Поста {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействиеn ← mСдвиг каретки на шаг влево и переход к выполнению команды с номером mn → mСдвиг каретки на шаг вправо и переход к выполнению команды с номером mn v mЗапись метки в текущую пустую клетку и переход к выполнению команды с номером mn ↕ mСтирание метки в текущей клетке и переход к выполнению команды с номером mn !Остановка выполнения программыn ? m,kПереход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m, если непустая – команда с номером k
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машиныv
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины