    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 113 

    8. Индуктивное вычисление функций на пространстве последовательностей 

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

    114 ГЛ.  1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    Математика. Обозначения. Пусть X — произвольный алфавит, т. е. какое-то 
конечное или бесконечное множество, например множество букв русского язмка или 
множество действительных чисел; 
    Q (X)   или просто Q -™ пространство всех конечных  последовательностей 
над X, т. е. Q = {xjX2 
    ;2+ .XjSX VieL.nJ; 
    Д — пустая последовательность, не содержащая ни одного элемента (Д е и); 
fik (X), или просто Qk, — пространство конечных последовательностей длины не 
менее k, т. е. ?2k = {xiXj ... х„: n ^ k, Xj e X); таким образом, 
    Q = QO=>?21 гэ Q2=>... 
    *: Q*X~»-Q— операция добавления (дописывания) элемента в конец 
последовательности, т. е. х^ ... х„*х = XiXj ... хпх, Д*х = х и т. п.; 
операция * естественно сужается на Qk Vk. 
    Кроме того, будем пользоваться стандартными математическими обозначениями: 
    Ым — тождественное отображение произвольного множества М в себя: IdM (х) = 
х Vx е М, 
    N — множество натуральных чисел, 
    Z+ — множество неотрицательных целых чисел, 
    Z — множество целых чисел, 
    R+ — множество неотрицательных действительных чисел, • 
    R — множество действительных чисел. 
    Через N, Z+ и т. д. будем обозначать множества, которые содержат кроме 
обычных еще и два идеальных элемента: +оо и —оо. 

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

    Определение. Функция F:jQ)-»-Y называется индуктивной, если Р(ш*х) можно 
вычислить, зная Т51 (и) и х, т. е. если 
    3G: Y>X->Y:Vo>?=Q, х«=Х F (со * х) = G (F (<о), х).	(1) 
    Примером индуктивной функции может служить функция F — [= «число элементов 
последовательности», F: Q -*• Z+. Действительно, Vco е Q, зс «= X F (со * х) = 
F (со) + 1, т. е. 3<3: Z+ « X -> Z+, а именно G(y, х) = у + 1, удовлетворяющее (1). 
    Индуктивные функции удобно вычислять. Если известно значение F0 функции F 
на пустой последовательности о>о = Д, то значение Fn функции F на 
последовательности w,, = XjXj ,.. хп можно найти следующим образом: 
    co1=coo*Xi,         FI = F (cOi) = G (F0, x,), eo2 = «>! * x2,        F2 = 
F (0)2) = G (Fb x2), 
    (2) 
    :»n-l*xn'    Fa = F(wn)=G(Fn-l'xn). 
    ll' I ( 


    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИИ 115 

    Если математическая последовательность о е ?2 является состоянием 
