Индуктивные функции
(по А.Г. Кушниренко)

Индуктивные функции

Пусть M -- некоторое множество. Функция f, аргументами которой являются последовательности элементов множества M, а значениями -- элементы некоторого множества N, называется индуктивной, если ее значение на последовательности ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ можно восстановить по ее значению на последовательности ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n-1]}}$ и по x[n], то есть если существует функция ${\hbox{\tt F}} : {\hbox{\tt N}}\times{\hbox{\tt M}} \to {\hbox{\tt N}}$ , для которой $\begin{displaymath} {\hbox{\tt f}}(\langle{\hbox{\tt x[1]}},\ldots,{\hbox{\tt x[... ...t x[1]}},\ldots,{\hbox{\tt x[n-1]}}\rangle),{\hbox{\tt x[n]}}).\end{displaymath}$

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

  k := 0; f := f0;
  {инвариант: f - значение функции на <x[1],...,x[k]>}
  while  k<>n do begin
  | k := k + 1;
  | f := F (f, x[k]);
  end;

Здесь f0 -- значение функции на пустой последовательности (последовательности длины 0). Если функция f определена только на непустых последовательностях, то первая строка заменяется на $\begin{displaymath} {\hbox{\tt k:=1; f:=f(<x[1]\gt);}}\end{displaymath}$

Если функция f не является индуктивной, полезно искать ее индуктивное расширение -- такую индуктивную функцию g, значения которой определяют значения f (это значит, что существует такая функция t, что $\begin{displaymath} {\hbox{\tt f}} (\langle{\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n... ...tt g}}(\langle{\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}\rangle))\end{displaymath}$ при всех $\langle{\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}\rangle$ ). Можно доказать, что среди всех индуктивных расширений существует минимальное расширение F (минимальность означает, что для любого индуктивного расширения g значения F определяются значениями g).

$\scriptstyle{\blacktriangleright}$ 1.3.1. Указать индуктивные расширения для следующих функций:

(а) среднее арифметическое последовательности вещественных чисел;

(б) число элементов последовательности целых чисел, равных ее максимальному элементу;

(в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке);

(г) максимальное число идущих подряд одинаковых элементов;

(д) максимальная длина монотонного (неубывающего или невозрастающего) участка из идущих подряд элементов в последовательности целых чисел;

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

Решение:

(а) $\langle$ сумма всех членов последовательности; длина $\rangle$ ;

(б) $\langle$ число элементов, равных максимальному; значение максимального $\rangle$ ;

(в) $\langle$ наибольший элемент последовательности; второй по величине элемент $\rangle$ ;

(г) $\langle$ максимальное число идущих подряд одинаковых элементов; число идущих подряд одинаковых элементов в конце последовательности; последний элемент последовательности $\rangle$ ;

(д) $\langle$ максимальная длина монотонного участка; максимальная длина неубывающего участка в конце последовательности; максимальная длина невозрастающего участка в конце последовательности; последний член последовательности $\rangle$ ;

(е) $\langle$ число групп из единиц, последний член $\rangle$ . $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.3.2 (Сообщил Д.В. Варсанофьев) Даны две последовательности целых чисел ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ и ${\hbox{\tt y[1]}}\ldots{\hbox{\tt y[k]}}$ .Выяснить, является ли вторая последовательность подпоследовательностью первой, то есть можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка ${\hbox{\tt n}}+{\hbox{\tt k}}$ .

Решение:

Вариант 1. Будем сводить задачу к задаче меньшего размера.

  n1:=n;
  k1:=k;
  {инвариант: искомый ответ <=> возможность из x[1]..x[n1]
     получить y[1]..y[k1] }
  while (n1 > 0) and (k1 > 0) do begin
  | if x[n1] = y[k1] then begin
  | | n1 := n1 - 1;
  | | k1 := k1 - 1;
  | end else begin
  | | n1 := n1 - 1;
  | end;
  end;
  {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1<>0
   (и n1 = 0), то ответ - нет}
  answer := (k1 = 0);

Мы использовали то, что если ${\hbox{\tt x[n1]}}={\hbox{\tt y[k1]}}$ и ${\hbox{\tt y[1]}}\ldots{\hbox{\tt y[k1]}}$ -- подпоследовательность ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n1]}}$ , то ${\hbox{\tt y[1]}}\ldots{\hbox{\tt y[k1-1]}}$ -- подпоследовательность ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n1-1]}}$ .

