Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

.pdf

Скачиваний:

Добавлен:

22.10.2023

Размер:

14.87 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 78 / 458 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. I

т.е. схему некоторого алгорифма (S, удовлетворяющего

(44)(мы отвлекаемся сейчас от неоднозначности опи санной выше схемы (S, связанной с выбором букв-

двойников,	букв а, р и порядком	формул	в	группах
(30) —(35),	(37) — (38)). Этот алгорифм мы		будем		ино
гда обозначать посредством (53 о 21).
Чтобы проиллюстрировать применение теоремы ком
позиции, вернемся к отсекающим		алгорифмам			(при
мер 6) п. 4). Пусть, как и в п. 4, Л—некоторый				алфавит,
а — б у к в а ,	не принадлежащая этому	алфавиту.		Мы не

сколько изменим схемы отсекающих алгорифмов, доба

вив	в схему первого из них формулу оса —• а. Именно,
обозначим через В1,				В2	нормальные алгорифмы в A U {а}
со	схемами
		f	аг)		а	(г) <= А	[} {а})
		1	а -* •
		(	Г)а		а	(т) <= Л)
	Пусть Р — слово вида
(45)			Р		PtaP2a	...	aPk,
где все Р{		(I ^ i ^		k)	— слова в .4.
	Легко	видеть, что
			В1(Р)~Ри
			В2(Р)		= Р2а ...		aPk.
Обозначим через			Вп(п^1)			нормальные алгорифмы
					В\ =	Вг,
					В\ =	(В2оВг),

В2п+1 = (В2оВ1)

и рассмотрим нормальные алгорифмы Вп:

В, = В\

Bn+i = {BloB2n).


		НОРМАЛЬНЫЕ		АЛГОРИФМЫ			73
Ясно, что для любого			слова вида		(45)	с k ^	п
		В я (Р)=рЯ„ .
Таким	образом, Вп		«выбирает»		п-ю	компоненту
а-кортежа длины, не меньшей п.
2) Теорема		объединения.		Очень	часто встречаются
ситуации,	когда	интересующий нас			результат		слагается

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

сформулировать следующее	предписание:	применить
к данному слову Р алгорифмы	21 и 23, затем к резуль
тату работы 91 приписать справа результат,		полученный

посредством 93. Алгорифм, возникающий согласно этому

предписанию из 91 и 93, естественно

назвать

объедине

нием 91 и 93. Имеет

место следующая

теорема

объедине

ния нормальных

алгорифмов.

4]). Каковы

бы

Т е о р е м а

( М а р к о в

[2; гл. 3,

ни

были

нормальные

алгорифмы

23 над

алфави

том А,

может

быть

построен

нормальный

алгорифм

над

А такой, что при

любом слове

Р в

(46)

£ (Р) ~

21 (Р) 23 (Р).

Почти очевиден следующий вариант теоремы объеди

нения.

Каковы

бы

ни были

нормальные

алго

Т е о р е м а

рифмы

и 23

над

алфавитом

и буква

а, можно

по

строить нормальный

алгорифм

над

A U {а} такой, что

6 (Р) ~

21 (Р) а23 (Р)

при

любом

слове

Р в алфавите

А.

Для

доказательства теоремы

6 достаточно

два

раза

применить теорему 5, используя при этом нормальный

алгорифм	Ф а , перерабатывающий всякое		слово Р в ал
фавите А в букву а * ) .
Теоремы 5—6 очевидным		образом распространяются
на случай	объединения нескольких нормальных алгориф
мов. Их	особенно удобно	использовать	(в сочетании

*) 2 ) а легко построить как композицию аннулирующего алго рифма (пример 3) п. 4) и алгорифма (пример 7) п. 4). Мы также предлагаем читателю в качестве простого упражнения по строить алгорифм 3 ) а непосредственно.

74 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА [ГЛ. 1

с теоремой композиции) тогда, когда результаты работы

нескольких алгорифмов, объединенные (как	правило,
с использованием разделительной буквы) в	систему,

сами должны рассматриваться как исходные данные не которого нового алгорифма.

