Диссертация (1149645), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Будем укладывать прямоугольник бесконечную полосу ширины kплитками размеров 1×1, 1×2, 1×3, …, имеющими соответственно вероятностивыпадения для первого ряда – q11, q12, q13,…, для второго ряда – q21, q22, q23,…,соответственно, и т.д., для k-го ряда – qk1, qk2, qk3,…, соответственно.Укладка плиток начинается с первого ряда и выполняется по следующемуалгоритму. Каждая новая плитка укладывается в тот ряд, который в данныймомент имеет наименьшую длину относительно начала отсчета. Началом отсчетасчитается момент времени, в который ни один из заполненных плитками рядов неявляется выступающим относительно других.

Если несколько рядов плитокимеют одинаковую длину, и она является наименьшей, то укладка выполняется вряд с наименьшим номером. Таким образом, чередуя укладку рядов, заполняемполосу.ПустьX 1jj 1,X 2jj 1,…,  X k j j 1– не зависящие друг от другапоследовательности независимых одинаково распределѐнных случайных величин,принимающих неотрицательные целые значения,j 0j 0gi  x    P  X ij  j  x j   qij x j ,  i  1, 2, ..., k причем qij – вероятность того, что плитка i-го ряда будет иметь длину j.Рассмотрим производящую функцию117Gk  x, t    pk ,n,m x nt m ,n 0 m 0где pk ,n,m  вероятность того, что в случайном процессе на каком-то шагепоявится прямоугольник размером k×n, состоящий из m плиток.Постановку задачи удобно пояснить посредством следующего примера.П р и м е р 3.10.

Замощение прямоугольника размера 4×15 шестнадцатьюплитками приведено на рисунке 3.3. Вероятность появления такого замощения в224случайном процессе равна q13q15q17 q24q27 q32q33q37 q42q43q44 .kq15q24q33q44q13q17q27q32q37q42q43q42q24q33q42 q42nРисунок 3.3 – Замощение прямоугольника плитками (k = 4, n = 15)Справедлива следующая теорема, сформулированная и доказанная автором.Т е о р е м а 3.6. В принятых выше обозначениях справедливо равенство:Gk  x, t  111. ... 1  g1  x  t 1  g 2  x  t1  gk  x  tД о к а з а т е л ь с т в о . В силу независимости последовательностей  X 1 j  ,j 1X 2j,…,  X k j  , а также ввиду того, что величины X ij  неотрицательныеj 1j 1целочисленные, имеемGk  x, t   n 0m 0i1 i2 ...ik  mP( X 11  ...

 X 1i1  n)  ...  P( X k1  ...  X kik  n) x nt m  ... P( X11  ...  X 1i1  n)  ...  P( X k1  ...  X kik  n) x nt i1 ...ik n 0 i1 0ik 0118       P( X 11  ...  X 1i1  n) t i1   ...    P( X k1  ...  X kik  n)t ik  x n n 0  i1 0 ik 0        ni1     P( X 11  ...  X 1i1  n) t  x   ...      P( X k1  ...  X kik  n) t ik  x n   n 0 i 0 n 0 i 0   1 k       n  i1     P( X 11  ...  X 1i1  n) x  t   ...

     P( X k1  ...  X kik  n) x n  t ik  .   i1 0  n0 ik 0  n0Применяясвойствомультипликативностипроизводящихфункций,получаем  ik  i1   i2i1i2Gk  x, t     g1  x  t     g 2  x  t   ...    g k  x  t ik   i1 0  i2 0 ik 0111. ... 1  g1  x  t 1  g 2  x  t1  gk  x  tТеорема 3.6 доказана.Таким образом, теорема 3.6, сформулированная и доказанная автором,позволяет вычислить с применением произведения Адамара производящуюфункцию вероятностей того, что в случайном процессе на каком-то шаге появитсяпрямоугольник размера k×n, состоящий из m плиток.Если случайные величины в рассмотренной выше задаче распределеныравномерно, то для вычисления произведений Адамара может быть примененатеорема 2.3. Справедлива следующая теорема, сформулированная и доказаннаяавтором.Т е о р е м а 3.7.

