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

91

Установление завершимости выполнения алгоритма иногда ока­зывается очень трудной задачей.

Пример 11.3. Завершимость для любого натурального п выполне­ния алгоритма

while п>1 do

if 2\п then n:=^ else n:=3n + 1 fi od

не доказана и не опровергнута по сей день, хотя на это направлялись серьезные усилия (см. [53]).

В случае рандомизированных алгоритмов мы сталкиваемся (см. ниже пример 11.4 и первую часть примера 11.5) с возможностью того, что алгоритм завершается с вероятностью 1, но математическое ожидание времени от начала выполнения до полного завершения алгоритма бесконечно. Поэтому утверждения о завершимости воз­можны в двух формах: завершимость с вероятностью 1 и конечность ожидаемого времени выполнения. Вторая форма является, вообще говоря, более сильной.

Пример 11.4. В теории вероятностей подробно рассматривается задача о блуждании частицы по прямой: за один шаг частица пе­редвигается на 1 вправо или на то же расстояние влево, направле­ние же движения на каждом шаге выбирается случайно, вероятно­сти выбора каждого из направлений одинаковы и равны ¹₂. Пусть в начальный момент частица находится в точке 0, и на прямой от­мечена некоторая точка т с целой координатой. Доказывается, что с вероятностью 1 частица через некоторое время попадает в точку т. Попытаемся теперь вычислить математическое ожидание а времени (общего числа шагов), которое потребуется для достижения точки т. Легко убедиться, что уже в случае т = ±1 это среднее бесконечно. Пусть, например, т = 1. Используем формулу полного математиче­ского ожидания: если шаг сделан вправо, то за этот один шаг мы достигаем цели, если же шаг сделан влево, то придется дождаться момента, когда частица вернется в точку 0 и тем самым повторится начальная ситуация:

а = 1-¹₂ + 2а-₂¹.

Если бы а было конечным, это бы дало 0 = ¹₂. Поэтому среднее бес­конечно.

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

Рассмотрим с этой точки зрения задачу 17. Итак, путник столкнул­ся со стеной, простирающейся бесконечно в обе стороны. Имеется дверь в этой стене, но путник не знает ни расстояния до двери, ни направления к ней. Если путник использует алгоритм поиска двери, состоящий в бросании перед каждым шагом монеты для определения направления (вправо или влево) этого шага, то он с вероятностью 1 найдет дверь, но математическое ожидание числа шагов равно бес­конечности, коль скоро в начальный момент путник не стоит прямо перед дверью. Иными словами, если p_k (k ^ 1) есть вероятность того, что после k шагов путник впервые окажется перед дверью, то

со со

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

k=1 k =1

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

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

См. [3].