Výkonnost a spolehlivost číslicových systémů Úloha 1 Generování a zpracování náhodných čísel Zadání 9 Trojúhelníkové rozdělení
Jan Kupka (A01165)
[email protected]
1. Zadání vytvořte generátor rozdělení jako funkci v jazyce Java, C či Pascal/Delphi (parametry rozdělení jsou zároveň parametry funkce generátoru) s využitím vhodné metody (inverzní transformace, kompoziční, vylučovací, atd.), napište hlavní program, ve kterém nejméně pro dvě množiny číselně dosazených parametrů generátoru otestujte správnost vytvořené funkce generátoru, zejména se testuje: střední hodnota, rozptyl či směrodatná odchylka, charakter rozdělení (histogram), experimentálně zjištěné hodnoty testovaných veličin porovnejte s teoretickými hodnotami určenými výpočtem z dané funkce rozdělení. Trojúhelníkové rozdělení f(x) = 0 pro x<0 f(x) lin. roste pro a>x>0 f(x) lin. klesá pro 2a>x>a f(x) = 0 pro x>2a
2. Řešení - programové Pro řešení úlohy jsem využil vylučovací metodu. Úlohu jsem řešil pomocí programu v jazyce JAVA a hodnoty jsem ověřoval ručním výpočtem integrálu a dosazením hodnot. Pro úlohu jsem využil standardní funkce jazyka JAVA pro generování rovnoměrného rozdělení. Pomocí vylučovací metody jsem z rovnoměrného rozdělení vybíral potřebné hodnoty pro trojúhelníkové rozdělení. Graf hustoty pravděpodobnosti zadané úlohy:
Z hustoty pravděpodobnosti je dobře vidět, že lze úlohu rozdělit na dva úseky (0,a) a (a,2a) a s každým pracovat zvlášť. Pro maximální jednoduchost jsem zvolil vrchol v bodě [a,a], tzn. že rostoucí první úsek funkce má rovnici y=x a druhý úsek funkce má rovnici y=|2a –x|. První náhodná proměnná (delitko) je generována v intervalu (0,1) a rozděluje interval (0,2a) na dva úseky. V prvním úseku volíme větší z dvou vygenerovaných čísel v intervalu (0,2a), což nám s nejnižší pravděpodobností generuje malá čísla a s nejvyšší vysoká čísla. V druhém úseku volíme nižší číslo, což nám s nejvyšší pravděpodobností generuje malá čísla a s nejnižší pravděpodobností vysoká. K druhému úseku musíme ještě připočítat hodnotu parametru a, abychom se posunuli do druhého úseku.
Po vygenerování náhodného čísla je toto číslo zařazeno do intervalu histogramu podle své hodnoty. Pomocí těchto hodnot je vytvořen jednoduchý hvězdičkový histogram. Hodnoty napravo od histogramu udávají odhady pravděpodobnosti P = (počet výskytů v daném intervalu / počet generování). Dále je odhadována střední hodnota pomocí průměru hodnot E = ( součet všech hodnot / počet generování). Rozptyl je vypočten jako D = ((součet druhých mocnin všech hodnot / počet generování) – druhá mocnina součtu všech hodnot).
2.1 Zdrojový kód programu import java.util.*; import java.text.DecimalFormat; public class Generator { public static double rovnomerne(int parametrA) { Random rand = new Random(); double nahodneCislo = rand.nextDouble() * parametrA; return nahodneCislo; } public static double rovnomerne() { return Math.random(); } public static double trojuhelnik(int parametrA) { double a, b; double vysledek; double delitko = rovnomerne(); a = rovnomerne(parametrA); b = rovnomerne(parametrA); if (delitko < 0.5) { if (a > b) { vysledek = a; } else { vysledek = b; } } else { if (a < b) { vysledek = a; } else { vysledek = b; } vysledek = vysledek + parametrA; } return vysledek; } public static void tester(int parametrA, int pocetGenerovani, int pocetIntervalu) { DecimalFormat df = new DecimalFormat("0.0000"); double hodnota;
int[] pole = new int[pocetIntervalu]; double sumator = 0; // pro vypocet stredni hodnoty double sumatorMocnin = 0; // pro vypocet rozptylu double dil = (2 * (double) parametrA) / pocetIntervalu; /* generovani cisel */ for (int i = 0; i < pocetGenerovani; i++) { hodnota = (double) trojuhelnik(parametrA); sumator = sumator + hodnota; sumatorMocnin = sumatorMocnin + Math.pow(hodnota, 2); // System.out.println(hodnota); for (int j = 0; j < pocetIntervalu; j++) { if ((hodnota > (j * dil)) && (hodnota < ((j + 1) * dil))) { pole[j]++; } } } System.out.println(); /* histogram - textove */ for (int i = 0; i < pocetIntervalu; i++) { System.out.println( "Interval od " + df.format(i * dil) + " do " + df.format((i + 1) * dil) + " - pocet hodnot: " + pole[i]); } System.out.println(""); /* histogram - graficky */ for (int i = 0; i < pocetIntervalu; i++) { for (int j = 0; j < (pole[i] / 500); j++) { System.out.print("*"); } System.out.println( " " + df.format((double) pole[i] / pocetGenerovani)); } double E = sumator / pocetGenerovani; double D = (sumatorMocnin / pocetGenerovani) - Math.pow(E, 2); System.out.println(); System.out.println("Stredni hodnota je " + df.format(E)); System.out.println("Rozptyl je " + df.format(D)); System.out.println(); } public static void main(String[] args) { System.out.println( "Generator trojuhelnikoveho rozdeleni pravdepodobnosti"); System.out.println("Jan Kupka (A01165)"); System.out.println(); System.out.println("TEST CISLO 1"); System.out.println( "Pocet generovani: 100000, pocet intervalu: 10, parametr a: 1"); tester(1, 100000, 10);
System.out.println("TEST CISLO 2"); System.out.println( "Pocet generovani: 100000, pocet intervalu: 20, parametr a: 2"); tester(2, 100000, 20); } }
2.2 Výstup programu Generator trojuhelnikoveho rozdeleni pravdepodobnosti Jan Kupka (A01165) TEST CISLO 1 Pocet generovani: 100000, pocet intervalu: 10, parametr a: 1 (0,0000-0,2000) (0,2000-0,4000) (0,4000-0,6000) (0,6000-0,8000) (0,8000-1,0000) (1,0000-1,2000) (1,2000-1,4000) (1,4000-1,6000) (1,6000-1,8000) (1,8000-2,0000)
** 0,0144 ***************** 0,0852 ******************* 0,0998 *********************** 0,1164 ************************************* 0,1877 ************************************* 0,1854 *********************** 0,1150 ******************* 0,0981 **************** 0,0843 ** 0,0136
Stredni hodnota je 0,9976 Rozptyl je 0,1764 TEST CISLO 2 Pocet generovani: 100000, pocet intervalu: 20, parametr a: 2 (0,0000-0,2000) (0,2000-0,4000) (0,4000-0,6000) (0,6000-0,8000) (0,8000-1,0000) (1,0000-1,2000) (1,2000-1,4000) (1,4000-1,6000) (1,6000-1,8000) (1,8000-2,0000) (2,0000-2,2000) (2,2000-2,4000) (2,4000-2,6000) (2,6000-2,8000) (2,8000-3,0000) (3,0000-3,2000) (3,2000-3,4000) (3,4000-3,6000) (3,6000-3,8000) (3,8000-4,0000)
0,0015 ** 0,0109 ******* 0,0380 ********* 0,0485 ********* 0,0481 ********** 0,0524 ********** 0,0506 ************ 0,0632 ***************** 0,0888 ******************** 0,1007 ******************* 0,0977 ***************** 0,0884 ************ 0,0614 ********** 0,0530 ********** 0,0501 ********* 0,0497 ********* 0,0489 ******* 0,0354 ** 0,0115 0,0013
Stredni hodnota je 1,9973 Rozptyl je 0,7009
3. Řešení – teoretické Náhodnou veličinu máme zadánu intervaly: f(x) = 0 pro x<0 f(x) lin. roste pro a>x>0 f(x) lin. klesá pro 2a>x>a f(x) = 0 pro x>2a Pro ukázku teoretického řešení zvolím hodnotu a=1. Z čehož plyne: f(x) = 0 pro x<0 f(x) = x 1>x>0 f(x) = 2 - x pro 2>x>1 f(x) = 0 pro x>2
Hustota pravděpodobnosti konkrétní úlohy
Výpočet střední hodnoty 1
E( )
x. f ( x)dx
2
x.xdx
x.(2 x)dx
0 1
3.
x 3
1
3.
x2
2
x 3
0
1 8 1 (4 ) (1 ) 1 3 3 3 1
Výpočet rozptylu 1
E(
2
x 2 . f ( x)dx
)
2
x 2 .xdx 0
4.
1
x 4
4.
1
2
2 3 x x 3 4 0
x 2 .(2 x)dx
1 16 2 ( 4 4 3 3 1
1 ) 4
3 32 24 4 6
7 6
2
( )
E(
2
7 2 1 6
) E2( )
1 6
Distribuční funkce F ( x)
P(
F ( x)
x)
f (t )dt
Interval (-∞,0) F(x)=0 Interval <0,1>
2
t 2
x
F ( x)
tdt 0
x
x2 2 0
Interval <1,2> 1
F ( x)
x
tdt
(2 t )dt
0
1 2x 2
1 2
1
2
x 2
2
1 2
x 2
Interval <2,∞) F(x)=1 Graf distribuční funkce:
2
t 2t 2
2
2x 1
x
1 (2 x 2 1
x2 1 ) (2 ) 2 2
Výpočet pravděpodobností P(0.0 P(0.2 P(0.4 P(0.6 P(0.8 P(1.0 P(1.2 P(1.4 P(1.6 P(2.0
0.2) F (0.2) 0.4) F (0.4) 0.6) F (0.6) 0.8) F (0.8) 1.0) F (1.0) 1.2) F (1.2) 1.4) F (1.4) 1.6) F (1.6) 1.8) F (1.8) 1.8) F (2.0)
F (0.0) F (0.2) F (0.4) F (0.6) F (0.8) F (1.0)
(0.2) 2 / 2 (0.0) 2 / 2 0.02 (0.4) 2 / 2 (0.2) 2 / 2 0.06 (0.6) 2 / 2 (0.4) 2 / 2 0.1 (0.8) 2 / 2 (0.6) 2 / 2 0.14 (1.0) 2 / 2 (0.8) 2 / 2 0.18 ( (1.2) 2 / 2 2 *1.2 1) ( (1.0) 2 / 2 2 *1.0 1) 0.68 0.5 0.18
F (1.2) ( (1.4) 2 / 2 F (1.4) ( (1.6) 2 / 2 F (1.6) ( (1.8) 2 / 2 F (1.8) ( (2.0) 2 / 2
2 *1.4 2 *1.6 2 *1.8 2 * 2.0
1) 1) 1) 1)
( (1.2) 2 / 2 ( (1.4) 2 / 2 ( (1.6) 2 / 2 ( (1.8) 2 / 2
2 *1.2 2 *1.4 2 *1.6 2 *1.8
1) 1) 1) 1)
0.82 0.68 0.14 0.92 0.82 0.1 0.98 0.92 0.06 1 0.98 0.02
4. Závěr Porovnání hodnot, které poskytuje program, s vypočtenými hodnotami. Hodnota P(0.0,0.2) P(0.2,0.4) P(0.4,0.6) P(0.6,0.8) P(0.8,.1.0) P(1.0,1.2) P(1.2,1.4) P(1.4,1.6) P(1.6,1.8) P(1.8,2.0) střední hodnota rozptyl
Program 0.0144 0.0852 0.0998 0.1164 0.1877 0.1854 0.1150 0.0981 0.0843 0.0136 0.9976 0.1764
Teoretický výpočet 0.02 0.06 0.10 0.14 0.18 0.18 0.14 0.10 0.06 0.02 1.00 0.17
Dle histogramů je patrné, že program generuje čísla dle trojúhelníkového rozložení. Hodnoty vypočítané programem se blíží k ručně vypočítaným hodnotám hlavně při vysokém počtu generování.
