Изменения

== Многопоточная сортировка слиянием ==Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.{{Определение|definition==Сортировка с однопоточным слиянием==Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую Пусть дан фиксированный граф <tex>G</tex> и правую части массива параллельнофиксированное число красок <tex>x</tex>. function mergeSortMT(array, left, right): mid = (left + right) Количество способов правильной <tex>x</tex>-раскраски графа <tex>G</ 2 tex> называется '''spawnхроматическим многочленом''' mergeSortMT. Обозначение: <tex>P(array, leftG, mid) mergeSortMT(array, mid + 1, rightx)</tex>. '''sync''' merge(array, left, mid, right)}}

В данном алгоритме оператор == Хроматический многочлен полного графа ==<tex>\mathrm P(K_{n},x)=x(x-1)...(x-n+1)=x^{\bf underline{spawnn}}</tex> запускает новый поток, а оператор так как первую вершину полного графа <tex>\mathrm K_{\bf {sync}n}</tex> ожидает завершения этого потока. Функция можно окрасить в любой из <tex>\mathrm {merge}x</tex> аналогична одноименной функции цветов, вторую — в любой из раздела [[Сортировка слиянием#оставшихся <tex>x-1</tex> цветов и т.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2|слияние двух массивов]]д.Очевидно, что если <tex>x</tex> меньше <tex>n<br/tex>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считатьто и многочлен равен <tex>0</tex>, что совершается так как один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: из его множителей <tex dpi="120">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)0</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br/>

==Многопоточное слияниеХроматический многочлен пустого графа ==Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в массив <tex dpi="120">A[left_{3} \dots right_P(O_{3n}]</tex>:[[Файл:MergeMT.png‎|430px|thumb|Слияние массивов]]# Убедимся, что размер <tex dpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex># Возьмем <tex dpi="120">x )= T[mid_{1}]</tex> - середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_^{2n}</tex> такое, что так как каждую из <tex dpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < xn</tex># вершин нулевого графа <tex dpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_O_{2n})</tex># можно независимо окрасить в любой из <tex dpi="120">A[mid_{3}] = x</tex># Сольем <tex dpi="120">T[right_{1} \dots mid_{1} - 1]цветов.<br /tex> и Примечание. Нулевой граф <tex dpi="120">T[right_{2} \dots mid_O_{2n}]</tex> в также можно обозначать <tex dpi="120">A[right_{3} \dots mid_overline{3} - 1]</tex># Сольем <tex dpi="120">T[mid_K_{1n} + 1 \dots right_{1}]</tex> и (дополнительный граф для полного графа <tex dpi="120">T[mid_{2} \dots right_K_{2n}]</tex> в <tex dpi="120">A[mid_{3} + 1 \dots right_{3}]</tex>).

===РеализацияХроматический многочлен дерева =={{Теорема|about= // если <tex dpi="120">right \leqslant left</tex> возвращает <tex dpiхроматический многочлен дерева|statement="120">left</tex> // если Граф <tex dpi="120">x \leqslant T[left]G</tex>, возвращает с <tex dpi="120">leftn</tex> // иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[leftвершинами является деревом тогда и только тогда, right]когда </tex> такойP(G, что <tex dpix)="120">array[i x(x-1)^{n- 1] < x}</tex>.|proof= integer binarySearch(xСначала покажем, array, left, right) // слияние что хроматический многочлен любого дерева <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и с <tex dpi="120">T[left_{2} \dots right_{2}]n</tex> в вершинами есть <tex dpi="120">A[left_{3} \dots right_{1} x(x- left_{1} + right_)^{2} n- left_{21}]</tex>.<br /> function mergeMT(T, leftДоказательство индукцией по числу <tex dpi="120">_{1}n</tex>, right. Для <tex dpi>n="120">_{1}</tex>, leftи <tex dpi>n="120">_{2}</tex>результат очевиден. Предположим, rightчто <tex dpi>P(T',x)="120">_x(x-1)^{n-2}</tex>, A, leftдля любого дерева <tex dpi="120">_{3}T'</tex>): nс количеством вершин равным <tex dpi="120">_{n-1}</tex> = right. Пусть <tex dpi="120">_{1}uv</tex> - left— ребро дерева <tex dpi="120">_{1}T</tex> + 1 n, такое что <tex dpi="120">_{2}v</tex> = rightявляется висячей вершиной. Хроматический многочлен дерева <tex dpi="120">_{2}T</tex> - leftбез ребра <tex dpi="120">_{2}uv</tex> + 1 '''if''' nравен <tex dpi>P(T/uv,x)="120">_x(x-1)^{1n-2}</tex> < nпо нашему предположению. Вершину <tex dpi="120">_{2}v</tex> swap(leftможно окрасить <tex dpi="120">_{x-1}</tex>способом, leftтак как её цвет должен только лишь отличаться от цвета вершины <tex dpi="120">_{2}u</tex>. Итого: <tex>P(T,x)=(x-1) swapP(right<tex dpiT/uv,x)="120">_x(x-1)^{n-1}</tex>, right.<tex dpi="120"br />_{2}<br /tex>) swap(nОбратно, пусть <tex dpi="120">_{1}G</tex>— граф, nу которого <tex dpi>P(G,x)="120">_x(x-1)^{2n-1}</tex>) '''if''' n<tex dpi="120">_{1}. Тогда верны два следующих утверждения:<br /tex> == 0 '''return''' '''else''' mid1. Граф <tex dpi="120">_{1}G</tex> = связен, потому что если было бы две компоненты связности (leftили больше), то <tex dpi="120">_{1}P(G,x)</tex> + rightделился бы на <tex dpi="120">_{1}x^2</tex>) без остатка.<br / >2 mid. В графе <tex dpi="120">_{2}G</tex> = binarySearch(T[midколичество рёбер равно <tex dpi="120">_{n-1}</tex>, так как по одной из теорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], Tтеорема 4), leftколичество рёбер в графе соответствует коэффициенту при <tex dpi="120">_x^{2n-1}</tex>, rightвзятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:<tex dpi="120"br />_{2}</tex>{P(G,x) mid<tex dpi="120">_x(x-1)^{3n-1}</tex> = x\left<tex dpi="120">_{3}</tex> + (mid<tex dpi="120">_x^{n-1}</tex> - left<tex dpi="120">_{n-1 \choose 1}</tex>) + (mid<tex dpi="120">_x^{n-2}</tex> +{n- left<tex dpi="120">_{1 \choose 2}</tex>) A[mid<tex dpi="120">_x^{n-3}</tex>] = T[mid<tex dpi="120">_{1}</tex>] '''spawn''' mergeMT-...+(T, left<tex dpi="120">_{-1}</tex>, mid<tex dpi="120">_)^{1}</tex> n- 1, left<tex dpi="120">_{2}</tex>, mid<tex dpi\right)="120">_x^{2n}</tex> -(n- 1, A, left<tex dpi="120">_{3}</tex>) mergeMT(T, mid<tex dpi="120">_x^{n-1}</tex> + ...+(-1, right<tex dpi="120">_)^{n-1}x}</tex>, mid<tex dpi="120">_{2}<br /tex>, rightИз этих двух утверждений (связность и <tex dpi="120">_{2}n-1</tex>ребро) следует, A, midчто граф <tex dpi="120">_{3}G</tex> + является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1и 3). '''sync'''}}

Оба массива содержат == Рекуррентные формулы для хроматических многочленов ==Будем обозначать за <tex dpi="120">n_{1} + n_{2} = nG/uv</tex> элементов. К моменту рекурсивных вызовов граф, полученный из графа <tex dpi="120">n_{2} \leqslant n_{1}G</tex>, значит,стягиванием ребра <tex>uv<br/tex>, то есть у которого вершины <tex dpi="135">n_{2} = 2 \cdot \frac{n_{2}}{2} \leqslant \frac{(n_{1} + n_{2})}{2} = \frac{n}{2}u</tex>.и <brtex>В худшем случае один из двух рекурсивных вызовов сольет v</tex dpi="135">\fracбудут отождествлены и при этом будут отброшены все петли и кратность ребер будет сведена к единице.{n_{1}}{2}Теорема|statement=Пусть <tex>u</tex> элементов и <tex dpi="120">T[left_{1} \dots right_{1}]v</tex> с - несмежные вершины графа <tex dpi="120">n_{2}G</tex> элементами . Если <tex dpi>G_1="120">T[left_{2} G\dots right_{2}]cup uv</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно, а <tex>G_2=G/uv<br/tex>, то <tex dpi="135">\frac{n_{1}}{2} + n_{2} \leqslant \frac{n_{1}}{2} + \frac{n_{2}}{2} + \frac{n_{2}}{2} P(G,x)= \frac{P(n_{1} G_1,x)+ n_{2}P(G_2,x)}{2} + \frac{n_{2}}{2} \leqslant \frac{n}{2} + \frac{n}{4} </tex>.|proof= \frac{3}{4}nРассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex>окрашены в разные цвета.Если добавить к графу <brtex>Асимптотика каждого вызова функции - G</tex> ребро <tex dpi="120">\Theta(\log n)uv</tex>, т.е. времято они не изменятся, затрачиваемое на бинарный поискто есть останутся правильными. Так как рекурсивные вызовы функции выполняются параллельноРассмотрим раскраски, а потоки при оценке независимыкоторых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это полученного из <tex dpi="120">T(\frac{3}{4}n)G</tex>. Тогда получим оценку сверхуслиянием вершин <tex>u<br/tex>и <tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)v</tex>.}}'''Замечание:'''Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.

==Сортировка с многопоточным слиянием=='''Следствие:'''Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы Хроматический многочлен любого графа <tex dpi="120">A[leftA \dots rightA]G</tex> и помещающего отсортированный массив равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе <tex dpi="120">B[leftB \dots leftB + rightA - leftA]G</tex>.

function mergeSortMT2(A, leftA, rightA, B, leftB):{{Теорема n |statement= r - p + 1 '''if''' n == 1 B[leftB] = A[leftA] '''else''' создадим новый массив T[1 Пусть <tex>u</tex> и <tex>v</tex> — смежные вершины графа <tex>G</tex>. Если <tex dpi>G_1="120">G\dotsbackslash uv</tex> n] mid и <tex>G_2= G/uv</tex>, то <tex>P(leftA + rightAG,x) / 2 newMid = mid - leftA + 1 '''spawn''' mergeSortMT2P(A, leftA, mid, TG_1, 1x) mergeSortMT2-P(A, mid + 1, rightA, TG_2, newMid + 1x)</tex>. '''sync'''|proof= mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)Следует из предыдущей теоремы.}}

Оценим данный алгоритм сверху при условии== Коэффициенты хроматического многочлена =={{Теорема|about=1|statement=Свободный член хроматического многочлена равен <tex>0</tex>.|proof=По определению хроматического многочлена графа <tex>G</tex>, что возможен запуск неограниченного количества независимых потоковего значение в точке <tex>x</tex> равно количеству способов раскрасить вершины <tex>G</tex> правильным образом в <tex>x</tex> цветов. Количество способов раскрасить граф в <tex>0</tex> цветов равно <tex>0</tex>. Из предыдущих пунктов То есть <tex dpi="130">T_{\mathrm {mergeSort}}P(nG,0) = T_{\mathrm {mergeSort}}0</tex>. Из этого следует, что <tex>P(\frac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 nG,x)</tex> кратен <tex>x</tex>, следовательно его свободный член равен <tex>0</tex>.}}

{{Теорема|about=2|statement=Оценка при фиксированном числе потоковСтарший коэффициент хроматического многочлена равен <tex>1</tex>.|proof=Воспользуемся рекуррентной формулой:<br/><tex>P(G,x) =ОчевидноP(G_{1},x) + P(G_{2}, что при отсутствии возможности запуска неограниченного количества независимых потоковx)</tex>, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <br/>где <tex dpi="120">N_G_{ind1}</tex>. Допустим— граф, полученный из <tex>G</tex> добавлением отсутствующего в <tex>G</tex> ребра <tex dpi="120">nuv</tex> много больше , а <tex dpi="120">N_G_{ind2}</tex>— граф, что полученный из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex> в общем случае верно для ПК одну и достаточно больших объемов данныхудалением возникших при этом кратных ребер. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущенийПрименяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/>::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi>P(G,x) ="135">\Theta{P(\fracK_{n},x) + a_{N_1}P(K_{indn-1},x) + a_{2}\log \fracP(K_{n-2},x) + \ldots = x^{N_\underline{indn}} + n) = \Theta(a_{1}x^{\fracunderline{n-1}}+a_{N_2}x^{ind}}\log \fracunderline{n-2}{N_{ind}+\ldots})</tex><br/>Из этой формулы видно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.}} {{Теорема|about=3|statement=Коэффициенты хроматического многочлена составляют знакопеременную последовательность.|proof=Индукция по количеству вершин.<br/>'''База индукции:'''<br/>::::Теорема верна для графа <tex>G</tex> из одной вершины, потому что <tex dpi>P(G,x)="135"x</tex>.<br/>\Theta'''Индукционный переход''' (\frac{<tex>n}{N_{ind}}\log \frac{to n}{N_{ind}}+1)</tex> операций нужно :<br/>Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на последовательную сортировку массива длиной <tex dpi="135">\fracn+1</tex> вершине.Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{N_{ind}n+1}</tex>обладает доказываемым свойством.::::Теперь предположим, что для всех <tex dpi="135">\Theta(n+1,m)</tex> необходимо на последовательное слияние-графов теорема верна.::[[#Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D0.BE.D0.B5_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|Многопоточное слияние]] будет работать Обозначим за <tex dpi="135">\Theta((\fracG</tex> граф, полученный из <tex>G_{n1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{N_{ind}1}-uv</tex>)^, а за <tex>G_{\log_{\frac{42}</tex> — граф, полученный из <tex>G_{31}}2} + \log n \cdot min</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/><tex>P(N_G_{ind1}, \log nx)=\ThetaP(G,x)-P(\fracG_{n}{N_{ind}})^{\log_{\frac{4}{3}}2},x)</tex>:.::::Прежде чем достигнуть ограничения на создание нового потокаТак как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, алгоритм углубится на а в <tex dpi="110">min(N_G_{ind2}, \log </tex> — <tex>n)</tex> уровней вглубь дерева рекурсиивершин, где на каждом уровне выполняется бинпоиск за то для <tex>G</tex> и <tex dpi="135">\Theta(\log n)G_{2}</tex>теорема верна::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна <br/>::::<tex dpi="135">T_{\mathrm P(G,x)=x^{mergen+1}-a_{1}'(x^{n) = 2T_}+a_{\mathrm 2}x^{mergen-1}}'(\frac -a_{3}x^{4n-2}n) + \Thetaldots}</tex> ,<br/><tex>{P(\log nG_{2},x) = \Theta(nx^{\log_n}-b_{\frac1}x^{4n-1}+b_{32}x^{n-2}2+\ldots})</tex> ,<br/>::Оценим [[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|сортировку с многопоточным слиянием]] снизу:::::Части массива длиной где <tex dpi="135">\fraca_{n1}</tex>, <tex>a_{N_{ind}2}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова …, <tex>\mathrm a_{mergeSortMT2n+1} </tex> от массива длиной , <tex dpi="135">\fracb_{n1}</tex>, <tex>b_{N_{ind}2}</tex> число потоков, равное …, <tex dpi="135">N_b_{indn}</tex>— некоторые неотрицательные целые числа. Тогда по основной теореме рекуррентных соотношенийИз этих равенств получаем:<br/>::::<tex dpi="135">T_{\mathrm {mergeSort}}'P(\fracG_{n}{N_{ind}1},x) = 2T_x^{\mathrm {mergeSortn+1}}'-(\fraca_{n1}+1)x^{2N_{indn}}) + \Theta(\fraca_{n2}+b_{N_{ind}1})x^{\log_{\frac{4n-1}{3}}2} = +\Theta(\frac{nldots</tex>.Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.}{N_{ind}})^ {\log_{\frac{Теорема|about=4}{|statement=Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.|proof=Из доказательства '''Теоремы (3}}2})''' видно, что при увеличении количества ребер графа на <tex>1</tex>Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием вышевторой коэффициент также увеличивается на <tex>1</tex>. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет Так как для пустого графа второй коэффициент равен <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})0</tex>, то утверждение верно для любого графа.}} ==Источники информацииЛитература ==#Cormen T1.HАсанов М. О., Leiserson CБаранский В.EА., Rivest RРасин В.LВ.- Дискретная математика: Графы, матроиды, Stein Cалгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). '''ISBN 978-5-8114-1068-2'''<br />2. Харари Ф. {{-Теория графов: Изд. 4-е. -}} Introduction to AlgorithmsМ.: Книжный дом "ЛИБРОКОМ", Third Edition2009. - 296 с. '''ISBN 978-5-397-00622-4''' [[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]