Базисные схемы обработки информации

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

В качестве дополнительного источника информации к данной главе можно порекомендовать книги [4] и [9].

Все задачи на написание программ можно разделить на следующие три группы.

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

2. Задачи на "программирование в малом". Большая часть задач, которые уже были нами рассмотрены, относятся именно к этой категории. Кроме совсем простых к ней относятся и более сложные, при решении которых оправдано применение различных методов разработки программ типа проектирования сверху вниз.

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

3. Большие проекты. Почти все практические задачи относятся именно к этому классу. Для них даже аккуратная формулировка постановки задачи является проблемой. Решение подобных задач требует применения специальных методов, большая часть из которых выходит за рамки нашего курса.

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

Предложенное деление задач на группы является достаточно условным и некоторые из них могут быть отнесены как ко второй, так и к третьей. В данной главе мы сосредоточимся на методах решения наиболее простых задач из второй категории, программная реализация которых не превосходит 10-20 строк текста. Все подобные задачи можно рассматривать, как задачи на обработку информации, что и поясняет название классификации методов их решения — схемы обработки информации, графическая иллюстрация взаимосвязи которых приведена на рис. 7.1.

Рекурсия и итерация

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

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

Итерация — способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.

Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

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

1) всегда ли и почему программа заканчивает работу?

2) почему после окончания работы программы будет получен требуемый результат?

Рассмотрим следующую задачу.

Задача 7.1. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log b)$$, таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land b \geqslant 0)$$, $$R=(z=ab)$$. Числа $$a$$ и $$b$$ в программе изменять нельзя.

Решение Фиксировав $$a$$, рассмотрим функцию $$mul_a(b)\colon \mathbb{Z}_M \rightarrow \mathbb{Z}_M$$, задаваемую следующим рекурсивным определением:

$$mul_a(0)=0$$,

$$mul_a(b) = 2\cdot mul_a(b/2)$$, когда $$b$$ положительно и четно,

$$mul_a(b) = mul_a(b-1) + a$$, когда $$b$$ положительно и нечетно.

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

Текст программы

public class MulR {
    static int mul(int x, int y) {
        // Xterm.print("  Вызов mul(" + x + "," + y + ")\n");
        return (y == 0) ? 0 :
            ((y1) == 0) ? mul(x,y >>> 1) << 1 : mul(x,y-1) + x;
    }	
    public static void main(String[] args) throws Exception {    
        int a = Xterm.inputInt("a -> ");
        int b = Xterm.inputInt("b -> ");
        Xterm.println("a * b = " + mul(a,b));
    }
}

Эта программа заканчивает работу, так как каждый следующий рекурсивный вызов уменьшает значение аргумента $$y$$ функции $$mul_a$$ не менее, чем на единицу (нечетное число уменьшается ровно на один, а четное — делится пополам, что при $$y=2$$ приводит к уменьшению на один, а при больших значениях $$y$$ — к большему уменьшению). В результате конечного числа таких операций $$y$$ гарантированно станет нулем, что приведет к завершению цепочки рекурсивных вызовов.

Обратите внимание на тот факт, что хотя приведенные выше рассуждения не являются справедливыми при отрицательных значениях числа $$b$$, это не означает неправильности программы, так как согласно спецификации ее поведение при $$b<0$$ может быть произвольным.

Доказательство правильности получаемого результата проведем с помощью метода математической индукции, показав, что при фиксированном $$a$$ и $$0\leqslant b\leqslant n$$ является тавтологией предикат $$P(b) =$$ ( данная программа печатает $$a\cdot b$$ ).

Справедливость базы индукции $$P(0)$$ следует непосредственно из текста программы, а индуктивный переход $$P(n) \Rightarrow P(n+1)$$ осуществляется следующим образом. Если предположить, что программа правильна при $$b=n$$, то $$mul_a(n) = a\cdot n$$. Рассмотрим далее два возможных случая.

Пусть сначала число $$y=n+1$$ — четно. Тогда результатом работы программы будет$$mul_a(n+1) = 2\cdot mul_a((n+1)/2) = 2\cdot a \cdot ((n+1)/2) = a\cdot (n+1)$$ . Первое равенство здесь следует из текста программы, а второе — из предположения индукции. Если число $$y=n+1$$ является нечетным, то $$mul_a(n+1) = mul_a(n) + a = a\cdot n + a = a\cdot (n+1)$$. Обоснование этих равенств проводится аналогично.

