Алгоритм и его свойства
Понятие алгоритма

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение этого термина связано с математикой. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов.

Термин алгоритм происходит от имени средневекового персидского математика Мухаммеда Аль-Хорезми (787 – 850 гг.), который еще в IX в. (825 г.) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.

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

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

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

Первоначально для записи алгоритмов пользовались средствами обычного языка (словесное представление алгоритмов).

Примеры алгоритмов

  1. Вычислить факториал числа n (произведение n натуральных чисел c=n!), который вычисляется по формуле c=1*2*3*4*…*n

Алгоритм:

  1. Полагаем c=1 и переходим к следующему пункту.
  2. Полагаем i=1 и переходим к следующему пункту.
  3. Полагаем c=i*c и переходим к следующему пункту.
  4. Проверяем, равно ли i числу n. Если i=n, то вычисления прекращаем. Если i<n, то увеличиваем i на 1 и переходим к пункту 3.
  1. Найти наименьшее число M в последовательности из n чисел a1, a2,…, an (n?0) . Прежде чем записать словесный алгоритм данного примера, детально рассмотрим сам процесс поиска наименьшего числа. Первоначально в качестве числа M принимается число a1, т.е. полагаем M=a1, после чего M сравниваем с последующими числами последовательности, начиная с a2. Если M? a2, то M сравнивается a3; если M? a3 , то M сравнивается a4; и так до тех пор, пока найдется число ai < M. Тогда полагаем M= ai и продолжаем сравнение с   M  последующих чисел из последовательности, начиная с ai+1, до тех пор, пока не будут просмотрены все n чисел. В результате просмотра всех чисел M будет иметь значение, равное наименьшему числу последовательности (i – текущий номер числа).

Алгоритм:

  1. Полагаем i=1 и переходим к следующему пункту.
  2. Полагаем M= ai и  переходим к следующему пункту.
  3. Сравниваем i с n; если i< n, то переходим к пункту 4; если i= n, то процесс поиска останавливаем.
  4. Увеличиваем i на 1 и переходим к следующему пункту.
  5. Сравниваем ai с M. Если M? ai, то переходим к пункту 3; иначе (M >ai) переходим к пункту 2.

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами (первый алгоритм).

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

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

 Свойства алгоритмов

Разработать алгоритм означает разбить задачу на определенную последовательность шагов. От разработчика алгоритма требуется  знание особенностей и правил составления алгоритмов.

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

Алгоритм представляет собой последовательность команд (инструкций, директив), определяющих действия исполнителя (субъекта или управляемого объекта). Исполнитель, выполняя алгоритм, может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В этом случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и строго выполняет инструкции. Таким образом, возможность решения задачи, механически исполняя команды алгоритма в указанной последовательности, называется формальностью.

Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того чтобы алгоритм мог быть выполнен, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. Нельзя повару поручать работу токаря, какая бы подробная инструкция ему не давалась. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Каждая команда алгоритма должна определять однозначно действие исполнителя. Такое свойство алгоритмов называется определенностью (или точностью) алгоритма.

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

Еще одно важное требование, предъявляемое к алгоритмам, – результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.

Разработка алгоритмов – процесс творческий, требующий умственных усилий и затрат времени. Поэтому предпочтительно разрабатывать алгоритмы, обеспечивающие решения всего класса задач данного типа. Например, если составляется алгоритм решения кубического уравнения ax3 + bx2 + cx + d = 0, то он должен быть вариативен, т.е. обеспечивать возможность решения для любых допустимых исходных значений коэффициентов a, b, c, d. Про такой алгоритм говорят, что он отвечает требованию массовости.

 

