2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Задача про 3 буфера
Сообщение17.01.2016, 21:18 
Заслуженный участник


23/07/08
10626
Crna Gora
Обозначим количество заявок в $1,2,3$ буферах соответственно $i,j,k$. Так как числа целые и удовлетворяют условиям $0 \leqslant i,j,k \leqslant n$, всего возможно $(n+1)^3$ комбинаций значений.

Тройку чисел $(i,j,k)$ можно интерпретировать как координаты точки в трёхмерном пространстве. Точки, соответствующие допустимым значениям $(i,j,k)$, образуют кубическую сетку (точки куба $0 \leqslant x,y,z \leqslant n$, имеющие целочисленные координаты). Каждый узел сетки — это возможное состояние всех трёх буферов. Например, узел с координатами $(2,7,4)$ соответствует состоянию, когда в первом буфере 2 заявки, во втором 7 заявок, в третьем 4 заявки.

Представьте одну подвижную точку, которая с каждым ходом перемещается с одного узла на другой. В начале (положение 0) она была в узле $(0,0,0)$, т.е. ни в одном буфере не было заявок. После первого хода она с вероятностью $P_1$ попадёт в узел $(1,0,0)$, с вероятностью $P_2$ в узел $(0,1,0)$ и с вероятностью $P_3$ в узел $(0,0,1)$. Теперь мы имеем положение $1$. В зависимости от положения $1$ после второго хода мы получим с разными вероятностями несколько возможных вариантов положения $2$. И так далее.

После $\ell$-ого хода мы получаем множество вариантов положения $\ell$ с различными вероятностями. В каждом узле сетки $(i,j,k)$ мы можем написать число $p^{\ell}_{i,j,k}$ (верхний индекс — номер положения), которое означает вероятность того, что подвижная точка, двигаясь случайно, попадёт после $\ell$-ого хода именно в этот узел. После очередного хода вероятности, написанные в каждом узле, изменятся, то есть числа $p^{\ell+1}_{i,j,k}$ будут какими-то другими.

Пока Вы меня понимаете?

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение17.01.2016, 21:24 


21/12/15
32
Санкт-Петербург
svv в сообщении #1091577 писал(а):
Пока Вы меня понимаете?

Да,пока понятно.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение17.01.2016, 22:59 
Заслуженный участник


23/07/08
10626
Crna Gora
Далее вместо «положение» будем говорить «момент». Итак, после $\ell$-го хода наступает $\ell$-ый момент.

Так вот, расчёт основан на следующем.
1) Мы знаем вероятности для нулевого момента (перед первым ходом). Именно, подвижная точка достоверно находится в узле $(0,0,0)$. Стало быть, $p^{0}_{0,0,0}=1$ и $p^{0}_{i,j,k}=0$ для остальных узлов.
2) Если мы знаем все вероятности для момента $\ell$, мы можем вычислить все вероятности для момента $\ell+1$.

Вот рекуррентная формула:
$p^{\ell+1}_{i,j,k}=p^{\ell}_{i-1,j,k}\;P_1+p^{\ell}_{i,j-1,k}\;P_2+p^{\ell}_{i,j,k-1}\;P_3$
Она справедлива с двумя оговорками:
$\bullet$ Работает только первый диспетчер
$\bullet$ Если в правой части в каком-то слагаемом один из индексов принимает некорректное значение (меньше нуля), это слагаемое выбрасывается. (Или, что эквивалентно, соответствующая вероятность $p^\ell_{...}$ для несуществующего узла считается нулевой.)

Ваша задача — догадаться, почему формула именно такова.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение17.01.2016, 23:35 


21/12/15
32
Санкт-Петербург
svv в сообщении #1091607 писал(а):
Ваша задача — догадаться, почему формула именно такова.

В состояние $(i,j,k)$ на $l+1$ моменте мы можем прийти 3 способами. На $l$ - ом моменте мы уже $j$ раз отправляем заявку во второй буфер; $k$ раз в третий буфер и $i-1$ раз в 1 буфер. Поэтому на $l+1$ моменте нам надо,чтобы заявка ушла в первый буфер. Вероятность этого у нас $p^{l}_{(i-1,j,k)}P_1$.

Аналогично для второго и третьего буферов. Поскольку эти события происходят независимо друг от друга, то отсюда и сумма вероятностей.

UPD.

