Автореферат (1149644), страница 4

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

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

Пусть в принятых выше обозначениях  X n n1 и Yn n1 – не зависящиедруг от друга последовательности независимых одинаково распределѐнных случайныхвеличин, принимающих неотрицательные целые значения, f  x    m0 P  X1  m  x m ,g  x    m0 P Y1  m  x m , P  Z0  0   1, F  ,     i 0  j 0 P  Si  j , j  0  i j . Тогда 1 11F  ,       .1x1fx1gx  x 1Пример 6. Пусть случайные величины X1 и Y1 имеют равномерное распределение исоответствующие производящие функцииf (x) = m –1 (1 + x + … + xm–1), g (x) = n –1 (1 + x + … + xn–1),где n = 3. Тогда по теореме 9 имеемF  ,    3m  hm2   m    3      S  ,    ,1m 2где hm   k 0 Cmk k mk  3   k m, S  ,     3     -1  2m  3   m1 m  m     3       m    3    hm    m    hm2 22mhm1  m  m     m2   m2hm2 .В параграфе 3.3 автором доказана теорема 10, позволяющая вычислить производящую функцию Gk  x, t    n0  m0 pk ,n,m x nt m вероятностей pk,n,m того, что в случайномпроцессе на каком-то шаге появится прямоугольник размера k×n, состоящий из m плиток.Укладка бесконечной полосы ширины k плитками размеров 1×1, 1×2, 1×3, …, имеющимисоответственно вероятности выпадения для первого ряда – q11, q12, q13,…, для второго ряда – q21, q22, q23,…, соответственно, и т.д., для k-го ряда – qk1, qk2, qk3,…, соответственно,начинается с первого ряда и выполняется по следующему алгоритму.

Каждая новая плитка укладывается в тот ряд, который в данный момент имеет наименьшую длину относительно начала отсчета. Началом отсчета считается момент времени, в который ни один иззаполненных плитками рядов не являлся выступающим относительно других. Если несколько рядов плиток имеют одинаковую длину, и она является наименьшей, то укладкавыполняется в ряд с наименьшим номером. Чередуя укладку рядов, заполняем полосу.Алгоритм укладки плиток в динамике образует алгоритм построения цепи Маркова.Пусть  X 1 j j 1,  X2 j j 1,…,  X k j j 1– не зависящие друг от друга последовательности не-зависимых одинаково распределѐнных случайных величин, принимающих неотрицательные целые значения,gi  x    j 0 P  X ij  j  x j   j 0 qij x j  i  1, 2, ..., k  ,причем qij – вероятность того, что плитка i-го ряда будет иметь длину j.1Толовиков М.И. Однородные цепи Маркова с двумя состояниями и суммы независимыхслучайных индикаторов // Вестник ЧГУ.

2004. №2(7). С. 134-136.14Теорема 10. В принятых выше обозначениях справедливо равенство:111.Gk  x, t   ... 1  g1  x  t 1  g 2  x  t1  gk  x  tТеорема 11. Пусть  X k k 1 и Yk k 1 – не зависящие друг от друга последовательности независимых случайных величин, принимающих неотрицательные целые значения, имеющих равномерное распределение и соответствующие производящие функцииg1 (x) = m –1 (1 + x + … + xm–1), g2 (x) = n –1 (1 + x + … + xn–1).Тогда в принятых выше обозначениях справедливы равенства:1) при n = 3G2(x,t) = R(x,t) S(x,t) –1,где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 , s 2fs = 0 при s < 0, f s   i 0 Csi it s i  3  t 2) при n = 4i sпри s ≥ 0;G2(x,t) = 4m(4 – t)m–4R(x,t) S(x,t) –1,гдеR  x, t    m  t   4  t   t  m  t   4  t  x  mt  m  t  4  t  x 2 23222 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 ,3m2m1m1S  x, t    m  t   4  t   mt  m  t   4  t  x  m2t  m  t  4  t  x 2 m12m1m3t  4  t  x3  t  m  t   4  t    4  t  f m  t  f m2  2 f m3   x m m 2mt 2  m  t  4  t    4  t   2 f m1  3 f m2   t  f m2  2 f m3   x m1 m 2m 2m2t 2  4  t   t  f m2  f m4   2 f m1  4  t   x m2  t 3  m  t  4  t     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 m2t  4  t  x3  t 2  m  t  4  t 3mt 3  4  t m3 4  t   f22f  f m21   t  f m4 f m2  f m23  x 2 m1  t m3 x3m ,m 2 mfs = 0 при s < 0, fs = 1 при s = 0, fs = (fs–1 + fs–2 + fs–3) t (4 – t)–1при s > 0.15Информация о вероятности pk,n,m может быть использована при разработке алгоритмов распределения ресурсов в вычислительных сетях1.

Под плитками будем пониматьзадачи, поступающие в вычислительную сеть, под длиной плитки – время, необходимоедля решения данной задачи, под рядом плиток – последовательность задач, направляемых управляющим узлом сети конкретному вычислительному узлу. Тогда вероятностейpk,n,m – вероятность того, что k вычислительных узлов за время n завершат выполнение mтекущих задач.

