Математическая логика и теория алгоритмов. Стенюшкина В.А. - 52 стр.

                    ЧАСТЬ 2 ТЕОРИЯ АЛГОРИТМОВ

                                     Введение

      Понятие алгоритма занимает одно из центральных мест в современной
математике.
      Алгоритм – предписание, однозначно задающее процесс преобразования
исходной информации в виде последовательности элементарных дискретных
шагов, приводящих за конечное число их к результату.
      Слово «алгоритм» происходит, по мнению многих, от имени узбекского
математика ал – Хорезми, который в IX веке разработал правила четырех ари-
фметических действий над числами в десятичной системе счисления. С другой
стороны, вычислительные процессы, с помощью которых искомые величины
определялись из известных величин по заданным правилам, стали возникать в
математике на самых ранних ступенях ее развития (Древний Египет, Вавилон,
Древняя Греция). В книге Евклида «Начала» (около 300 г до н. э.) имеется алго-
ритм нахождения наибольшего общего делителя двух чисел, который, не иск-
лючено, был известен и ранее. Представим его в виде рекурсивной процедуры.
      Вход: неотрицательные целые числа а, b (а>b).
      Выход: НОД (а,b).
      Евклид (а, b)
      1 если b=0
      2 то НОД ← а
      3 иначе НОД ← Евклид (b, а mod b)
      Реализация: Евклид (30,21) = Евклид (21,9) = Евклид (9,3) = Евклид
(3,0)=3; НОД (3,21)=3.
      Входными и выходными данными алгоритма могут служить самые раз-
нообразные конструктивные объекты. Это открывает возможность широкого
применения понятия алгоритма. Можно говорить об алгоритме перевода с од-
ного языка на другой, об алгоритме работы авиадиспетчера (перерабатывающе-
го информацию о движении самолетов в предписания летчикам) и других при-
менениях алгоритмического описания.
      Отметим несколько общих свойств алгоритмов.
      1) Всякий алгоритм применяется к входным данным и имеет результатом
выходные данные. На элементарных шагах появляются промежуточные дан-
ные. Данные должны быть специфицированы, в частности, указан алфавит дан-
ных и способы построения сложных данных из простых. Примерами данных
могут быть числа, массивы чисел, изображения на экране и т. д.
      2) Единицы объема данных и памяти ЭВМ должны быть согласованы. В
прикладных алгоритмических моделях объем данных можно измерять числом
ячеек памяти, в которых данные размещены. При этом исходят из того, что па-
мять ЭВМ состоит из одинаковых ячеек, каждая из которых может содержать
один или несколько символов алфавита данных.
       3) Элементарные шаги алгоритма состоят из базовых операций, число
которых конечно. В частности, под операциями можно подразумевать машин-