Таким образом, нами проверена истинность индуктивного перехода $$P(n) \Rightarrow P(n+1)$$, что и завершает доказательство.

Для того чтобы увидеть цепочку рекурсивных вызовов функции $$mul_a$$ достаточно убрать символы комментария из первой строки этого метода. Это позволяет понять, почему программа имеет сложность порядка $$\Theta(\log b)$$. Докажем аккуратно, что глубина рекурсии (количество рекурсивных вызовов) для нашей программы не превосходит $$2\cdot [\log b] + 1$$ (здесь $$[x]$$ — целая часть от $$x$$ ).

Каждый рекурсивный вызов функции $$mul_a$$ уменьшает значение аргумента $$y$$ либо на единицу, либо вдвое. Два последовательных вызова этой функции всегда приводят к уменьшению величины $$y$$ более, чем в два раза, поэтому $$y$$ обратится в нуль после не более, чем после $$2\cdot [\log b] +1$$ рекурсивных вызовов. Обратите внимание, что мы не учитываем в наших рассуждениях самый первый, нерекурсивный вызов функции $$mul_a$$.

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

Рассмотрим еще одну задачу.

Задача 7.2. Напишите программу, печатающую значение многочлена степени $$n\geqslant0$$ в заданной точке $$x_0$$. Коэффициенты многочлена хранятся в массиве $$a$$ в порядке убывания степеней и являются целыми числами, также как и значение $$x_0$$. Величины $$n$$, $$x_0$$ и элементы массива $$a$$ изменять в программе нельзя.

Решение Заметим, что$$P_n(x)=a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n = x\cdot P_{n-1}(x) + a_n$$ , где $$P_{n-1}(x)=a_0x^{n-1}+a_1x^{n-2}+\ldots+a_{n-1}$$. Воспользовавшись этим, определим функцию $$f\colon \mathbb{Z}_M \rightarrow \mathbb{Z}_M$$ следующим образом:

$$f(0) = a_0$$,

$$f(n) = x_0\cdot f(n-1) + a_n$$, при $$n>0$$.

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

Текст программы

public class PolVal {
    static int a[], x0;
    static int p(int k) {
        return (k == 0) ? a[0] : x0 * p(k-1) + a[k];
    }	
    public static void main(String[] args) throws Exception {    
        int n = Xterm.inputInt("n -> ");
        a = new int[n+1];  
        for (int i=0; i<=n; i++)
            a[i] = Xterm.inputInt("a[" + i + "] -> ");
        x0 = Xterm.inputInt("x0 -> ");
        Xterm.println("P(" + x0 + ") = " + p(n));
    }
}

Завершение программы за конечное число шагов следует из уменьшения на единицу при каждом рекурсивном вызове аргумента функции $$p$$, а ее правильность получается из доказательства по индукции следующего утверждения $$R(n) =$$ ( программа печатает значение $$P(x_0)$$ многочлена $$P_n(x)=a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n$$ степени $$n$$ в точке $$x_0$$ ).

База индукции проверяется непосредственно, ибо при нулевом значении аргумента функция $$p(k)$$ возвращает $$a[0]$$, что совпадает с $$P_0(x_0)$$. Индуктивный переход удается осуществить благодаря формуле, приведенной в начале решения данной задачи, которая позволяет выразить значение $$P_n(x_0)$$ через $$P_{n-1}(x_0)$$.

Рекурсивное решение задачи зачастую является менее эффективным, чем эквивалентное ему по другим параметрам итерационное решение. Обычным способом программной реализации итерации является цикл, и поэтому мы будем считать, что спецификация задачи на итерацию имеет вид $$\{Q\}\ "S0;while(e)S;" \ \{R\}$$.

Рассмотрим $$X$$ — множество значений всех программных переменных (прямое произведение множеств значений отдельных переменных), его подмножества $$X_Q \subset X$$ и $$X_R \subset X$$, определяемые предикатами $$Q$$ и $$R$$, и преобразование $$T\colon X \rightarrow X$$, соответствующее однократному выполнению тела цикла S. Тогда построение условия продолжения цикла e и его тела S сводится к нахождению предиката $$e$$ и преобразования $$T$$ таких, что $$\forall x \in X_Q\ \exists k \geqslant 0\ T^k(x) \in X_R$$.

