---
# System prepended metadata

title: 4.  Компьютерные системы и сети 2021
tags: [Old, CSN, Lecture]

---

# 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




