4792

Алгоритмы. Императивный подход. О понятии алгоритма. Декларативный подход

Лекция

Информатика, кибернетика и программирование

Алгоритмы. Императивный подход. Содержательное понятие алгоритма. Точное математическое определение алгоритма и изучение этого понятия - предмет специальной математической дисциплины - теории алгоритмов, которая, в свою очередь, опирается на...

Русский

2012-11-27

132.5 KB

14 чел.

Алгоритмы. Императивный подход.

1.Содержательное понятие алгоритма.

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

 

Алгоритм - это некоторое правило преобразования информации, применение которого к заданной (исходной) информации приводит к результату - новой информации.

     

Рис 1

Так, например, применение правила сложения дробей к 1/2 и 2/3 приводит к результату 5/6.

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

 

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

Рис 2

На рис. 2 изображена последовательность команд C1, C2, …, Ck по преобразованию информации, выполняемая алгоритмом.

Так, алгоритм сложения дробей можно задать следующей последовательностью команд:

Пример 1. Алгоритм сложения дробей.

Вход: A/B, C/D;

1. Вычислить Y = B*D;         {Перейти к следующей команде}

2. Вычислить X1 = A*D;       {Перейти к следующей команде}

3. Вычислить X2 = B*C;        {Перейти к следующей команде}

4. Вычислить X = X1+X2;      {Перейти к следующей команде}

5. Вычислить Z = НОД(X,Y); {Перейти к следующей команде}

6. Вычислить Е = X div Z;       {Перейти к следующей команде}

7. Вычислить F = Y div Z;       {Закончить работу}.

Выход: E/F

Наш алгоритм состоит из 7-ми инструкций, каждая из которых содержит описание одного из арифметических действий над целыми числами: сложение, умножение, вычисление НОД и целочисленное деление div. Кроме того, каждая инструкция (в неявном виде) содержит указание на следующую выполняемую инструкцию. Таким образом, алгоритм описывает детализированный по шагам процесс преобразования информации. Уровень детализации описания определяется набором допустимых команд. Этот набор называют набором команд Исполнителя или Интерпретатора. 

2. Исполнитель (алгоритмов) и его система команд.

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

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

Представим себе, что в нашем распоряжении находится Исполнитель, интерпретирующий команды - операции целочисленной арифметики - сложение, вычитание, умножение, вычисление неполного частного (div) и остатка (mod), вычисление НОД и НОК с запоминанием результатов и умением переходить к следующей команде. Тогда для этого Исполнителя можно составлять самые разнообразные алгоритмы арифметических вычислений - т.е. вычислений, заданных формулами типа X = НОД((A + B) div 100,  (A * B - 7) mod 10) используя команды, аналогичные командам алгоритма из примера 1.

Пример 2. Алгоритм деления отрезка пополам с помощью циркуля и линейки.

Вход: Отрезок AB;

  Построить окружность O1 с центром A и радиусом AB;

  Построить окружность O2 с центром B и радиусом AB;

  Найти точки С и D пересечения окружностей O1 и O2;

  Построить отрезок CD;

  Найти точку Е пересечения AB и CD.

Выход: Точка Е - середина отрезка AB.

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

Упражнение. Предложить полную систему команд Исполнителя – решателя геометрических задач на построения.

Пример 3. Алгоритм решения приведенного квадратного уравнения  x2 + px + q = 0;

Вход: Коэффициенты p и q уравнения x2 + px + q = 0;

Вычислить D = p2 - 4q;

Если D < 0 то (ответить “Решений нет”; Перейти к 1);

Если D = 0 то (вычислить x = -p/2; Перейти к 1);

Вычислить x1 = (-p+(D))/2;

Вычислить x2 = (-p-(D))/2);

1:Закончить работу.

Выход “Решений нет” или корень x или корни x1, x2.

В этом примере используется команда вида

Если <условие> то (<последовательность команд>)

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

Второй характерной командой, используемой в примере, является команда перехода. Она имеет вид

Перейти к < N >,