Основные особенности и свойства алгоритмов:

  1. Наличие ввода исходных данных.
  2. Наличие вывода результата выполнения алгоритма, поскольку цель выполнения алгоритма – получение результата, имеющего вполне определенное отношение к исходным данным.
  3. Дискретность – разбивка алгоритма на элементарные команды, и выполнение очередной команды начинается после завершения предыдущей.
  4. Формальность – свойство, позволяющее любому исполнителю, способному воспринимать и выполнять отдельные указания алгоритма, правильно выполнить весь алгоритм.
  5. Определенность (точность) – однозначность предписанной последовательности действий, не допускающей ее двоякого толкования.
  6. Понятность – свойство, предусматривающее то, что алгоритм должен состоять только из тех команд, которые исполнитель может выполнить.
  7. Результативность (конечность) – исполнение алгоритма должно закончиться за конечное число шагов.
  8. Корректность – алгоритм должен задавать правильное решение задачи.
  9. Массовость – алгоритм разрабатывается для решения некоторого класса задач, различающихся исходными данными.
  10. Эффективность – алгоритм должен выполняться за разумное конечное время. При этом выбирается наиболее простой и короткий способ решения задачи при соблюдении всех ограничений и требований к алгоритму.

 

Свойства дискретности, формальности, точности, понятности и конечности являются необходимыми (иначе это не алгоритм). Свойство массовости не является необходимым свойством алгоритма, оно скорее определяет его качество.

Формы записи алгоритмов

Алгоритмы можно записывать по-разному. Форма записи, состав и количество операций алгоритма зависит от того, кто будет исполнителем этого алгоритма.

Способы описания алгоритма:

  1. Формульная запись
  2. Табличная запись
  3. Развернутая словесная
  4. На алгоритмическом языке
  5. Графический (в виде блок схемы)
  6. На языке программирования
    1. Формульная запись алгоритма производится с помощью простых математических, химических, физических формул.

Например:

S=V*t; V=S/t; t=S/V

    1. Табличная запись производится с помощью букв латинского алфавита и знака, который называется знаком присвоения :=.

Например:

ШАГ ОПИСАНИЕ ДЕЙСТВИЙ
                              1. a:=5x
                              2. b:=a+3
                              3. c:=4x
                              4. d:=c-7
                              5. y:=b/d
    1. Развернутое (словесное) описание алгоритма производится на любом национальном языке, единственным условием является соблюдение свойств алгоритма. Используется обычно для описания алгоритмов, предназначенных исполнителю – человеку. Команды записываются на обычном языке и выполняются по порядку. В командах могут использоваться формулы, специальные обозначения, но каждая команда должна быть понятна исполнителю. Естественный порядок команд может быть нарушен, в этом случае команды можно нумеровать и указывать команду, к которой требуется перейти.

Например:

ШАГ ОПИСАНИЕ ДЕЙСТВИЙ
                              1. число 7 умножить на переменную x
                              2. из результата шага 1 вычесть число 4
                              3. число 5 умножить на переменную x
                              4. к результату шага 3 прибавить число 3
                              5. результат шага 2 разделить на результат шага 4
    1. Запись алгоритма на алгоритмическом языке записывается с помощью служебных слов, языка и формул (знаков присвоения).

Например: найти большее из трех чисел.

Алгоритм БИТ

  1. чтение a, b, c
  2. если a < b к 4
  3. y:=b; к 5
  4. y:=a
  5. если y > c к 7
  6. y:=c
  7. запись y
  8. конец
    1. Запись алгоритма в виде блок-схем (или графическая запись). Алгоритмы представляются в виде блок-схем. Существуют специальные стандарты для построения блок-схем, где определяются графические изображения блоков. Команды алгоритмов записываются внутри блоков на обычном языке или с использованием математических формул. Блоки соединяются по определенным правилам линиями связи, которые показывают порядок выполнения команд.
    1. На языке программирования. Если алгоритм разработан для решения задачи на ЭВМ, то для того, чтобы он мог выполниться исполнителем – ЭВМ, его необходимо записать на языке, понятном этому исполнителю. Для этого разработано множество языков программирования для решения задач разных классов. Запись алгоритма на языке программирования называется программой.

 

Контрольные вопросы
  1. Что такое алгоритм?
  2. Перечислите основные особенности алгоритмов.
  3. Назовите способы представления алгоритмов.