«ОБРАБОТКА ИНФОРМАЦИИ ИАЛГОРИТМЫ»

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

Решение задачи (получение новой информации); Перевод текста (изменение формы представления); Составление каталога в библиотеке (систематизация); Поиск в телефонной книге (поиск информации).

Происхождение термина «алгоритм» от написания имени математика средневековья Мухаммеда аль – Хорезми.

Машина Тьюринга (Алан Тьюринг) Машина Поста (Эмиль Пост)

Машина Поста состоит из: бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой или содержать метку; каретки, способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.

1)V m - поставить метку, перейти к m-й строке программы. 2) m - стереть метку, перейти к m-й строке программы. 3)<- m - сдвинуться влево, перейти к m-й строке программы. 4)-> m - сдвинуться вправо, перейти к m-й строке программы. 5)? m, k - если в ячейке нет метки, то перейти к m-й строке программы, иначе перейти к k-й строке программы. 6)! – конец программы (стоп). У команды «стоп» отсылки нет.

VVV Задача 1 Выполнить на машине Поста программу: 1. V ! Начальное состояние информационной ленты изображено.

Задача 2. Выполнить на машине Поста программу: ! Начальное состояние информационной ленты изображено. VVV

Задача 3. Выполнить на машине Поста программу: ? 2, V 6 6. ! VVVVV

Задача 4 (задание 1 из практикума) Составить программу перевода информационной ленты машины Поста из начального состояния в конечное. VVVVV VVVV Н.с К.с

V !

VVVVV 1) 2 2) 3 3)? 2,4 4) 5 5)V 6 6)!