Ясно, что алгорифм (5, построенный согласно тео реме 5, применим к тем и только тем словам в Р, к ко

торым применимы оба алгорифма 21					и 53, т. е. имеет
место		2. Каковы	бы	ни были	нормальные		ал
С л е д с т в и е
горифмы	<& и 33 над алфавитом			А, можно		построить	нор
мальный	алгорифм	над А,	применимый		к	тем и только
тем словам в А, к которым			применимы		оба	алгорифма	Ш

и93.

Вкачестве примера применения теорем композиции и объединения построим алгорифм Ф, распознающий гра фическое равенство слов в алфавите А. Пусть а — бук ва, не принадлежащая А. Мы хотим, чтобы для любых слов Р и Q в А выполнялось

IS) (PaQ)

и
(47)		2)(P<xQ)= Д =		P ~ Q .
	Рассмотрим нормальный алгорифм ®i со схемой
		I т)аг)	а	(г) е	А)
		1 а-»-
	Для каждого слова Р обозначим через Р его обра
щение		(см. пример 9)	п. 4). Легко		видеть, что		для	лю
бого слова PaQ			ID, (PaQ)
и			ID, (PaQ)
и
(48)		£ , ( P a Q ) = A		^ Q	= P.
	По теореме композиции построим алгорифм 3)2 так,
НТО		®2(PaQ)~%(B2(PaQ)),
		®2(PaQ)~%(B2(PaQ)),
где	SR9	— обращающий	алгорифм		(пример	9)	п.	4),
а	В2 — построенный		выше	«высекающий»		алгорифм.

$ и	НОРМАЛЬНЫЕ АЛГОРИФМЫ				75
Очевидно,
(49)		2>2 (PaQ) ~ Q.
Построим далее алгорифм $53 по теореме объедине
ния так, что
	£>3 (PaQ) ~	В, (PaQ) a© 2		(PaQ),
где Bi — построенный		выше	«высекающий»		алгорифм.
Ввиду	(49)
(50)	©з (PaQ) ~		PaQ.
Наконец, по теореме композиции строим алгорифм 35
так, что
	35 (PaQ) ~ 35, (353(PaQ)).
Ввиду (48) для 35 выполняется (47), что и требова
лось.
3)	Т е о р е м а р а з в е т в л е н и я .			Иногда	приходит

ся рассматривать предписания следующего типа (рис. 4): для данного исходного слова Р проверить, удовлетво


ряет	ли	оно	данному		условию бФ; если Р			удовлетво
ряет	si, то		применить к Р алгорифм				91, в	противном
			ПроЗсрна
			1/шбия с#
	Рис. 4. Разветвление нормальных алгорифмов.
случае применить к Р					алгорифм 93. Ясно, что такое пред
писание определяет				алгорифм		в том случае,		когда усло
вие si разрешимо,				т. е. когда		мы располагаем алгориф
мом,	применимым			к любому слову Р и аннулирующим
Р тогда		и только		тогда, когда Р удовлетворяет усло
вию	si*).	Возможность оформления					сформулирован
ного	предписания			в	виде	нормального		алгорифма
(при	условии, что			91, 93 и алгорифм,			«разрешающий»

*) Мы говорим, что алгорифм аннулирует слово Р, если он перерабатывает Р в пустое слово.

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. I

условие

заданы

как

нормальные

алгорифмы)

выте

кает

из

следующей

теоремы

( М а р к о в

[2;

гл. 3,

5]).

Т е о р е м а

Каковы

бы

ни были

нормальные

алго

рифмы

21,

может быть построен

нормальный

ал

горифм

33 над объединением

А их

алфавитов

такой, что

при любом

слове

Р в А

если

& не

применим

Р, то и 3) не применим

к Р;

если

применим

к Р, то

33 (Р) ~

21 (Р)

в том случае,

когда

6 ( Р ) = Л ,

3) (Р) ~

23 (Р)

е гол случае,

когда

<£(/>)# Л .

Теорема

разветвления

легко

распространяется

на

случай, когда выбор работающего алгорифма зависит от

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

нескольких

