Е

Е.П. Емельченков, В.И. Мунерман, Т.А.Самойлова, В.Н.Федоров

Раздел 2. Информация. Алгоритмы. Первые шаги программиста.

С давних пор математики использовали системы правил, которые позволяли им решать различные задачи. Эти системы правил постоянно модернизировались, так как их авторы стремились к наибольшей эффективности. Требовалось, чтобы правила приводили к решению задачи как можно скорее.

История математики помнит множество математических турниров, участвуя в которых математики оттачивали свои системы правил. В отличие от рыцарских турниров, математические турниры играли огромную роль в истории, развивая и двигая вперед математическую науку и практику. Один из таких турниров состоялся 12 февраля 1535 года в Болонье. Математик Фиоре вызывал на поединок каждого, кто желал сравниться с ним в искусстве решения кубических уравнений. Вызов Фиоре принял Николо Тарталья. За десять дней для начала турнира он узнал, что Фиоре знаком с методом решения кубических уравнений, найденным Сципионом дель Ферро. Тарталья в короткое время нашел более рациональный метод и, буквально, разгромил своего противника на турнире.

В средние века научиться выполнять арифметические операции над большими числами можно было только в университете, да и то не в каждом. Лучше всего это умели делать в Италии, где математики преуспели в работе с числами, записанными в римской системе счисления, использовавшейся в средневековой Европе. В IX веке математик Абу Джафар Магомет ибн Муса аль-Хорезми, чье имя буквально переводится как "Отец Джафара, Магомет, сын Мусы, уроженец Хорезма", опубликовал трактат, в котором были описаны правила выполнения арифметических действий над числами, записанными в десятичной системе счисления. Эти правила оказались настолько простыми, что скоро стали доступны младшим школьникам. Трактат содержал также многочисленные рецепты решения различных математических задач. Трактат был переведен на латынь и несколько столетий был популярен в Европе. При переводе Аль-Хорезми превратилось в Алгоритми.

Ссылки на правила из книги Аль-Хорезми начинались словами: "Так говорил Алгоритми" (по латыни "Dixit Algoritmi"). Впоследствии алгоритмами стали называть сами правила решения математических задач. В настоящее время слово "алгоритм" вышло за пределы математики. Его стали использовать в самых различных областях, понимая под алгоритмом точно сформулированное правило, назначение которого - быть руководством для достижения необходимого результата.

Когда мы говорим о решении задач при помощи систем правил, мы подразумеваем, что кто-то или что-то выполняет действия, заданные этими правилами. Например, правила, определяющие последовательность действий при приготовлении пищи, выполняет повар. Изготовление детали на токарном станке определяется системой правил, называемой технологическим процессом. Эти правила может выполнить токарь или станок с программным управлением. Человек или устройство, способные выполнять перечисленные в алгоритмах правила, называется исполнителем.

Каждый исполнитель полностью характеризуется своей системой команд.

Опишем теперь более подробно понятие алгоритма.

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

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

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

Пример 7. Определить, может ли слон, стоящий на заданном поле шахматной доски попасть на другое заданное поле.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Решение. Напоминаем, что, во-первых, траектория перемещения слона - гипотенуза равнобедренного прямоугольного треугольника. Во-вторых, на шахматной доске клетки адресуются парой значений, состоящих из буквы и цифры, как показано на рисунке 34.

1. Заменить буквенные обозначения вертикальных координат обоих полей числовыми: a - 1, b - 2, ... , h - 8.

2. Пусть координаты первого поля (x₁, y₁), второго - (x₂, y₂).

3. Если |x₁ - x₂| = |y₁ - y₂|, то ответ: "слон попадает из одного поля на другое. В противном случае ответ: "слон не попадает из одного поля на другое".

Исполнителем этого алгоритма может быть не только человек, но и компьютер, который уже сегодня может играть в шахматы на гроссмейстерском уровне.

Пример 8. Найти все простые числа, не превосходящие заданное число N.

Решение. Воспользуемся алгоритмом, известным под названием "Решето Эратосфена". Для реализации этого алгоритма нам потребуются только карандаш и бумага. Простые числа мы будем подчеркивать, а все остальные - зачеркивать.

1. Если N < 2, сообщить, что таких простых чисел нет и остановиться.

2. Записать на листе бумаги все натуральные числа от 2 до N.

3. Выбрать наименьшее неподчеркнутое число и подчеркнуть его.

4. Пусть это число равно K. Вычеркнуть каждое K-тое из следующих за K чисел.

5. Если среди невычеркнутых чисел остались неподчеркнутые, перейти к шагу 3, в противном случае остановить работу.

Незачеркнутыми остались только простые числа.

Проверим работу нашего алгоритма на первых двадцати числах. Вместо зачеркнутого числа будем ставить знак . Так как 20 больше 2, мы сразу перейдем к пункту 2.

3. Наименьшее неподчеркнутое число - 2. Подчеркнем его.

4. Вычеркнем каждое второе после 2 число. Получим

5. Так как остались неподчеркнутые числа, перейдем к шагу 3.

3. Наименьшее неподчеркнутое число - 3. Подчеркнем его.

4. Вычеркнем каждое третье после 3 число. Получим

5. Так как остались неподчеркнутые числа, перейдем к шагу 3.

На этом мы останавливаем выполнение алгоритма и предлагаем читателю самостоятельно убедиться в том, что правило пятого шага может быть сформулировано так:

Если остались неподчеркнутые числа и наименьшее из них не превосходит квадратного корня из N, перейти к шагу 3.

Правила из примеров 7 и 8, безусловно, являются алгоритмами, однако, часто встречаются совокупности правил, внешне похожие на алгоритмы, но алгоритмами не являющиеся. Для того, чтобы убедиться в том, что совокупность данных правил - алгоритм, необходимо проверить наличие у них следующих свойств.

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

Определенность. Алгоритм может быть выполнен исполнителем, который понимает каждую команду алгоритма, и может выполнить ее в строгом соответствии с ее назначением. При выполнении команд нет места произволу исполнителя. Например, получив команду "Рядом!", исполнитель -собака должен выполнить ее единственным возможным способом: стать слева от хозяина. После выполнения каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной. Это свойство также называется детерминированностью.

Массовость. Алгоритм должен решать любую задачу из рассматриваемого класса задач.

Результативность. Выполнение алгоритма должно завершаться за конечное число шагов и при этом должен быть получен ответ на вопрос задачи. Один из возможных ответов может указывать на то, что задача решения не имеет.

Покажем, что этими свойствами обладает алгоритм "Решето Эратосфена".

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

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

Массовость алгоритма состоит в том, что он может быть применен к любому натуральному числу.

Результативность следует из того, что каким бы ни было число N, алгоритм может быть выполнен за конечное (пусть даже и очень большое) время.

Пример 9. Рассмотрим одно из правил выхода из лабиринта, которое называется "правило правой руки".

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

Рис. 35. Лабиринт, в котором "правило правой руки"

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