программистской последовательности Р элементов типа X, то соответствующая (2) 
программа запишется в виде: 

    Р. встать в начало   ' 
    F:=FO 
    цикл Vx е непрочитанной части Р  выполнять 
    . F := G (F, x) 
    конец цикла 
    (2') 

    Заметьте, что индексы в математическом описании (2) схемы вычисления F, т. 
е. значки х, и FI, относятся к этапам вычислений и обозначают состояния 
объектов х и F в (2') в различные моменты времени. При программной реализации 
эти индексы исчезают. 
    Легко проследить аналогию между схемами (2) — (2') и методом 
математической индукции. Роль базы индукции играет начальное значение функции 
F0, а роль шага индукции — шаг вычислений, т. е. G. Именно поэтому 
удовлетворяющие (1) функции называются индуктивными. 
    Определение. Действием алфавита X на множестве Y называется правило, 
сопоставляющее каждому символу х е X отображение Y-*-Y, т. е. отображение G: Y*X->-Y. 
    Вместо G (у, х) мы будем часто писать у ° х, подчеркивая аналогию с 
операцией *—действием алфавита X на И. 
    Таким образом, определение индуктивной функции можно переформулировать 
так: функция F: Q->-Y называется индуктивной, сел» существует действие °: 
Y*X-»-Y такое, что диаграмма 
    Q*X F*IdX     I 
    Y*X 
    a 
    i
    Y 
    коммутативна, т. е. Vco e Q, x е X F (<o » x) = F (со) ° х.. Допуская 
вольность речи, можно сказать, что F индуктивна, если она является 
гомоморфизмом fl-)-Y, согласованным с действием X. 
    Замечание. В этом определении требуется существование какого-нибудь 
действия. Однако если F индуктивна, то действие X на Р(й) определено 
однозначно, а на Y\F(Q) оно не существенно. 
    Утверждение (критерий индуктивности). F индуктивна -о 
    Va, b е Q: F (a) = F (b), Vx е X выполнено F (a * х) = F (b * х) 
    т. е. F индуктивна тогда и только тогда, когда из равенства значений F на 
последовательностях а и b следует равенство и на любых «одинаково удлиненных» 
последовательностях а*х и Ь*х. 

    116 ГЛ.  I. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    Доказательство. То, что это условие является необходимым (=4>), очевидно 
следует прямо из определения индуктивной функции. Докажем достаточность (-*=). 
Для этого определим действие X на F (2) формулой у о х = =F(a* х), где а — 
любой элемент множества F~J (у). Это определение корректно, так как если Ь — 
другой элемент множества F~' (у), то F(a) = F(b) и, значит, F(a« x) = F (b» 
х). Для у е Y\F (Q) определим действие X как-нибудь, например формулой у о х=у 
Vxs X. Очевидно, что для так определенного действия о ум ^ &, х е X F (a « x) 
= F (и) о х. В 
    На практике для того, чтобы выяснить, является ли F индуктивной, разумно 
действовать по определению: рассмотреть Р(ы*х) и попытаться выразить эту 
величину через Р(ш). Если это удалось и в полученных выражениях фигурируют 
лишь F(w), х и константы, то F индуктивна и, более того, найденные выражения и 
есть G, Если же эти выражения содержат что-то еще , то обычно следует вывод, 
что информации, заключенной в F(w) и х, недостаточно для вычисления F(o>*x), 
т. е. F не является индуктивной. Критерий индуктивности позволяет доказать это строго. 
    Рассмотрим, например, функцию f = «число максимальных элементов 
последовательности», f:Q(R)—»-Z+, f(A) =0. Выразим f (со*х): 
    f  1,	если	х > максимального   элемента ш, 
    f (со * х) = <  f (со),	если	х < максимального  элемента со, 
    (, f(w)+l,	если	х = максимальному элементу со. 
    В правой части фигурируют f(co), х и «максимальный элемент «». Таким 
образом, можно сделать вывод, что f неиндуктивна —. информации, заключенной в 
f(co) и х, недостаточно для вычисления f(to*x). Хотя в данном случае и 
очевидно, что максимальный элемент со не может быть найден по f(w), т. е. по 
числу максимальных элементов в о>, можно доказать неиндуктивность f и строго» 
За, Ь е Q, х е X, а именно а=1, Ь = 2, х = 2 такие, что f (a) =j :•= f(b)= 1, 
но f(a*x)= I, a f(b*x)=2, т. е. f (а*х) Ф f (b*x), Следовательно, по критерию 
индуктивности f не является индуктивной, 
    Стационарные значения. Пусть F: Я->• Y — индуктивная функция и о :Y*X -> Y 
— соответствующее ей действие X на Y. Значение s ^ Y называется стационарным, если 
    Vx е X   s°x = s. 
    Если при вычислении F(co) какой-нибудь индуктивной функции обнаруживается, 
что значение FI стационарно, то вычисления можно прервать, ибо F (со) *= FI. 
Схему вычисления значения индуктивной функции (2') с учетом стационарных 
значений можно переписать в виде: 
    Р.встать в начало F:=FO 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 117 

    цикл Vx е непрочитанной части Р пока=(Р> не стационарно 
       . выполнять . F:-G(F,x) 
   конец цикла 

    Пример. Пусть 
    X — произвольный алфавит из двух или более символов, хО е X, 
    Y = {да, нет}, 
    F = «все элементы последовательности равны хО», F: И -> Y. 
    Определим   °   (действие X на Y) следующим образом: да о хО = да, 
    даох   = нет, для любого х =? хО,	• нет°х = нет, для любого  х. 
    Легко видеть, что F(u>*x) = F(w) ° к, т. с. F индуктивна, а значение нет е 
Y является стационарным. Таким образом, вычисление F(co) можно записать так: 

    F :=да 
    цикл Vx е непрочитанной части Р . пока F ^ кет	* . выполнять 
    . F := (х ф хО) 
    конец цикла 

    Обычно программа, учитывающая наличие стационарных значений, более понятна 
и проста, ,дем, программа, перебирающая элементы последовательности до конца 
даже__после_тогр, как^ответ ужег не может измениться^ Кроме того*, учет 
стационарных значений в пока оЬЫ'Шб позволяет упростить тело цикла (что и 
сделано в примере ними1). Разумеется, в целях оптимизации можно игнорировать 
существование стационарных значений. 
    Индуктивные расширения функций. Многие функции на пространстве 
последовательностей не являются индуктивными. Это означает, что информации, 
заключенной в F(co) и х, недостаточно дли 11ЫЧИСЛСЧ1НН 1;((1>*х). Можно, 
однако, посмотреть, какой именно информации нам не хватает, и рассмотреть 
более сложную функцию, 'включив в нее и эту информа.цию^тоже. 
    Определение. Функция F: fl-*-Y называется индуктивным, расширением функции 
f: fi -*• YI, если 
    а) F индуктивна, 
    б) Эя: Y->Yf такое, что Vco e= Q     f (to) = n(F (со)). 
    Пример. Рассмотрим функцию f = «число максимальных элементов 
последовательности», Мы видели, что эта функция не 

    118 ГЛ.  1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    является  индуктивной — для вычисления f(ffl*x)   надо знать максимальный 
элемент со. Рассмотрим новую функцию: 
    F:Q->Z + *R, F(co) = (f (со),max (to)), 
    где max: и -*• R — фу^нкция,^сопоставляющая каждой последователь-нести 
максимум ее элементов, max (A) — —do. 
    ' Зная f(to), тах(ш) и х, можно найти и f(«*x), н тах(а>*х), т. е. F 
—индуктивная функция. Очевидно также, что VtoeQ, зная F(<o), можно найти f(w) 
—достаточно просто «забыть» max (со). Таким образом, F •— индуктивное 
расширение f, и f можно вычислить так: 
    Р.встать в начало 
    у :=0; m := — со 
    цикл Vx е непрочитанной части Р  выполнять выбор 
    .     , при х < m => ничего не делать 
    .     .при   х = т=>у:=у+1 . при  х>т=^у:=1; т:=х конец выбора 
    конец цикла 
    ответ := у 
    Минимальное индуктивное расширение. Для одной и той же функции f можно 
придумать разные индуктивные расширения. Например, тождественное отображение 
IdQ:?2->?2 является индуктивным расширением для любой функции f. Для этого 
расширения n = f, т.е. задача получения f(co) no F(w) есть в точности исходная 
задача. Таким образом, это индуктивное расширение абсолютно бесполезно. 
    Наибольший практический интерес представляет такое индуктивное расширение, 
которое содержит минимум информации об ш. Мы покажем сейчас, что такое 
минимальное расширение существует и что оно единственно с точностью до изоморфизма. 
    Определение. Пусть F; Q -> Y и F: Q -> Y — две функции на Ц. Скажем, что F 
^ F, если Зр: Y -> Y такое, что Vco е И f ((o)jpp(F (ш)), т. е. если f (ш) 
можно найти по F (ш). 
    Определение. Индуктивное расширение F: Q->Y функции.f .называется 
минимальным, если 
    а) FJQ) = Y, 
    б) для любого другого индуктивного расширения F функции f 
    F?*F~.       Г .    -'    :-. .   /'/.:^-,;        ;      Р. 
    Утверждение. Минимальное расширение единственно с точл цостыо до изоморфизма. 
    .4'. :  '      '•   i-MiM 
    I v-\ 
    •Ufl 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИИ 119 

    •    Доказательство.   Пусть  F(: 2-»Yi   и   Fa: S-»Yz—два минимальных 
индуктивных расширения f. Тогда 
    F,(Q)-Yi.     F2(")=Y2,      F, >F,.      F1>Fl. Так как FI ^ Fa и Fa ^ 
Ft, то существуют pu и pai такие, что 
    V» e U Fi (w)-p2i (Fi (ш)) я F, (a)=pi2 (Fj (w)). 
    Докажем, что ри о pnoldy,. Возьмем любое у, е Yi. Так как F, (Q)=Ki, то 
существует ш а и такое, что Ft (tt))=yi. Так как V* е Q FI (о))™рц (рм (F( 
(ш))), то PIJ ° P3i (yiJ^Yi. Поскольку у, любое, то pu ° Pzi — Idy^ Аналогично 
доказывается, что pjj о pi2=Idy2, и, значит, pi2 и p2i — изоморфизмы. • 
    Теорема, Минимальное расширение существует. 
    Доказательство. Доказательство этой теоремы состоит из двух этапов. 
Сначала строится некоторое вполне конкретное индуктивное расширенно (назовем 
его каноническим), а затем доказывается его минимальдость. 
    Каноническое индуктивное расширение функции f. Обозначим через <BI * ш> 
результат добавления (приписывания) последовательности сог s Q в конец пос« 
ледователыюстн mi sQ (для одиоэлсмсцтаой последовательности Шг это согли 
суется со старим смыслом знака *).|Ъведем на Si бинарное отношение »* сле« 
дующим образом:	' 
    а и Ь •<=*- уш е 3 f (а * co)=f (Ь * ш).	/ ЯсноГ^что^ 
    1) »• есть отношение эквивалентности на Q, 
    2) а я» Ь => Vx sXa*x«sb»x, 
    3) a >»b=*"f (a)=f (b). 
    Рассмотрим фактор-множество Y=2/»s по отношению эквивалентности *** а 
