И этот робот будет убежден, что фигура нарисованная ниже не прямоугольник.
И этот робот будет прав. Ведь третья фигура не совпадает точно с первыми двумя которые мы сами показали ему и сказали, что это прямоугольники, а следовательно нет никаких оснований называть прямоугольником третью фигуру. Это означает, что робот по нашей просьбе нарисовать прямоугольник, сможет нарисовать фигуру №1 и фигуру №2 и всё.
Попробуем по другому. НЕ БУДЕМ НИЧЕГО ОБЪЯСНЯТЬ. А ПРОСТО РАССКАЖЕМ, ЧТО НУЖНО ДЕЛАТЬ.
Что произошло (а кстати случайно он мог нарисовать и правильно), почему всё так плохо!? А потому, что наша команда неопределённа. Представьте, что вас посылают в магазин и говорят, что нужно купить продуктов на 50 рублей. А каких? Вот мы сказали роботу соединить четыре точки линиями, а оказалось, что это можно сделать несколькими способами, как несколькими способами можно потратить 50 рублей в магазине. И кроме того, он может быть не знает, что такое прямой угол.
Значит, мы должны скомандовать так, чтобы он мог понять наши команды только одним способом. Есть и ещё одна проблема. Представьте себе, что вас посылают в магазин, а задание говорят на французском. Вряд ли вы сможете его выполнить, даже если оно будет очень подробное и очень точное.
Какой из всего сказанного выше следует вывод. А такой: Не такая уж это простая задача научить кого-нибудь, сделать что-нибудь. Сразу возникает масса сложнейших проблем для решения которых нужна целая наука.
Главное понятие
Самым важным понятием нашей науки является алгоритм. Пока не будем давать точного определения. Постараемся понять что это такое как-нибудь, а потом уточним.
Предположим, мы прочитали в учебнике, что самый короткий путь из точки А в точку В, это прямая. Это утверждение становится нашим знанием. Да теперь мы знаем, что если понадобится пройти из точки А в точку В самым коротким путём, то нужно будет идти по прямой. Но сможем ли мы в конкретной ситуации пройти этой самой прямой. Например, в лесу. Сомневаюсь. От того, что мы знаем, что надо делать ещё не появляется знание как это сделать.
Для того чтобы пройти по прямой, например в лесу, мы должны сделать подробную инструкцию как это сделать. В этой инструкции должны быть точные команды, гарантирующие прямой путь. Например, инструкция может быть такой:
1. Запомнить направление стрелки компаса
2. Выбрать зрительно направление движения
3. Пока не закончено движение выполнять команды:
4. Сделать шаг вперёд
5. Если стрелка компаса отклонилась по часовой стрелки то:
6. Вернуться назад
7. Изменить направление движение на чуть правее.
8. Перейти на команду 4
9. Если стрелка компаса отклонилась против часовой стрелки то:
10. Вернуться назад.
11. Изменить направление движения на чуть левее.
12. Перейти на команду 4.
Примечание:Мы в своей инструкции пользуемся тем свойством, что стрелка компаса остаётся неподвижной, только в том случае, когда человек с компасом движется по прямой.
Как будет действовать исполнитель этой инструкции? Он многократно будет пытаться делать шаг в некотором направлении. Если в результате очередного шага стрелка компаса отклонится, он будет возвращаться назад и пытаться шагнуть еще раз до тех пор пока не удаться сделать такого шага, после которого стрелка компаса останется на месте. После чего он уже не вернётся назад, а будет двигаться дальше.
Как видите в этой инструкции нигде не объясняется, что такое прямая линия, но если исполнитель будет её точно исполнять, то ему гарантируется прямой путь. Помните, мы уже говорили о том, что можно уметь делать не понимая, как это получается.
Так вот такая инструкция в которой просто описаны действия для исполнения называется алгоритмом.
Не всякая последовательность команд является алгоритмом
Все команды, алгоритма должны быть понятны исполнителю. Он может оказаться не в состоянии выполнить ту или иную команду, но они обязательно должны быть понятны. Например, вы можете дать такую команду: "Взлететь и пролететь 15000 метров."
В случае с человеком такая команда будет понятна но не выполнима. А в случае с автопилотом самолёта такая команда будет исполнима, но не понятна (не думаю, что автопилот способен понимать команды на русском языке) и тогда можно говорить, что мы вообще имеем дело не с алгоритмом. Следовательно понятие алгоритма тесно связано с понятием исполнителя алгоритма и о исполнителе мы будем говорить ещё дальше. А сейчас ещё несколько свойств алгоритма.
Любую команду алгоритма можно выполнить только одним способом
Команды, которые можно выполнить несколькими способами мы далее будем называть неопределёнными. Например, команда "Сходить в магазин" будет неопредёлённой, так как неясно о каком магазине идет речь. Команда "Сходить в магазин находящийся на нашей улице" тоже плоха, так как может оказаться, что на нашей улице много магазинов, а кое-кому может оказаться не понятным какая улица имеется ввиду.
Если же любую команду можно выполнить только одним способом, то мы можем обнаружить, что сколько раз бы не исполнялся конкретный алгоритм, он всегда будет приводить к одному и тому же результату если конечно он исполняется в одинаковых условиях.
Дополнение про одинаковые условия очень важно. Возьмём, например такой простейший алгоритм:
§ Зайти в ближайший магазин.
§ Если есть молоко то купить иначе не покупать.
Его всегда можно выполнить, так как всегда есть ближайший магазин. Он конечно может быть от нас за 100 километров (если мы в тайге в Сибири или на Дальнем Востоке), но всегда ближе того магазина который от нас за 200 километров, а стало быть он ближайший. Если в нём есть молоко, то мы всегда можем его купить, а если его нет, то ничто не помешает нам его не покупать, следовательно все команды понятны и исполняемы, но вот результат зависит от того есть в магазине молоко или нет. Мы можем выйти из него как с молоком, так и без него, следовательно наш алгоритм может привести к разному результату в разных условиях.
Очень важен порядок команд
Как мы уже поняли алгоритм, это не просто набор команд. Это упорядоченный набор команд и если выполнять их в разной последовательности, то можно получить и совершенно различные результаты.
Пример: Алгоритм кипячения воды в чайнике
|
Первый вариант
|
Второй вариант
|
|
1. Налить воду в чайник
2. Зажечь спичку
3. Открыть газ.
4. Зажечь газ
5. Поставить чайник на плиту.
6. Подождать пока закипит и снять
|
1. Открыть газ
2. Зажечь спичку
3. Налить воду в чайник.
4. Зажечь газ
5. Поставить чайник на плиту.
6. Подождать пока закипит и снять
|
Второй вариант конечно же приведёт к другому результату. Во-первых, пока мы будем наливать воду спичка погаснет, а во-вторых, открыв газ так рано, мы рискуем взорваться.
Важное дополнение
Как видно и рассказанного выше алгоритм, - это очень точное описание того, что нужно сделать, чтобы добиться результата. Очень точное описание, это такое описание, которое можно понять только одним способом. Но дело в том, что слова русского языка (как и любого другого человеческого языка ) очень часто имеют много значений. Например, бык это животное и это же опора моста. Очень часто встречаются фразы вообще не имеющие точного смысла. Например: "Очень горячая вода". Только вдумайтесь, "очень горячая", это насколько горячая? Это 60 градусов или 100 градусов. Этой водой можно например обжечься или нет? И таких вот ситуаций крайне много. Именно из-за таких ситуаций люди часто неточно понимают друг друга. Но человек всё же может понять, что ему сказали, а в отношениях с машиной нужна абсолютная точность, Нельзя дать станку команду "Немного обточить деталь" он нас не поймёт. Поэтому совершенно необходимо придумать такой язык, на котором можно было бы записывать алгоритм абсолютно точно, но об этом мы подумаем немного позже.
ИСПОЛНИТЕЛЬ
Это второе важнейшее понятие алгоритмики. Как мы уже видели раньше один и тот же алгоритм может быть одновременно понятен и не понятен (разным исполнителям). Для разных исполнителей он может оказаться выполнимым и невыполнимым. Примеры уже были раньше, но приведём ещё один: рассмотрим такую команду: "Решить уравнение 2х+1=5" Для ученика младших классов такая команда окажется невыполнимой, так как он не умеет решать уравнения. Но в то же время он сможет выполнить следующие команды:
1. Из 5 вычесть 1.
2. Результат предыдущего действия разделить на 5.
3. Результат предыдущего действия приравнять х.
В результате выполнения данных трёх команд школьник получит решение уравнения (то есть он будет уметь, не понимая), а мы для себя сделаем важный вывод: Если мы хотим, чтобы наш алгоритм мог выполнить очень простой исполнитель (мало знающий), то алгоритм нужно записывать очень простыми командами.
Возникает вопрос конечно. А почему мы так стараемся ради простого исполнителя. Можно ведь взять исполнителя который будет понимать и очень сложные команды. А дело в том, что сложный исполнитель может оказаться очень дорогим. Да и вообще единственный исполнитель который может понимать по настоящему сложные команды это человек. А человек может работать далеко не в любым условиях. Он например не может опуститься под воду на большую глубину, он не может работать при температуре в 100 градусов, не может очень быстро обрабатывать много информации (например при управлении атомной станцией). А любая машина, даже такая сложная как компьютер способна понимать только очень и очень простые команды.
Итак:
1. Мы можем рассчитывать только на очень простого исполнителя, понимающего только очень простые команды и чем проще тем лучше.
2. Этих команд ограниченное количество и набор команд конкретного исполнителя не изменяется без переделки самого исполнителя (никогда токарный станок не станет прессом )
Машина Поста
Рассмотрим сейчас простейшего исполнителя – компьютер. Это действительно простейший исполнитель. Все его умения сводятся к чтению слова данных состоящего из нулей и единиц и различным операциям с ними. Видимая сложность компьютера происходит от того, что из этих простейших операций нужно создавать очень сложные и кроме того, человеку требуется много удобств: хороший монитор, большая память, удобные средства ввода информации и т.д. Но в принципе любой компьютер можно свести к очень простому устройству. Одно из таких устройств, предложил американский математик Эмиль Пост.
Машина Поста состоит из бесконечной ленты и головки. Лента разделена на клетки. В каждой клетке может быть записан один символ из алфавита фиксированного для каждой данной машины Поста. В любой момент времени головка обозревает ровно одну клетку и может работать только с ней.
Машины Поста работают под управлением программ. Программы состоят из команд. Запись команд для машин Поста имеет три поля: номер команды, операцию и отсылку. Команды нумеруются начиная с 1. Отсылка показывает, какую команды нужно выполнять после данной. Что касается видов операций, то их бывает пять:
1. ® движение головки на одну клетку вправо
2. ¬ движение головки на одну клетку влево
3. Запись символа в обозреваемую клетку.
4. СТОП – команда остановки работы
5. Команда ветвления {(s1,m1)(s2,m2)….(sn,mn)} Здесь s1, s2 … sn - некоторые символы из алфавита машины Поста, m1, m2,…. mn - отсылки.
Все символы si должны быть различными, однако не требуется, чтобы в команде ветвления был употреблён весь алфавит. Эта команда выполняется следующим образом. Анализируется символ из обозреваемой клетки. Если он совпадает с si следующей будет команда с номером Mi При этом головка никуда не перемещается и на ленту ничего не записывается. Если в клетке стоит символ, не упомянутый в данной команде, происходит так называемая безрезультативная остановка машины Поста ("машина ломается").
Другие возможные исходы выполнения программы на машине Поста - бесконечная работа и так называемая результативная остановка вызываемая командой СТОП. Последний исход называется нормальным, именно так и должна заканчиваться работа машины. Приведём несколько примеров программ:
Пример 1:
1. ® 2
2. I 1
Эта программа состоит из двух команд, однако за счёт того, что отсылка во второй команде равна 1, обе команды будут выполнятся многократно, а сама программа сделает очень многое - она будет заполнять ленту символами I справа от клетки, которую головка обозревала в начальный момент. Работа этой программы никогда не завершится.
Давайте проследим, как будет меняться состояние машины Поста. Предположим, что на выполнение каждой команды требуется единица времени.
Составив соответствующие программы, машину Поста можно научить арифметическим операциям. Договоримся, что числа на ленте будем записывать в единичной системе счисления. Например, 4 запишется как IIII.
Программа:
1. ¬ 2
2. I 3
3. СТОП
увеличит на единицу записанное на ленте число в предположении, что в начальный момент головка обозревает левую единицу числа. Предположим теперь, что головка обозревает произвольную единицу числа. Напишем программу прибавления единицы в этом случае:
1. ¬ 2
2. {(I; 1), ( ;3), (I; 4)}
3. СТОП
Идея этой программы проста: головка смещается влево, пока не найдёт первую пустую клетку, а затем записывает в неё символ I.
В предыдущих примерах предполагалось, что алфавит машины Поста содержит лишь пробел и символ I. Пусть теперь в алфавит входит ещё и символ 0. Решим следующую задачу. На ленте записана последовательность символов I и 0. Головка обозревает самый левый элемент последовательности. Требуется заменить все символы I на 0 и 0 на I.
1. {(I; 2), (0; 3), ( ;5)}
2. 0 4
3. I 4
4. ® 1
5. СТОП
Проследите за работой программы, изображая состояние ленты и положение головки после выполнения очередного шага.
Наконец рассмотрим следующую задачу. Сдвинуть число, записанное в единичной системе, на одну позицию влево. В начальный момент времени головка обозревает левую единицу числа.
1. ¬ 2
2. I 3
3. ® 4
4. {(I; 3), ( ;5)}
5. ¬ 6
6. 7
7. СТОП
Машины Поста были предложены в качестве формализации нестрого понятия алгоритма. Формализация понятия алгоритма позволяет строго доказывать теоремы о не существовании алгоритмов для решения каких-нибудь задач. Пост предположил, что любой алгоритм может быть записан в виде программы для машины Поста. Сделаем несколько оговорок.
Алгоритм понимается здесь в самом общем смысле: от алгоритма не требуется выполнения свойства конечности. Таким образом работа алгоритма над некоторыми данными может никогда не кончиться. В
Том случае будем говорить, что алгоритм не применим к этим исходным данным. Алгоритм может быть неприменим и по другим причинам, например в случае остановки машины Поста по причине безрезультативной остановки. Результат применения алгоритма P к исходным данным X будем обозначать через P(X); будем считать, что это выражение не определено если алгоритм P не применим к X. Определим понятие эквивалентности двух алгоритмов. Алгоритм P называется эквивалентным алгоритму Q, если для любых исходных данных X выполняется равенство P(X)=Q(X). Это означает, что либо оба выражения не определены, либо оба определены и равны.
Исходные данные для машины Поста задаются состоянием ленты и положением головки. Чтобы избавиться от проблемы поиска исходных данных на ленте, договоримся, что в начальный момент головка обозревает самый левый непустой символ исходных данных. Кроме того, потребуем, чтобы среди символов исходных данных не было пробелов. Тогда исходные данные для машины Поста можно будет записывать в виде конечной последовательности непустых символов из некоторого конечного набора - входного алфавита машины. Конечные последовательности символов из алфавита называются словами в этом алфавите. Можно сказать, что машина Поста перерабатывает слова в некоторые другие слова. Теперь мы можем сформулировать более строго теорему Поста:
Теорема Поста: Для всякого алгоритма, исходными данными и результатами которого являются слова, существует эквивалентная ему программа для машины Поста.
Заметим, что ограничение всего лишь словами на самом деле нас нисколько не стесняет, так как все математические объекты, с которыми могут работать алгоритмы можно закодировать в виде слов.
Теорема Поста не может быть доказана математически, так как она включает в себя нестрогое понятие алгоритма. Она может быть лишь подтверждена большим количеством примеров и отсутствием опровергающих примеров и некоторыми общими рассуждениями, то есть точно также как устанавливаются законы природы в естественных науках.
Дополнительные задания
И9.1. На ленте записаны два положительных целых числа в единичной системе счисления, разделённые одним пробелом. Головка в начальный момент расположена у левого конца левого числа. Написать программу для машины Поста, которая после результативной остановки оставит на ленте запись одного числа, являющегося суммой двух исходных.
И9.2. В условиях задачи 1 написать программу для вычисления величины разности двух чисел.
И9.3. В условиях задачи 1 написать программу для вычисления произведения двух чисел.
И9.4. Написать программу нахождения целой части корня квадратного из числа, записанного на ленте машины Поста в единичной системе счис
