Kolejki - dostęp do zasobów

Definicja klasyczna. Prawdopodobieństwo warunkowe i całkowite. Zmienne losowe i ich parametry. Niezależność. Prawa wielkich liczb oraz centralne twierdzenia graniczne i ich zastosowania.
prin
Użytkownik
Użytkownik
Posty: 52
Rejestracja: 20 paź 2007, o 22:59
Płeć: Kobieta
Lokalizacja: gdańsk
Podziękował: 1 raz

Kolejki - dostęp do zasobów

Post autor: prin » 24 paź 2007, o 15:54

Każdy spośród N uŜytkowników \(\displaystyle{ U_{1}}\), \(\displaystyle{ U_{2}}\),,…, \(\displaystyle{ U_{N}}\), żąda dostępu do jednego z K zasobów \(\displaystyle{ R_{1}}\), \(\displaystyle{ R_{2}}\),…, \(\displaystyle{ R_{K}}\), które wybiera
losowo i niezależnie od pozostałych użytkowników. W ten sposób przy zasobach tworzą się kolejki. Wyznacz
prawdopodobieństwa następującego zdarzenia:
dokładnie m dowolnych kolejek ma długość 1.
Ostatnio zmieniony 24 paź 2007, o 16:46 przez prin, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

UNIX_admin
Użytkownik
Użytkownik
Posty: 185
Rejestracja: 6 maja 2006, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 32 razy

Kolejki - dostęp do zasobów

Post autor: UNIX_admin » 22 lis 2007, o 18:18

jesli podasz rozklad weslug jakiego generowane sa zadania uzytkownikow oraz jaki jest czas obslugi w serwerze, to bedzie mozna przeanalizowac dlugosci kolejek. Jesli natomiact chodzi Ci o problem: mamy N kulek i umieszczamy je losowo w K koszykach, jakie jest p-stwo, ze w dokladnie m koszykach znajda sie 2 kulki, to rozwiazanie jest duzo prostsze. (pisze 2 kulki, bo zakladam, ze jesli do serwera wejda w tym samym czasie 2 zadania, to jedno zostanie wziete do obslugi, a drugie trafi do kolejki i tylko w tym przypadku dlugosc kolejki bedzie rowna 1)

Rozwiazanie:

N kulek mozna umiescic w K koszykach na \(\displaystyle{ {N+K-1 \choose K-1}}\) sposobow.
Pozostawiam to bez dowodu, bo to raczej dosc intuicyjne, jesli ktos chce wyjasniej, niech pisze.

Rozwazmy teraz ile sposrod tych ustawien spelnia warunki zadania. Zarezerwujmy 2m kulek i m koszykow, zostanie N-2m kulek oraz K-m koszykow. Analogicznie jak poprzednio N-2m kulek mozna ukiescic w K-m koszykach na \(\displaystyle{ {N+K-3m-1 \choose K-m-1}}\) sposobow.

Zatem szukane p-stwo wynosi: \(\displaystyle{ \frac{{N+K-3m-1 \choose K-m-1}}{{N+K-1 \choose K-1}}}\)

PS. co do mianownika, jestem pewien, ale dobrze by bylo, zeby ktos sprawdzil, czy mozna tak wyznaczyc licznik

liczniek jest ZLY, poprawiony wynik ponizej
Ostatnio zmieniony 26 lis 2007, o 12:40 przez UNIX_admin, łącznie zmieniany 1 raz.

prin
Użytkownik
Użytkownik
Posty: 52
Rejestracja: 20 paź 2007, o 22:59
Płeć: Kobieta
Lokalizacja: gdańsk
Podziękował: 1 raz

Kolejki - dostęp do zasobów

Post autor: prin » 22 lis 2007, o 19:53

Co do mianownika nie jestem pewna, ale licznik napewno nie będzie tak banalny.. Liczyłam to z kilkoma innymi osobami + konsultacje u wykładowcy, z tego co wiem będzie to dość skomplikowana suma.. Twój licznik nie zapewnia tego, że przy innych zasobach nie będzie kolejek długości jeden i ze te m kolejek mają własnie taka długość.. w każdym razie dzięki za pomoc..