Именно этот факт является основным результатом, вытекающим из определения слабейшего предусловия $$wp$$ для оператора цикла (см.лекцию 6). Геометрическая интерпретация математической модели итерации, сводящейся к многократному применению преобразования $$T$$, приведена на рис. 7.2.

К сожалению эта математическая модель итерации является слишком общей и трудно применимой на практике, так как она не дает конкретных рекомендаций по нахождению условия продолжения цикла e и тела цикла S по заданным $$Q$$ и $$R$$. К рассмотрению более частных и более полезных схем мы сейчас и перейдем.

Инвариант и ограничивающая функция цикла

Основная идея метода проектирования цикла при помощи инварианта — выражение взаимосвязи между меняющимися в теле цикла объектами в виде неизменного условия. Польза инварианта состоит в том, что такое описание взаимосвязи легко понимаемо и позволяет, зная, как меняются одни объекты, выводить, как должны изменяться другие. Тем самым инвариант помогает сконструировать команды S0 и S.

Определение 7.1. Инвариант цикла $$I\colon X \rightarrow \{T,F\}$$ — предикат, который истинен перед выполнением цикла и после каждой его итерации.

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

Для построения корректного условия продолжения цикла e используется ограничивающая функция $$h$$. При каждом шаге цикла значение $$h(x)$$ должно уменьшаться по крайней мере на единицу и оставаться положительным до завершения цикла. Ограничивающая функция позволяет гарантировать завершение цикла.

Определение 7.2. Ограничивающая функция $$h\colon X \rightarrow \mathbb{Z}$$ — неотрицательная функция, являющаяся верхней границей числа оставшихся итераций цикла.

Схема проектирования цикла при помощи инварианта.

На первом этапе выполняются простые присваивания S0, делающие инвариант $$I$$ истинным, а в качестве условия продолжения цикла e берется предикат $$h>0$$. На втором этапе конструируется тело цикла S, реализующее преобразование $$T$$ : сначала обеспечивается уменьшение ограничивающей функции $$h$$ , а затем — сохранение инварианта $$I$$.

Геометрическая интерпретация данной схемы приведена на рис. 7.3, где через $$X_{S0}$$ обозначено множество, получающееся из $$X_Q$$ с помощью совокупности присваиваний S0.

Рассмотрим применение этой схемы для решения следующей задачи.

Задача 7.3. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log b)$$, таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land b \geqslant 0)$$, $$R=(z=ab)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается, следует использовать инвариант $$I = (y \geqslant 0 \land z + xy = ab)$$ и ограничивающую функция $$h = y$$.

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

Начальные присваивания должны сделать истинным инвариант (в случае истинности предусловия) и при этом быть максимально простыми и легко находимыми. В данном случае достаточно быстро можно обнаружить, что хорошим кандидатом на роль S0 является следующая совокупность присваиваний "x=a;y=b;z=0;".

Условие продолжения цикла e нам уже по существу дано, так как очередная итерация цикла должна происходить только при $$h>0$$. По этой причине логично предположить, что наша программа должна содержать оператор "while(y>0)S;", тело которого S пока неизвестно.

Мы обязаны обеспечить завершение цикла, следовательно величина $$y$$ должна уменьшаться на каждой его итерации. Уменьшение $$y$$ каждый раз на единицу заведомо не позволит получить достаточно эффективную программу. По этой причине необходимо уменьшать величину $$y$$ более быстро. Хорошей мыслью является попытка делить величину $$y$$ пополам тогда, когда это можно (при четных $$y$$ ). Легко оценить, что если бы деление пополам происходило на каждом шаге цикла, то количество его итераций было бы примерно равно $$\log b$$. Это вполне согласуется с тем, что требуется в решаемой задаче.

Так как после итерации цикла инвариант должен остаться истинным, то уже зная, как меняется $$y$$, вычисляем, как следует изменять $$z$$ (ибо по условию задачи мы не можем изменять $$a$$ и $$b$$ ). В результате находим (либо в уме, либо формально вычисляя $$wp$$ ), что при четных $$y$$ величину $$x$$ следует удваивать, а при нечетных — необходимо увеличивать значение переменной $$z$$ на $$x$$.

