Уточнение понятия алгоритма. Универсальные исполнители

27-28 урок, 11 класс – теория

Учитель: Брух Т.В.

Дата:_____________

Тема урока: «Уточнение понятия алгоритма. Универсальные исполнители»

Цели:

образовательная: дать представление об основных понятиях формального алгоритма: входной алфавит, слово, алфавит состояний, начальное состояние, пассивное состояние, «пусто»;

развивающая: совершенствование умственной и познавательной деятельности учащихся, развитие мышления учащихся;

воспитательная: сознательное усвоение материала учащимися;

Ход урока:

1. Организационный момент

2. Изучение нового материала

Работа с презентацией

Уточнённое понятие алгоритма:

Алгоритм - это организованная последовательность действий, понятных для некоторого исполнителя, ведущая к решению поставленной задачи.

• Исполнитель алгоритма - это тот объект или субъект, для управления которым составлен алгоритм.

• назовите свойства алгоритма (понятность, точность, конечность, дискретность, результативность);

• назовите способы записи алгоритмов (графический, словесный, в виде программ);

• Назовите типы алгоритмов? Приведите примеры. (линейные, алгоритмы с ветвлениями, алгоритмы с повторениями)

Алгоритм – это конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, детерминированности, результативности, конечности и массовости).

Определения алгоритма, которые мы с вами рассматривали не являются строгими, так как в них используются не определяемые точно термины, например «правило». Однако математики достаточно долго пользовались интуитивным понятием алгоритма. В рамках подобного определения были сформулированы и успешно применялись на практике алгоритмы для решения таких задач, как нахождение корней квадратного и кубических уравнений, решение систем линейных уравнений (метод Гаусса) и др.

Постепенно математики подходили к постановке и решению все более сложных задач. Так, например, Г. Лейбниц в XVII веке пытался построить общий алгоритм решения любых математических задач. В XX веке эта идея прибрела более конкретную форму: построить алгоритм проверки правильности любой теоремы при любой системе аксиом. Построить такие алгоритмы не удавалось, и математики выдвинули предположение: а вдруг для того или иного класса задач в принципе невозможно построить алгоритм решения. Следовательно, если алгоритма не существует, то они ищут то, чего нет.

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

Попытки выработать формальное определение алгоритма привели в 20-30 –х годах XX века к возникновению теории алгоритмов. В первой половине XX века разные математики (А. Тьюринг, Э. Пост, А.Н. Колмагоров, А.А.Марков идр.) предложили несколько подходов к формальному определению алгоритма: нормальный алгоритм Маркова, машина Тьюринга, машина Поста и т. д. В дальнейшем было показано, что все эти определения эквивалентны.

Мы рассмотрим формальное определение алгоритма, введенное А. Тьюрингом.

Тьюринг признан одним из основателей информатики и теории искусственного интеллекта, его считают первым теоретиком современного программирования и, наконец, первым в мире хакером. Между прочим, его «хакерская деятельность» внесла во время второй мировой войны существенный вклад в победу союзных войск над германским флотом, а один из коллег Тьюринга однажды сказал: «Я не берусь утверждать, что мы выиграли войну благодаря Тьюрингу. Однако без него могли бы её и проиграть».

Для уточнения понятия алгоритма была предложена абстрактная вычислительная конструкция, которая позже была названа машиной. Тьюринг описал свою машину в 1936 году.

Целью создания такой абстрактной воображаемой машины было получение возможности доказательства существования или не существования алгоритмов решения различных задач. Руководствуясь этой целью, Тьюринг искал как можно более простую, «бедную» алгоритмическую схему, лишь бы она была универсальной.

Прежде чем мы начнем знакомиться с машиной Тьюринга, необходимо сделать замечания относительно объектов, с которыми работают алгоритмы.

1. Замечание. Алгоритм имеет дело не с объектами реального мира, а с некоторыми изображениями этих объектов (объектами работы алгоритмов могут быть только слова).

2. Любой алфавит можно заменить другим (закодировать). Будем считать, что алгоритмы работают со словами, и мы формально описываем объекты – слова, над которыми работают алгоритмы, в некотором алфавите.

Описание машины Тьюринга

Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач. Этот математический аппарат был назван «машиной» по той причине, что по описанию он похож на вычислительную машину. Принципиальное отличие машины Тьюринга от вычислительной машины заключается в том, что у машины Тьюринга запоминающее устройство есть бесконечная лента: у реальных вычислительных машин устройство может быть сколь угодно большим, но не бесконечным.

В каждой машине Тьюринга есть две части:

1. Неограниченная в обе стороны лента, разделённая на ячейки;

2. Автомат (головка для считывания/записи, управляемая программой)

С каждой машиной Тьюринга связаны два конечных алфавита:

• алфавит входных символов А={а0,а1,а2,…,ам}

• алфавит состояний Q={q0,q1,q2,…,qм}

буква а0 - признак того, что ячейка пуста

состояние q1 – начальное

состояние q0 – пассивное (если машина попала в это состояние, то она закончила свою работу).