Пустьпоследовательности X k k 1независимыхи Yk k 1 – не зависящие друг от другаслучайныхвеличин,принимающихнеотрицательные целые значения, имеющих равномерное распределение исоответствующие производящие функцииg1  x  1 m1 j1 n1 jx,gxx .2m j 0n j 0119Тогда в принятых выше обозначениях справедливы равенства:1) при n = 3G2  x, t  R  x, t ,S  x, t гдеR  x, t   3m  m  t  3  t   t  m  t  3  t  x  mt  3  t  x 2 2t 2  3  t  f m2 x m  t 2   3  t  f m1  tf m2  x m1 ,S  x, t    3  t   m  t   3  t   mt  m  t  3  t  x  m2t  3  t  x 2 22t  m  t  3  t    3  t  f m  tf m2  x m  mt 2  2  3  t  f m1  tf m2  x m1 t 3  3  t   f m21  f m f m2  x 2 m ,is s 2 i s i i 0 Cs it  3  t fs  fs t   0 при s  0;при s  0,2) при n = 4G2  x, t   4m  4  t m4R  x, t ,S  x, t гдеR  x, t    m  t   4  t   t  m  t   4  t  x  mt  m  t  4  t  x 2 232m2t  4  t  x3  t 2  m  t  4  t 3222 f m2  2 f m3  x m t 2  4  t   mf m2  4  t    m  t  4  t   f m1  f m2   t  m  t   f m2  2 f m3   x m1 mt 2  4  t   f m1  4  t   t  f m4  f m2   x m2  t 4  4  t   f m23  f m4 f m2  x 2 m t 4 t  f m4 f m2  f m23    4  t   f m3 f m2  f m4 f m1  x 2 m1,120S  x, t    m  t   4  t   mt  m  t   4  t 3m3t  4  t m1mx3  t  m  t   4  t 2mt 2  m  t  4  t m2t 2  4  t m 22t  fm 2m 2 4  t   2 fm1m1m1x  m2t  m  t  4  t  4  t  fmm1x2  t  f m2  2 f m3   x m  3 f m2   t  f m2  2 f m3   x m1  f m4   2 f m1  4  t   x m2  t 3  m  t  4  t m 2  4  t   f m2 f m  f m21  2  f m3 f m  f m2 f m1    t  f m23  f m4 f m2  x 2 m mt 3  4  t m3 4  t   f2f  f m21   t  f m4 f m2  f m23  x 2 m1  t m3 x3m ,m 2 m 3 f s it  4  t 1 при s  0, i 1f s  f s  t   1 при s  0,0 при s  0.Длядоказательстватеоремы3.7потребуетсяследующаялемма,сформулированная и доказанная автором.Л е м м а 3.2.

Для любых целых m, k (m ≥ 2, k < m) справедлива следующаяформула:P x1xk,23m1  d1 x  d2 x  d3 x 1  b1x  bm xQ xгдеP  x   f k x k  b1  d2 f k 1  d3 f k 2  x k 1  b12d3 f k 1x k 2 bm  d2  f m1 f k 1  f m2 f k   d3  f m1 f k 2  f m2 f k 1  2 f m3 f k   x mk b1bmd3  f m1 f k 1  f m2 f k  d3  f m3 f k 2  f m4 f k 1   x mk 1  bm2 d32  f m1 f m3 f k 2  f m1 f m4 f k 1  f m22 f k 2  f m2 f m3 f k 1  f m2 f m4 f k  f m23 f k  x 2 mk ,Q  x   1  b1d1x  b12d2 x 2  b13d3 x3  bm  f m  d2 f m2  2d3 f m3  x m 121b1bm  2d2 f m1  d1d2 f m2  3d3 f m2  2d1d3 f m3  x m1 b12bmd3  2 f m1  d1 f m2  d3 f m4  x m2 bm2  d2 f m f m3  2d3 f m f m3  d2 f m21  2d3 f m1 f m2  d32 f m2 f m4  d32 f m23  x 2 m b1bm2 d3 f m f m2  f m21  d3  2  f m1 f m4  f m2 f m3   d1  f m2 f m4  f m23  x 2 m1  bm3 d3m x3m ,d1 f s 1  d 2 f s 2  d3 f s 3f s  f s  d1 , d 2 , d3   1 при s  0,0 при s  0.при s  0,Д о к а з а т е л ь с т в о .

