# Zadanie 1

$v = 10^8 m/s$
$s = 2.5km$
$delay = \frac{2.5km}{10^8 m/s} = 0.000025s$
$b = 10Mb/s$
$2*delay = t$
minimalna długość ramki $r$:
$t = r / b$
$2 * 0.000025s = \frac{r}{10^7 b/s}$
$500 bitów= r$

# Zadanie 2

$P(p, n) = n p * (1 - p)^{n - 1}$

$(fg)' = f'g + fg'$
$((1 - p)^n)' = n (1-p)'(1-p)^{n-1}$
$P(p, n)' = n * (1 - p)^{n - 1} + np * n (1-p)'(1-p)^{n-1}$
$P(p, n)' = n * (1 - p)^{n - 1}(1 - np)$
Jedyne miejsce zerowe w przedziale $p \in(0, 1)$ to $1/n$.
$\lim_{n \to \infty} P(\frac{1}{n}, n) = \lim_{n \to \infty} (1 - \frac{1}{n})^{n - 1} =$$= \lim_{n \to \infty}\frac{1}{(1 - \frac{1}{n})} (1 - \frac{1}{n})^{n} = \lim_{n \to \infty} \frac{n}{n - 1} (1 - \frac{1}{n})^{n} = \frac{1}{e}$

# Zadanie 3

Rozważmy scenariusz, w którym mamy dwa wierzchołki: A i B, które zawsze mają coś do wysłania i często kolidują.

Powiedzmy, że oba próbują nadać swoje pakiety jednocześnie, kolidują i A wygrywa, ma teraz do odczekania < 2 rund, z kolei B ma < 4. Teraz A ma większe szanse na wysłanie kolejnych pakietów, a każda przegrana B jeszcze zwiększa tą przewagę i po 16 przegranych kolizjach B porzuca swój pakiet i mówimy, że A przejeło kanał.

# Zadanie 4

$M(x) = x^3 + x$
$G(x) = x^2 + x + 1$
$B(x) = x^r \cdot M(x) + S(x)$
$G(x) | B(x)$
$r = 2$ (stopień G)
$B(x) = x^5 + x^3 + S(x)$
Suma kontrolna:
$S(x) = x$ (bo $x^5 + x^3 + x$ dzieli się przez G)

dla $G'(x) = x^7 + 1$
$B(x) = x^{10} + x^8$
Suma kontrolna:
$S(x) = x^3 + x$

# Zadanie 5

Teza: $x + 1 | P(x) \iff$ P(x) ma parzystą liczbę składników.
Dowód:
- Zauważmy, że wielomiany z parzystą liczbą składników $n$ możemy podzielić na $n/2$ wielomianów dwuelementowych w postaci $x^k + x^m = x^k(1 + x^{m - k})$ (dla $k < m$).
- Lemat: Wielomiany w postaci $x^m + 1$ dzielą się przez $x+1$
Dowód: Zauważmy, że $x^m + 1 = x^m - 1$ w świecie modulo 2.
$x^m - 1 = (x - 1)(x^{m-1} + x^{m - 2} + ... + 1)$

Skoro wszystkie składowe wielomiany dzielą się przez $x+1$, to ich suma też się dzieli.

- Dla wielomianów z nieparzystą liczba elementów możemy wyróznić jeden element, wszystkie pozostałe dobrać w pary jak wyżej i okaże się, że cały wielomian się nie dzieli, bo ten wyróżniony element $x^n$ nie dzieli się przez $x + 1$.

# Zadanie 7

Każdy bit informacji jest sprawdzany przez unikalną kombinację co najmniej dwóch bitów parzystości.
- Jeżeli dokładnie jeden bit informacji zostanie przekłamany mamy dwa bity parzystości, które teraz się nie zgadzają, żeby powiedzieć, który został przekłamany.
- Jeżeli dokładnie jeden bit parzystości został przekłamany to możemy sprawdzić parzystość bitów za które odpowiadał i się o tym przekonać.

# Zadanie 8

Błąd dwóch bitów oddalonych od siebie o nie więcej niz 5 bitów można przedstawić jako wielomian szóstego stopnia $x^m(x^k + 1)$ gdzie $k \leq 6$.
Wielomian $x^3 + x + 1$ wykryje błędy na takich wielomianach.
Przyjrzyjmy się $x^m(x^k + 1)$:
- G nie dzieli $x^m$,
- G nie dzieli $(x^k + 1)$, bo:
- $(x + 1), (x^2 + 1)$ są mniejszego stopnia niż G,
- $(x^ 3 + 1) = G(x) - x$,
- $(x^ 4 + 1) = G(x) * x - (x^3 + x^2 + x - 1)$,
- $(x^5 + 1) = G(x) * (x^2 + 1) + (x^x + x)$,
- $(x^6 + 1) = G(x) ^2 + x^2$.

# Zadanie 9

Odbiorca sprawdza, czy G dzieli wiadomość, jeżeli dzieli to wiadomość jest poprawna, jeżeli nie dzieli to reszta z dzielenia daje informację o tym gdzie wystąpił błąd.

# Zadanie 10
(Paradoks urodzinowy)
Sposobów na wybranie $2^{m/2}$ różnych liczb m-bitowych (których jest $2^m$) jest $2^m \cdot (2^m - 1) \cdot ... \cdot (2^m - 2^{m/2} + 1)$, czyli ppb tego zdarzenia to około $e^{- \frac{2^m}{2 \cdot 2^m}} = e^{-1/2}$ czyli około 60%. Prawdopodobieństwo zdarzenia przeciwnego, to około 40% (czyli $\Omega (1)$).