условий.

Т е о р е м а

8 (ср. М а р к о в

[2; гл. 3,

§ 5]). Каковы

бы

ни были

нормальные

алгорифмы

%ь . . .,

2f„+ 1 , S b

. . . ,

Q>„

(и >

0),

можно

построить такой нормальный

алгорифм

над

объединением

А их

алфавитов,

что

для

любого

слова

А*)

35 (Р)

21, (Р),

если

е , ( Я ) =

Л ,

212 (Р),

если

( Е , ( Р ) # Л ,

< М Р ) = Л ,

213 (Р),

есл«

6 , ( Р ) # Л ,

М Р ) # Л , е 3 (^)=г=Л,

2t„(P),

если

(МР)=5бЛ,..., 6 Я - , ( Р ) # Л , 6Я (Р) =

Л ,

Я Я + 1 ( Р ) ,

есл«

S , ( P ) ^ A , <5а(Р)=£ Л,...,

ВД#Л.

*) Следует иметь в виду, что если два выражения связаны

знаком графического

неравенства ^ф, то они

осмыслены

и пред

ставляют собой различные слова. Словесное предписание, соответ ствующее алгорифму £>, таково: применяем к Р алгорифм бг, если процесс применения Gi закончился, то смотрим, пуст или нет ре

зультат;	в случае, когда	6 i (	^ > ) = r r A , применяем к Р алгорифм	Щи
в случае,	когда &i(P)=£	Л ,	применяем к Р алгорифм 6 2 и	т. д.

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

С л е д с т в и е

Пусть

$Ф — разрешимое

свойство

слов

в алфавите

А,

21, 53,

К —- нормальные

алгорифмы

над А. Можно построить нормальный

алгорифм

55 над

так,

что для

любого

слова

Р в

21 (Р), если

слово

обладает

свойством

S4-,

23 (Р), если

слово

Р не обладает

свойством S4-.

С л е д с т в и е

Пусть

s4-u...,

Жп

—разрешимые

свойства

слов

алфавите

А,

210

21„ —

нормальные

алгорифмы

над

А.

Можно

построить

нормальный

алгорифм

над А

так,

что при

любом

слове

Р в

выполняется

•

\{Р)<

если

не

обладает

ни

одним

из

свойств

s4-i (1 <

i <

п),

21, (Р),

если

обладает

свойством

s4-x,

212 (Р),

если

не

обладает

свойством

six

обладает

свойством

М2,

21„(Р),

если

не

обладает

свойствами

М[

(I г О ' ^ п

— 1) и обладает свойством

s£n.

4) Т е о р е м а п о в т о р е н и я . О п е р а т о р

н а и

м е н ь ш е г о ч и с л а . З а д а н и е н о р м а л ь н ы х а л г о р и ф м о в р е к у р с и е й . Во многих случаях возни кает необходимость в итерации некоторого процесса до тех пор, пока получающийся результат не удовлетворит определенному условию. Например, таким повторяемым процессом может быть прибавление единицы к нату ральному числу, а проверяемым условием — свойство натурального числа быть большим, скажем, пяти. В слу чае, когда рассматриваемый процесс есть словарный алгорифм 2Т, а условие является алгорифмически про веряемым, можно сформулировать следующее алгорифмическое предписание (рис. 5): применить к исходному

слову	Р алгорифм 21, проверить, обладает	ли результат
21 (Р)	(если, конечно, 21 применим к Р)	нужным свой

ством; при положительном исходе этой проверки обо

рвать переработку	слова Р	и считать	21 (Р)	результатом,
при отрицательном	исходе	перейти к	слову	21 (Р) и по
ступить с ним так	же, как	и с Р, и т. д.