причем число N используется в записи алгоритма как специальная отметка некоторой команды. В примере используются команды перехода Перейти к 1, а числом 1 отмечена команда 1:Закончить работу.

Выполнение команды перехода заключается в том, что Исполнитель переходит к выполнению команды, отмеченной отметкой N (нарушая при этом естественную последовательность выполнения команд).

 

2. Основные свойства алгоритмов.

Понятию алгоритма присущи следующие свойства:

 

1. Элементарность. Каждая команда из набора команд Исполнителя содержит указание выполнить некоторое элементарное (не детализируемое более подробно) действие, однозначно понимаемое и точно выполняемое Исполнителем.

Понятие элементарности поэтому относительно. Так, в алгоритме примера 1 содержится команда вычисления НОД двух чисел. Это означает, что Исполнитель умеет находить НОД, причем алгоритм вычисления (алгоритм Евклида или какой-нибудь другой) скрыт от человека, составляющего алгоритмы для этого Исполнителя. Если набор команд Исполнителя не содержит команды вычисления НОД, вычисление НОД должно быть определено в виде алгоритма.

Пример 4. Алгоритм Евклида вычисления наибольшего общего делителя целых положительных чисел A и B: НОД(A, B).

Вход A, B;

 Вычислить U = A;

 Вычислить V = B;

 Пока U <> V выполнять

   Если   U < V

      то  Вычислить V = V - U

      иначе Вычислить U = U - V;

   Вычислить D = U.

Выход: D - наибольший общий делитель A и B.

В этом примере использована команда повторения. Она имеет вид

Пока <Условие> выполнять <Команда>

Выполняя эту команду, Исполнитель проверяет истинность Условия. Если Условие истинно, Исполнитель выполняет Команду, указанную после слова выполнять и повторяет проверку Условия. Выполнение Команды и проверка Условия повторяются до тех пор, пока Условие истинно. Если Условие ложно, Исполнитель переходит к выполнению команды, следующей за командой повторения. В этом же примере использована еще одна разновидность команды ветвления - команда вида

Если <Условие> то <Команда 1> иначе < Команда 2>

Выполняя эту команду, Исполнитель проверяет Условие. Если Условие выполнено, выполняется Команда 1, в противном случае выполняется команда 2. Далее Исполнитель переходит к следующей команде. Заметим, что команда повторения, как и команды ветвления, содержат в себе другие команды.

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

Так, в исполнении алгоритма в примере 3 возможны ветвления, которые, однако, однозначно определены условиями D < 0, D = 0.

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

Так, в примере 2 описан алгоритм сложения любых двух дробей. Одна-единственная задача, решаемая Исполнителем в данный момент, определена значениями исходных данных A, B, C, D. Изменение исходных данных означает решение другой задачи из этого же класса задач.

Аналогично, алгоритм примера 2 строит середину любого отрезка, заданного его концами, а в примере 3 с помощью алгоритма решается любое приведенное квадратное уравнение.

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

Так, в примере 2 результат - точка E - середина отрезка AB. Алгоритм примера 3 выдает результат “Решений нет “ даже в том случае, когда уравнение не имеет действительных корней, поскольку его дискриминант меньше нуля.

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

3. Абстракция данных

Примеры Исполнителей, рассмотренные выше, используют абстрактные представления о предметных областях, над которыми определяются алгоритмы. Они показывают, что понятие Исполнителя является одной из основных абстракций, используемых для описания алгоритмов. Именно система команд Исполнителя и есть уточнение набора средств, с помощью которых строятся алгоритмы. В наших примерах системы команд Исполнителя предметно-ориентированы. Так, в примере 1 Исполнитель имеет дело с целочисленной арифметикой, а в примере 3 - с арифметикой действительных чисел. Особенно наглядно это демонстрирует Исполнитель примера 2, команды которого выполняют геометрические построения.

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

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

