Задача взята из книги А. Шеня "Программирование теоремы и задачи". Решения задачи в книге не приводится. Если кто знает принцип, поясните его хотя бы в общих словах, или приведите ссылку
на источник, буду благодарен. Просто долго мучаюсь с задачей и не могу найти правильного решения.

Задача. Дана программа вычисления значения некоторого многочлена Р(х ₁ , х ₂ , ..., x _n ), содержащая только комады присваивания. Их правые части - выражения, содержащие сложение, умножение, константы, переменные х ₁ , х ₂ , ..., x _n и ранее встречавшиеся(в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n частных производных, причем общее число арифмитических операций не более чем в С раз превосходит число арифметических операцийв исходной программе. Константа С не зависит от n.
[Указание: Можно считать что каждая комманда - сложение двух чисел, умножение двух чисел или умножение на константу. Использовать индукцию по числу команд, применяя индуктивное предположение к программе, получающейся отбрасывание первой команды.]

rmull, Спасибо.

rmullЯ решал без индукции.

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

Теперь построим графовую модель задачи. Граф будет DAG-ом, с помеченными дугами, из каждой вершины выходит от 0 до 2 дуг. n вершин будут соответствовать неизвестным x ₁ , ..., x _n . Рядом с ними можно подписать их векторы частных производных, каждый содержит все нули, кроме одной единицы. Ещё у нас будет K вершин, соответствующие командам, вернее, производным переменных, стоящих в левых частях команд.

Для команд вида
A = B + C
производная равна
A' = B' + C'
поэтому из вершины, соответствующей A', рисуем дуги в вершины B' и C' с метками = 1.

Для команд вида
A = B * C
производная равна
A' = B' * C + B * C'
из вершины A' рисуем дугу в B', помеченную C, и дугу в C', помеченную B.

Структура графа известна до выполнения алгоритма, а метки на дугах станут известны в ходе вычислений. Если мы найдём метки на дугах и будем вычислять для каждой вершины соответствующий вектор из n частных производных, то сложность получится O(N*(N+K)).

Но, если немного подумать, то можно заметить, что производную по x _i можно найти так: если мы рассмотрим все пути, ведущие из корня в вершину x _i , и для каждого перемножим метки на нём, и просуммируем всё, то получится искомая величина. И мы можем найти для каждой вершины такую сумму по всем путям из корня в данную вершину в сумме за O(N+K).

Понятно, что граф в явном виде в программе строить не обязательно. Он нужен просто для упрощения понимая сути алгоритма.

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

rmull, Большое спасибо, теперь стало намного понятнее.

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

Пусть у нас есть такая функция, считающая полином от трёх переменных:

Построим граф. Вершины обозначим x1p, x2p, x3p, ap, bp, cp, dp, ep.
Дуги:
ap -> x1p (вес = x2)
ap -> x2p (вес = x1)
bp -> x2p (вес = 1)
bp -> x3p (вес = 1)
cp -> ap (вес = b)
cp -> bp (вес = a)
dp -> bp (вес = 2)
ep -> cp (вес = 1)
ep -> dp (вес = 1)

Функция, считающая производные:

Можете вручную посчитать производные и сравнить найденные значения для различных x1, x2, x3.
Для каждой команды из первоначальной функции добавляется новая переменная и не более двух команд +=. Следовательно, объём нового кода линейно зависит от объёма старого.

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