Программа написана!

Текст программы

public class MulI {
    public static void main(String[] args) throws Exception {    
        int a = Xterm.inputInt("a -> ");
        int b = Xterm.inputInt("b -> ");
        int x = a, y = b, z = 0;
        while (y > 0) { 
            if ((y1) == 0) {
                y >>>= 1; x +=  x;
            } else {
                y  -=  1; z +=  x;
            }
        }
        Xterm.println("a * b = " + z);
    }
}

Схема вычисления инвариантной функции

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

Определение 7.3. Пусть $$X$$ — некоторое множество, $$F\colon X\rightarrow Y$$ — заданная на нем функция, а $$P$$ — предикат такой, что $$P(x) = (F(x)$$ легко вычислить ). Обозначим через $$X_P$$ то подмножество множества $$X$$, где $$P(x)=T$$. Если существует преобразование $$T\colon X\setminus X_P\rightarrow X$$ такое, что $$\forall x\in X\setminus X_P\ F(T(x))=F(x)$$, то функция $$F$$ называется $$T$$ -инвариантной или просто инвариантной функцией.

Простейшим примером инвариантной функции является хорошо известная еще из средней школы функция $$f\colon \mathbb{R} \rightarrow \mathbb{R}$$, $$f(x)=\sin x$$. Она является $$T$$ -инвариантной относительно преобразования $$T\colon \mathbb{R} \rightarrow \mathbb{R}$$, $$T(x) = x+2\pi$$.

Наибольший общий делитель двух целых чисел (greatest common divisor, $$gcd(x,y)$$ или просто $$\mbox{НОД(x,y)}$$ ) инвариантен относительно преобразования $$T\colon\mathbb{Z}\times \mathbb{Z} \rightarrow \mathbb{Z}\times \mathbb{Z}$$, задаваемого формулой$$T(x,y)=\begin{cases} (x-y,y), \text{если $x\geqslant y$},\\ (x,y-x), \text{иначе}. \end{cases}$$

Доказательство этого факта, основанное на основной теореме арифметики о разложении числа на простые множители, является достаточно простым и оставляется читателю. Обратите только внимание на то, что функция $$gcd(x,y)$$ не определена в точке $$(0,0)$$.

Для вычисления значения $$T$$ -инвариантной функции $$F$$ в точке $$x_0\in X$$ применяется следующая схема.

Схема вычисления инвариантной функции.

Многократно выполняется преобразование $$T$$ , дающее последовательность точек $$x_0, x_1, \ldots$$ Если очередная точка $$x_n$$ попадaет в подмножество $$X_P$$ , то итерации завершаются. По определению инвариантной функции $$F(x_n)$$ легко вычисляется и совпадает с искомым $$F(x_0)$$.

Рисунок 7.4 содержит графическую иллюстрацию этой схемы.

Схема вычисления инвариантной функции значительно облегчает проектирование программы "S0;while(e)S;S1;", так как нам изначально известны инвариант $$I = (F(x) = F(x_0))$$ и условие продолжения цикла $$e(x) = !P(x)$$. Тело цикла S конструируется, как программная реализация известного преобразования $$T$$, а написание S1, вычисляющей $$F(x_n)$$, не может представлять трудностей в силу самого определения инвариантной функции.

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

Задача 7.4. Напишите программу, находящую наибольший общий делитель $$gcd(x,y)$$ двух целых неотрицательных чисел $$x$$ и $$y$$, не равных одновременно нулю. Воспользуйтесь следующими свойствами наибольшего общего делителя (не забудьте научиться доказывать все эти свойства):

Решение Если через $$\mathbb{Z}_M^+$$ обозначить множество всех неотрицательных целых чисел, представимых в ЭВМ, то $$X = \mathbb{Z}_M^+\times \mathbb{Z}_M^+ \setminus \{(0,0)\}$$, $$Y=\mathbb{Z}_M^+$$, $$X_P = \{(x,y)\in X\ x=0 \lor y=0\}$$, $$F(x,y) = gcd(x,y)$$. В качестве преобразования $$T\colon X\setminus X_P \rightarrow X$$ можно взять$$T(x,y)=\begin{cases} (x-y,y), \text{если $x\geqslant y$},\\ (x,y-x), \text{иначе}. \end{cases}$$