Для вычисления произведения Адамара1xk1  d1 x  d 2 x 2  d3 x3 1  b1 x  bm x mвоспользуемся теоремой 2.3, полагая n = 3 и b2  b3  ...  bm1  0 . Вычисляя дваопределителя третьего порядка, получаемP x1xk,23m1  d1 x  d2 x  d3 x 1  b1x  bm xQ xгде P  x  – функция, указанная в формулировке леммы, аQ  x   1  b1d1x  b12d2 x 2  b13d3 x3  bm  f m  d2 f m2  2d3 f m3  x m b1bm  2d2 f m1  d1d2 f m2  3d3 f m2  2d1d3 f m3  x m1 b12bmd3  2 f m1  d1 f m2  d3 f m4  x m2 bm2  d2 f m f m3  2d3 f m f m3  d2 f m21  2d3 f m1 f m2  d32 f m2 f m4  d32 f m23  x 2 m b1bm2 d3 f m f m2  f m21  d3  2  f m1 f m4  f m2 f m3   d1  f m2 f m4  f m23  x 2 m1 122bm3 d32  f m f m2 f m4  f m f m23  2 f m1 f m2 f m3  f m23 f m4  f m32  x3m ,С другой стороны, согласно лемме 2.1 функция Q  x   det Q , гдеQ   qij – такая матрица порядка m + 3, чтоm 31 при i  j;j iпри 1  i  m, 1  j  i  3;  d j i xqij  bi  j при m  1  i  m  3, 1  i  j  m;0 в остальных случаях.Вычисляя det Q по определению, заметим, что максимальную степень 3mпеременной x имеет только одно слагаемое, равное 13mq14q25qm,m3qm1,1qm2,2qm3,3   13m 1m 3bm3 d3m x3m  bm3 d3m x3m .Таким образом, получаемbm3 d32  f m f m2 f m4  f m f m23  2 f m1 f m2 f m3  f m23 f m4  f m32   bm3 d3m .Лемма 3.2 доказана.Д о к а з а т е л ь с т в о т е о р е м ы 3.7.

По теореме 3.6 имеемG2  x, t  11.1  g1  x  t 1  g 2  x  tДля вычисления произведения Адамара первый множитель преобразуем,используя равенство1  xmx .1 xj 0m 1jПолучаем1m1 x.1  g1  x  t m  t 1  m  m  t 1 x  t  t  m 1 x mВторой множитель произведения Адамара приводим к виду:1231) при n = 3131;11  g 2  x  t 3  t 1  t  3  t  x  t  3  t 1 x 22) при n = 4141.11  g 2  x  t 4  t 1  t  4  t  x  t  4  t 1 x 2  t  4  t 1 x3По свойству линейности произведения Адамара имеем:1) при n = 3G2  x, t  3m1 x1 m  t  3  t  1  m  m  t  x  t  t  m 1 x m11  t 3  t  x  t 3  t  x211(по формуле (1.7) из последнего равенства получаем требуемое);2) при n = 4G2  x, t  4m1 x1 m  t  4  t  1  m  m  t  x  t  t  m 1 x m11  t  4  t  x  t  4  t  x 2  t  4  t  x3111(по лемме 3.2 из последнего равенства следует требуемое).Теорема 3.7 доказана.Информация о вероятности pk,n,m может быть использована при разработкеалгоритмов распределения ресурсов в вычислительных сетях [17].

Под плиткамибудем понимать задачи, поступающие в вычислительную сеть, под длиной плитки– время, необходимое для решения данной задачи, под рядом плиток –последовательность задач, направляемых управляющим узлом сети конкретномувычислительному узлу. Тогда pk,n,m – вероятность того, что k вычислительныхузлов за время n завершат выполнение m текущих задач. Теорема 3.7 позволяет124рассчитать вероятности p2,n,m для случая, когда распределение вероятностей того,что задача, направляемая конкретному вычислительному узлу, будет решена зафиксированное время, равномерно.125ЗаключениеВ диссертационной работе рассмотрены вопросы приложения произведенияАдамара степенных рядов рациональных функций к решению некоторых задачкомбинаторного анализа и дискретной теории вероятностей.В ходе работы над диссертацией автором получены следующие результаты:1)Получен новый комбинаторно-алгебраический метод вычисленияпроизведений Адамара рациональных функций вида1xk,1  ax  bx n 1  cx  dx m1xk,1  d1 x  d 2 x 2  ...

Характеристики

Список файлов диссертации