Т-t—t (m + i- l)(m + 0

Со

Т

Т

Со со

V p_k = 1 и /_t kp_k = до.

k =1 k =1

Пример 11.5. Обратимся к системам автоматизированного обуче­ния. При использовании известного педагогического приема — зада­ния вопросов вразбивку —с каждым выбранным системой вопросом может быть связана следующая цепочка действий: вопрос обучаемо­му; прием и проверка ответа; сообщение, правилен ли ответ и объяв­ление правильного ответа, если был дан неправильный ответ. Нетруд­но привести примеры учебных тем, когда такой подход выглядит ра­зумно: таблица умножения, исторические даты, иностранные слова (здесь же —неправильные глаголы), значения иероглифов, название созвездий (показываются картинки), определение на слух музыкаль­ных интервалов и т. д. Прообразом одного из алгоритмов выбора во­просов служит способ заучивания ответов с помощью колоды карто­чек, на лицевой стороне каждой из которых написан вопрос, а на обороте — ответ. Из колоды выбирается наугад карточка, и делает­ся попытка ответить на вопрос. Если это не удается, ответ прочи­тывается на обороте. Затем карточка возвращается в колоду, и все повторяется. На примере колоды карточек предлагаемый рандомизи­рованный алгоритм (называемый алгоритмом кратных карт ^х) может быть проинтерпретирован так: выбранная карточка, содержащая во­прос с известным обучаемому ответом, уже не возвращается в ко­лоду; если же обучаемый не смог дать правильный ответ, то, кроме того что в колоду возвращается эта карточка, туда добавляется еще один ее экземпляр. Сеанс обучения заканчивается, когда в колоде не остается карточек.

Пусть вопросы занумерованы числами 1,2,..., n. Каждый этап сеанса обучения характеризуется кратностями m₁,m₂,...,m_n вопро-

См. [3].

§ 11. Завершимостъ работы алгоритма

сов (не исключается равенство нулю каких-то кратностей); пусть т = т_г + т ₂ + ■■■ + т_п. Если т = О, то сеанс заканчивается, иначе вы­бирается очередной вопрос; вероятность того, что будет выбран i -й

вопрос, должна равняться —.

Сеанс обучения становится бесконечным, если, например, с неко­торого момента обучаемый начинает давать только неправильные от­веты. Но можно интересоваться вероятностями и средним временем ожидания некоторых событий в течение этого бесконечного сеанса. Пусть в некоторый момент только один вопрос, скажем, вопрос с но­мером 1, имеет кратность 1, а все остальные — кратности большие, чем 1. Предположим, что начиная с этого момента обучаемый ста­бильно дает неправильные ответы на предлагаемые вопросы. Найдем вероятность того, что рано или поздно обучаемый получит вопрос с номером 1, а также математическое ожидание времени, проходяще­го до появления этого вопроса (время измеряется количеством задан­ных вопросов). Пусть т — суммарная кратность, а п — общее число вопросов, т > п ^ 2. Вероятность получить вопрос с номером 1 после

i вопросов с другими номерами равна —, если i = 0, и равна

т-\ т m + i-2 1 т - 1

----------. -------- ----- ---------------. -------- ш -------------------------------

т т + 1 '" m + i-1 m + i (m + i-l)(m + i)'

если i ^ 1. Поэтому вероятность получить рано или поздно вопрос с номером 1 равна

- + (т-1)Ут---------- ^4тт----- ^- (11.1)

Так как

1 11

zz —

(m + i -l)(m + i) m + i-1 m + i ' то для частичной суммы

%=Xi

(m + i -l)(m + i)

i = l

имеем

1 1

N m m + N '

и lim s_N = —, откуда значение выражения (11.1) (искомая вероят­ность) есть

m m

94 Глава 3. Оценивание числа шагов (итераций) алгоритма

Математическое ожидание времени есть

Дата добавления: 2014-01-11