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

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

   Пусть 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