обозначим через?: 2-»Y естественную проекцию Q на фактор-множество. Тог--да 2) 
можно переписать в виде 
    Va, beQ: F(a)='F(b)    yxeX    F(a « x)-F(b * х), 
    т. е. для F выполняется критерий индуктивности. 
    Из 3) вытекает, что f постоянна на множествах уровня функции F и* еле* 
дозательно, можно определить проекцию Я: Y-*Yf формулой л(ш)=1 (а), где 
ш—какой-нибудь представитель класса эквивалентности ш. Наконец, из определении 
F u я вытекает, что I — я о F. 
    Таким образом,   F — индуктивное расширение f и F(Q)««Y. 
    Докажем теперь минимальность F, т. е. покажем, что для любого F: Q-^Y 
индуктивного расширения t существует р: Y-»Y такое, что \/asQ F(a)-«•»р о F 
(а). Так как г(а)—-это класс эквивалентности а, то нам надо показать, что по 
значению F(a) класс эквивалентности а определяется однозначно. Действительно, 
пусть F (b) — F (a) (b s U). В силу индуктивности F y<>> s 2 F (a • ш)=« 
—F(b«o)), а так как F—расширение f. то и f (а • ш)=! (Ь * ш), т. е. а *« Ь. 
Таким образом, для элементов а и b из разных классов эквивалентности F(a) т^ 
F(fa) и по значению F(a) класс ^эквивалентности а (т. е. F(a)) определяется 
однозначно. • 
    Утверждение (критерий минимальности индуктивного расширения). Индуктивное 
расширение F: Q-»-Y функции f: G-»-Y[ является минимальным тогда и только 
тогда, когда 
    1) F(Q)=»Y,	. 
    2) Va, b s Q F (а) ф F (b) =*- a qb b, где л* — отношение эквивалентности, 
введенное выше (a sfr b -*=»- Эю s Q f (a * co)=?^f (b * ш)). 

    120 ГЛ.  1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    Доказательство. Необходимость очевидна. Докажем достаточность. Рассмотрим 
каноническое минимальное расширение F(:Q->Y. Так как V$*$, то существует 
p:Y-»Y такое, что v<oeQ F~(<o)=p о Р(и). Так как F(Q)=Y, a F(Q)=Y, то p(Y)=Y, 
т. е. р является отображением «на». Для того чтобы доказать, что р—изоморфизм, 
осталось показать, что р не склеивает точек и з Y=F(2). Действительно, 
рассмотрим две разные точки из F(Q): 
    уа. ybe=F(Q),   Уа^уь,   ya = F(a),    yb=F(b). Так как F(ajT^F(b), то, 
согласно 2), "F(a)=^F(b), т. е. р(у ^Р^УЛ- H 
    Пример использования критерия минимальности. Очевидно, что функция 
    F:Q->Z + *R,      F (со) = (f (и), max (со)) 
    не является минимальным индуктивным расширением функции f =. = «число 
максимальных элементов последовательности», так как F(Q) =И= Z+*R. Например, 
Зсо е Q : F (со) = (0, х) при х ф — оо. 
    Однако если ограничить область значений функции, т. е. рассматривать ее 
как отображение F: Q->-Y = (0,—°°)U N*R, то такая функция будет минимальным 
индуктивным расширением f. Докажем это, пользуясь критерием минимальности. 
    1) F (Q) = Y. Действительно, V (п, х) е N * R Эш = хх...х (п элементов) 
такая, что F (<о) = (п, х), а (0, — оо) = F (Д). 
    2) Пусть а, befi и F(a) =5*= F(b). Покажем, что а дб Ь. Пусть F(a) = 
(na,Xa), F(b) = (пь, хь). Если па =И= пь, то это просто значит, что f(a)^ f(b) 
и, следовательно, а д& Ъ. Если же па = пь, но ха ф '•? хь, то без ограничения 
общности можно считать, что ха < х&. Тогда f(a*xa)= na + I, f (Ь*ха) = па, т. 
е. f (а*ха) ф f (b*xa) и, значит, а?6Ь. 
    Разные пространства и доопределения. На практике типичны ситуации, когда 
сама функция f и ее удобное индуктивное расширение F определены на разных 
пространствах. Например, для функции f = «среднее арифметическое элементов 
последовательности», определенной только на Q1, можно использовать индуктивное 
рас-ширенгз F =(2, п), где S: Q -»• R — сумма элементов последовательности 
(Z(A)=0), a n: ?2-vZ-f-— число элементов последовательности. Таким образом, в 
этом случае f определена на Ql, a F — на П. Если в уже рассматривавшемся 
примере f = «число максимальных элементов последовательности» не использовать 
идеальных элементов ±оо, то функция F = (f, max) будет определена лишь на Q1, 
хотя f определена на Q. 
    Естественно, такие расхождения надо учитывать при программной реализации. 
Например, нахождение числа максимальных элементов последовательности без 
использования идеальных элементов tfcoo пришлось бы записать так: 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 121 


    если Р.пуста то ответ := 0 иначе 
    . Р.встать в начало 
    . Р.прочесть очередной элемент в (вых:х) 
    . у:= 1; т:— х 
    . цикл Vx е непрочитанной части Р выполнять 
    . .   выбор 
    . .   . при х < m => ничего не делать 
    . .   . при х = т=Ф-у:=у+ 1 
    . .   . при х > т =Ф- у := 1; т := х 
    . . конец выбора 
    . конец цикла 
    . ответ := у 
    конец если	. 

    Как видно из этого примера, __иметь_..дело с индуктивными функциями на Q 
