Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 19
Текст из файла (страница 19)
Но иногда речь может идти только о доказательстве завершимости работы алгоритма — тогда характер ростафункции L отходит на второй план. То, что выполнение алгоритма Евклида завершается, было доказано в самом начале обсуждения этогоалгоритма без обращения к функциям с логарифмическим ростом.Пример .. Алгоритм, заданный оператором циклаwhile n > 3 doif 2 | n then n := n2 + 1 else n := n + 1 fiod(запись 2 | n означает, что n делится на 2) завершает свою работудля любого натурального n.
Для доказательства достаточно рассмотреть функцию n − (−1)n и убедиться в ее убывании при n > 3 в ходевыполнения алгоритма.Пример .. Если n — данное неотрицательное целое число, тозавершимость выполнения алгоритмаs := 0;for i = 1 to n do s := s + 1i odочевидна — выполнение оператора цикла завершится после n шагов;легко видеть, что при выполнении этого оператора значение L(n, i) == n − i убывает, оставаясь при этом неотрицательным целым.В доказательствах завершимости, основанных на подборе подходящей убывающей целочисленной функции, используется следующеесвойство множества N неотрицательных целых чисел:Не существует бесконечной убывающей последовательности n0 >> n1 > n2 > ... элементов множества N.Имеются и другие примеры (частично) упорядоченных множествс этим свойством, и соответствующие порядки используются для доказательства завершимости выполнения алгоритмов .Вместо сложных примеров, мы адресуем читателя к задачам , , заимствованным из [, разд.
.]. В книге [] кроме двух названных задач содержится интересныйи полезный материал о частично упорядоченных множествах и некоторых специальных типах таких множеств. (Решения задач , не обязательно должны содержатьявные упоминания порядков на множествах, хотя введение некоторых порядков полностью проясняет ситуацию.)§ . Завершимость работы алгоритмаУстановление завершимости выполнения алгоритма иногда оказывается очень трудной задачей.Пример .. Завершимость для любого натурального n выполнения алгоритмаwhile n > 1 doif 2 | n then n := n2 else n := 3n + 1 fiodне доказана и не опровергнута по сей день, хотя на это направлялисьсерьезные усилия (см. []).В случае рандомизированных алгоритмов мы сталкиваемся(см.
ниже пример . и первую часть примера .) с возможностьютого, что алгоритм завершается с вероятностью 1, но математическоеожидание времени от начала выполнения до полного завершенияалгоритма бесконечно. Поэтому утверждения о завершимости возможны в двух формах: завершимость с вероятностью 1 и конечностьожидаемого времени выполнения. Вторая форма является, вообщеговоря, более сильной.Пример .. В теории вероятностей подробно рассматриваетсязадача о блуждании частицы по прямой: за один шаг частица передвигается на 1 вправо или на то же расстояние влево, направление же движения на каждом шаге выбирается случайно, вероятно1сти выбора каждого из направлений одинаковы и равны .
Пусть2в начальный момент частица находится в точке 0, и на прямой отмечена некоторая точка m с целой координатой. Доказывается, чтос вероятностью 1 частица через некоторое время попадает в точку m.Попытаемся теперь вычислить математическое ожидание a времени(общего числа шагов), которое потребуется для достижения точки m.Легко убедиться, что уже в случае m = ±1 это среднее бесконечно.Пусть, например, m = 1. Используем формулу полного математического ожидания: если шаг сделан вправо, то за этот один шаг мыдостигаем цели, если же шаг сделан влево, то придется дождатьсямомента, когда частица вернется в точку 0 и тем самым повторитсяначальная ситуация:a=1·11+ 2a · .221Если бы a было конечным, это бы дало 0 = . Поэтому среднее бес2конечно.Глава . Оценивание числа шагов (итераций) алгоритмаРассмотрим с этой точки зрения задачу .
Итак, путник столкнулся со стеной, простирающейся бесконечно в обе стороны. Имеетсядверь в этой стене, но путник не знает ни расстояния до двери, нинаправления к ней. Если путник использует алгоритм поиска двери,состоящий в бросании перед каждым шагом монеты для определениянаправления (вправо или влево) этого шага, то он с вероятностью 1найдет дверь, но математическое ожидание числа шагов равно бесконечности, коль скоро в начальный момент путник не стоит прямоперед дверью.
Иными словами, если pk (k ¾ 1) есть вероятность того,что после k шагов путник впервые окажется перед дверью, то∞Xk =1pk = 1 и∞Xkpk = ∞.k =1Пример .. Обратимся к системам автоматизированного обучения. При использовании известного педагогического приема — задания вопросов вразбивку — с каждым выбранным системой вопросомможет быть связана следующая цепочка действий: вопрос обучаемому; прием и проверка ответа; сообщение, правилен ли ответ и объявление правильного ответа, если был дан неправильный ответ. Нетрудно привести примеры учебных тем, когда такой подход выглядит разумно: таблица умножения, исторические даты, иностранные слова(здесь же — неправильные глаголы), значения иероглифов, названиесозвездий (показываются картинки), определение на слух музыкальных интервалов и т.
д. Прообразом одного из алгоритмов выбора вопросов служит способ заучивания ответов с помощью колоды карточек, на лицевой стороне каждой из которых написан вопрос, а наобороте — ответ. Из колоды выбирается наугад карточка, и делается попытка ответить на вопрос. Если это не удается, ответ прочитывается на обороте. Затем карточка возвращается в колоду, и всеповторяется.
На примере колоды карточек предлагаемый рандомизированный алгоритм (называемый алгоритмом кратных карт ) можетбыть проинтерпретирован так: выбранная карточка, содержащая вопрос с известным обучаемому ответом, уже не возвращается в колоду; если же обучаемый не смог дать правильный ответ, то, крометого что в колоду возвращается эта карточка, туда добавляется ещеодин ее экземпляр.
Сеанс обучения заканчивается, когда в колоде неостается карточек.Пусть вопросы занумерованы числами 1, 2, ..., n. Каждый этапсеанса обучения характеризуется кратностями m1 , m2 , ..., mn вопроСм. [].§ . Завершимость работы алгоритмасов (не исключается равенство нулю каких-то кратностей); пустьm = m1 + m2 + ...
+ mn . Если m = 0, то сеанс заканчивается, иначе выбирается очередной вопрос; вероятность того, что будет выбран i-йmвопрос, должна равняться i .mСеанс обучения становится бесконечным, если, например, с некоторого момента обучаемый начинает давать только неправильные ответы. Но можно интересоваться вероятностями и средним временеможидания некоторых событий в течение этого бесконечного сеанса.Пусть в некоторый момент только один вопрос, скажем, вопрос с номером , имеет кратность 1, а все остальные — кратности большие,чем 1. Предположим, что начиная с этого момента обучаемый стабильно дает неправильные ответы на предлагаемые вопросы. Найдемвероятность того, что рано или поздно обучаемый получит вопросс номером , а также математическое ожидание времени, проходящего до появления этого вопроса (время измеряется количеством заданных вопросов).
Пусть m — суммарная кратность, а n — общее числовопросов, m > n ¾ 2. Вероятность получить вопрос с номером после1i вопросов с другими номерами равна , если i = 0, и равнаmm−1mm+i−21m−1·...·=,mm+1m+i−1 m+i(m + i − 1)(m + i)если i ¾ 1. Поэтому вероятность получить рано или поздно вопросс номером равна1+ (m − 1)mТак как∞Xi =11.(m + i − 1)(m + i)(.)111=−,(m + i − 1)(m + i)m+i−1m+iто для частичной суммыsN =NXi =11(m + i − 1)(m + i)имеемsN =и lim s N =n→∞11−,mm+N1, откуда значение выражения (.) (искомая вероятmность) есть1m−1+= 1.mmГлава . Оценивание числа шагов (итераций) алгоритмаМатематическое ожидание времени есть(m − 1)∞Xi =1i.(m + i − 1)(m + i)(.)∞Piрасходится: члены этого ряда поло(m + i − 1)(m + i) 11жительны, и i-й член есть Θ(является величиной порядка ).iiПри этом рядi =1Отсюда математическое ожидание (.) равно бесконечности.Пусть теперь u вопросов (будем считать, что это вопросы с номерами 1, 2, ..., u) имеют кратность 1, а остальные n − u вопросов — кратность большую, чем 1, и пусть u ¾ 2.
Оказывается, что пристабильных неправильных ответах обучаемого на задаваемые вопросы математическое ожидание времени, проходящего до получениявсех, кроме какого-то одного, вопросов с номерами 1, 2, ..., u, естьконечная величина. Докажем конечность среднего времени ожидания какого-нибудь одного вопроса с номером от 1 до u, далее можноприменить индукцию. Вероятность получить такого рода вопрос после i вопросов с номерами из диапазона от u + 1 до n полностьюопределяется значениями u, m, i:m−u+i−1um−u m−u+1·...·.mm+1m+i−1m+iЭта вероятность при i > u равнаu(m − u)(m − u + 1)...(m − 1).(m − u + i)(m − u + i + 1)...(m + i − 1)(m + i)Поэтому искомое математическое ожидание есть сумма некоторогоконечного числа слагаемых и ряда∞Xi = u +1u(m − u)(m − u + 1)...(m − 1)(i + 1),(m − u + i)(m − u + i + 1)...(m + i − 1)(m + i)илиu(m − u)(m − u + 1)...(m − 1)∞Xi = u +1i+1.(m − u + i)(m − u + i + 1)...(m + i)Упрощая, получаемu(m − u)(m − u + 1)...(m − 1)∞Xj =1j +u+1.( j + m)( j + m + 1)...( j + m + u)§ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