78 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА [ГЛ. 1

Т е о р е м а 9 ( М а р к о в			[2;	гл. 3,	§	6]).	Каковы	бы
ни были	нормальные	алгорифмы		%	и	33,	может быть
построен	нормальный	алгорифм		S над		объединением		А
	21	21 (Р)	ПроВврш			А Выполнено
			услооая d				ВыхоВ

d не Выполнено

Рис . 5. Повторение нормального алгорифма.

их	алфавитов		такой,	что (5		перерабатывает		произволь
ное	слово	Р е	А в слово		Q	тогда и	только	тогда, когда
существует		ряд	слов	Р0,	...,	Рп (п>	0) со	следующими
свойствами:
(51)			Р^Р,
(52)			Я, =	Я(Р,_,)		( 0 < / < л ) ,

(53)P„==Q,

(54)

ЯЭ(Р,)=5#Л

(0 < / < / * ) ,

(55)2 3 ( Р „ ) ^ Л .

Иногда, прежде чем применять к данному слову алгорифм 21, оказывается целесообразным проверить,

Р	Проверка	& не Выполнено	21
	i/слоВия <А

J d Выполнено

Выход

Рис. 6. Видоизмененное повторение нормального алгорифма.

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

i I ]

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

Т е о р е м а

10 ( М а р к о в

[2; гл. 3, § 6]). Каковы

бы

ни

были

нормальные

алгорифмы

и 23,

можно

по

строить нормальный

алгорифм

над

объединением

их

алфавитов

такой,

что

перерабатывает

произволь

ное

слово

Р е

А в

слово

тогда и только

тогда,

когда

существует ряд слов Р0, ...,

Рп

(п ^

0),

удовлетворяю

щий условиям

(51) — (53), (55)

условию

5 3 ( Л - ) # Л

(0 < / < п).

Про

алгорифм

(5, построенный

согласно

теореме 9

(теореме 10), будем говорить, что он является повто

рением (видоизмененным	повторением)	алгорифма 51,
управляемым алгорифмом 23.
Теорема повторения	позволяет задавать нормальные

алгорифмы при помощи таких хорошо известных из


теории		рекурсивных			функций средств,			как	ц-оператор
и	примитивная рекурсия.
	Пусть si—			некоторое свойство натуральных чисел*).
Обозначим			через
(56)					\ins4- (п)
наименьшее				натуральное число,			обладающее		свойством
si.	В случае,			когда	свойство	si	не выполняется ни для
какого		натурального			числа,	выражение		(56)	считается
лишенным			смысла.
	С двухместным алгорифмически проверяемым отно
шением		si	можно связать следующее					алгорифмическое

предписание: для данного исходного слова Р последо

вательно проверять si(P,0),				si(P,l)	и т. д. до обнару
жения	числа	k, при	котором первый		раз	выполнится
si(P,k);	это	число	считать	результатом.		Возможность

оформления такого предписания в виде нормального


алгорифма		(при		условии,	что		мы	имеем	нормальный
алгорифм,		проверяющий			отношение			si)	вытекает из
следующей		теоремы (в теоремах					11 —12 А — произволь
ный	алфавит,		а — некоторая			не	принадлежащая				алфа
виту А 0 {0\|} буква).
Т е о р е м а			11	(ср. Ц е й т и н			[5;	стр. 304]).		По	вся
кому	нормальному			алгорифму		51 над		алфавитом			А[){а}
*) Напомним, что под натуральными								числами	мы	понимаем
слова	в алфавите		{0\|} вида 0, 0\|,		0\| \|	и	т. д.

80	АЛГОРИФМЫ И		ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА			[ГЛ. 1
можно	построить	нормальный алгорифм			23 над	алфави
том A U {0\|} так, что для любого				слова	Р в алфавите А
выполняется: если		при	каждом	натуральном		i
(57)			151 (Poi),
то

(58)3 3 ( Р ) ~ ц я ( Я ( Р < т ) = = Л ) .

Д о к а з а т е л ь с т в о . Обозначим через 23i такой нормальный алгорифм, что для любого слова Q в ал фавите A U {а0|}

» . ( Q ) = 5 = QI

(см. пример 8) п. 4). По теореме 10 построим алго рифм 232, являющийся видоизмененным повторением ал горифма 33], управляемым алгорифмом 91. Тогда для любого Р е Л, удовлетворяющего условию (57), будет выполняться

	932(РоО) са Рацп{%{Pan)			== Л) .
