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.
Kolejki - dostęp do zasobów
-
- 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
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
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.
-
- 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
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..
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..
-
- 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
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?
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?