302
правки
Изменения
Новая страница: «==Определения== {{Определение |definition= '''Взаимное исключение''' (англ. ''mutual exclusion'') — свойств…»
==Определения==
{{Определение
|definition=
'''Взаимное исключение''' (англ. ''mutual exclusion'') — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. ''race condition''); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию.
}}
То есть критические секции не могут выполняться параллельно: <tex>\forALL i,j:i\neqj \Rightarrow CS_i \rightarrow CS_j \vee CS_j \rightarrow CS_i </tex>. Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.
{{Определение
|definition=
'''Критическая секция''' (англ. ''critical section'') — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.
}}
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекуррентного соотношения, задающего числа Фибоначчи:
<tex>
F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z</tex>
<tex>a_n</tex> член может быть записан следующим образом: <tex>a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).</tex>
Для этого можно использовать метод производящих функций (англ. ''generating function method'').
==Метод производящих функций==
Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.
#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
#:<tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k</tex>
#Домножить каждую строчку на <tex>z</tex> в соответствующей степени (<tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n \in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex> — это производящая функция, назовем ее <tex>G(z)</tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.
#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде.
#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.
==Примеры==
===<tex>1</tex> пример===
==См. также==
* [[Производящая функция]]
== Источники информации ==
* [http://www.genfunc.ru/theory/rsol/ Решение рекуррентных соотношений]
[[Категория: Параллельное программирование]]
{{Определение
|definition=
'''Взаимное исключение''' (англ. ''mutual exclusion'') — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. ''race condition''); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию.
}}
То есть критические секции не могут выполняться параллельно: <tex>\forALL i,j:i\neqj \Rightarrow CS_i \rightarrow CS_j \vee CS_j \rightarrow CS_i </tex>. Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.
{{Определение
|definition=
'''Критическая секция''' (англ. ''critical section'') — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.
}}
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекуррентного соотношения, задающего числа Фибоначчи:
<tex>
F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z</tex>
<tex>a_n</tex> член может быть записан следующим образом: <tex>a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).</tex>
Для этого можно использовать метод производящих функций (англ. ''generating function method'').
==Метод производящих функций==
Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.
#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
#:<tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k</tex>
#Домножить каждую строчку на <tex>z</tex> в соответствующей степени (<tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n \in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex> — это производящая функция, назовем ее <tex>G(z)</tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.
#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде.
#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.
==Примеры==
===<tex>1</tex> пример===
==См. также==
* [[Производящая функция]]
== Источники информации ==
* [http://www.genfunc.ru/theory/rsol/ Решение рекуррентных соотношений]
[[Категория: Параллельное программирование]]