Таким образом, нам известны инвариант $$I=(gcd(x,y)=gcd(x_0,y_0))$$ и условие продолжения $$e=(x\ne 0\land y\ne 0)$$. Начальные присваивания S0 в данном случае не нужны, тело цикла S пишется по определению $$T$$, a программа S1, вычисляющая $$gcd(x,y)$$ для $$(x,y)\in X_P$$, реализуется с помощью справедливой для этих значений аргумента формулы $$gcd(x,y)=x+y$$.

Текст программы

public class Gcd {
    public static void main(String[] args) throws Exception {
        int x = Xterm.inputInt("x -> ");
        int y = Xterm.inputInt("y -> ");
        Xterm.print("gcd(" + x + "," + y + ") =");
        while ( (x != 0)  (y != 0) ) {
            if (x >= y) x -= y;
            else        y -= x;
        } 
        Xterm.println(" " + (x+y));
    }
}

Обратите внимание на тот факт, что в построенной программе не понадобилось наличие переменной, соответствующей значению инвариантной функции $$gcd(x,y)$$.

Рассмотрим еще одну задачу.

Задача 7.5. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log b)$$, таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land b \geqslant 0)$$, $$R1=(z=ab)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается. Воспользуйтесь тем, что функция $$F\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M$$, $$F(x,y,z) = z+xy$$ является инвариантной относительно преобразования $$T\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M$$, задаваемого формулой$$T(x,y,z)=\begin{cases} (2x,y/2,z), \text{если $y$ — четно},\\ (x,y-1,z+x), \text{иначе}. \end{cases}$$

В данном случае $$X=\mathbb{Z}_M\times\mathbb{Z}_M^+\times\mathbb{Z}_M$$, $$Y=\mathbb{Z}_M$$, $$P=(y=0)$$, $$X_P = \{(x,y,z)\in X \colon y=0\}$$. Функция $$F$$ и преобразование $$T$$ заданы в условии задачи.

Таким образом, нам известны инвариант $$I=(F(x,y,z)=F(a,b,0))$$ и условие продолжения $$e=(y\ne 0)$$. Начальные присваивания S0 очевидны ( "x=a; y=b; z=0;" ), тело цикла S пишется по определению $$T$$, a программа S1, вычисляющая $$F(x,y,z)$$ для $$(x,y,z)\in X_P$$, в данном случае вырождается в пустой оператор ";", так как для этих значений аргумента $$F(x,y,z)=z$$. В результате получаем уже знакомую нам программу.

Текст программы

public class MulInv {
    public static void main(String[] args) throws Exception {
        int a = Xterm.inputInt("a -> ");
        int b = Xterm.inputInt("b -> ");
        int x = a, y = b, z = 0;
        while (y > 0) {
            if ((y1) == 0) {
                y >>>= 1; x +=  x;
            } else {
                y  -=  1; z +=  x;
            }
        }
        Xterm.println("a * b = " + z);
    }
}

Функции на пространстве последовательностей

Еще одной ситуацией, в которой общая схема итерации значительно упрощается, является задача вычисления индуктивных функций. Такие функции определены на последовательностях $$X^*$$ элементов из некоторого алфавита $$X$$. Напомним важнейшие из определений лекцию 3.

Алфавит $$X$$ — произвольное непустое множество.

Символом алфавита $$X$$ называют любой его элемент, а цепочкой над алфавитом — произвольную последовательность символов $$\omega$$. Цепочки часто называют также словами, фразами и предложениями. Пустая цепочка обозначается специальным символом $$\varepsilon$$, а множество всех цепочек над алфавитом $$X$$ принято обозначать $$X^*$$.

Длиной $$|\omega|$$ цепочки $$\omega \in X^*$$ называется количество входящих в нее символов. Множество всех цепочек длины не менее $$k$$ обозначают через $$X^*_k$$. Справедлива следующая последовательность включений: $$X^* \supset X^*_1 \supset X^*_2 \supset X^*_3 \supset \ldots$$