Теорема 11, сформулированная и доказанная автором, позволяет рассчитать вероятности p2,n,m для случая, когда распределение вероятностей того, что задача,направляемая конкретному вычислительному узлу, будет решена за фиксированное время, равномерно.ЗАКЛЮЧЕНИЕВ диссертационной работе рассмотрены вопросы приложения произведения Адамара степенных рядов рациональных функций к решению некоторых задач комбинаторного анализа и дискретной теории вероятностей.В ходе работы над диссертацией получены следующие результаты:1) Получен новый комбинаторно-алгебраический метод вычисления произведенийАдамара рациональных функций:1xk1xk,,1  ax  bx n 1  cx  dx m 1  d1 x  d 2 x 2  ...  d n x n 1  b1 x  b2 x 2  ...  bm x mгде m, n, k  (m ≥ 2, n ≥ 2, 0 ≤ k < m).

Метод выражен теоремами 1, 2 и 3. Известный ранее алгебраический метод вычисления произведений Адамара рациональных функцийтребует вычисления определителей порядка m + n. С помощью методов комбинаторногоанализа и линейной алгебры порядок определителей автором снижен до величиныmin(m, n), что расширяет возможности применения произведения Адамара для получениярешения конкретных задач в явном виде, поскольку в этом случае порядок определителей от величины max(m, n) не зависит, он равен произвольному, но фиксированному числу min(m, n).2) С помощью доказанной автором теоремы 1 получено общее решение задачи перечисления замощений прямоугольника размера 2×r плитками размеров 1×1, 1×m и 1×n,а для n = 3 автором получена формула (1) в явном виде.

Решение этой задачи при n = 2 спомощью комбинаторных методов ранее опубликовали в своих работах Л. Шапиро иЙ.Х. Ким.3) С помощью доказанных автором теорем 2 и 3 получено общее решение задачиперечисления замощений прямоугольника размера 2×r плитками произвольной длины.Полученный автором новый метод вычисления произведений Адамара рациональныхфункций позволяет в данной задаче снять ограничения на длину плитки и решить известную ранее задачу в новой постановке.4) С помощью полученного автором нового метода вычисления произведенийАдамара рациональных функций (теорема 1) решена задача перечисления упорядоченных разбиений компонент двумерного вектора на слагаемые (первая компонента разбивается на слагаемые 1 и n, а вторая – на слагаемые 1 и m, где m, n – произвольные целыечисла, m ≥ 2, n ≥ 2). Ранее эта задача была решена только в частных случаях при n = 2.5) С помощью доказанных автором теорем 2 и 3 решена задача перечисления упорядоченных разбиений компонент двумерного вектора на произвольные слагаемые.

По1Жук С.Н. Об онлайн-алгоритмах упаковки прямоугольников в несколько полос // Дискретная математика. 2007. Т. 19, вып. 4. С. 117-131.16лученный автором новый метод вычисления произведения Адамара рациональных функций позволяет в данной задаче снять ограничения на величину слагаемого и решить известную ранее задачу в новой постановке.6) Комбинаторным методом автором получены явные формулы для вычисленияпроизводящей функции суммы весов замощений прямоугольника плитками по числу типов взаимного расположения плиток при m = 2, n = 2 (теорема 4), а также при m = 2, n ≥ 2(теорема 5). Объект исследования в данном случае является новым.7) Получено общее решение задачи вычисления производящей функции весов замощений прямоугольника плитками по числу типов взаимного расположения плиток, атакже вычисления производящей функции весов разбиений (теорема 6).

Решение получено с применением метода трансфер-матрицы, что по сравнению с комбинаторным методом позволяет снять ограничения на длину плитки, а также на величину слагаемого вразбиении.8) С применением произведения Адамара автором явно вычислены производящиефункции распределений некоторых статистик от серий рекуррентных событий (теоремы 7 и 8), производящие функции распределений некоторых статистик от осциллирующего случайного блуждания (теорема 9), а также производящая функция вероятностейтого, что в случайном процессе на каком-то шаге появится прямоугольник размера k×n,состоящий из m плиток (теоремы 10 и 11). Явно вычислены распределения некоторыххарактеристик случайных последовательностей при условии, что производящие функцииисходных случайных величин рациональны.

Ранее произведение Адамара в задачах исследования распределений статистик от серий указанных выше случайных событий неприменялось. Применение произведения Адамара позволяет явно вычислить производящие функции распределений некоторых характеристик случайных последовательностей втех случаях, в которых их явное вычисление с помощью комбинаторных методов затруднительно.СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ АВТОРОМПО ТЕМЕ ДИССЕРТАЦИИ1. Потехина Е.А., Толовиков М.И. Распределение серий в последовательностях1-зависимых индикаторов // Череповецкие научные чтения – 2010: Материалы Всероссийской научно-практической конференции (3 ноября 2010 г.): В 3 ч.

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

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