Точнее способов-то много, имеется в виду что раз у нас 3 координаты, то,так сказать, "недойти" к $l $- му моменту мы можем только по одной из них.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 00:06 
Заслуженный участник


23/07/08
10626
Crna Gora
Vaarallinen в сообщении #1091615 писал(а):
В состояние $(i,j,k)$ на $l+1$ моменте мы можем прийти 3 способами.
Да, верно. При этом события
$\bullet$ в результате $(\ell+1)$-го хода система попала в состояние $(i,j,k)$ из состояния $(i-1, j, k)$
$\bullet$ в результате $(\ell+1)$-го хода система попала в состояние $(i,j,k)$ из состояния $(i, j-1, k)$
$\bullet$ в результате $(\ell+1)$-го хода система попала в состояние $(i,j,k)$ из состояния $(i, j, k-1)$
являются взаимоисключающими (здесь нужно такое слово). А вероятность того, что произойдёт любое из взаимоисключающих событий, равна сумме вероятностей каждого из них.

Теперь найдём, например, вероятность первой альтернативы. Для этого должны произойти совместно два события:
$\bullet$ в момент $\ell$ система находилась в состоянии $(i-1,j,k)$
$\bullet$ на $(\ell+1)$-м ходу диспетчер положил заявку в буфер 1
Эти события независимы (вероятности $P_1,P_2,P_3$ не зависят от состояния), поэтому вероятность того, что эти события произойдут совместно, равна произведению их вероятностей.

Аналогично для второй и третьей альтернатив.

Дальнейшая программа:
$\bullet$ Записать рекуррентную формулу для $\ell>n$ (или $\ell>n+1$, Вы сами уточните) — с учётом действий второго диспетчера. В ней будет уже побольше слагаемых (9 или, если объединить некоторые, 7), но для компьютерной программы, которая, как предполагается, будет это вычислять, это — тьфу. :-)
$\bullet$ Учесть эффекты, связанные с полным или пустым буфером (с которых мы начинали разговор). Вы теперь понимаете, что в нашей геометрической интерпретации этому соответствуют узлы, находящиеся на поверхности (на гранях) куба.

Вот и всё. Уверен, Вы справитесь. :P

Upd. Мы не расстаёмся: Вы напишете формулу — я проверю, у Вас могут быть вопросы, и т.д.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 17:43 


21/12/15
32
Санкт-Петербург
svv
Итак,вот что получилось.

Чтобы получить блокировку по первому буферу на $n+m$ шаге нам надо выполнение следующих условий на $n+m-1$ шаге:
$i = n$, а во втором буфере $a$ заявок или в третьем $b$ заявок (считаем,что $i$ - ая ось соответствует первому буферу; $j$ - второму; $k$ - третьему);
$j = 0$ или $k = 0$. При этом второй и третий буфер могут быть оба пустые.

Вероятность такого события: $P = p^{n+m-1}_{n,0,b} \cdot P_1 \cdot G_2 + p^{n+m-1}_{n,a,0} \cdot P_1 \cdot G_3 + p^{n+m-1}_{n,0,0} \cdot P_1 \cdot (G_2 + G_3)$.

Аналогичные рассуждения для второго и третьего буферов. Тогда:

$P = p^{n+m-1}_{n,0,b} \cdot P_1 \cdot G_2 + p^{n+m-1}_{n,a,0} \cdot P_1 \cdot G_3 + p^{n+m-1}_{n,0,0} \cdot P_1 \cdot(G_2 + G_3) +$ $p^{n+m-1}_{0,n,c} \cdot P_2 \cdot G_1 + p^{n+m-1}_{d,n,0} \cdot P_2 \cdot G_3 + p^{n+m-1}_{0,n,0} \cdot P_2 \cdot (G_1 + G_3) +$ $+ p^{n+m-1}_{f,0,n} \cdot P_3 \cdot G_2 + p^{n+m-1}_{0,e,n} \cdot P_3 \cdot G_1 + p^{n+m-1}_{0,0,n} \cdot P_3 \cdot (G_2 + G_1)$.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 23:22 
Заслуженный участник