проще, чем с функциями на Q1. Поэтому, если индуктивная функция F определена 
на ?21, разумно попытаться доопределить ее на ?3 с сохранением G, т. е. 
попытаться найти такое уО = =. Р(Д), что  

Vx е X     F (х) •= F (Д * х) = G (F (Д), х) = Q (уО, х),    т. е. G (уО, х) = F (х). 

    Если при этом F рассматривается как индуктивное расширение f, то надо еще 
сохранить и п: 

    НД) = я(Р(Д)) = я(уО). 

    Вернемся к примеру «число максимальных элементов последовательности». 
Функцию max: Ql(R)-»-R можно было доопределить на Q, так как существует уО = 
—°° е R такое, что 

    Vx е X    G (— оо, х) = max (— оо, х) = х = F (х). 

    Аналогично индуктивную функцию F, = «произведение элементов числовой 
последовательности» (F:Q1(R)->R, G(y, х) = у*х) можно доопределить на Q, так 
как существует уО = 1 е ft такое, что 

    Vx<=X    G(l,x) = l*x = x = F(x). 

    Наоборот, индуктивную функцию F — «первый элемент последовательности» (F: 
Ql(X)-»-X, G(y,x)=y) доопределить на Q нельзя, так как не существует такого уО 
е X, что 

    Vx е X    G (уО, х) = F (х),    т. е.    уО = х. 

    Другими  словами,  не  существует  уО е X,  который   был  бы  равен всем 
х е X одновременно. 
    Наконец, если такого yOeY для F: ?21(X)->Y и G: Y*X-*-Y найти не удается, 
то можно попытаться расширить пространство Y. Собственно говоря, именно такое 
расширение пространства R до R 

    122 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    и  было  использовано   в   примере  «число  максимальных  элементов последовательности». 
    Практика. На практике индуктивное вычисление функции на пространстве 
последовательностей сводится обычно к применению одного из двух приемов. 
Первый прием состоит в том, чтобы прямо представить неиндуктивную функцию в 
виде композиции индуктивных   (например, среднеарифметическое можно 
представить в виде S/n, где ? — сумма, а п — число элементов 
последовательности — две индуктивные функции). Если это удается, то в качестве 
индуктивного расширения можно взять объединение полученных индуктивных функций 
(для среднеарифметического—пару_ |S, n)). Разложение функции в композицию 
индуктивных , однако, творческая задача и потому применяется только в 
простейших случаях, где "такое разложение более или менее очевидно. 
    Второй прием состоит в выражении f(co*x) через Ц®) и х. После этого надо 
посмотреть, какой информации, кроме {(со) и х, не хватает для вычисления 
f(o>*x). Пусть это информация И (со). Если !T!"tGi"*x) выражается через f(eo), 
И (со) и х, то в качестве индуктивного расширения f ^можно взять пару Д,|1). В 
противном случае недостающая информация 'обозначается f2(co) и рассматривается 
f2(a>*x). И опять: если f2(co*x) выражается через х и функции 1(<в), И(о>) и 
f2(o>), то тройка (f,fl,f2) является индуктивным расширением f. В противном 
случае рассматривается недостающая информация f3 и т. д. до тех пор, пока не 
будет получено индуктивное расширение f. Второй прием, в отличие от первого, 
является регулярным и почти не требует творческих усилий. Ниже мы в основном 
будем "пользоваться именно вторым приемом •— добавлением к функции недостающей 
для индуктивности информации. 
    Рассмотрим несколько примеров индуктивного вычисления функций на 
пространстве последовательностей. ' 
    Номер первого элемента, равного хО. Пусть стоит задача определить номер 
первого элемента, равного хО, в последовательности Р элементов типа X: 

    дано        : Р : последовательность элементов типа X, 
    хО: X получить: | номер первого вхождения хО в Р или О, 
    1 если элемента, равного хО, в Р нет 

    Попытаемся вычислить этот номер индуктивно: 
    'S / • 
    *&•• иЩ(^ 
    ИД)» О    f (ш * х) = I f (ш)> ~ли *° -ез ш илн х ф х0' '	I nl        в 
противном случае, 
    где nl *= n 4- 1 —• номер  элемента х  (п — длина  последовательности 
о>)|. Условие хО е ш легко выразимо через f{co}: xOewr^1?' 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 123 

    ч^Цсо)^ 0. Поэтому i.(co*x) можно переписать в виде 
    _ f f (и),     если f (со) *?• 0 или х =? хО, (<S*X)~ln+l,   если f(co) = 
0 и.х-ий, Таким образом, знания f(co) и х недостаточно для вычисления f(w*x) 
—нужно знать еще и п —длину со. Рассмотрим более сложную функцию F, включив в 
нее и эту информацию: 

    F = (f, n),    F : Q -> Z + * Z +,    n (со) = «число  элементов  со». 

    Очевидно, что F является индуктивным расширением f. Хотя это расширение и 
не минимально (докажите это), оно определено на всем Q и легко вычислимо. 
Поэтому для практических целей его достаточно. 
    Наконец, заметим, что все значения f ф О являются* стационарными. 
Используя обозначения «ответ» и «число прочитанных» вместо f и п 
соответственно, можно записать программу в виде: "программа номер первого (вх: 
хО) в последовательности (вх:Р) : Z+ . дано        : Р: последовательность 
элементов типа X, 

    хО: X . получать: | номер первого вхождения хО в Р или О, 
    |если элемента, равного хО, в.Р нет 
    .	Р. встать в начало 
    .	ответ := 0; число прочитанных := О 
    .	цикл Vx е непрочитанной части Р 
    .	. пока ответ = О 
    .	. выполнять 
    .	. число прочитанных.увеличить на 1 
    .	. если х = хО то ответ := число прочитанных конец если 
    .	конец цикла 
    конец программы 

    Среднеарифметическое. 
    дано        : Р : последовательность элементов типа R,    ' • 
    Р.не пуста получить: | среднеарифметическое элементов последовательности 
    Мы уже говорили о том, что в качестве индуктивного расширения для этой 
