Previous Page  10 / 13 Next Page
Information
Show Menu
Previous Page 10 / 13 Next Page
Page Background

Опишем намеченную процедуру подробно. Для каждого автома-

та

G

s

указанное слово

α

=

α

(1)

α

(2)

. . .

дает путь

a

s

(1)

a

s

(2)

. . .

Обозначим через

D

s

множество натуральных чисел

i

, для которых

ребро

a

s

(

i

)

a

s

(

i

+ 1)

лежит в множестве

Q

0

s

.

Известно, если

i

D

s

,

то в момент

i

автомат

G

s

выдает прогноз

β

s

(

i

)

; если

i /

D

s

, то

в момент

i

автомат не дает никакого прогноза. Введем функцию

k

7

Φ(

k

)

, k

= 1

,

2

, . . .

, по следующему правилу: для каждого

k

рас-

смотрим такие

s

, для которых числа

k, k

1

, . . . , k

R

входят в

множество

D

s

. Другими словами, выбираются те автоматы, которые

давали прогноз от момента

k

R

до момента

k

. Наименьший из таких

номеров

s

обозначим через

Φ(

k

)

. Итак, равенство

Φ(

k

) =

i

означает

следующее: во-первых, множество чисел

{

k

R, . . . , k

}

содержится в

множестве

D

i

, во-вторых, указанное множество чисел не содержится

в множестве

D

i

0

при

i

0

< i

. Функция

Φ

построена. Отметим ее свой-

ство, которое следует из ее определения и будет использовано далее:

если для некоторого

i

числа

{

k

R, . . . , k

}

входят в множество

D

i

,

то

Φ(

k

)

i

. Наконец, взяв автомат с найденным номером

i

= Φ(

k

)

,

возьмем выданный им (в момент

k

) прогноз

β

i

(

k

)

. В результате для

угадывания слова

α

=

α

(1)

α

(2)

. . .

получили цепочку прогнозов

β

(

k

) =

g

i

(

k

)

, k

= 1

,

2

, . . . , i

= Φ(

k

)

.

(4)

В цепочке (4) возможны пропуски (отмечаем их черточками), так как

для некоторых

k

величина

Φ(

k

)

может быть не определена. Образно

говоря, в каждый момент времени

k

каждый

m

-й автомат пытается

угадать символ

α

(

k

+ 1)

нашего слова; но из всех прогнозов отбира-

ется прогоз, выданный автоматом с наименьшим номером, который

угадывал (возможно, не всегда удачно) в моменты времени от

k

R

до

k

(без прерываний).

Теорема 2.

1. Функция

k

Φ(

k

)

определена при

k > k

0

,

где

k

0

постоянная

,

зависящая от

α

. 2. Пусть число

R

выбрано так

,

что

R >

4

mT

i

для всех

i

= 1

, . . . , m

.

Тогда последовательность (4) дает

процесс частичного угадывания с интервалом угадывания

R

.

J

Докажем первое утверждение теоремы. По условию

α

L

s

=

=

L

(

q

0

s

, Q

s

, Q

0

s

)

для некоторого

s

. Поскольку

lim

α

=

Q

0

s

, соответству-

ющий путь в орграфе

G

s

полностью лежит в

Q

0

s

, начиная с некоторого

момента

k

0

. Следовательно, числа

k, k

1

, . . . , k

R

принадлежат мно-

жеству

Q

0

s

для всех

k > k

0

, если число

k

0

достаточно велико. Поэтому

функция определена при

k > k

0

.

Доказательство второго утверждения теоремы 2 требует некоторых

приготовлений. Число

k > k

0

назовем точкой скачка функции

Φ

при

Φ(

k

)

6

= Φ(

k

+ 1)

.

Лемма 6.

В любом отрезке длиной

R

имеется не более

2

m

точек

скачка.

12

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2