Совокупности данных, обрабатываемые алгоритмами, принято называть структурами данных (Исполнителя). Структуры данных (способы описания упорядоченных данных) влияют на эффективность алгоритма, а также на простоту его понимания и программной реализации. Структуры данных являются главными строительными блоками, из которых формируются алгоритмы. Алгоритмические структуры данных должны, с одной стороны, адекватно описывать ту предметную область, над которой определяется Исполнитель, с другой стороны – эффективно отображаться в универсальные структуры данных (например, в структуру компьютерной памяти). Эти в какой-то степени противоречивые требования приводят к следующему, более формальному пониманию термина «структура данных».

 

Структура данных состоит из трех основных компонент:

  •  Набор предметно-ориентированных операций для обработки специфических типов абстрактных объектов описываемой предметной области.
  •  Структура памяти, в которой хранятся данные, описывающие абстрактные объекты.
  •  Интерпретация (реализация) каждой из операций в терминах структуры памяти.

Первая компонента определения – набор операций над абстрактными объектами – называется абстрактным типом данных (АТД). Вторая и третья компоненты вместе образуют реализацию структуры данных.

АТД определяет, что делает структура данных - какие операции она поддерживает, не раскрывая, как они выполняются.


Пример 5. АТД Планиметрия

Примитивные типы объектов:  точка, прямая, окружность.

Примитивные операции:

Line: (точка, точка)  прямая

 l = Line(A, B) определяет прямую l, проходящую через точки A, B 

Circle: (точка, точка) окружность

o = Circle(A, B) определяет окружность о с центром в т. А, проходящую через т. В.   

CircleRad: (точка, точка, точка) окружность

o = CircleRad(A, B, C) определяет окружность о с центром в т. А, построенную раствором циркуля c ножками, установленными в B, C.   

IntersectLines(прямая, прямая)  точка

 A = Intersect(l, m) определяет точку пересечения прямых  l и m 

IntersectCircles(окружность, окружность) (точка, точка)

(A, B) = IntersectCircles(o, p) определяет пару точек A, B пересечения окружностей o и p.

IntersectLineCircle(прямая, окружность) (точка, точка)

(A, B) = IntersectLineCircle(l, o) определяет пару точек A, B пересечения прямой l и окружности o.

Из примитивных типов объектов АТД Планиметрия можно теперь строить т.н. составные типы. Например тип треугольник можно определить как тройку точек (вершин)

Треугольник = (точка, точка, точка)

Из примитивных (основных) операций АТД можно определять производные операции. Например, операция

ParralelLine: (точка, прямая) прямая,

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

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

4. Команды управления.

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

В рамках рассматриваемого нами императивного подхода к описанию алгоритмов используют следующую классификацию команд управления: команды ветвлений, повторения, перехода.

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

Синтаксис   

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

Совокупность синтаксических правил, определяющих описание алгоритма, можно разбить на две группы:

  •  правила описания данных;
  •  правила описания операторов.  

Семантика

Совокупность правил, определяющих выполнение алгоритма, можно также разбить на две группы:

  •  правила интерпретации данных;
  •  правила интерпретации операторов.

 Мы обратим сейчас внимание на содержательном уровне на семантические аспекты операторов управления.  

Рассмотрим алгоритмы решения двух задач, относящихся к различным предметным областям:

а) Алгоритм Евклида вычисления НОД двух натуральных чисел:

Алгоритм Evclid;

   Начало

       Вход(a,b);

       u := a; v := b;

       Пока u <> v выполнить

           начало

              w := u - v;

              Если w > 0

                  то       u := w

                  иначе v := -w;

          конец;

      Выход(u)

   конец.

 

б) Приближенное (с заданной точностью Eps) решение уравнения f(x) = 0 методом деления отрезка пополам:

Алгоритм EquationSol;

    Начало

         Вход(a, b, Eps);

         u := a; v := b;

         Пока u - v >= Eps выполнить

           начало

             w := (u + v)/2;

             Если f(u)*f(w) > 0  

                   то u := w

              иначе v := w;

            конец;

           Выход(u)

       Конец.

Алгоритм Еvclid работает с целыми числами. Предметная область алгоритма EquationSol - область вещественных чисел. Несмотря различие в предметных областях, между этими алгоритмами существует сходство, играющее большую роль для понимания сути алгоритмизации и программирования. В самом деле, последовательность операторов (команд) каждого из этих алгоритмов может быть описана так:

Начало

   < оператор - процедура ввода >;

   < последовательность операторов (инициализация)>;

    Пока <условие> выполнить

        начало

          <оператор>;

           Если <условие>

              то < оператор >

               иначе < оператор > ;

           конец;

           < оператор - процедура вывода >

     Конец.

Еще более наглядно такое описание выглядит на языке блок схем:

Блеск и нищета языка блок-схем

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

6. Базовые управляющие структуры

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

К основным структурам управления относятся:

последовательное выполнение

 

 

 

 

ветвление

 

повторение

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

Программирование управления – описание управления алгоритма - осуществляется комбинированием основных управляющих структур. Например, комбинирование ветвления и повторения приводит к блок-схеме

 

 

Основной результат можно теперь сформулировать следующим образом:

Структура управление любого алгоритма может быть реализована в виде комбинации основных управляющих структур.

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

Отметим, что оператор перехода Перейти_к_<N> оператор Goto не включен ни в список основных, ни дополнительных управляющих операторов. Это - не случайность. Бесконтрольное применение этого оператора приводит к тому, что алгоритм теряет свойства, указанные выше. Поэтому структурное программирование иногда называют программированием без Goto.

7. Семантика операторов управления

Ключевым аспектом семантического определения операторов управления является понятие условия. Как правило, в алгоритмических системах условия определяются в терминах АТД - т.н. логического типа. Логический тип имеет два значения – F и T,  также функционально полный набор логических операций (and, or, xor, not, …) со стандартными интерпретациями алгебры высказываний (т.н. таблицы истинности логических связок). Кроме того, каждый предметно-ориентированный АТД имеет, как правило, несколько операций логического типа. Например, АТД «натуральные числа» должен содержать операции логического типа  (<,  <=,  >,  >=,  =,  <>).

Семантика оператора Если U то P иначе Q  определяется равенствами

U = T  Если U то P иначе Q =df= P

U = F  Если U то P иначе Q =df= Q

Важную роль в семантическом описании управляющих операторов играет понятие неопределенности. Неопределенность возникает как следствие того, что некоторые операции АТД вообще говоря, частично определены. Так, операция A/B не определена при B = 0.

Еще один источник неопределенности – бесконечно повторяющиеся циклы. Оператор Пока T выполнять P   - не определен, причем эта неопределенность не может быть раскрыта, поскольку не существует конструктивного способа (алгоритма), который по описанию цикла распознавал, завершится ли этот цикл, или нет. Поэтому полные семантические описания управляющих обязаны содержать правила учета неопределенностей.

Для обозначения неопределенности введем специальный символ . Тогда семантика оператора  Если U то P иначе Q дополняется равенством

U =   Если U то P иначе Q =df=

8. Парадигма процедурного программирования.

Основная идея, методология (парадигма) обсуждаемого подхода к определению алгоритма может быть выражена «формулой» Н.Вирта:

АТД + Структуры управления = Алгоритмы

Алгоритмы + структуры данных = программы.


Лекция 2.  О понятии алгоритма. Декларативный подход

1. О формализации понятия алгоритма.

Термин «алгоритм» впервые был использован средневековыми учеными, переводившими на латынь сочинения Аль Хорезми. Алгоритмами они называли правила арифметических действий на многоразрядными числами. В XVII веке В.Лейбниц выдвинул идею формализации математики – т.е. построения универсального метода решения математических задач в виде системы правил манипулирования символами, с помощью которых эти задачи формулируются. Напомним, что именно В.Лейбниц ввел в употребление современную символику дифференциального и интегрального исчисления, в большой степени решившую задачу вычислений производных и интегралов при помощи формальных правил манипулирования символами.