Вариант 2. Функция $\langle{\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n1]}}\rangle$ $\mapsto$ [максимальное k1, для которого ${\hbox{\tt y[1]}}\ldots{\hbox{\tt y[k1]}}$ есть подпоследовательность
${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n1]}}$ ] индуктивна. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.3.3. Даны две последовательности $\begin{displaymath} {\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}\quad\mbox{и}\quad {\hbox{\tt y[1]}}\ldots{\hbox{\tt y[k]}}\end{displaymath}$ целых чисел. Найти максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка ${\hbox{\tt n}}\cdot{\hbox{\tt k}}$ .

Решение. (сообщено М.Н. Вайнцвайгом, А.М. Диментманом). Обозначим через ${\hbox{\tt f}}({\hbox{\tt p}},{\hbox{\tt q}})$ максимальную длину общей подпоследовательности последовательностей $\begin{displaymath} {\hbox{\tt x[1]}}\ldots{\hbox{\tt x[p]}}\quad{и}\quad {\hbox{\tt y[1]}}\ldots{\hbox{\tt y[q]}}.\end{displaymath}$ Тогда $\begin{eqnarray*} {\hbox{\tt x[p]}}\ne{\hbox{\tt y[q]}} &\! \Rightarrow\!& {\hb... ...\tt 1}},{\hbox{\tt q}}\!-\!{\hbox{\tt 1}})\!+\!{\hbox{\tt 1}});$}\end{eqnarray*}$ (Поскольку ${\hbox{\tt f}}({\hbox{\tt p}}-{\hbox{\tt 1}},{\hbox{\tt q}}-{\hbox{\tt 1}})+{\h... ...}-{\hbox{\tt 1}}), {\hbox{\tt f}}({\hbox{\tt p}}-{\hbox{\tt 1}},{\hbox{\tt q}})$ ,во втором случае максимум трех чисел можно заменить на третье из них.) Поэтому можно заполнять таблицу значений функции f, имеющую размер ${\hbox{\tt n}}\cdot{\hbox{\tt k}}$ . Можно обойтись и памятью порядка k (или n), если индуктивно (по p) вычислять $\langle{\hbox{\tt f(p,0)}},\ldots,{\hbox{\tt f(p,k)}}\rangle$ (как функция от p этот набор индуктивен). $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.3.4. (из книги Д. Гриса) Дана последовательность целых чисел ${\hbox{\tt x[1]}},\ldots,{\hbox{\tt x[n]}}$ . Найти максимальную длину ее возрастающей подпоследовательности (число действий порядка ${\hbox{\tt n}}\,\log{\hbox{\tt n}}$ ).

Решение. Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входят помимо максимальной длины возрастающей подпоследовательности (обозначим ее k) также и числа ${\hbox{\tt u[1]}},\ldots,{\hbox{\tt u[k]}}$ , где ${\hbox{\tt u[i]}}$ -- минимальный из последних членов возрастающих подпоследовательностей длины i. Очевидно, ${\hbox{\tt u[1]}}\leqslant\ldots\leqslant{\hbox{\tt u[k]}}$ . При добавлении нового члена в x значения u и k корректируются.

     n1 := 1; k := 1; u[1] := x[1];
     {инвариант: k и u соответствуют данному выше описанию}
     while n1 <> n do begin
     | n1 := n1 + 1;
     | ...
     | {i - наибольшее из тех чисел отрезка 1..k, для кото-
     |   рых u[i] < x[n1]; если таких нет, то i=0 }
     | if i = k then begin
     | | k := k + 1;
     | | u[k+1] := x[n1];
     | end else begin {i < k, u[i] < x[n1] <= u[i+1] }
     | | u[i+1] := x[n1];
     | end;
     end;

Фрагмент ... использует идею двоичного поиска; в инварианте условно полагаем u[0] равным минус бесконечности, а u[k+1] -- плюс бесконечности. Наша цель: ${\hbox{\tt u[i]}} < {\hbox{\tt x[n1]}}\leqslant{\hbox{\tt u[i+1]}}$ .

  i:=0; j:=k+1;
  {u[i] < x[n1] <= u[j], j > i}
  while (j - i) <> 1 do begin
  | s := i + (j-i) div 2;    {i < s < j}
  | if x[n1] <= u[s] then begin
  | | j := s;
  | end else begin {u[s] < x[n1]}
  | | i := s;
  | end;
  end;
  {u[i] < x[n1] <= u[j], j-i = 1}`

Замечание. Более простое (но не минимальное) индуктивное расширение получится, если для каждого i хранить максимальную длину возрастающей подпоследовательности, оканчивающейся на x[i]. Это расширение приводит к алгоритму с числом действий порядка ${\hbox{\tt n}}^2$ .

$\scriptstyle{\blacktriangleright}$ 1.3.5. Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последовательность? $\scriptstyle\blacktriangleleft$

pvv
1/8/1999

Индуктивные функции (по А.Г. Кушниренко)

Индуктивные функции
(по А.Г. Кушниренко)