ps. w zadaniu przyjmuje się że pusta kolejka to brak użytkowników którzy korzystają z danych zasobów.. chodzi o to aby dokładnie m zasobów miało po jednym użytkowniku..

UNIX_admin
Użytkownik
Użytkownik
Posty: 185
Rejestracja: 6 maja 2006, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 32 razy

Kolejki - dostęp do zasobów

Post autor: UNIX_admin » 22 lis 2007, o 20:04

jesli pusta kolejka = brak uzytkownikow, to wystarczy zamienic liczbe 3 na 2 i juz. A te skaplikowane sumy sumuja sie wlasnie do prostego dwumianu, czesto tak bywa, a mianownik jest na 100% OK, studiowalem kiedys matematyke dyskretna i jeszcze cos pamietam.

Przedstaw to zadanie w wersji kulek i koszykow (bo moze zle zrozumialem problem), to podam rozwiazanie. Jesli podajesz w wersji z zadaniami obslugi i serwerami, to mysisz sprecyzowac ile trwa odsluga jedneda zadania, cze kazde zadanie obslugiwane jest tak samo (przez taki sam czas), kiedy tworza sie kolejki, no i przede wszystkim jaki jest rozklad generowanego ruchu.


PS. oczywiscie licznik jest ZLY, juz poprzwiam

[ Dodano: 26 Listopada 2007, 14:11 ]
Wiec jeszcze raz od poczatku.

Problem:
mamy N nierozroznialnych kul oraz K rozroznialnych koszykow. Umieszczamy kule w koszykach w losowy sposob. Wyznaczmy p-stwo, ze w dokladnie m (dowolnych) koszykach znajdzie sie dokladnie po jednej kuli.

Rozwiazanie:

wszystkich mozliwych rozmieszczen jest (jak juz wczesniej pisalem) \(\displaystyle{ {N+K-1 \choose K-1}}\)

Rozwazmy teraz rozmieszczenia spelniajace warunki zadania. Zarezerwujmy wiec \(\displaystyle{ m}\) kul oraz \(\displaystyle{ m}\) koszykow i w kazdym z tych koszykow umiescmy po jednej kuli. Koszyki, ktore rezerwujemy mozna wybrac na \(\displaystyle{ {K \choose m}}\) sposobow. Pozostale
\(\displaystyle{ N-m}\) kule mozna umiescic w pozostalych \(\displaystyle{ K-m}\) koszykach na \(\displaystyle{ {N+K-2m-1 \choose K-m-1}}\) sposobow. Ale wsrod tych rozmieszczen znajda sie tez takie, przy ktorych w pewnych koszykach znajdzie sie jedna kula. Zatem odejmijmy wszystkie rozmieszczenia (teraz rozwazamy N-m kul oraz K-m koszykow), w ktorych w dokladnie jednym z koszykow znajdzie sie dokladnie jedna kula, takich rozmieszczen jest \(\displaystyle{ {K-m \choose 1} {N+K-2m-1-2 \choose K-m-1-1}}\). No ale teraz z kolei dwukrotnie odjelismy rozmieszczenie, w ktorym w dokladnie dwoch koszach znalazlo sie po jednej kuli, wiec dodajmy je, a jest ich \(\displaystyle{ {K-m \choose 2} {N+K-2m-1-4 \choose K-m-1-2}}\), etc. Czyli korzystamy tu z tzw zasady wlaczania-wylaczania.

Ostatecznie otrzymujemy wynik

\(\displaystyle{ \frac{ {K \choose m} {N+K-2m-1 \choose K-m-1} + \sum_{i=1}^{K-m} (-1)^{i} {K-m \choose i} {N+K-2m-1-2i \choose K-m-1-i} }{{N+K-1 \choose K-1}}}\)

oczywiscie mozna to uproscic, ale w tej postaci chyba lepiej widac skad co sie bierze. Mam nadzieje, ze teraz jest dobrze. Moze ktos to potwierdzic?

ODPOWIEDZ