Synchronizačný signál

Tento príklad sa opieral o koncept očakávanej (priemernej) hodnoty náhodnej premennej. Očakávaná hodnota náhodnej premennej sa dá chápať ako priemer všetkých hodnôt, ktoré táto premenná môže nadobúdať, vážený pravdepodobnosťou, že ich nadobudne.

Zhrnutie zadania

Pre interval [0, D] a striktne rastúcu postupnosť T(0), …, T(N-1) nájdi X také, že E(X) bude minimálna, pričom:

E(X) = t+T(i) - X | i, kde {i = 0 a zároveň Xt+T(0)} alebo {X > t+T(i-1) a zároveň Xt+T(i)}

kde t je celočíselná náhodná premenná z [0, D - T(N-1)].

Riešenie

Začneme niekoľkými pozorovaniami, ktorými značne zredukujeme veľkosť množiny potenciálnych hodnôt X a následne jednoducho pre každú potenciálnu hodnotu X vyčíslime E(X). Hľadaným riešením potom bude X, ktorého E(X) bolo minimálne. Na vyriešenie úlohy je nutné vykonať len posledné spomenuté pozorovanie, pričom ostatné pozorovania uvádzame pre ilustráciu uvažovania nad problémom.

Iste ste si všimli, že v poslednom argumente sme nevyužili celočíselnosť t. Táto bola v zadaní spomenutá len ako pomôcka, aby si riešiteľ odvodil, že X môže byť len celé číslo a mohol začať experimentovať s riešeniami založenými na hrubej sile, t.j. vyhodnotiť všetky možné hodnoty X a t a priamo vyčíslovať E(X).

Zostáva teda už len efektívne vyhodnotiť všetky E(T(i)). Vzorové riešenie jednoducho pre každé X = T(i) rozdelí validné hodnoty t na intervaly tj, pričom v každom tj sa čaká na rovnaký signál T(j) a pre každý interval vypočíta priemernú dobu čakania. Výsledné E(X) je potom, podľa definície očakávanej hodnoty náhodnej premennej (viď. odkaz v úvode), priemer týchto dôb čakania vážený dĺžkami prislúchajúcich intervalov hodnôt t. Pre detailnejší opis prosím konzultujte okomentovaný zdrojový kód vzorového riešenia (v jazyku C).

Vypracoval: Daniel Švoňava

Autor príkladu: Daniel Švoňava