Автомат каждый раз видит только одну ячейку. В зависимости от того, какую букву он видит, а так же в зависимости от своего состояния q_i, автомат может выполнять следующие действия:

• записать новую букву в обозреваемую ячейку;

• выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте;

• перейти в новое состояние.

Программы для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.

Примеры

Описать машины Тьюринга, которые реализуют:

1. Счетчик четности. Выход машины Тьюринга равен 0 или 1 в зависимости от того, четно или нечетно число единиц в последовательности из 0 и 1, записанной на ленте машины Тьюринга. В конце последовательности стоит символ B. В начальном состоянии головка видит первый левый символ.

2. Инверсию заданного слова в алфавите {0, 1} (0 заменяет на 1, а 1 – на 0). В начальном состоянии головка видит первый левый символ.

3. Прибавление единицы к заданному двоичному числу. В начальном состоянии головка видит первый правый символ.

4. вычесть единицу от заданного двоичного числа. В начальном состоянии головка видит первый правый символ.

5. «Переворачивание» заданного слова в алфавите {a, b, c}. В начальном состоянии головка видит первый правый символ.

6. Сложить два двоичных числа.

Определение по Посту (формальное).

Алгоритм – это программа для машины Поста, приводящая к решению поставленной задачи.

Гипотеза Поста:

Всякий алгоритм представим в форме Машины Поста.

Машины Поста и Тьюринга эквивалентны по своим возможностям.

В машине Поста в ячейках бесконечной ленты можно записывать только два знака: 0 и 1.

Это ограничение не влияет на её универсальность, так как любой алфавит может быть закодирован двумя знаками.

Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая:

• умеет двигаться вперед, назад и стоять на месте;

• умеет читать содержимое, стирать и записывать 0 или 1;

• управляется программой.

Состоянию машины Поста соответствует одна из шести следующих команд:

1. Записать 1, перейти к i-ой строке программы.

2. Записать 0, перейти к i-ой строке программы.

3. Выполнить сдвиг влево, перейти к i-ой строке программы.

4. Выполнить сдвиг вправо, перейти к i-ой строке программы.

5. Останов.

6. Если 0, то перейти к i-ой строке программы, иначе перейти к j-ой строке программы.

Состояние машины – это состояние ленты и положение каретки.

К аварийной остановке машины могут привести следующие (недопустимые) действия:

• попытка записать 1 (метку) в заполненную ячейку;

• попытка стереть метку в пустой ячейке;

• уход каретки в бесконечность (зацикливание).

Команды машины будем обозначать следующим образом:

→ а - шаг вправо, перейти к строке с номером а;

← а - шаг влево, перейти к строке с номером а;

V a - записать метку, перейти к строке с номером а;

X a - стереть метку, перейти к строке с номером а;

? a; b - просмотреть ячейку; если в ячейке находится 0, то перейти к строке

с номером а, иначе – к строке с номером b;

! - останов.

Проводится обсуждение программы для машины Поста.

На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии слева от ячейки. Необходимо подвести каретку к ячейке, стереть метку и оставить каретку слева от неё.

Решение:

Программа для машины Поста:

1. → 2

2. ? 1; 3

3. X 4

4. ← 5

5. !

3. Практическая работа

Задание 1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.

a) Начальное состояние ленты:

1. 1110011

2. 1110111

3. 1001011

1. ? 3; 2

2.  1

3.  4

4. ? 6; 5

5.  1

6.  7

7. ? 8; 9

8. !

9.  4

b) Начальное состояние ленты:

1. 111101

2. 111011

3. 111111

1. ? 4; 2

2. Х 3

3.  9

4. V 5

5.  6

6. ? 7; 6

7. V 8

8.  9

9. ? 11; 10

10.  1

11. !

c) Начальное состояние ленты:

1. 1011

2. 11001

3. 10101

1. ? 4; 2

2. Х 3

3.  6

4. V 5

5.  1

6. ? 4; 7

7.  8

8. ? 9; 11

9. V 10

10.  1

11. !

Ответы:

a) 1) 1110011000

    2) зацикливание

    3) 1001011000

b) 1) зацикливание

    2) 010011

    3) 01010110

c) 1) зацикливание (…111)

    2) зацикливание (…1111001)

    3) зацикливание (1010111…)

Задание 2. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.

Пояснение: выделенная цифра, например 1, означает, что эту ячейку каретка обозревает в начальный момент времени.

a) Начальное состояние ленты:

1. 1111101

2. 111111

1. ? 2; 4

2. V 3

3. !

4. X 5

5.  6

6. ? 8; 7

7.  6

8.  1

b) Начальное состояние ленты:

1. 111111

2. 11101

3. 101111

1. ? 2; 3

2. !

3.  4

4. ? 7; 5

5. X 6

6.  9

7. V 8

8.  2

9. ? 12; 10

10. X 11

11.  1

12. V 13

13.  1

Решение. Выделенная цифра показывает, на какой ячейке остановится машина.

a) 1) 110000001

    2) 11000001

b) 1) 1100101

     2) 10001

     3) 111111

4. Домашнее задание

Составить программы для машины Поста.

1. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

2. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.