Легко построить алгорифм 933			так, что
	2 3 3 ( Р ) ~ 932 (Ра0).
Искомый алгорифм 93 строим теперь как компози
цию алгорифмов 933 и		«высекающего» алгорифма В2
(стр. 72)	. Очевидно, при	выполнении		(57)
93	(Р) ~ В2(233 (Р)) ~ В2(Pa[in		(21 (Pan) == Л)).
Следовательно,
	93(Р)~цп(21 (Pan)		=	Л),

т.е. выполняется (58), что и требуется.

Те о р е м а 12 (определение нормального алгорифма при помощи примитивной рекурсии). Пусть 91 и 23 —


нормальные		алгорифмы			соответственно		над	алфавитами
А и Ai	=	А [) {0\а}.		Можно		построить	нормальный		ал
горифм	(S	над	А\ так,		что при любом		слове	Р в	алфа
вите А	и любом		натуральном			числе m
			S(Pa0)~9t(P),
		© (Pam		+	1) ~ 93 (PamaS (Paw)).

НОРМАЛЬНЫЕ АЛГОРИФМЫ

Наметим доказательство этой теоремы. Обозначим через £)i такой нормальный алгорифм над А\, что при любых натуральных тип

!£>i {man)

£), (man) === Л = «J =?= «•
(Такой алгорифм,	распознающий	графическое	равен
ство, был построен	выше (стр. 74).)	Применяя	теоремы

композиции и объединения к алгорифму £>i и «высекаю щим» алгорифмам В2, Вц (см. стр. 72), легко построить нормальный алгорифм Ф 2 (над Ах) так, что при любых словах Р и Q в А и любых натуральных т, п

I5D2 (PamaQan)

(59)3)2 (PamaQan) = Л == m = п.

Аналогично, нетрудно построить алгорифм Ф 3 так,

что

(60)2>3 (PamaQan) ~ РатаЪ (PanaQ) an |.

Построим теперь нормальный алгорифм 3?4 как ви доизмененное повторение 5)3 с управляющим алгориф мом ф 2 (теорема 10) и рассмотрим композицию Фв этого алгорифма с алгорифмом 2D5 таким, что

S)s (Pam) ~ Pamal (Р) a0

Таким образом,

(61)	£>6 (Рат) ~		© 4	(3)5 (Pam)) ~ 5Е)4 (РатаЭД (Р) аО).
Ввиду		(59) -	(61)
(62)	© 6	(РаО) ~	Ф4	(РаОаЯ (Р) аО) ~ PaOal (Р) аО.

При т > 0 применимость £>6 к слову Рат равно сильна существованию цепочки слов Р 0 , Р\, ..., Рт та кой, что

(63)	Л,=г=я(Я),
(64)	p i + I == 33 (PaiaPi)	(0 ^ i < m),

<<< < Предыдущая 1 2 3 4 5 6 78 / 458 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ

#
29.10.20235.79 Mб13Куцый П.Ф. Повелители молний.pdf
#
25.10.202312.79 Mб19Кучко А.С. Аэрофотография. Основы и метрология.pdf
#
25.10.202318.43 Mб47Кушманов И.В. Электронные приборы учеб. пособие.pdf
#
27.10.202319.55 Mб11Кушнарев Д.М. Использование энергии взрыва в строительстве.pdf
#
19.10.20232.48 Mб24Кушнарев, Ю. М. Авторулевой Печора учебное пособие для студентов судоводительского факультета.pdf
#
22.10.202314.87 Mб19Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf
#
24.10.202311.94 Mб20Кушнерев Н.Т. Программирование для ЭВМ Минск-32.pdf
#
25.10.202312.78 Mб21Кушнирская М.Ц. Крашение древесины в производстве мебели.pdf
#
27.10.202320 Mб7Кэтермоул К.В. Принципы импульсно-кодовой модуляции.pdf
#
23.10.20234.75 Mб13Лабинский Ю.В. Корабельные ядерные реакторы учеб. пособие.pdf
#
23.10.20238.6 Mб4Лабозин П.Г. Качество крупнопанельного домостроения.pdf