# SIECI Ćwiczenia 1-3 ###### tags: `Sieci` ## Ćwiczenia 1 ### 1. ![](https://i.imgur.com/CypbYWg.png) * `10.1.2.3/8` Maska: `11111111.00000000.0000000.00000000` Adres sieci: `10.0.0.0` Adres rozgłoszeniowy: `10.255.255.255` Przykładowy adres: `10.1.1.1` * `156.17.0.0/16` Maska: `11111111.11111111.00000000.00000000` Adres sieci: `156.17.0.0` Adres rozgłoszeniowy: `156.17.255.255` Przykładowy adres: `156.17.2.137` * `99.99.99.99/27` Maska: `11111111.11111111.11111111.11100000` Adres sieci: `99 = 01100011` `01100011 & 11100000 = 01100000 = 96(dec)` `99.99.99.96` Adres rozgłoszeniowy: `01100000 | ~11100000 = 01100000 | 00011111 = 01111111 = 127(dec)` `99.99.99.127` Przykładowy adres: `99.99.99.100` * `156.17.64.4/30` Maska: `11111111.11111111.11111111.11111100` Adres sieci: `4(dec) & 11111100 = 00000100 & 11111100 = 00000100 = 4(dec)` `156.17.64.4` Adres rozgłoszeniowy: `00000100 | ~11111100 = 00000100 | 00000011 = 00000111 = 7(dec)` `156.17.64.7` Przykładowy adres: `156.17.64.5` * `123.123.123.123/32` Maska: `11111111.11111111.11111111.11111111` Nie jest to adres sieci tylko adres pojedyńczego hosta. ### 2. ![](https://i.imgur.com/OUcmloX.png) Do stworznenia 5 podsieci będziemy potrzebować 3 bitów ($\log_25$). Rozmiar maski to 16 bitów, więc pierwsze 16 bitów adresu IP musi pozostać niezmieniona. Pierwszy adres będzie miał następne 3 bity 000. Jego końcówka więc wygląda tak: `00000000.00000000`. Docelowy adres będzie musił wiziąć pod uwagę, że dodatkowe 3 niezmienne bity będą musiały pozostać niezmienione, więc maska powiększy się o 3. Docelowo będzie wyglądać tak: * `00001010.00001010.00000000.00000000/19 = 10.10.0.0/19` * Drugi adres będzie w miał następne 3 bity w postaci 001 więc docelowy adres będzie wyglądał tak: `00001010.00001010.00100000.00000000/19 = 10.10.32.0/19` * Trzeci: `00001010.00001010.01000000.00000000/19 = 10.10.64.0/19` * Czwarty: `00001010.00001010.01100000.00000000/19 = 10.10.96.0/19` * Ostatni adres będzie nieco większy ponieważ 3 bity mogą przechować 8 możliwości, a my wykorzystujemy tylko 5. Maska w ostatnim adresie nie będzie większa o 3 tylko o 1. Docelowy adres: `00001010.00001010.10000000.00000000/17 = 10.10.128.0/17` * `00001010.00001010.10000000.00000000/19 = 10.10.128.0/19` * `00001010.00001010.10100000.00000000/19 = 10.10.160.0/19` * `00001010.00001010.11000000.00000000/19 = 10.10.192.0/19` * `00001010.00001010.11100000.00000000/19 = 10.10.224.0/19` Liczba adresów IP zmniejsza się dzieląc sieć na 5 podsieci, ponieważ są one zajmowane również przez adresy rozgłoszeniowe i adresi sieci. W poprzedniej sieci były 2 zajęte adresy, teraz mamy 10. Aby usyskać minimalną podsieć należy za każdym razem dzieląc sieć, zwiększać maskę o jeden, wtedy otrzymamy najmniejszą możliwą podsieć. Otrzymujemy więc: * 1: `00001010.00001010.10000000.00000000/17 = 10.10.128.0/17` * 2: `00001010.00001010.01000000.00000000/18 = 10.10.64.0/18` * 3: `00001010.00001010.00100000.00000000/19 = 10.10.32.0/19` * 4: `00001010.00001010.00010000.00000000/20 = 10.10.16.0/20` * 5: `00001010.00001010.00000000.00000000/20 = 10.10.0.0/20` Najmniejsza podsieć, to ta z największą maską czyli 4 lub 5. Jej rozmiar to $2^{32-20}-2 = 2^{12} - 2 = 4094$. ### 3. ![](https://i.imgur.com/jpCiwH8.png) Zakres routingów: * 1: A `default` * 2: B `10.0.0.0 ` - `10.0.1.255` * 3: B `10.0.2.0 ` - `10.0.2.255` * 4: B `10.0.3.0 ` - `10.0.3.255` * 5: C `10.0.1.0 ` - `10.0.1.255` * 6: B `10.0.0.128` - `10.0.0.255` * 7: B `10.0.1.8 ` - `10.0.1.15` * 8: B `10.0.1.16 ` - `10.0.1.23` * 9: B `10.0.1.24 ` - `10.0.1.31` ![](https://i.imgur.com/qlYsalT.png) Wpisy od 2 do 4 możemy skleić w jeden - `10.0.1.0 - 10.0.3.255 = 10.0.0.0/22` 7- `10.0.1.8 - 10.0.1.15 = 10.0.8/29` Od 8 do 9 `10.0.1.16 - 10.0.1.31 = 10.0.1.16/28` Zmniejszona tablica routingu będzie więc wyglądać: | Podsieć | Cel | Początek | Koniec | |:-------------- | --- | ----------- | ----------------- | | `default ` | A | `0.0.0.0` | `255.255.255.255` | | `10.0.0.0/22 ` | B | `10.0.0.0` | `10.0.3.255` | | `10.0.1.0/24 ` | C | `10.0.1.0` | `10.0.1.255` | | `10.0.1.8/29 ` | B | `10.0.1.8` | `10.0.1.15` | | `10.0.1.16/28` | B | `10.0.1.16` | `10.0.1.31` | ### 4. ![](https://i.imgur.com/Yg6uhMc.png) Zakres routingów: * 1: A `default` * 2: B `10.0.0.0 ` - `10.255.255.255` * 3: C `10.3.0.0 ` - `10.3.0.255` * 4: B `10.3.0.32` - `10.3.0.63` * 5: B `10.3.0.64` - `10.3.0.95` * 6: B `10.3.0.96` - `10.3.0.127` ![](https://i.imgur.com/kRosrAW.png) Patrząc na rysunek, możemy zauważyć, że "przebijając" górną siecią B przez C w C zostaną nam zakresy: `10.3.0.0 - 10.3.0.31 = 10.3.0.0/27` i `10.3.0.128 - 10.3.0.255 = 10.3.0.128/25`. Dlatego możemy zredukować wszystkie określenia B od jednego, szerokiego `10.0.0.0 - 10.255.255.255 = 10.0.0.0/8`, i dodać dwie podsieci C "nad" B. ![](https://i.imgur.com/DDazWQX.png) | Podsieć | Cel | |:---------------- |:--- | | ` default ` | A | | ` 10.0.0.0/8 ` | B | | ` 10.3.0.0/27 ` | C | | ` 10.3.0.128/25` | C | ### 5. ![](https://i.imgur.com/vRaZQfV.png) Wpisy w tablicy będziemy uporządkowywać od najdłuższych pasujących prefiksów do najkrtószych. Jeżeli długość prefiksu jest taka sama, to nie sortujemy. **Dowód:** Załóżmy, że wpisy w tablicy roubingu są uporządkowane od najdłużyszch pasujących prefiksów do najkrótszych. Udowodnimy, że wybór pierwszego pasującego wpisu prowadzi do najlepszego dopasowania: Weźmy dowolny adres IP, oznaczmy go jako $x$. Niech $y$ będzie pierwszym wpisem w tablicy routingu, do którego nie pasuje $x$. Przez $n$ oznaczmy długość prefiksu $y$, a skoro $x$ pasuje do $y$, to pierwsze $n$ bitów $x$ oraz $y$ są takie same. Teraz weźmy dowolny wpis $z$ będący w tablicy routingu za $y$. Oznacza to, że $z$ ma mniejszy prefiks od $y$, a więc długość $m$ prefiksu $z$ spełnia nierówność $m \leq n$. Oznacza to, że dopasowane zostanie nie więcej bitów $x$ niż $n$, czyli $y$ nie jest gorszym dopasowaniem niż $z$, więc wybór "pierwszy pasujący" odpowiada zasadzie najlepszego dopasowania. $\Box$ ### 6. ![](https://i.imgur.com/XpEVbPR.png) Stan stabilny to taki w którym kolejne wysyłania wektorów nie powodują aktualizacji. Algorytm ten polega na okresowym powiadamianiu sąsiadów o całej swojej tablicy przekazywania, czyli w każdym korku tablica routingu będzie aktualizowana o nowe wpisy. Początkowo każdy zna tylko własnych sąsiadów. W tabelce liczbą będziemy oznaczać "odległość", a puste komórki będą w tym kroku jeszcze nieosiągalne. * Stan początkowy | Z: | A | B | C | D | E | F | |:---- | --- |:--- |:--- | --- |:--- |:--- | | do A | - | 1 | | | | | | do B | 1 | - | 1 | | | | | do C | | 1 | - | | 1 | 1 | | do D | | | | - | 1 | | | do E | | | 1 | 1 | - | 1 | | do F | | | 1 | | 1 | - | | do S | 1 | 1 | | | | | * Krok 1 | Z: | A | B | C | D | E | F | |:---- | -------- |:-------- |:-------- |:-------- | -------- |:-------- | | do A | - | 1 | 2(via B) | | | | | do B | 1 | - | 1 | | 2(via C) | 2(via C) | | do C | 2(via B) | 1 | - | 2(via E) | 1 | 1 | | do D | | | 2(via E) | - | 1 | 2(via E) | | do E | | 2(via C) | 1 | 1 | - | 1 | | do F | | 2(via C) | 1 | 2(via E) | 1 | - | | do S | 1 | 1 | 2(via B) | | | | * Krok 2 | Z: | A | B | C | D | E | F | |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- | | do A | - | 1 | 2(via B) | | 3(via C) | 3(via C) | | do B | 1 | - | 1 | | 2(via C) | 2(via C) | | do C | 2(via B) | 1 | - | 2(via E) | 1 | 1 | | do D | | 3(via C) | 2(via E) | - | 1 | 2(via E) | | do E | 3(via B) | 2(via C) | 1 | 1 | - | 1 | | do F | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | - | | do S | 1 | 1 | 2(via B) | | 3(via C) | 3(via C) | * Krok 3 | Z: | A | B | C | D | E | F | |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- | | do A | - | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | | do B | 1 | - | 1 | 3(via E) | 2(via C) | 2(via C) | | do C | 2(via B) | 1 | - | 2(via E) | 1 | 1 | | do D | 4(via B) | 3(via C) | 2(via E) | - | 1 | 2(via E) | | do E | 3(via B) | 2(via C) | 1 | 1 | - | 1 | | do F | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | - | | do S | 1 | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | Jak widać w 3. kroku osiągniemy stan stabilny - wszystkie routery w sieci będą znały drogę do pozostałych, a wyznaczone ścieżki są najkrótsze. ### 7. ![](https://i.imgur.com/mPXb4UB.png) * Stan początkowy - tablica z zadania 6. | Z: | A | B | C | D | E | F | |:----- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- | | do A | - | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | | do B | 1 | - | 1 | 3(via E) | 2(via C) | 2(via C) | | do C | 2(via B) | 1 | - | 2(via E) | 1 | 1 | | do D | 4(via B) | 3(via C) | 2(via E) | - | 1 | 2(via E) | | do E | 3(via B) | 2(via C) | 1 | 1 | - | 1 | | do F | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | - | | do S | 1 | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | * Krok 1 | Z: | A | B | C | D | E | F | |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- | | do A | - | 1 | 2(via B) | 1 | 3(via C) | 3(via C) | | do B | 1 | - | 1 | 3(via E) | 2(via C) | 2(via C) | | do C | 2(via B) | 1 | - | 2(via E) | 1 | 1 | | do D | 1 | 3(via C) | 2(via E) | - | 1 | 2(via E) | | do E | 3(via B) | 2(via C) | 1 | 1 | - | 1 | | do F | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | - | | do S | 1 | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | Tutaj A i D dowiadują się o połączeniu między sobą. * Krok 2 | Z: | A | B | C | D | E | F | |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- | | do A | - | 1 | 2(via B) | 1 | 2(via D) | 3(via C) | | do B | 1 | - | 1 | 2(via A) | 2(via C) | 2(via C) | | do C | 2(via B) | 1 | - | 2(via E) | 1 | 1 | | do D | 1 | 2(via A) | 2(via E) | - | 1 | 2(via E) | | do E | 2(via D) | 2(via C) | 1 | 1 | - | 1 | | do F | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | - | | do S | 1 | 1 | 2(via B) | 2(via A) | 3(via C) | 3(via C) | Stan stabilny, wyszystkie ścieżki są najkrótsze. ### 8. ![](https://i.imgur.com/fCuJOum.png) Na początku zróbmy tablice routingu dla działającego połączenia * Krok 1: | X | A | B | C | D | E | | ---- | --- | --- |:--- |:--- |:--- | | do A | - | 1 | 1 | | | | do B | 1 | - | | 1 | | | do C | 1 | | - | 1 | | | do D | | 1 | 1 | - | 1 | | do E | | | | 1 | - | * Krok 2: | X | A | B | C | D | E | | ---- | -------- | -------- |:-------- |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | | | do B | 1 | - | 2(via D) | 1 | 2(via D) | | do C | 1 | 2(via A) | - | 1 | 2(via D) | | do D | 2(via B) | 1 | 1 | - | 1 | | do E | | 2(via D) | 2(via D) | 1 | - | * Krok 3: | X | A | B | C | D | E | | ---- |:-------- | -------- |:-------- |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | 3(via D) | | do B | 1 | - | 2(via D) | 1 | 2(via D) | | do C | 1 | 2(via D) | - | 1 | 2(via D) | | do D | 2(via B) | 1 | 1 | - | 1 | | do E | 3(via B) | 2(via D) | 2(via D) | 1 | - | Teraz gdy mamy gotową tabele możemy przerwać połączenie między D i E * Stan początkowy: | X | A | B | C | D | E | | ---- |:-------- | -------- |:-------- |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | 3(via D) | | do B | 1 | - | 2(via D) | 1 | 2(via D) | | do C | 1 | 2(via D) | - | 1 | 2(via D) | | do D | 2(via B) | 1 | 1 | - | 1 | | do E | 3(via B) | 2(via D) | 2(via D) | 1 | - | * Krok 1: E zostaję odpięte od D | X | A | B | C | D | |:---- |:-------- | -------- |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | | do B | 1 | - | 2(via D) | 1 | | do C | 1 | 2(via D) | - | 1 | | do D | 2(via B) | 1 | 1 | - | | do E | 3(via B) | 2(via D) | 2(via D) | ==DIS== | * Krok 2: D informuje C i B, ale na razie komunikat dociera do C, że nie łączy się z E. C wysyła komunikat do A, że nie łączy się z E. | X | A | B | C | D | |:---- |:-------- | -------- |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | | do B | 1 | - | 2(via D) | 1 | | do C | 1 | 2(via D) | - | 1 | | do D | 2(via B) | 1 | 1 | - | | do E | 3(via B) | 2(via D) | ==DIS== | DIS | * Krok 3: A informuje C, że droga do E porzebiega przez B, a później do B dobiega informacja, że D nie ma połączenia do E. B wysyła komunikat do A, że nie ma połączenia. | X | A | B | C | D | |:---- |:-------- |:-------- |:------------ |:-------- | | do A | - | 1 | 1 | 2(via B) | | do B | 1 | - | 2(via D) | 1 | | do C | 1 | 2(via D) | - | 1 | | do D | 2(via B) | 1 | 1 | - | | do E | 3(via B) | ==DIS== | ==4(via A)== | DIS | * Krok 4: A otrzymuje komunikat że B i C nie ma połączenia do E. C informuje D, że zna drogę do E przez A. | X | A | B | C | D | |:---- |:-------- |:-------- |:-------- |:------------ | | do A | - | 1 | 1 | 2(via B) | | do B | 1 | - | 2(via D) | 1 | | do C | 1 | 2(via D) | - | 1 | | do D | 2(via B) | 1 | 1 | - | | do E | ==DIS== | DIS | 4(via A) | ==5(via C)== | * Krok 5: D informuje B, że zna drogę do E przez C. A wysyła informacje do C, że nie ma połączenia do E. | X | A | B | C | D | |:---- |:-------- |:------------ |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | | do B | 1 | - | 2(via D) | 1 | | do C | 1 | 2(via D) | - | 1 | | do D | 2(via B) | 1 | 1 | - | | do E | DIS | ==6(via D)== | 4(via A) | 5(via C) | * Krok 6: B informuje A, że zna droge do E przez D. Otrzymuje tak poison reverse. | X | A | B | C | D | |:---- |:------------ |:-------- |:-------- |:-------- | | do A | - | 1 | 1 | 2(via B) | | do B | 1 | - | 2(via D) | 1 | | do C | 1 | 2(via D) | - | 1 | | do D | 2(via B) | 1 | 1 | - | | do E | ==7(via B)== | 6(via D) | 4(via A) | 5(via C) | ### 9. ![](https://i.imgur.com/ITglfs0.png) ```graphviz graph finite_state_machine { rankdir=LR; node [shape = circle]; A -- B; B -- C; C -- A; C -- D; } ``` * Stan początkowy: | X | A | B | C | D | | ---- |:-------- |:-------- |:--- |:-------- | | do A | - | 1 | 1 | 2(via C) | | do B | 1 | - | 1 | 2(via C) | | do C | 1 | 1 | - | 1 | | do D | 2(via C) | 2(via C) | 1 | - | * Krok 1: Uszkodzenie połączenia między C i D. | X | A | B | C | D | | ---- |:-------- |:-------- |:------- |:-------- | | do A | - | 1 | 1 | 2(via C) | | do B | 1 | - | 1 | 2(via C) | | do C | 1 | 1 | - | ==DIS== | | do D | 2(via C) | 2(via C) | ==DIS== | - | * Krok 2: C wysyła informację do A i B, ale narazie indormacja dochodzi tylko do A, a B wysyła informacje do A, że zna droge do D przez C. | X | A | B | C | D | | ---- |:------- |:-------- |:--- |:------- | | do A | - | 1 | 1 | ==DIS== | | do B | 1 | - | 1 | ==DIS== | | do C | 1 | 1 | - | DIS | | do D | ==DIS== | 2(via C) | DIS | - | * Krok 3: Do B dochodzi informacja, że połączenie między C i D zostało przerwane, a A wysyła informacje do C, że zna drogę do D przez B. | X | A | B | C | D | | ---- |:------------ |:------- |:--- |:--- | | do A | - | 1 | 1 | DIS | | do B | 1 | - | 1 | DIS | | do C | 1 | 1 | - | DIS | | do D | ==3(via B)== | ==DIS== | DIS | - | * Krok 4: B wysyła informacje do A, że połączenie między C i D zostało przerwane, a C wysyła informacje do B, że zna drogę do D przez A. | X | A | B | C | D | | ---- |:------- |:--- |:------------ |:--- | | do A | - | 1 | 1 | DIS | | do B | 1 | - | 1 | DIS | | do C | 1 | 1 | - | DIS | | do D | ==DIS== | DIS | ==4(via A)== | - | * Krok 5: C wysyła informacje do B, że połączenie między C i D zostało przerwane, a B wysyła informacje do A, że zna drogę do D przez C. | X | A | B | C | D | | ---- |:--- |:------------ |:------- |:--- | | do A | - | 1 | 1 | DIS | | do B | 1 | - | 1 | DIS | | do C | 1 | 1 | - | DIS | | do D | DIS | ==5(via C)== | ==DIS== | - | Dalsze kroki zapętlają się i dostajemy cykl. ### 10. ![](https://i.imgur.com/52RcSpp.png) ```graphviz digraph finite_state_machine { rankdir=LR; node [shape = circle]; a1 -> x0; a1 -> y0; x0 -> a2; y0 -> a2; a2 -> x1; a2 -> y1; "..." [ style = dashed ]; x1 -> "..." [ style=dashed ]; y1 -> "..." [ style=dashed ]; } ``` Router $a0$ przesyła komunikat do routertów $x0$ i $y0$ (1 jednoskta czasu). Router $x0$ i $y0$ przesyłają do $a1$, kóry otrzyma 2 komunikaty. Router $a1$ ma do przekazania dwa komunikaty, każdy do dwóch następnych routerów (zajmuje mu to 2 jednoski czsu). Router $a2$ ma do przekazania 4 komunikaty (4 jednoski czasu) itd... Poprawione 10 (chyba) Weźmy graf (sieć, wierzchołek-router) taki że wierzchołek $A_0$ ma dwie krawędzie, do $X_0,Y_0$. $X_0,Y_0$ mają po jednej krawędzi do wierzchołka $A_1$. $A_1$ ma dwie krawędzie, do $X_1,Y_1$. $X_1,Y_1$ mają po jednej krawędzi do wierzchołka $A_2$. $A_2$ ma dwie krawędzie, do $X_2,Y_2$. I tak dalej do $A_{\lfloor{n/3}\rfloor}$ Router $A_0$ przesyła komunikat do routerów $X_0$ i $Y_0$ w jednej jednostce czasu. Routery $X_0$ i $Y_0$ przesyłają komunikat do $A_1$ w jednej jednostce, do którego dojdą dwa komunikaty. Router $A_1$ ma teraz do przekazania dwa komunikaty, każdy do dwóch następnych routerów. Zajmie mu to dwie jednoski czsu. Po przejściu przez $X_1, Y_1$ router $A_2$ będzie miał do przekazania cztery komunikaty routerom $X_2, Y_2$ czyli zajmie mu to cztery jednostki czasu, itd. do $A_{\lfloor{n/3}\rfloor}$. W sumie będziemy mieć $2*\sum_{i=0}^{\lfloor{n/3}\rfloor} 2^i=2^{1+\lfloor{n/3}\rfloor}-1$ jednostek czasu, a $1+\lfloor{n/3}\rfloor\in \Omega(n)$ ## Ćwiczenia 2 ### 1. ![](https://i.imgur.com/9kguNdW.png) droga ($s$) = $2,5$km = $2500$m prędkość ($V$) = $10^8 \frac{m}{s}$ bandwidth ($b$) = $10$Mb = $10^7$bitów opóźnienie ($d$) = $\frac{s}{V}$ = $2,5*10^{-5}$s Długość ramki = $b*d*2$ = $10^7*2,5*10^{-5}*2$ = $500$bitów ### 2. ![](https://i.imgur.com/7tIeabH.png) Protokół ALOHA wysyła bez uprzedniego sprawdzania czy ktoś nadaje i sprawdzania czy będzie kolizja (np. stacje naziemne transmitujące do satelity + stacje się nawzajem nie widzą). Czas dzielimy na rundy(sloty). Założenie jest takie, że mamy dużo wysyłających nadajacych rzadko + pakiety mają takie same długości. Wysyłamy pakiet/slot czasowy z prawdopodobieństwem p. 1. Załóżmy, że uda się nam wysłać ramkę. 2. Załóżmy, że innym n-1 uczestnikom nie uda sie wysłać ramki. 3. Takich przypadków, że jednemu udało się wysłać, a reszenie nie jest $n$. Skoro każdy wysyła z prawdopodobieństwiem $p$, to szansa, że jeden wyśle a pozostałe nie wyślą jest równa: * $P(p,n)=n*p*(1-p)^{n-1}$ Teraz liczymy pochodną po $p$ i otrzymujemy: $P'(p)=n(1-p)^{n-1}-(n-1)*n*(1-p)^{n-2}*p$ $P'(p)=-\frac{n*(1-p)^n(n*p-1)}{(p-1)^2}$ Miejsca zerowe: $p=\frac{1}{n}$ Jeśli miejsce zerowe jest w $\frac{1}{n}$ to jest tam ekstemum. Teraz liczymy drugą pochodną: $P''(p)=\frac{n^2*(1-p)^{n-1}*(n*p-1)}{(p-1)^2}+\frac{2*n*(1-p)^n*(n*p-1)}{(p-1)^3}-\frac{n^2*(1-p)^n}{(p-1)^2}$ $P''(p)=-\frac{(n-1)*n*(1-p)^n*(n*p-2)}{(p-1)^3}$ Miejsca zerowe: $p=\frac{2}{n}$ * Podstawiając $1/n$ do drugiej pochodnej otrzymujemy coś ujemnego -> maksimum. * $lim_{n \to \infty}[P(\frac{1}{n}, n) = (1-\frac{1}{n})^{n-1} = (1-\frac{1}{n})^n * (1-\frac{1}{n})^{-1} ]= \frac{1}{e} * 1 = \frac{1}{e}$ ### 3. ![](https://i.imgur.com/RkAGkcq.png) A i B muszą sobie wysłać nawzajem jakieś pakiety w tym samym czasie. Próbują zrobić to w tym samym czasie następuje kolizja. Oba nadajniki czekają więc losową ilość czasu między na przedziale [0, 2]. Zakładamy, że A losuje szybsze wysłanie więc wysyła pakiet pierwszy, a B notuje kolizje. Teraz gdy A ma dalej pakiety do wysłania i B próbuje coś do niego wysłać więc znowu oba notują kolizje. Z racji tego że to druga nieudana próba dla B, B losuje na przedziale [0,4], a A losuje na przedziale [0,2], więc szansa na to że wygra znowu A jest większa. Następnym razem B znowu przegrywa i teraz losuje na [0,8]. Dzieje się tak, aż B przegra wszystkie próby (16 przegranych kolizji z rzędu) i wtedy B wycofuje się na dłuższy czas lub na przykład odrzuca pakiet. Prawdopodobieństwo takej sytuacje juest dość duże, bo po 4-5 przegranych próbach szansa na przejęcie kanau przez B jest bardzo niska. Wtedy mówimy że A przejeło kanał. ### 4. ![](https://i.imgur.com/h8w69sA.png) * wiadomość $m=1010 \iff M(x)=x^3+x$ ::: info $B(x) = x^r * M(x) + S(x)$ - gdzie s wybieramy tak, żeby B(x) był podzielny przez G(x) ::: 1. $G(x) = x^2 + x + 1 \iff g=111_2$ deg=2 Dzielimy $x^r*M(x)=x^5+x^3 = 101000_2$ przez G(x) $x^3+x^2+x$ reszta $S(x)=x$ Suma kontrolna powinna mieć $deg(G)=2$ bity, czyli $s = 10$ 2. $G(x)=x^7+1 \iff g=10000001_2$, deg=7 Dzielimy $x^r*M(x)=x^{10}x^8 = 10100000000_2$ przez G(x) $x^{3}+x$ reszta $S(x)=x^3+x$ Suma kontrolna powinna mieć $deg(G)=7$ bity, czyli $s = 0001010$ ### 5. ![](https://i.imgur.com/9BctmWU.png) TEZA: Jeżeli liczba zapalonych bitów w słowie maszynowym jest parzysta dzielenie przez $x+1$ da resztę 0, a w przeciwnym przypadku 1. Musimy pokazać, że $x+1$ dzieli bez reszty wszystkie wielomiany o parzystej liczbie składników. Każdy wielomian w postaci $x^n-x^k \equiv x^n+x^k$, więc w szczególności $x-1 \equiv x+1$. Dla $m = 0 \to s=0$ i $m = 1 \to s=1$ więc oczywiste. **Założenie indukcyjne:** Załóżmy, że $m=k$, gdzie $k$ całkowite: $x^k-1=(x-1)*P(x)$, gdzie P to wielomian. Weźmy teraz $m=k+1$: $x^{k+1}-1=(x-1)*Q(x)$, gdzie $Q$ to wielomian. $x^{k+1}-1= (x-1)*x^k+x^k-1$ $x^{k+1}-1= (x-1)*x^k+(x-1)*P(x)$(z zał indukcyjnego) $x^{k+1}-1= (x-1)*(x^k+P(x))$ $x^{k+1}-1= (x-1)*(x^k-x-1)$ $x^{k+1}-1= (x-1)*(x^k*(x-1)+x^k-x-1)$ $x^{k+1}-1= (x-1)*(x^{k+1}-x^k+x^k-x-1)$ $x^{k+1}-1= (x-1)*Q(x)$ ### 7. Z wykładu wiemy, że wystarczy pokazać, że odległość jest większa bądź równa 3. Czyli chcemy pokazać że nie występuje odległość 1 i 2. Macierz generująca $G$ kodu (7,4) i jego macierz kontroli parzystości $H$, a $x$, $y$ to kody z $G$. Wtedy $x-y$ należy do $H$ ponieważ $H$ jest kodem liniowym. Teraz sprawdzamy czy możliwe jest: 1.$dist(x,y)=1$ wtedy wszystkie kolumny w $H$ są niezerowe, ale jeśli $x-y$ jest kodem (7,4), to $G(x-y)=0$, co jest sprzecznością. 2.$dist(x,y)=2$, wtedy $G(x-y)=0$ a tak jest tylko w wypadku kuedy 2 kolumny są liniowo zależne, a w kodzie Hamminga nie ma liniowej zależności. ### 8.