Обработка информации и алгоритмы Алгоритмическая машина Поста

Обработка информации Исполнитель Исходные данные Правила обработки Результаты

Направления обработки информации Получение новой информации, новых сведений Изменение формы представления информации Систематизация, структурирование данных Поиск информации

Алгоритмы Слово « алгоритм » произошло от имени выдающегося математика средневекового Востока Мухаммеда аль - Хорезми, описавшего еще в IX веке правила выполнения вычислений с многозначными десятичными числами. Алгоритм – набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.

Алгоритм и СКИ Совокупность всех команд языка исполнителя называется системой команд исполнителя алгоритмов – СКИ. Алгоритм управления работой алгоритмической машины представляет собой конечную последовательность команд, посредством выполнения которой машина решает задачу обработки информации.

Свойства алгоритмов Алгоритм Понятность Дискретность Формальность Массовость Конечность

Дискретность ( прерывность, раздельность ) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых ( или ранее определенных ) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего. Свойства алгоритмов Конечность ( результативность ) – алгоритм должен приводить к решению задачи за конечное число шагов. Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Формальность ( определенность ) – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче. Понятность для исполнителя – т. е. исполнитель алгоритма должен знать, как его выполнять.

Виды алгоритмов 1. Линейный действие 1 действие 2 действие 3 2. Разветвляющийся действие условие Да Нет действие 1 условие Да Нет действие 2 а ) Неполное ветвление б ) Полное ветвление

3. Циклический а ) Цикл с предусловием Виды алгоритмов Тело цикла условие Нет Да Тело цикла условие Нет Да б ) Цикл с постусловиемб ) Цикл с параметром Тело цикла i от k до n i=n+1 in+1

Алгоритмические машины « Машина Тьюринга » – универсальный исполнитель обработки любых символьных последовательностей в любом алфавите Алан Тьюринг ( ) Англия

Автоматическая обработка информации Автомат – машина Поста. Программа – алгоритм, записанный по строгим правилам языка команд исполнителя на языке программирования для данного исполнителя. Эмиль Пост ( ), США

Модель машины Поста Каретка – считывающее устройство и процессор машины. Возможные действия : распознать, пустая клетка или помеченная знаком ; стереть знак в текущей клетке ; записать знак в пустую текущую клетку ; Назначение – производить преобразования на информационной ленте.

Система команд ……

Задачи 1. Применимы ли программы к заданным состояниям машины Поста ? 1. ? ? ? ! 9. 4 …… …… ……

2. Дано несколько чисел. Удалить те, которые стоят на четных местах. Каретка находится над первой меткой первого числа. 3. На ленте машины Поста расположено n чисел, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого числа. Определить количество чисел. 4. Дан массив меток. Каретка располагается где - то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение. Задачи

Умный мячик Исполнитель, который умеет составлять слова из букв, расположенных вдоль линейки. Состав Умный мячик состоит из : линейки, вдоль которой прыгает « умный мячик »; букв, расставленных над делениями линейки ( символ «*» обозначает невидимую букву ). Текущее состояние « умного мячика » описывается буквами на линейке и положением « мячика » над ней.

Система команд

Составить слово « горизонт ». ! +3! -4! +7! -2! -1! +2! -3!. Пример 1

Пример 2 ЭТО алг ПОКА НЕ а (-1)! КОНЕЦ -3! +1! +1! алг +7! -4! алг ПОКА НЕ ш (+1)!. -3! +1! +1! -1! +7! -4! -3! ПОКА НЕ ш (+1)!. -3! +1! +1! -1! +7! -4! -3! +9 ? ш (!, +1!).

Что получится после выполнения программы : -3! -2! +3! -1! +4! +2! -2! -5!. -3! +1! +1! +3! -4!. Задание 1

Напишите для исполнителя программу, по которой он сможет собрать слово « агроном ». Задание 2