# 4. Компьютерные системы и сети 2021

## Плотность и кумулятивная функция вероятности совместного распределения для дискретного канала

Плотность совместного распределения дискретных случайных величин $X$ и $Y$ (в нашем случае - входные и выходные символы канала):
$$
p_{x,y} = P(X=x, Y=y)
$$

Кумулятивная функция вероятности совместного распределения:
$$
P_{x,y} = P(X \le x, Y \le y)
$$

Примем (без ограничения общности), что для дискретного канала $x,y \in \bf N$, где $\bf N$ - множество натуральных чисел, и что размеры алафитов $x$ и $y$ равны $n$. Тогда $p_{x,y}$ и $P_{x,y}$ - это матрицы размером $n\times n$

Уважаемые коллеги - ответьте, пожалуйста (с именем и фамилией), на вопросы -
1. Как из матрицы $p_{x,y}$ получить матрицу $P_{x,y}$ ?
2. Как из матрицы $P_{x,y}$ получить матрицу $p_{x,y}$ ?

### Формула условной вероятности

$$
p(x,y) = p(y|x) p(x) = p(x|y) p(y)
$$

### Формула Скляра
$$
p(x,y) = p(x) \cdot c(x,y) \cdot p(y)
$$

Величина c(x,y) -- имеет название -- связь, копула, "матрица канала"

### Прошлое задание на лабораторную работу
Взять свое имя и фамилию и две даты рождения - свою и своего друга (в формате 1 лаб.раб.) и породить две последовательности, каждая длиной 10000 символов
Первая последовательность - входная последовательность в канале, а вторая - выходная.
1. По этим двум строкам нужно подсчитать матрицу p(x,y)
2. Подсчитать взаимную информацию $I$
3. Получить матрицу c(x,y) из матрицы p(x,y) и двух векторов: p(x) и p(y)

## Как получить "эмпирическую копулу" - ?

Во-первых, надо рассмотреть интегральную копулу $C(u,\;v)$ - двухмерную функцию распределения, определённую на квадрате $[0,\;1]\times [0,\;1]$, такую, что все (два) её маргинальных распределения **равномерны** на интервале ${\displaystyle [0,\;1]}$.

Вот некоторые ее свойства:
$$
C(u,\;0)=C(0,\;v)=0, \quad
C(u,\;1)=u;\quad
C(1,\;v)=v.
$$
При анализе данных с неизвестным распределением, можно построить «эмпирическую копулу» путём такой свёртки, чтобы маргинальные распределения получились равномерными. Математически это можно записать так:

$$
{\displaystyle C_{n}\left({\frac {i}{n}},{\frac {j}{n}}\right)={\frac {1}{n^2}}\cdot } \underline{NumberOfPairs(x,y)}
$$
таких что
$$
{\displaystyle x\leq x_{(i)}{\text{ и }}y\leq y_{(j)}\,,1\leq i\leq n,1\leq j\leq n}$$

где $x(i)$ —представляет i-ую порядковую статистику $x$ (порядковая статистика находится путем сортировки ).

Во-вторых, из матрицы $C_{i,j}$ надо получить матрицу $с_{i,j}$ (см. задание 2 в начале лекции)

## Текущее задание на лабораторную работу

Разработать и реализовать свой алгоритм синхронизации клиента и сервера

### Пример простого алгоритма синхронизации:

1) Клиент отмечает текущее местное время (желательно все отметки времени брать по Гринвичу - UTC формат без сдвига по часовым поясам ) в пакете «запроса времени» и отправляет запрос на сервер
2) При получении запроса сервер ставит отметку серверного времени и возвращает ее
3) После получения отметки серверного времени клиент вычитает текущее время из времени отправки и делит на два для вычисления задержки.

Текущее время вычитается из времени сервера, чтобы определить дельту времени между клиентом и сервером и добавляется половинная задержка, для получения уточненной дельты часов клиента относительно сервера. (Пока этот алгоритм очень похож на SNTP)

Клиент повторяет шаги 1) 2) и 3) несколько раз (пять или более), каждый раз делая паузу на несколько секунд. В это время может быть разрешен другой трафик, но его следует минимизировать для достижения наилучших результатов.

Результаты приема пакетов накапливаются и сортируются в порядке от наименьшей задержки до наибольшей. Средняя задержка определяется путем выбора выборки средней точки (медианы) из этого упорядоченного списка.

Все результаты, отклоняющиеся примерно на одно *стандартное отклонение?* от медианы, отбрасываются, а оставшиеся образцы усредняются.

Этот алгоритм предполагает синхронизацию нескольких клиентов с одним сервером.

### Ссылка на готовую javascript реализацию -
https://npm.runkit.com/timesync

### Ссылка на историю и один из алгоритмов синхронизации в сети -
https://www.wikiwand.com/en/Network_Time_Protocol