Формальное понятие алгоритма было сформулировано как одно из понятий математической логики в 30-х годах XX века. В работах Э. Поста, А. Тьюринга, С. Клини, А. Черча и др. логиков. Несколько позже А.А. Марков ввел еще один формализм описания алгоритмов – т.н. нормальные алгорифмы Маркова. Как мы уже отмечали, формальные аспекты понятия «алгоритм» изучаются в теории алгоритмов. Мы сейчас рассмотрим только одно из нескольких эквивалентных определений алгоритма, а именно – определение алгоритма как частично-рекурсивной функции (С. Клини, А.Черч).

2. Понятие вычислимости. Вычислимые функции

Альтернативный (императивному) т.н. декларативный (описательный) подход к описанию алгоритмов состоит в описании алгоритма как функции преобразования Вход Выход.  

Алгоритм: Вход Выход

или, в более привычных «школьных» обозначениях   

y = A(x),

где A – алгоритмическая функция

x Х – входные данные (аргументы) из области определения X

y Y – выходные данные (значения) из области значений Y.

Изучение понятия алгоритма, следовательно, можно определить как изучение свойств функции A.

Точная постановка задачи формального определения алгоритма заключается в формализации понятия вычислимой функции.

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

Отметим, что в качестве областей определения аргументов и области значения функции выступают натуральные числа. Почему именно они?

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

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

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

Арифметика изобилует примерами вычислимых функций:

Z = x+y,  z = min(x, y),  z = x div y, …

Более сложные примеры прямо апеллируют к интуитивному понятию алгоритма:

 Y = {наименьшее простое число, большее x и такое, что y+2 - также простое}

Y = {максимальный показатель степени в разложении числа x в произведение степеней простых сомножителей } 

2. Примитивно-рекурсивные функции

 

В этом разделе мы введем понятие примитивно-рекурсивной функции (ПРФ) и убедимся в том, что примитивно-вычислимые функции вычислимы.  

0. Базисные примитивно-рекурсивные функции:

  1.  s(x) =df= x + 1        примитивно рекурсивна (по определению)
  2.  o(x) =df= 0          примитивно рекурсивна (по определению)
  3.  pi(x1,…,xi,…,xn) =df= xi     примитивно рекурсивна (по определению)

Правила построения примитивно-рекурсивных функций

  1.  Правило суперпозиции

Если F(y1, …, yn) примитивно рекурсивна и

g1( x1,…,xk), g2(x1,…,xk),  . . . gn(x1,…,xk) примитивно рекурсивны, то

H(x1, …, xk) =df= F(g1( x1,…,xk), g2(x1,…,xk),  . . . gn(x1,…,xk)) также примитивно рекурсивна

  1.  Правило примитивной рекурсии

Если F(x1,…,xn-1), G(x1,…,xn, xn+1)примитивно-рекурсивные функции, то функция H(x1,…, xn), определяемая соотношениями

а) H(x1, … , xn-1, 0) =df= F(x1,…,xn-1)

b) H(x1, … , xn-1, s(y)) =df= G(x1,…,xn-1, y, H(x1, … , xn-1, y))

также примитивно рекурсивна.

  1.  Функция называется примитивно-рекурсивной, если она определена с помощью конечного числа правил 1, 2 из функций, определенных правилом 0 (из базисных примитивно-рекурсивных функций).

Определение класса примитивно-рекурсивных функций типично для теории алгоритмов и математической логики. В математике такие определения часто называют рекуррентными, в математической логике и теории алгоритмов, а как следствие, и в программировании – рекурсивными.

Суть рекуррентных (рекурсивных) определений заключается в следующем:

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

 Упражнение. Определить класс управляющих структур алгоритмов с помощью рекурсивных определений.

Поскольку базисные функции класса ПРФ, вне всякого сомнения, вычислимы, и правило суперпозиции также эффективно применимо (вычислить значения аргументов, а затем – значение функции), получаемые с помощью определений 0, 1 функции являются вычислимыми. Многие классы функций, используемые в математике, обладают свойствами 0 и 1, т.е. содержат функции s(x), o(x), pi(x1, …, xn) и замкнуты относительно операции суперпозиции. Таким образом, «эксклюзивность» и, как следствие, имя классу примитивно-рекурсивных функций дает правило (схема) примитивной рекурсии. Отметим, что функция проектирования pi(x1, …, xn) используется для решения технической проблемы представления функции одного переменного как функции многих переменных.