23/07/08
10626
Crna Gora
Vaarallinen в сообщении #1091854 писал(а):
Вероятность такого события: $P = p^{n+m-1}_{n,0,b} \cdot P_1 \cdot G_2 + p^{n+m-1}_{n,a,0} \cdot P_1 \cdot G_3 + p^{n+m-1}_{n,0,0} \cdot P_1 \cdot (G_2 + G_3)$.
Достаточно близко к истине. Ваша формула эквивалентна вот чему (перегруппируем слагаемые):
$P = (p^{n+m-1}_{n,0,0}+p^{n+m-1}_{n,0,b}) \cdot P_1 \cdot G_2 + (p^{n+m-1}_{n,0,0}+p^{n+m-1}_{n,a,0}) \cdot P_1 \cdot G_3$
Я понимаю, что Вы хотите сказать: здесь $b$ означает любое число. Но в формулу-то надо подставить какое-то конкретное $b$. А откуда его взять?

Давайте введём удобное обозначение. Блокировка 1,3 означает ситуацию, когда первый диспетчер пытается положить заявку в уже полный буфер 1, а второй пытается взять заявку из пустого буфера 3.

Казалось бы, ситуация определённая. Но при этой блокировке возможно ещё $n+1$ взаимоисключающих альтернатив, отличающихся значением второго буфера, который в такой блокировке не участвует. По правилам теории вероятностей, вероятность блокировки 1,3 равна сумме вероятностей всех альтернативных вариантов, то есть
$P_{1,3}=P_1\;G_3\;\sum\limits_{a=0}^n p^{n+m-1}_{n,a,0}$
А это как раз хорошо, потому что нам даны вероятности конкретных значений всех буферов, в том числе второго, именно таков наш строительный материал. Хоть в формулу входит переменная $a$, это немая переменная суммирования, её можно заменить на другую, например, $j$ (так и сделаю), а левая часть от какого-то конкретного значения $a$ не зависит.

Итак, вероятность того, что на ходу $n+m$ возникнет блокировка 1,2 или 1,3:
$P = P_1\;G_2\;\sum\limits_{k=0}^n p^{n+m-1}_{n,0,k} + P_1\;G_3\;\sum\limits_{j=0}^n p^{n+m-1}_{n,j,0}$

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 23:25 


21/12/15
32
Санкт-Петербург
svv в сообщении #1092005 писал(а):
Как насчет блокировки 1,1 — она возможна? (Это вопрос постановки задачи.)

Что под этим подразумевается? Ситуация, когда оба диспечера выбирают первый буфер, когда в нем уже $n$ заявок?

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 23:30 
Заслуженный участник


23/07/08
10626
Crna Gora
Извините, ум за разум зашёл. Считайте, что я этого не говорил.
Да, я имел в виду такую ситуацию, забыл, что это не считается блокировкой.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 23:33 


21/12/15
32
Санкт-Петербург
svv в сообщении #1092007 писал(а):
Извините, ум за разум зашёл. Считайте, что я этого не говорил.
Да, я имел в виду такую ситуацию, забыл, что это не считается блокировкой.

Хорошо :)

Я утром подробнее посмотрю то,что Вы написали.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение18.01.2016, 23:34 
Заслуженный участник


23/07/08
10626
Crna Gora
Теперь надо написать рекуррентную формулу с учётом действий второго диспетчера, про которую я говорил, что в ней будет то ли 7, то ли 9 слагаемых.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение19.01.2016, 13:21 


21/12/15
32
Санкт-Петербург
svv в сообщении #1092009 писал(а):
Теперь надо написать рекуррентную формулу с учётом действий второго диспетчера, про которую я говорил, что в ней будет то ли 7, то ли 9 слагаемых.


Пусть на $l$ - ом шаге мы оказались в точке $(i-1,j,k)$. На $l+1$ включается второй диспечер и теперь нам надо это учитывать. Диспечеры действуют независимо друг от друга.

Итак, получается такое соотношение для $l+1$ шага: $p^{l}_{i-1,j,k} \cdot P_1 \cdot G_1 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_2 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_3$. То есть, первый диспечер выбирает первый буфер, а второй диспечер выбирает первый буфер ИЛИ второй диспечер выбирает второй буфер ИЛИ второй диспечер выбирает третий буфер.

Для точки $(i,j-1,k)$: $p^{l}_{i,j-1,k} \cdot P_2 \cdot G_1 + p^{l}_{i,j-1,k} \cdot P_2 \cdot G_2 + p^{l}_{i,j-1,k} \cdot P_2 \cdot G_3$.

Для точки $(i,j,k-1)$: $p^{l}_{i,j,k-1} \cdot P_3 \cdot G_1 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_2 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_3$.