Операция $$\circ\colon X^*\times X^* \rightarrow X^*$$ конкатенации (или сцепления ) двух цепочек определена следующем образом. Пусть $$\omega_1 = a_1 a_2 \ldots a_n$$, $$\omega_2 = b_1 b_2 \ldots b_m$$, тогда $$\omega_1 \circ w_2 = a_1 a_2 \ldots a_n b_1 b_2 \ldots b_m$$.

Теперь можно дать определение индуктивной функции.

Определение 7.4. Функция $$f\colon X^* \rightarrow Y$$ называется индуктивной, если $$f(\omega\circ x)$$ можно вычислить, зная $$f(\omega)$$ и $$x$$, т.е. если $$\exists G\colon Y \times X\rightarrow Y$$ такое, что $$\forall \omega\in X^* \ \forall x\in X\ f(\omega\circ x) = G(f(\omega),x)$$.

Одним из простейших примеров индуктивной функции является функция длина цепочки $$|\omega|\colon X^* \rightarrow \mathbb{Z^+}$$. Она индуктивна, так как для нее существует функция $$G\colon \mathbb{Z^+\times X \rightarrow \mathbb{Z^+}$$, определенная формулой $$G(y,x) = y+1$$, удовлетворяющая предыдущему определению.

Для вычисления значения $$f(\omega)$$ индуктивной функции $$f$$ на цепочке $$\omega=a_1a_2\ldots a_n$$ применяется следующая схема.

Схема вычисления индуктивной функции.

Рассматривается последовательность цепочек $$\varepsilon$$, $$a_1$$, $$a_1a_2$$, $$\ldots$$, $$a_1a_2\ldots a_n=\omega$$. Сначала вычисляется значение $$f(\varepsilon)$$ функции $$f$$ на пустой цепочке $$\varepsilon$$, а затем используется отображение $$G$$ , позволяющее найти значение функции $$f$$ на удлиненной цепочке, что дает возможность последовательно определить все требуемые величины вплоть до $$f(\omega)$$.

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

Схема вычисления индуктивной функции напоминает метод доказательства по индукции. Аналогом базы индукции является вычисление $$f(\varepsilon)$$, а индуктивному переходу соответствует вычисление функции $$f(\omega\circ x)$$ на удлиненной цепочке $$\omega \circ x$$ с использованием вычисленного на предыдущем шаге значения $$f(\omega)$$.

Схема вычисления индуктивной функции позволяет легко построить программу вида "S0;while(e)S;", получающую на каждой следующей итерации цикла очередной элемент $$a_i$$ цепочки (последовательности) $$\omega=a_1a_2\ldots a_n$$, которая находит значение $$f(\omega)$$. Инвариантом данного цикла является $$I=(0\leqslant i \leqslant n\land f=f(a_1a_2\ldots a_i))$$, условием продолжения — $$e=(i \leqslant n)$$, S0 должно вычислять $$f(\varepsilon)$$, а S — быть программной реализацией функции $$G$$.

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

Задача 7.6. Напишите программу, определяющую значение в целой точке $$t$$ многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

Заметим, что$$P_n(t)=a_0t^n+a_1t^{n-1}+\ldots+a_{n-1}t+a_n = t\cdot P_{n-1}(t) + a_n$$ , где $$P_{n-1}(t)=a_0t^{n-1}+a_1t^{n-2}+\ldots+a_{n-1}$$. Поэтому функция $$f\colon (\mathbb{Z}_M)^* \rightarrow \mathbb{Z}_M$$, определенная, как $$f(\omega) = f(a_0a_1\ldots a_n) = P_n(t)$$, удовлетворяет соотношению $$f(\omega\circ x) = t\cdot f(\omega) + x$$, что доказывает ее индуктивность. Отображение $$G\colon\mathbb{Z}_M\times \mathbb{Z}_M\rightarrow\mathbb{Z}_M$$ действует по формуле $$G(y,x) = ty+x$$, а $$f(\varepsilon)=0$$, что приводит к следующей программе.

Текст программы

public class Pol {
    public static void main(String[] args) throws Exception {
        int t = Xterm.inputInt("t -> ");
        int y = 0;
        try {
            while (true) {
                int x = Xterm.inputInt("x -> ");
                y = t*y + x;
            }
        } catch (Exception e) {
            Xterm.println("\ny = " + y);
        }	    
    }
}

Этот эффективный метод вычисления значения многочлена в точке носит имя схемы Горнера.

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

Задачи для самостоятельного решения

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

При использовании схемы вычисления инвариантной функции необходимо указать множества $$X$$, $$Y$$ и $$X_P$$, функцию $$F$$ и преобразование $$T$$ (см. определение инвариантной функции) и объяснить программную реализацию преобразования $$T$$.

Задача 7.7. Напишите рекурсивную программу, печатающую значение производной многочлена степени $$n\geqslant0$$ в заданной точке $$x_0$$. Коэффициенты многочлена хранятся в массиве $$a$$ в порядке убывания степеней и являются целыми числами, так же как и значение $$x_0$$. Величины $$n$$, $$x_0$$ и элементы массива $$a$$ изменять в программе нельзя.

Указание Пусть $$P_n(x)=a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n$$. Продифференцируем по $$x$$ равенство $$P_n(x) = x \cdot P_{n-1}(x) + a_n$$ и подставим затем $$x=x_0$$. Мы получим следующие соотношения:

$$P'_0(x_0) = 0$$,

$$P'_n(x_0) = x_0 \cdot P'_{n-1}(x_0) + P_{n-1}(x_0)$$.

Воспользовавшись ими и формулами

$$P_0(x_0) = a_0$$,

$$P_n(x_0) = x_0 \cdot P_{n-1}(x_0) + a_n$$,

легко определить рекурсивную функцию неотрицательного целого аргумента $$g\colon \mathbb{Z}_M \rightarrow \mathbb{Z}_M \times \mathbb{Z}_M$$, $$g(n) = (P'_n(x_0), P_n(x_0))$$ для вычисления которой и пишется программа.

Задача 7.8. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land a > 0 \land b \geqslant 0)$$, $$R=(z=a^b)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается, следует использовать инвариант $$I = (y \geqslant 0 \land z \cdot x^y = a^b)$$ и ограничивающую функцию $$h = y$$.

Задача 7.9. Напишите программу, находящую наибольший общий делитель $$gcd(x,y)$$ двух целых неотрицательных чисел $$x$$ и $$y$$, не равных одновременно нулю. Воспользуйтесь следующим свойством наибольшего общего делителя (докажите его!):$$gcd(x,y)=\begin{cases} gcd(x\%y,y), \text{если $x\geqslant y$},\\ gcd(x,y\%x), \text{иначе}. \end{cases}$$ Здесь операция $$x\%y$$ позволяет найти остаток от деления $$x$$ на $$y$$.

Задача 7.10. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land a > 0 \land b \geqslant 0)$$, $$R1=(z=a^b)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается. Воспользуйтесь тем, что функция $$F\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M$$, $$F(x,y,z) = zx^y$$ является инвариантной относительно преобразования $$T\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M$$, задаваемого формулой $$T(x,y,z)=(x,y-1,xz)$$.