Убедимся в вычислимости функций, определяемых правилом 2, сопоставив этому правилу фрагмент алгоритма в императивном стиле:  

 


 Вход: x1,…,xn-1 , y

 H := F(x1,…,xn-1),

 Для i := 1 до  y  выполнить H := G( x1,…,xn-1 ,i,  H )

 Выход: H 

 

Переменные x1,…,xn-1 играют роль параметров (не меняют значения в теле цикла). Переменная y - верхнее значение параметра цикла. Вычисление каждого следующего значения H использует предыдущее значение Н.

Пример: П. Р. Функция Add сложения двух натуральных чисел

Add(x, o) = x;   {x + 0 = x}

Add(x,s(y)) = s(Add(x, y))   {x + (y + 1) = (x + y) + 1  

  1.  Мю-оператор

Основной результат о примитивно-рекурсивных функциях и их связи с императивными алгоритмами можно сформулировать так:

Примитивно-рекурсивные функции вычислимы. Вычисление примитивно-рекурсивной функции можно реализовать в виде императивного алгоритма, использующего число 0, функцию s, оператор присваивания и оператор повторения с параметром.   

Можно построить пример вычислимой функции, не принадлежащей классу примитивно-рекурсивных функций. Методы построения такого рода контрпримеров будут рассмотрены в курсе теории алгоритмов. Здесь мы только укажем на один из таких примеров – т.н. функцию Аккермана.

Функция Аккермана А(x, y) определена на множестве натуральных чисел рекурсивно:

A(0, y) = y + 1,

A(x, 0) = A(x - 1, 1),

A(x, y) = A(x - 1, A(x, y - 1));

Упражнение.

a) Опишите функции A(1, y), A(2, y), A(3, y), A(4, y) явным образом;

б) Реализуйте рекурсивную программу вычисления A(x, y);

в) Реализуйте программу вычисления A(x, y) без рекурсии.

Таким образом, для формализации класса вычислимых функций правила примитивной рекурсии недостаточно. Более того, оказалось, что никакое “разумное” расширение класса ПРФ до формально описанного класса всюду определенных функций, являющихся вычислимыми, невозможно. Поэтому любой формализм неибежно приводит к частично-определенным функциям (функциям, не определенным при некоторых значениях аргумента). Свойство результативности алгоритма оказывается нетривиальным.

Определим еще одно правило порождения вычислимой функции – т.н. -оператор.

Правило -операции

Пусть F(x1,…,xn,y) – вычислимая функция. Тогда функция G(x1,…,xn), определенная правилом

  G(x1,…,xn) = { Наименьшее y | F(x1, …, xn, y)  =  0 }

является (по определению) результатом применения -операции к функции F(x1,…,xn,y). Стандартная форма записи -операции:

G(x1,…,xn) =  y ( F(x1, …, xn, y)  =  0 }

Говорят, что функция G – результат применения -оператора к функции F.

Отметим одно принципиальное обстоятельство: решение уравнения F(x1, …, xn, y) = 0 для любой вычислимой функции F возможно осуществить последовательным перебором значений y, однако такой способ решения не дает гарантии того, что перебор когда-нибудь завершится. Если это уравнение не имеет решения, перебор не завершится, и, следовательно, значение функции G не будет найдено. Функция G, таким образом, определена частично. Оказывается, что это обстоятельство действительно является принципиальным: ни один из мыслимых алгоритмических подходов к решению нашего уравнения не может дать гарантированного ответа на вопрос о том, является ли результат -операции всюду определенной функцией.   

Поэтому формализация понятия вычислимости конфликтует с понятием тотальной определенности. Выход один: формально определить класс частично-определенных функций, а затем объявить те из них, которые являются тотальными, вычислимыми.  

  1.  Частично-рекурсивные функции как формализация понятия вычислимых функций.

Функция называется частично-рекурсивной, если она определена с помощью конечного числа правил суперпозиции, примитивной рекурсии и -операции из функций, определенных правилом 0 (из базисных примитивно-рекурсивных функций).

