В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 5
Текст из файла (страница 5)
В начале алгоритма они соответствуют левому и правому крайним элементаммассива. Будем двигать i слева вправо, если порядок следования текущего слева (a[i]) иопорного (p) – «правильный» (т.е., a[i] < p). Будем двигать j справа влево, если порядок следования опорного (p) и текущего справа (a[j]) – «правильный» (т.е., p < a[j]).Остановка может произойти либо на опорном элементе (всё, что находится с этой стороныстоит «правильно» по отношению к опорному), либо на «неправильно» стоящем элементе.Если позиции индексов различаются – меняем величины местами и продолжаем движение– вплоть до «смыкания» индексов. Кстати, индексы тогда будут равны как раз (новой)позиции опорного элемента...После всех перестановок при «сближении» индексов массив разделён на два подмассива, водном сосредоточены элементы, не превышающие опорный, во втором – не меньшие, чемон.
В хорошем случае эти два подмассива не вырожденные, в «плохом» – один из них пустили содержит «мало» элементов.К этим подмассивам применяем такую же процедуру разделения, выбирая для каждогоподмассива свой опорный элемент. В результате элементы этих подмассивов будут перегруппированы относительно своих опорных элементов и почти (в «хорошем» случае) вдвоеменьше по размеру.Идеально было бы иметь в качестве опорного элемента в каждом случае некое среднеезначение по этому массиву, но сделать это невозможно без некоторой сортировки, а потомуопорным часто выбирается просто средний элемент.22void QuickSort(int a[], int l, int r){int i = l, j = r, p = a[(l + r)/2];}while (i <= j) {while (Less(a[i],p))i++;while (Less(p,a[j]))j--;if (i <= j) {Swap(a[i],a[j]);i++; j--;}}if (l < j)QuickSort(a,l,j);if (i < r)QuickSort(a,i,r);Встречные индексы i и j «пропускают» правильно расположенные элементы и «останавливаются» на расположенных неправильно либо на опорных значениях.
После «остановки»обоих индексов соответствующие им значения обмениваются местами, а каждый из индексов делает следующий шаг. Так продолжается до тех пор, пока индексы не «поменяютсяместами» (бывший больший станет меньше бывшего меньшего). После чего эта процедура повторяется для двух фрагментов изначального массива, причём только если размерфрагментов – более одного элемента.236.Метод Монте-КарлоЭто – общее название группы методов, основанных на получении большого числа реализаций случайного процесса, который подобран так, чтобы его вероятностные характеристикисовпадали с искомыми величинами решаемой задачи. При этом вычисление точного значениякакой-то величины заменяется оценкой соответствующих вероятностных характеристик.Для пояснения этих слов (возможно, не совсем понятных сейчас) рассмотрим уже знакомый нам пример с вычислением определённого интеграла – но немного с другой стороны.Поскольку большая часть сведений, излагаемых здесь, только станет известна при будущемизучении теории вероятностей и математической статистики, мы будем вынуждены ограничиваться фактами и утверждениями, которые либо кажутся интуитивно понятными, либо вкаком-то виде уже известны.
Поэтому многие термины, определяемые только в рамках этихбудущих дисциплин, используются здесь без обоснования и часто даже без определения.Вычисление определённого интеграла функции () на отрезке [, ], проделанное ранее,можно попытаться реализовать и по-другому. Ведь площадь под графиком функции наотрезке является равновеликой площади прямоугольника, одна сторона которого – самотрезок, а вторая – некоторое «среднее» значение функции () на этом интервале. Мыможем определить это среднее значение, зная величину интеграла, но если бы мы егоузнали каким-то другим образом, то величину интеграла можно было бы определить поэтому среднему, просто умножая его на длину отрезка!Как же найти это «среднее» значение? Предположим, что мы случайным образом получаем некое количество точек этого отрезка , = 1, ..., .
Эти точки соответствуютзначениям некоторой случайной величины u (здесь мы делаем различие между обозначением случайной величины (u) и её отдельными значениями ( )). Если случайные точки«разбросаны» по отрезку более или менее равномерно (о подобных случайных величинахпринято говорить, что они имеют равномерное распределение на этом отрезке), то средислучайных значений ( ) функции () все её возможные значения будут представленыдостаточно равноправно. Новая случайная величина (u) (как, впрочем, и любые другие случайные величины) имеет такую характеристику, как математическое ожидание,M (u), причём известно, что оно (мат.
ожидание) может быть определено на основе плотности распределения () случайной величины:∫︁M (u) = ()() Как известно, для равномерно распределённой на отрезке [, ] случайной величины плотность её распределения равна:{︃() =1,−0,поэтому ∈ [, ] ̸∈ [, ]1 ∫︁M (u) = () .− Видно, что математическое ожидание случайной величины (u), где u – равномерно распределённая случайная величина, и есть то самое неизвестное нам «среднее» значениефункции () на отрезке [, ]. Но для случайных величин существует возможность эмпирического определения (оценки) их неизвестного мат. ожидания – с помощью значения«выборочного среднего»:1 ∑︁M (u) ≈ ( ), =124откуда∫︁ () ≈ − ∑︁ ( ).
=1Возвращаясь к пояснению слов, сказанных ранее по поводу сути метода Монте-Карло,можно отметить, что в приведённом примере мы воспользовались взаимосвязью значениянужного нам определённого интеграла с математическим ожиданием некоторой случайнойвеличины, а само мат. ожидание попытались оценить по полученной выборке её значений.С точки зрения формулы мы не получили вроде бы ничего нового: формула неотличима отформулы центральных прямоугольников, но на самом деле точки, в которых вычисляютсязначения функции, расположены не в равномерной сетке, а случайным образом, так чтозначения их координат имеют равномерное распределение на отрезке [, ].Разумеется, возникновение подобных численных методов решения математических задачпри помощи моделирования случайных величин обусловлено развитием вычислительнойтехники.Ошибка оценки пропорциональна обратной величине корня квадратного из числа испытаний,т.е., для того чтобы уменьшить ошибку в 10 раз, надо увеличить число испытаний (т.е., объёмработы) в 100 раз.
Понятно, что таким способом добиться высокой точности невозможно,поэтому метод Монте-Карло особенно эффективен при решении задач, где результат нужен снебольшой точностью (∼ 5 − 10%).Правда теперь, поскольку мы должны при вычислениях использовать случайную величинус равномерным распределением, встаёт проблема получения значений такой величины.6.1.Определение площадей (объёмов) фигурПредположим, что надо определить площадь некоторой ограниченной фигуры. Если случайным образом «набросать» точек в квадрат, содержащий фигуру, то количество точек,попавших в неё, будет примерно пропорционально её площади.
Т.е., отыскание отношенияплощадей (фигуры и квадрата) сводится к вычислению отношения двух чисел: количестваточек, попавших в фигуру, и общего количества точек. Точно так же можно попытатьсяопределить значение числа (см. далее).Аналогично можно оценивать объёмы трёхмерных фигур и фигур большей размерности. Вэтом и большинстве последующих примеров характеристикой, связанной с искомой величиной, является вероятность попадания случайной точки в фигуру. Эта вероятность оцениваетсяотношением числа благоприятных исходов бросания к их общему числу.
Лишь в примере сиглой Бюффона (см. далее) оценивается вероятность немного другого события.Достаточно очевидно, что такие «вычислительные» методы будут работать тогда, когдаточки будут «равномерно разбросанными» по прямоугольнику (по параллелепипеду), т.е.,случайная величина, которой мы будем пользоваться, будет равномерно распределённой вдвух, трёх или более измерениях. Однако, не все генераторы псевдослучайных чисел могут«подходить» для этой цели.256.2.Вычисление числа Попробуем применить изложенные идеи для вычисления числа , поскольку оно входит в значение площади известной фигуры: круга.Будем бросать случайные точки на квадрат, в который вписан круг.
Площадь квадрата – это диаметр(два радиуса) круга в квадрате (42 ). Площадь круга – произведение на квадрат радиуса круга (2 ).Отношение числа точек, попавших в круг, к общемучислу точек в квадрате, оценивает величину 4 .Существует ещё один известный способ вычислениячисла – так называемый метод иглы Бюффона. Суть его заключается в следующем.
На разлинованную равноудалёнными параллельными прямымиплоскость произвольно бросается игла, длина которой равна расстоянию между соседними прямыми, так что при каждом бросании игла либоне пересекает прямые, либо пересекает ровно одну. Можно доказать, что отношение числа пересечений иглы с какой-нибудь линией к общему числу бросков стремится к 2 приувеличении числа бросков до бесконечности.6.3.Численное интегрирование методом Монте-КарлоЕщё один вариант численного интегрирования почти не отличается от способа определения площадей фигур на плоскости и объёмов в пространстве (см. изложенное выше),поэтому также применим для вычисления многократных интегралов. Выбирается область,содержащая полностью значения интегрируемой функции, причём для простоты её лучше выбрать параллелепипедом нужной размерности.
В этот параллелепипед случайнымобразом бросается достаточное количество точек, а затем оценка вычисляемого интегралаполучается как произведение объёма параллелепипеда на отношение числа точек, попавших в область интегрирования, к общему числу точек. Однократные интегралы на практике методом Монте-Карло не вычисляют, для этого есть более точные методы. А вот припереходе к многократным интегралам ситуация меняется: аналоги формул однократного интегрирования становятся значительно более сложными, а метод Монте-Карло – чтовесьма существенно – остаётся практически без изменений.6.4.Получение случайных чиселСпособов получения случайных величин (или подобных им), в сущности, не так много.Можно попытаться использовать какие-то физические эффекты (скажем, шумы в полупроводниках) или предметы (монета, игральная кость, вращающийся барабан с цифрами и неподвижной стрелкой), где получаемое значение зависит от такого большого числафакторов, что предвидеть его просто невозможно. Однако такие способы, во-первых, бывает сложно сопрягать с устройством, которое может применяться для вычислений, а,во-вторых, не всегда они позволяют получить необходимую скорость формирования случайных значений.Можно построить специальные таблицы случайных величин или использовать уже гото26вые.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