Задача 7.11. Напишите программу, находящую наибольший общий делитель $$gcd(x,y)$$ двух целых неотрицательных чисел $$x$$ и $$y$$, не равных одновременно нулю. Программа должна иметь временную сложность порядка $$\Theta(\log \max(x,y))$$ и не использовать операций деления и нахождения остатка от деления (допустимо деление пополам, реализуемое с помощью операции сдвига). Воспользуйтесь следующими свойствами наибольшего общего делителя (докажите их!):

$$gcd(2x,2y)=2gcd(x,y)$$, $$\qquad gcd(2x, 2y+1)=gcd(x,2y+1)$$.

Указание Воспользуйтесь инвариантностью функции $$F(x,y,z)=z\cdot gcd(x,y)$$ относительно следующего преобразования $$T$$:$$T(x,y,z)=\begin{cases} (x/2,y/2,2z), \text{если оба числа $x$ и $y$ — четны},\\ (x/2,y,z), \text{если $x$ — четно, а $y$ — нечетно},\\ (x,y/2,z), \text{если $x$ — нeчетно, а $y$ — четно},\\ (x-y,y,z), \text{если $x$ и $y$ — нечетны и $x\geqslant y$},\\ (x,y-x,z), \text{если $x$ и $y$ — нечетны и $x < y$}. \end{cases}$$ Не забудьте доказать $$T$$,-инвариантность функции $$F$$.