функции можно взять F = (S, n), где S: Q->R-r. сумма элементов 
последовательности, а п: И->-Z+,—• число элемен-тов. Соответствующая программа 
записывается в виде: программа следнеарифметическое (ex:P):R 
    . дано        ; Р : последовательность элементов типа R, 
    t	P.не пуста 


    124	ГЛ.  1. НАЧАЛА ПРОГРАММИРОВАНИЯ . 


    ^олучить: | среднеарифметическое элементов последовательности 
    
    . Р.встать в начало 
    . сумма := 0; п := О 
    . цикл Vx e непрочитанной части Р выполнять 
    . .     сумма := сумма + х 
    . .     п         := п         +1 
    . конец цикла 
    . ответ := сумма/п 
    конец программы 

    Представление среднеарифметического в виде композиции индуктивных функций, 
как уже отмечалось, является творческой задачей. Можно было идти и стандартным 
(вторым) путем, т. е. выра-15Sl!iJLtu)*?) ,2?ES3JU?iL иЛь Посмотрим, к чему 
приведет этот путьз 
    f (со * х) = (S (со) + 5/(п (о>) + 1) =tf (о>) • п (») + х)/(п (со) + 1) 
Так как в правой части кроме f(cc) и х используется п(ш), то 
    F = (f,n),    где    п (и) = «число элементов и», n:Q->Z+. 
    Функция F в целом определена лишь на Q1. Попробуем продолжить ее на и. Для 
этого надо найти такое уО, что 
    VxeR    x = f(x) = f (A*x) = (f (Д) * п (Д) + х)/(п (Д) + 1) = 
    = (уО * 0 + х)/1 
    или Vx eRx = yO*0 + x. Но полученное равенство выполнено VyO e R. 
Следовательно, можно доопределить f (Д) чем угодно, например нулем. В 
результате получим программу: 

    'программа среднеарифметическое {ex:P):R . дано       : Р : 