В итоге: $p^{l}_{i-1,j,k} \cdot P_1 \cdot G_1 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_2 + p^{l}_{i-1,j,k} \cdot P_1 \cdot G_3 +$$ p^{l}_{i,j-1,k} \cdot P_2 \cdot G_1 + p^{l}_{(i,j-1,k)} \cdot P_2 \cdot G_2 + p^{l}_{(i,j-1,k)} \cdot P_2 \cdot G_3 +$$ + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_1 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_2 + p^{l}_{i,j,k-1} \cdot P_3 \cdot G_3$.

Немного в раздумьях, какую нотацию выбрать для $p^{l+1}_{...}$. Пока у нас был только первый диспечер, то все было понятно: из состояний на $l$-ом шаге $(i-1,j,k)$, $(i,j-1,k)$, $(i,j,k-1)$ в результате работы этого диспечера на $l+1$ мы однозначно приходили в состояние $(i,j,k)$. Но ведь теперь мы можем двигаться не только "вперед" по осям, но и "назад".

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение19.01.2016, 16:16 
Заслуженный участник


23/07/08
10626
Crna Gora
Vaarallinen в сообщении #1092178 писал(а):
Но ведь теперь мы можем двигаться не только "вперед" по осям, но и "назад".

Верно. И потому в результате действий двух диспетчеров (слово пишется с буквой «т») точка-состояние по одной координате съезжает вперёд, а по другой назад. Например, было состояние $(2,7,4)$. Допустим, первый диспетчер положил заявку в буфер 1, второй забрал из буфера 2. В результате такого «хода 1,2» (будем так говорить) состояние будет $(3,6,4)$. Иначе говоря (и обобщая), в результате хода 1,2 мы попадаем в точку $(i,j,k)$ из точки $(i-1,j+1,k)$.

Собственно говоря, второй диспетчер для того и нужен, чтобы не позволять точке-состоянию упереться в угол куба $(n,n,n)$ («все буферы заполнены») и застрять там навсегда.

Подправьте с учётом этого формулу.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение19.01.2016, 16:28 


21/12/15
32
Санкт-Петербург
svv в сообщении #1092256 писал(а):
Подправьте с учётом этого формулу.


$p^{l+1}_{i,j,k} =$ $p^{l}_{i,j,k} \cdot P_1 \cdot G_1 + p^{l}_{i-1,j+1,k} \cdot P_1 \cdot G_2 + p^{l}_{i-1,j,k+1} \cdot P_1 \cdot G_3 +$ $p^{l}_{i+1,j-1,k} \cdot P_2 \cdot G_1 + p^{l}_{i,j,k} \cdot P_2 \cdot G_2 + p^{l}_{i,j-1,k+1} \cdot P_2 \cdot G_3 +$ $+ p^{l}_{i+1,j,k-1} \cdot P_3 \cdot G_1 + p^{l}_{i,j+1,k-1} \cdot P_3 \cdot G_2 + p^{l}_{i,j,k} \cdot P_3 \cdot G_3$

Некоторые пояснения.

$p^{l}_{i,j,k} \cdot P_1 \cdot G_1 $ - формула такая, потому что если нет блокировки, то в буфер будет положена заяввка и тут же забрана. Что будет, если буфер полон и оба диспетчера выбирают его - обсуждалось на первой странице.

 Профиль  
                  
 
 Re: Задача про 3 буфера
Сообщение19.01.2016, 16:42 
Заслуженный участник


23/07/08
10626
Crna Gora
Да, формула правильная. В ней 9 слагаемых. Если же сгруппировать коэффициенты при $p^\ell_{i, j, k}$, которое встречается 3 раза, их будет 7. Но делать это не нужно, и так хорошо.

Следующий шаг.
Осознайте, что формула неприменима для узлов на поверхности куба (т.е. таких, у которых одна или несколько координат равны $0$ или $n$).
Осознайте, что единственно правильного варианта для поверхностных узлов нет, так как он зависит от дополнительных условий задачи: надо дополнительно оговаривать, что происходит, когда диспетчер пытается положить заявку в полный буфер или забрать из пустого. Вы говорили, что в этом случае происходит блокировка по одному диспетчеру, но нужно четко сформулировать, что происходит с буферами, продолжается ли «игра» и т.д. Возможно, Вы это уже говорили, тогда, пожалуйста, повторите.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group