Виды и свойства алгоритмов

        В среде математиков известна такая притча. В давние времена, когда никто и понятия не имел о компьютерах и их возможностях, один индийский мудрец оказал большую услугу своему правителю. Правитель решил отблагодарить его и предложил ему самому выбрать награду. На что мудрец ответил, что пожелал бы видеть шахматную доску, на каждой клетке которой были бы разложены зернышки пшена в следующем порядке: на первой – 2, на второй – 2х2=4, на третьей – 2х2х2=8, на четвертой 24=16, и так далее на всех клетках.
Сначала правитель обрадовался легкости расплаты. Но вот выполнить обещание не смог, так как он и его слуги вряд ли когда-нибудь смогли бы отсчитать 264 зерен на последнюю клетку, что соответствует примерно 18,4 миллиардам миллиардов (!) .
Задача, сформулированная в этой притче, относится к разряду тех, при решении которых самый современный компьютер бессилен так же, как в древности слуги правителя. Зная производительность современных ЭВМ, не представляет труда убедиться в том, что пользователю не хватит всей его жизни для отсчета зерен.

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

Определение:   Алгоритмизация — процесс разработки алгоритма (плана действий) для решения задачи.
Другие примеры алгоритмов.
Любой прибор, купленный в магазине, снабжается инструкцией по его использованию.
Каждый шофер должен знать правила дорожного движения.
Массовый выпуск автомобилей стал возможен только тогда, когда был придуман порядок сборки машины на конвейере.
 

     Алгоритм можно задавать в разных формах:

  • словесно;
  • в виде графики;
  • в виде таблицы;
  • в алгоритмическом языке и т. д. 

    Например: алгоритм решение старинной задачи "О волке, козе и капусте"выглядит так:

  1. перевези козу;
  2. переправься;
  3. перевези волка;
  4. перевези козу обратно;
  5. перевези капусту;
  6. переправься;
  7. перевези козу.

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

  1. Достать ключ из кармана.
  2. Вставить ключ в замочную скважину.
  3. Повернуть ключ два раза против часовой стрелки.
  4. Вынуть ключ.

      Алгоритм решения задачи - сквэрворда выглядит так:

Программа на языке TURBO PASCAL была написана на основание заданного алгоритма:

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

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

     

    Детерминированность (от лат. determinate — определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае.
    Например, алгоритм в виде блок-схемы:

    •  
           Конечность - каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. В приведенных примерах каждое описанное действие реально и может быть выполнено. Поэтому и алгоритм имеет предел, то есть конечен.
          Задача выполненная в электронной таблице EXCEL тоже является алгоритмом:

           Массовость - один и тот же алгоритм можно использовать с разными исходными данными. Например: алгоритм приготовления любого бутерброда.
    1. Отрезать ломтик хлеба.
    2. Намазать его маслом.
    3. Отрезать кусок любого другого пищевого продукта (колбасы, сыра, мяса).
    4. Наложить отрезанный кусок на ломоть хлеба.



     

            Результативность - в алгоритме не было ошибок. Пример: рассмотрим алгоритм нахождения большего из двух заданных чисел А и В:

    1. Из числа А вычесть число В.
    2. Если получилось отрицательное значение, то сообщить, что число В больше.
    3. Если получилось положительное значение, то сообщить, что число А больше.

    При всей простоте и очевидности алгоритма, не каждый сразу поймет его ошибочность. Ведь если оба числа равны, то не получится ни­ какого сообщения. Значит, надо обязательно предусмотреть это вариант, например:

    1. Из числа А вычесть число В.
    2. Если получилось отрицательное значение, то сообщить, что число В больше.
    3. Если получилось положительное значение, то сообщить, что число А больше.
    4. Если получился ноль, то сообщить, что числа равны.

             Алгоритмы делятся на следующие типы:

    1. Линейный алгоритм
      Определение:        Алгоритм, в котором команды исполняются строго одна за другой, называют линейным алгоритмом.
      Например:

    Следующий алгоритм тоже является линейным, так как все условия определения выполняются;

           2.  Алгоритм ветвления
    Определение:  Алгоритм, в котором порядок действий зависит от выполнения условия, называют алгоритмом ветвления.
    Например:

    Следующий алгоритм тоже является алгоритмом ветвления, так как все условия определения выполняются;
          3.  Алгоритм повторения
    Определение:  Алгоритм, в котором выполняются одни и те же действия, называют алгоритмом повторения.
    Например:

    Следующий алгоритм тоже является алгоритмом повторения, так как все условия определения выполняются;

            Алгоритм рекурсии
     Определение:  Само-себе  обрушающиеся алгоритмы называются алгоритмами рекурсии
    Например, алгоритм вычисления факториала,

                          алгоритмы вычисления элементов комбинаторики и т.д.

     

    В начало