последовательность элементов типа R, 
    Р.не пуста . получить: | среднеарифметическое элементов последовательности 
    , Р.встать в начало 
    . f :=0; п:=0 
    . цикл Vx е непрочитанной части Р выполнять 
    . .    f :=(f*n + x)/(n+l) 
    . .    n:=n+l 
    . конец цикла 
    . ответ :=f 
    конец программы 

    Дисперсия.   Дисперсией    элементов    последовательности    со =| 
    = Xix2 ... хп называется величина  (2 (xi ~" m)2)/n> где ™ 
—среднеарифметическое. Попробуем применить первый подход -= предста
    8   ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 125 
    вить дисперсию в виде композиции индуктивных функций: 
    fvo» = 
    t^i^f, _  Ё(х?-2тх! + т2) 
    E^-rn Zxi-mZ(xi~ 
    I 
    У. *|-т Z xi _ Ё х? 
    (f.,)' 
    Обозначим s2 = Z x?. sl = Z xi'  s° = Z ^ = П-   Тог*Да   f (™) = = s2/sO— (sl/sO)2. 
    Очевидно, что каждая из трех функций s2, sl, sO индуктивна, и, значит, F = 
(s2, sl,sO)   является индуктивным расширением f: 

    «СЛ-.:.    
    программа дисперсия (вх : Р): R 
    . дано        : Р : последовательность элементов типа R, 
    Р.не пуста . получить: | дисперсию элементов последовательности 
    . Р.встать в начало 
    . s2:=0     | сумма квадргтоз элементов прочитанной части Р 
    . sl := 0     | сумма	элементов прочитанной части Р 
    . sO:=0     | число	элементов прочитанной части Р 
    . цикл Vx е непрочитанной части Р выполнять         ^ 
    . .    s2:= s2 + x* * 2 
    . .    sl := sl -f х 
    . .    sO:=sO+ 1 
    . конец цикла 
    . ответ := s2/sO — (sl/sO) ** 2 
    конец программы 

    Задачу можно было решать и стандартным .(вторым)  путем --       С 
выражать f(w*x) через 1(ы)- В этом случае мы бы получили*	• f (» • х) ~ -^-р 
(f (ш))+ (Хп~ У •)'.     Р^Ц^п^п), 
    где  m — среднеарифметическое,  an — число  элементов  последовательности. 
    Функция F индуктивна (докажите это), однако в целом определена на Q1. 
Функция п определена на Q; т, как мы знаем, можно доопределить на Q 
произвольным образом (например, нулем). 
    (^ 
    К 
    п -1 


    126 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    Посмотрим, нельзя ли доопределить f; 
    Y(x-x) f(x) = .?=!_———=-0    VxeR. 
    С другой стороны, 
    */л      \      - п(Д)      /"./АЧ  ,   (х —т"(Д))2\      0 ......    ,.   
   л 
    f(i*x)-n(A)+llf(A) +    п(Д) + 1    J-T(*W + «')-a 
    Таким образом, VyO e R f (x) = G(yO,x^ и   можно   доопределить Z на Д 
произвольно, например положив f (Д) = О, программа дисперсия {вх : Р): R 

    . дано        : Р : последовательность элементов типа R, 
    Р.не пуста . получить: | дисперсию элементов последовательности 
    . Р.встать в начало 
    . f- := 0     | дисперсия прочитанной части Р 
    . т:=0     (среднеарифметическое прочитанной части Р 
    . п := 0     | число элементов прочитанной части Р 
    . цикл Vx е непрочитанной части Р выполнять 
    . .    f  := п/(п + 1) *.(f + (х - m) ** 2/(п + 1)) 
    ..    m := (m*n + x)/(n+ 1) 
    . .    n :=n+l 
    . конец цикла 
    , ответ := f 
    конец программы	• 

    Поиск по образцу. 

    дано       :   Р : последовательность элементов типа символ получить: | 
число вхождений группы из 4 символов "abed" в Р 
    Действуем стандартным (вторым) путем: 1(Д).= 0, 
    , ,        . _ ( f (со) + 1,   если х = "А" и со кончается на "abc", 
    I (СО ^ X) —*~  1    г /    \ 
    If (со)	в противном случае. 

    В правой части кроме 1(<а) и х фигурирует H(CD)=«G> кончается ua "abc"». 
Таким образом, для вычисления f(w*x) нужно знать И (со). Попробуем рассмотреть 
функцию Fl= (f,fl). Легко видеть, что эта функция не является индуктивной: 
информации, заключенной в f(u>), И .(со), и х хватает для вычисления f(co*x), 
но недоста* точно для вычисления Н(со*х): 
    ,. ,        ). = J да'    если х=="с" и ш кончается на "ab", '     \ нет   
в противном случае. 
    Таким образом, для вычисления fl(co*x) нужно знать f2(co)= «ш кончается на 
"а.Ь"», Рассмотрим Р2_== {f, fl,f2). Однако и эта функ

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 127 

    кия не является индуктивной: заключенной в ней информации не достаточно 
для нахождения f2(co*x): 

    f2 (со * х) = J да' (. нет 
    если х = "Ь" и со кончается на "а", нет   в противном случае. 
    Рассмотрим f3(co)=«to кончается на "а"» и соответственно F3 i=(f, fl, 
f2,13). Легко видеть, что F3 уже индуктивна: 
    f3 (со * х) 
    _ f да,,    ее \ нет   в 
    противном случае. 

    Функция F3 является индуктивным расширением f, но она достаточно сложна. 
Поэтому пошзобущ,.^,,,помощью критерия ^мини^-мальности^найти расшире/цщ .рсщррще. 
    "Сразу видно, что расширение F3 не минимально, так как fl, f2 и f3 не 
независимы: например, если fl(w)= да, то заведомо f2(co) = ,= нет и f3(co) = 
нет. У тройки (fl,f2, f3) всего четыре допустимых состояния. Эти состояния 
можно представить одним числом в диапазоне от 0 до 3: 
    3,	если со кончается на "abc", 
    2,	если со кончается на "ab"", 
    1,	если со кончается на "а", 
    О	в противном случае. 
    п(со): 
    Функция F = (f, n): Q-*Z+«{0 .. 3} индуктивна и, более того, является 
минимальным индуктивным расширением f  {докажите это)^ программа число 
вхождений abed в (вх: Р): 2 + 

    . дано        :   Р : последовательность элементов типа символ 
    . получить: | число   вхождений  группы из 4 символов  "abed"  в Р 
    -. Р.встать в начало . f := 0 | число найденных вхождений 
    . п:=0 (число найденных символов в незаконченном вхождении . цикл Vx г 
непрочитанной части Р выполнять , .     выбор 
    ..     .   при п = 3 и x = "d"=s-n:=0; f := f + 1 ..     .   при п = 2 и x 
= V=*-n:=3 ..     .  при n= 1 и x = "b"=*-n:=2 .  при	х = "а" =*• n := 1 . .   
  .  иначе                        к>п:= О . .     конец выбора . конец цикла . 
ответ := f конец программы 


    128 ГЛ.  I. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    Значение заданного по убывающим степеням многочлена в точке. 

    Пусть заданы точка tO, последовательность Р, в которой в порядке убывания 
степеней расположены коэффициенты многочлена, и требуется определить значение 
многочлена в точке tO. Обозначим состояние последовательности Р через со = а„ 
... aja^o, где ап — первый элемент последовательности, а а0 — последний. Наша 
задача, таким образом, состоит в нахожден 
    ии 
    f(co) = antOn+ ... + aX+V°+aO-Будем действовать стандартно: 
    f (со * х) = antOn+1+ .. - + a2t03+ a,t02+ afltO + x = f (со) * tO + x. 
    В правой части не используется ничего, кроме f(«), x и не зависящей от 
последовательности величины tO, т. е. функция f индуктив-на. Из соотношения х 
= f (х) = f (Д*х) = f (A)*tO + х следует, что f(A)*tO = 0, т. е. f(A) = 0. 
    программа значение многочлена (вх: Р) в точке (ex:tO):R . дано        :    
Р : последовательность элементов типа R, tO : R . получить: | значение в точке 
10 многочлена, коэффициенты  кото-| рого расположены в Р   в порядке убывания  степеней 
    . Р.встать в начало 
    . f:=0 
    . цикл Vx <= непрочитанной части Р выполнять 
    , .    f:=f*tO + x 
    . конец цикла 
    . ответ := f 
    конец программы 

    Обратите внимание, что мы регулярным образом, ничего не придумывая, 
получили схему Горнера вычисления значения многочлена в точке.	
    Производная многочлена, заданного по убывающим степеням. Пусть в условиях 
предыдущей задачи надо определить не значение многочлена, а значение его 
производной Г (со). Мы могли бы стандартно выражать Г,(со*х), но того же 
результата можно достичь, просто продифференцировав f (со*х) по t и взяв 
значение в 10: 

    f' (а * х) = (f (со) * tO + х)' = f' (ш) * to + f (to). 

    В правой части кроме Г (со) и константы tO фигурирует еще и f(co). 
Рассмотрим F = (f, f). Эта функция индуктивна, и ее можно продолжить на Q, 
положив Г.(Д).= 0: программа производная многочлена {вх: Р) в точке (вх: tO): 
R , дано       1   Р 1 последовательность элементов типа R, tO:R 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 129 

получить: | значение в точке tO производной многочлена, | коэффициенты 
которого расположены в Р | по убыванию степеней 
    
    . Р.встать в начало 
    . df:=0 
    . f :=0 
    . цикл Vx е непрочитанной части Р выполнять 
    . .     df :=df * tO + f 
    . .    f :=f*tO + x 
    . конец цикла 
    . ответ := df 
    конец программы	

    Полученную схему, по-видимому, разумно назвать схемой Горнера вычисления 
производной многочлена в точке. 
    Анализ правильности формулы. Пусть Х={(,), t, +} —алфавит из четырех 
символов. Среди последовательностей в алфавите X некоторые являются 
правильными алгебраическими формулами, например t, '(t), t + t, ((t + t)+t). 
Нужно определить, является ля последовательность символов правильной формулой: 

    f (ш) => «ю является правильной формулой», f: Й1 (X) -> {да, нет). 

    Мы не будем подробно расписывать ход решения этой задачи. Приведем сразу 
индуктивное расширение F=(fl,f2, f3) .функции f, где 
    fl = «ш может быть продолжена до правильной формулы», П: Q->- {да, нет}, 
    Г2 = «число левых скобок — число  правых  скобок»,  f2:  Q-»-Z, 
    f3 = «последний элемент со», [3: Q1 ->-X. 
    Функцию F можно доопределить на Q, положив Р(Д)--* '= (да, 0, "+"). 
Отображение л определим следующим образом» 
    f(co) = да-*=*-? (со) ='(да,0,"1")   или   F (со) = (да, 0,:')"). 
    Таким образом, пустая последовательность «кончается» знаком 4" и 
«является» неправильной формулой. Этот же вывод можно сделат:. и из очевидного тождества 

    Vco е Ql     f (<а) = f ("t + " * ш). 

    Подставляя формально в это тождество ш = А, получим f(A)=-•r= f("t+") = нет. 
    программа формула (вх : Р) правильна : да/нет 
    . дано	:Р : последовательность элементов типа символ 
    .	|Р состоит из символов "(", ")", "t", "+" 
    « получить: 

    5    А. Г, Кушниренко, Г. В. Лебедев 
    130 ГЛ. I. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    . Р.встать в начало 
    , начало правильно := да 
    . разность	:= О 
    . последний элемент := "-)-" 
    . цикл Vx е непрочитанной части Р 
    . .     пока начало правильно 
    . .     выполнять 
    . .      выбор 
    . .      .   при х = " ("=>- разность.увеличить на 1 
    . .       . 'при х = ")" =>-разность.уменьшить на I 
    . .      конец выбора 
    . .      начало правильно := разность >= 0 и 
    . .	сочетание (последний элемент,х) допустимо 
    . .      последний элемент:= х 
    . конец цикла 
    .. ответ := начало правильно и разность = 0 и 
    (последний элемент = ")'" или последний элемент = "t") конец программы 
    программа сочетание (вх: .ч! ,х2: символ) допустимо: да/дет . дано        
: . получить: 
    .   ответ :=(xl="(" и ?х2="(" или x2="t")) или (xl="+" и (х2="(" или 
x2="t")) или (xl="t" и (х2=")" или х2="+")) или (Х1=")" и (х2=")" или х2="+")) 
    конец программы 

    Замечание 1. Бинарные операции и индуктивные функции. В частном* случае, 
когда область значений индуктивной функции F, совпадает с алфавитом X, 
действие ° является бинарной операцией на X и значение F на ы = Х[Х2 ... хп 
выражается формулой 

    F(w)=Xi°X2°    ,.,     ,°Хп, 

    где действия выполняются слева направо. На Q1 функция F доопределяется 
формулой F (х) = х Vx е X. F можно продолжить на Q, положив F(A)= е, тогда и 
только тогда, когда Vx е X е°х = х, т. е. только тогда, когда е является левым 
нейтральным элементом операции ° . Элемент s е X является стационарным 
значением тогда и только тогда, когда Vx е X s ° х  = s. 
    Так, например, числовая функция «сумма элементов» задается бинарной 
операцией +, «произведение элементов»—операцией *, «максимум элементов» = 
бинарной операцией max. 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИИ 131 

    Замечание 2. Однопроходные алгоритмы и минимальность, При решении 
конкретных задач, связанных с последовательностями, возможны разные стратегии. 
Например, задачу «число максималь» ных элементов последовательности» можно 
решать так: сначала перебрать все элементы последовательности и найти 
максимум, потом перебрать элементы последовательности еще раз и подсчитать 
число элементов, равных найденному максимуму. Каждый перебор всех элементов 
последовательности в программировании принято называть проходом. Общие 
стратегии (алгоритмы) работы с последовательностями принято классифицировать 
по числу проходов и называть однопроходными, двухпроходными и т. д. Одну и ту 
же задачу можно решать за разное число проходов. Схема индуктивного вычисления 
функций на пространстве последовательно"стёи"""всёгда приводит к 
однопроходному алгоритму, т. е. алгоритму, который читает ^элементы 
последовательности от начала к концу по одному разу каждый. Обычно 
однопроходные алгоритмы выполняются быстрее, чем мног опроходные. Таким 
образом, индуктивное вычисление является оптимальным по скорости. 
    Минимальность индуктивного расширения означает минималь-ностТПю" памяти, 
т. е. по" объему информации, которая хранится в процессе вычисления. 
    Таким образом, основной теоретический результат этого раздела можно 
сформулировать так: для любой функции f на пространстве последовательностей 
существует минимальный по памяти вычисляющий f однопроходный алгоритм; этот 
алгоритм единствен с точностью до изоморфизма. 
    Замечание 3. Другие программные структуры данных. Изложенный выше метод 
индуктивного вычисления значений функций применим и к функциям, заданным на 
других программных структурах — векторах, списках, очередях и т. п. Например, 
значение в точке tO производной многочлена, коэффициенты которого в порядке 
убывания степеней расположены в динамическом векторе, можно найти так: 
    программа произиодпая многочлена (вх : v) в точке (вх:10): Я . дано        
:   v : динамический вектор элементов типа R, 
    10 :R 
    . получить: | значение в точке tO производной многочлена, | коэффициенты 
которого расположены в v | по убыванию степеней 
    . df:=0 . f :=0 . цикл VI 
    5* 
    : t..у.число элементов выполнять 


    132 ГЛ. I. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    . .     df := df * tO + f . .     f   :=  f*tO + v(i) . конец цикла . 
ответ := df конец программы 
    Элементы других структур не обязательно всегда перебирать в том порядке, в 
котором они находятся в структуре. Если, например, в динамическом векторе 
коэффициенты многочлена расположены в порядке возрастания степеней, то можно 
перебирать изо от конца к началу. Тогда в получающейся последовательности со 
Они будут расположены в порядке убывания степеней и можно будет применить 
схему Горнера: программа производная многочлена (вх: v) в точке (вх: tO) : R . 
дано        :   v : динамический вектор элементов типа R, 
    10: R . получить: | значение в точке tO производной многочлена, 
    | коэффициенты которого расположены в v .	[по возрастанию степеней 
    .   df:=0	••,-'• 
    f:=o	•;;>.;.••••.',' 
    '.   цикл Viе 1..v.число элементов реверс выполнять 
    .    .     df := df * tO + f 
    .    .    f:=f*tO + v(i) 
    . конец цикла 
    . ответ := df	
    конец программы 

    Замечание 4. Разные задачи и схема индуктивного вычис-'ления функции. 
Пространство последовательностей полезно уметь узнавать в самых разных 
ситуациях. Вернемся, например, к задаче «число препятствий в полосе» из разд. 
4. Продвигаясь вдоль полосы с запада на восток и анализируя клетку слева от 
Путника, мы фактически имеем дело с последовательностью элементов типа 
«занято/свободно» и с функцией «число препятствий в полосе», определенной на 
таких последовательностях. Попробуем решить эту задачу регулярным образом, 
находя индуктивное расширение искомой функции; 

    f f (со) + li   если х — первая клетка нового 
    f (со * х) «= <	препятствия, 
    (. f (со)	в противном случае. 

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

    8   ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 133 

    х == занято и последний элемент со =. свободно. Функция F = (f, последний 
элемент со) 
    является индуктивным расширением f, и программу можно записать 
    в виде: 
    программа число препятствий в полосе 
    . дано        : [Путник у западного края под полосой препятствий 
    .	|лицом на восток 
    . получить: | Путник у восточного края, в Счетчике — число 
    |препятствий в полосе . объекты: 
    было занято: да/нет 

    Объект «было занято» будет содержать информацию о послед» нем элементе со. 
Поскольку F определена на непустых последова» тельностях, а положение Путника 
в начальный момент соответствует! состоянию «прочитан один элемент 
последовательности», то прежде всего установим начальное значение F, т. е. 
состояние Счетчика и объекта «было занято»: 

    . Счетчик установить в нуль 
    . если Путник.слева занято то 
    . .     Счетчик.увеличить на единицу	; 
    . конец если 
    . было занято := Путник.слева занято 

    Само индуктивное вычисление F записывается как обычно, толь* ко вместо 
чтения элемента последовательности надо перемещать Путника на восток: 

    . цикл пока Путник.впереди свободно выполнять 
    . .     Путник.сделать шаг    | т. е. получить очередной элемент со 
    . .     если Путник.слева занято и не было занято то 
    . .     .    Счетчик.увеличить на единицу 
    . .     конец если 
    . .     было занято := Путник.слева занято 
    . конец цикла 
    конец программы 

    Заметьте, что в аналогичной программе в разд. 4 никакие объекты не 
используются. Возникает вопрос: как же так — ведь функция «число препятствий в 
полосе» не является индуктивной ц без дополнительной информации ее за один 
проход вычислить целы зя! Дело в том, однако, что в разд. 4 мы тоже 
использовали эту безусловно необходимую информацию о последней пройденной 
клет< ке, но с чисто программистской точки зрения делали это по-другомуз 

    134 ГЛ. 1, НАЧАЛА ПРОГРАММИРОВАНИЯ 

вместо того чтобы запоминать текущее состояние в специальном объекте «было 
занято», потом делать шаг и смотреть, что было раньше, мы сначала 
анализировали текущее состояние и попадали в один из двух случаев в выборе, а 
уж потом — внутри выбора —• делали очередной шаг. Образно говоря, информация о 
последней пройденной клетке запоминалась не в специальном объекте, а в тексте программы. 
    В общем случае, если F(w) = (f(w), f1 (последний элемент w)) и число 
различных значений И невелико, можно хранить состояние f1 не в объекте 
программы, а в ее тексте, т. е. использовать выбор с соответствующим 
количеством случаев: сначала анализировать со-стояние И, а потом — внутри 
выбора — читать очередной элемент последовательности и вычислять новое значение f, 

    ЗАДАЧИ  И  УПРАЖНЕНИЯ 

    В приведенных ниже задачах указана функция, значение которой надо 
вычислить. Требуется определить, является ли эта функция индуктивной. Если да 
— выписать G, если нет — придумать индуктивное расширение и выписать G для 
него. Написать программу <вх : Р, вых : искомое значение), считая, что со — 
это состояние последовательности Р элементов типа X. Как и раньше, если 
противное явно не оговорено, под X понимается произвольный алфавит из двух или 
более символов. 
    1. Последний элемент «в, f: fil-^X. 
    2. В w встречается х0, f: Q -> {да, нет}. 
    3. Число элементов, удовлетворяющих условию Q(x), f: ?2 -> 2+\ 
    4. Максимальное значение, f: Ql(R)-*-R. 
    5. Максимальное значение, f: Q(R+)-»-R+. 
    6. Минимальное значение, f: Ql(R+)->-R+. 
    7. Минимальное   и   максимальное   значения,   f:  .Ql (R)-> R*R. 
    8. Три наибольших значения, f: Q3(R)-*- M e R3, M =i *= {(xl,x2,x3): xl sS 
х2 < хЗ}. 
    9. Сумма элементов, f: Q(R)-»-R. 
    10. Произведение элементов, f: Q(R)-^R. 
    В задачах 11—14 SA обозначает множество всех конечных подмножеств 
множества А. 
    11. Объединение элементов, f: Q(SA)-»-SA, А— любое. 
    12. Пересечение элементов, f: Q(SA)->-SA, A — любое. 
    13. Объединение элементов, f: Q(SA)->SA, A= {0,1}. 
    14. Пересечение элементов, f: Q(SA)->SA, A= {0,1}. 
    15. Наибольший  общий  делитель элементов,  f:  ?21(N)->-N. 
    16. Величина числа, записанного в двоичной системе счисления^ I: Ш{{0, 1})-*Z+. 

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЯ. 135 

    17. Все элементы равны между собой, f: Й(Х)-> (да,,нет)-. 
    18. Число различных элементов, f: Q(X)->-Z+. 
    19. Число пар соседних элементов со, удовлетворяющих уело-вню Q(xl,x2), f: Q(X)->Z+. 
    20. Номер последнего элемента, равного хО, f: 0(X)->Z+', Г.{Д)=0. 
    21. Число вхождений в со подпоследовательности рф2 ... pit, все pi 
различны, f: Q(X)->Z+. 
    22. Число локальных максимумов, f: Q(R)->Z+. (Элемент последовательности 
называется локальным максимумом, если у него нет соседа большего, чем сам 
элемент. В любой одноэлементной последовательности, например, ровно один 
локальный максимум), 
    23. Последовательность возрастает, f: Q(R)-> {да,"нет}, [. (A)==j = Да. 
    24. Номер первого элемента, имеющего максимальное значение, f: n(R)-*Z+, 
f(A)= 0. 
    25. Значение записанного по возрастающим степеням многочле-на в точке Ш, 
{: Q(R)-»- R, f (Д) == 0. 
    26. Значение производной записанного по возрастающим степеням многочлена в 
точке tO, f: Q(R) ->- R, f (Д) = 0. 
    27. Значение k-fl производной записанного по убывающим степеням многочлена 
в точке tO, f: fi(R)-> R, f(A) = 0. 
    28. Средняя длина связной возрастающей подпоследовательности, f: Q1(R)->R+. 
    29. Средняя длина связной постоянной подпоследовательности f: Q1(R)->R+. 
    30. Средняя длина связной группы  пробелов, f: Q(S)->R-f-. 
    31. Средняя длина идентификатора, f: Q(S)-»-R+ (идентификатором 
iiaauiiatTcii последовательность букв и цифр, начинающаяся с Оукиы). 
    32. Количество вхождений в последовательность цифры, которая встречается в 
последовательности максимальное число раз, f: fi(X)-*-r*-Z+, X = {О, 1, 2, 3, 
4, 5, 6, 7, 8, 9}. 
    33. Размерность пространства, натянутого на последовательность векторов 
R2, f: Q(R2)->-Z+. 
    34. Сумма квадратов отрицательных элементов числовой последовательности, 
f: ?3(R)-*-R. 
    35. Число элементов числовой последовательности, больших всех предыдущих 
элементов, f; Q|R)-*-Z+, 