Всюду определенные частичнорекурсивные функции называются общерекурсивными.

Понятие общерекурсивной функции и есть уточнение интуитивного понятия вычислимой функции.

Тезис Черча.  Все вычислимые функции общерекурсивны.

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

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

6. Толкование схемы вычисления частично-рекурсивной функции в терминах алгоритмического языка.

-оператор легко реализуется с помощью оператора повторения. Именно:

y := 0;

Пока F(x1, …, xn, y)  <>  0 выполнить y := s(y)  

Реализации других правил порождения частично-рекурсивных функций мы уже обсуждали. Таким образом, каждую частично-рекурсивную функцию можно представить в виде алгоритма, вычисляющего ее значение в императивном стиле. Принимая во внимание тезис Черча, можно говорить о том, что функциональный (декларативный) стиль описания алгоритма транслируется в императивный стиль описания и наоборот, императивный стиль описания алгоритма транслируется в декларативный (функциональный) стиль.     

В частности, оператор Пока U выполнять P интерпретируется как функция  Покавыполнить (U, P), которая, в свою очередь, описывается рекурсивно:

Покавыполнить ( F, P ) = НетОперации;

Покавыполнить ( T, P ) = (P; Покавыполнить ( U, P ));

С одной стороны, ЭВМ оказывается универсальным Исполнителем, т.е. Исполнителем, система команд которого позволяет моделировать любую другую систему команд. С другой стороны машинная ориентация языка ЭВМ крайне неудобна для описания алгоритмов «в человеческом изложении». Поэтому любая технология проектирования программы как алгоритма, предназначенного для исполнения на ЭВМ, должна опираться на приемы, характерные для человеческого мышления, оперировать привычными для человека понятиями из той предметной области, которой принадлежит задача.

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

Эта необходимость и привела к появлению языков программирования высокого уровня как языков записи алгоритмов, предназначенных для исполнения на ЭВМ.


Алгоритм

Вход

Выход

С1

С2

Сk-1

Ck

ход

Выход

Ввод

 Инициализация

 Оператор

 Условие

 Оператор

 Оператор

 Условие

фрагмент 1

фрагмент 2

 Оператор 1

 Оператор 2

Условие

True

 Условие

 Оператор

True

 Оператор

Оператор

 Условие

 Условие


 

А также другие работы, которые могут Вас заинтересовать

34247. Эколо́гия 11.75 KB
  социальная экологияэкология личности семьи социальной группы Методы исследований в экологии подразделяются на полевые экспериментальные и методы моделирования. Полевые методы представляют собой наблюдения за функционированием организмов в их естественной среде обитания. Экспериментальные методы включают в себя варьирование различных факторов влияющих на организмы по выработанной программе в стационарных лабораторных условиях. Методы моделирования позволяют прогнозировать развитие различных процессов взаимодействия живых систем между собой...
34248. Абиотические факторы 13.98 KB
  Биотические факторы это совокупность влияний одних организмов на другие в процессе их жизнедеятельности опыление растений затенение верхними ярусами нижних поедание одних особей другими. К биотическим факторам относятся и антропические роль которых год от году возрастает. АБИОТИЧЕСКИЕ БИОТИЧЕСКИЕ Физические климатические влага свет температура ветер давление течения продолжительность суток Влияние растений друг на друга и на другие организмы в биоценозе прямо или опосредованно Физические эдафические влагоемкость...
34249. МЕДИЦИНСКАЯ ЭКОЛОГИЯ 13.27 KB
  Устанавливается причино-следственные связи между состоянием среды и здровья, разрабатывает методы диагностики и профилактики, неблагоприятного влияния среды на человека
34250. Основные экологические проблемы современности 11.51 KB
  На планету вываливаются горы отбросов; человек провоцирует природные катастрофы.не подрывать природные ресурсы сдерживание роста населения; развитие новых промышленных технологий позволяющих избежать загрязнения поиск новых чистых источников энергии; увеличение производства продовольствия без роста посевных площадей.