Podstawy informatyki: zestaw na powtórkę

Wzory, najważniejsze kroki metod dla każdego tematu i 20 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.

Nowe zadania Wróć do przedmiotu

W oknie drukowania wybierz „Zapisz jako PDF”, aby zachować kopię na swoim urządzeniu.

1Wzory i metody

Systemy liczbowe

Wagi pozycji: dwójkowy 2^k, ósemkowy 8^k, szesnastkowy 16^k
Na dziesiętny: Σ d_k·b^k
Z dziesiętnego: dziel przez podstawę, czytaj reszty od dołu do góry
Szesnastkowy ↔ dwójkowy: jedna cyfra szesnastkowa = 4 bity
Kod uzupełnień do dwóch (U2): odwróć bity i dodaj 1

Rachunek zdań i dowody

Wiersze tablicy prawdy: 2ⁿ
Implikacja: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Zaprzeczenie implikacji: ¬(p → q) ≡ p ∧ ¬q
Równoważność: p ↔ q ≡ (p → q) ∧ (q → p)
Prawa de Morgana: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Prawa rozdzielności: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Zaprzeczanie kwantyfikatorów: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Metoda

Policz różne zmienne: tablica prawdy ma 2ⁿ wierszy, a zaczyna się od samych jedynek.
Każdej podformule daj osobną kolumnę i wypełniaj kolumny od wewnątrz na zewnątrz.
Stosuj regułę każdego spójnika: → jest 0 tylko dla 1 → 0, ↔ jest 1, gdy obie strony się zgadzają.
Przy równoważnościach porównaj końcowe kolumny wiersz po wierszu; przy wnioskowaniu patrz tylko na wiersze, w których każda przesłanka jest równa 1.
Aby zaprzeczyć zdaniu z kwantyfikatorem, przesuń ¬ do środka, zamień ∀ i ∃ oraz zaprzecz formule wewnętrznej.

Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki

Podstawowe bramki: A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Reguły algebry Boole’a: X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
Prawa de Morgana: (X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Kolejność na mapie Karnaugha: 00, 01, 11, 10 (Gray code)
Grupa 2ᵏ komórek: traci k zmiennych
Multiplekser 4-do-1: F = A′B′I₀ + A′BI₁ + AB′I₂ + ABI₃
Przerzutniki: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Liczniki: n-bitowy: 2ⁿ stanów; mod-N: najmniejsze n z 2ⁿ ≥ N; f_out = f_clk/N
Licznik asynchroniczny (ripple): f_max = 1/(n·t_pd)
Liczniki pierścieniowy i Johnsona: n i 2n stanów

Metoda

Dla układu przechodź od wejść do wyjścia bramka po bramce i zapisuj wartość na każdym przewodzie albo zapisz jego wyrażenie i wypełnij tablicę prawdy.
Przy upraszczaniu wpisz jedynki (a stany nieokreślone jako X) na mapę Karnaugha z wierszami i kolumnami w kodzie Graya: 00, 01, 11, 10.
Pokryj jedynki jak najmniejszą liczbą jak największych grup po 1, 2, 4, 8 lub 16 komórek, zawijając przez brzegi; każda grupa to jeden iloczyn ze zmiennych, które pozostają stałe. Dla postaci POS grupuj zera.
Przy przerzutnikach i licznikach odczytuj wejścia przy każdym aktywnym zboczu zegara, zapisuj stan po każdym zboczu i pamiętaj, że n-bitowy licznik zawija się po 2ⁿ stanach.

Teoria liczb i arytmetyka modularna

Dzielenie z resztą: a = q·n + r, 0 ≤ r < n
Euklides: gcd(a, b) = gcd(b, a mod b)
Najmniejsza wspólna wielokrotność: lcm(a, b) = a·b/gcd(a, b)
Odwrotność: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Kongruencja liniowa: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Funkcja φ Eulera: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Metoda

Najpierw zredukuj każdą liczbę modulo n; reszty leżą między 0 a n − 1.
Aby znaleźć NWD, dziel wielokrotnie algorytmem Euklidesa; ostatnia niezerowa reszta jest NWD.
Aby znaleźć element odwrotny, uruchom rozszerzony algorytm i zachowaj współczynnik przy a; dodaj n, jeśli jest ujemny.
Rozwiąż a·x ≡ b, mnożąc przez a⁻¹; dwie kongruencje połącz, zapisując x = r₁ + m₁k.
Przy potęgach zapisz wykładnik binarnie i wielokrotnie podnoś do kwadratu; w RSA d = e⁻¹ mod φ(n), gdzie φ(n) = (p − 1)(q − 1).

Teoria grafów

Lemat o uściskach dłoni: Σ deg(v) = 2|E|
Grafy pełne: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Graf regularny: |E| = n·k/2
Drzewo i las: |E| = n − 1, |E| = n − c
Liście drzewa: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: cykl: wszystkie stopnie parzyste; ścieżka: dokładnie 2 stopnie nieparzyste
Cykle Hamiltona w K_n: (n − 1)!/2
Aktualizacja w algorytmie Dijkstry: d(v) = min(d(v), d(u) + w(u, v))
Marsze o długości L: (Mᴸ)_ij

Metoda

Zapisz stopień każdego wierzchołka; suma stopni jest równa dwukrotności liczby krawędzi.
W zadaniach o grafach eulerowskich sprawdź, czy graf jest spójny, i policz wierzchołki o nieparzystym stopniu.
Dla drzew użyj n − 1 krawędzi i lematu o uściskach dłoni.
W algorytmie Dijkstry prowadź tabelę tymczasowych odległości i w każdej rundzie zatwierdzaj niezatwierdzony wierzchołek o najmniejszej odległości.
Dla minimalnego drzewa rozpinającego posortuj krawędzie według wagi i pomijaj każdą krawędź zamykającą cykl (Kruskal) albo rozbudowuj jedno drzewo od wierzchołka startowego (Prim).

Podsieci IPv4

Hosty na podsieć: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
Rozmiar bloku: 256 − (mask octet)
Adres sieci: IP AND maska
Adres rozgłoszeniowy: IP OR (NOT maska): wszystkie bity hosta równe 1
Podsieci z n pożyczonych bitów: 2ⁿ

2Zadania do ćwiczenia

1.Systemy liczboweŚredni

Ustaw bity tak, aby zapisywały −26 w 8-bitowym kodzie uzupełnień do dwóch. Jaka jest wartość wzorca U odczytanego jako liczba bez znaku?

N = −268 bit

U =

2.Systemy liczboweTrudny

Ustaw bity na 8-bitowy wynik działania 1110 0101 >> 3. Jaka jest wartość wyniku R w zapisie dziesiętnym?

1110 0101>> 3

R =

3.Rachunek zdań i dowodyŚredni

W ilu z 8 wierszy tablicy prawdy (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) jest prawdziwe? Nazwij tę liczbę N.

(r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q)

N =

4.Rachunek zdań i dowodyTrudny

Dane są przesłanki b ∨ a; b → c; a → c. Jaki wniosek z nich wynika? Kliknij go.

b ∨ ab → ca → c

1b
2b ∧ a
3¬c
4c

5.Logika cyfrowa: bramki, mapy Karnaugha i przerzutnikiŚredni

Użyj mapy Karnaugha, aby znaleźć minimalną postać iloczynu sum (POS) funkcji F(A, B, C, D) = Σm(5, 6, 7, 11, 13, 14, 15). Ile sum (czynników) N ona ma?

F(A, B, C, D) = Σm(5, 6, 7, 11, 13, 14, 15)

N =

6.Logika cyfrowa: bramki, mapy Karnaugha i przerzutnikiTrudny

Dla F(A, B, C, D) = Σm(2, 9, 12, 14) + d(3, 7), gdzie d oznacza stany nieokreślone, znajdź liczbę N istotnych implikantów prostych.

F(A, B, C, D) = Σm(2, 9, 12, 14) + d(3, 7)

N =

7.Teoria liczb i arytmetyka modularnaŚredni

Znajdź funkcję φ Eulera φ(1183), czyli liczbę liczb całkowitych od 1 do 1183 względnie pierwszych z 1183.

n = 1183 = 7·13²

φ(1183) =

8.Teoria liczb i arytmetyka modularnaTrudny

29 jest liczbą pierwszą. Użyj małego twierdzenia Fermata, aby znaleźć 22⁶¹⁵⁰⁶ mod 29.

p = 29k = 61506

22⁶¹⁵⁰⁶ mod 29 =

9.Algorytmy i złożonośćŚredni

Dlaczego wiele bibliotecznych procedur sortowania przełącza się na sortowanie przez wstawianie dla bardzo małych podtablic?

ASortowanie przez wstawianie jest O(n log n) w najgorszym przypadku
BAlgorytmy rekurencyjne nie radzą sobie z tablicami poniżej 10 elementów
CSortowanie przez wstawianie ma mały narzut i jest szybkie dla małych lub prawie posortowanych danych
DSortowanie przez wstawianie zużywa mniej pamięci niż każdy inny algorytm sortowania dla dużych danych

10.Algorytmy i złożonośćTrudny

Algorytm Strassena mnoży macierze, używając 7 zamiast 8 rekurencyjnych mnożeń bloków o połowie rozmiaru. Jaki jest jego czas działania?

AΘ(n³)
BΘ(n² log n)
CΘ(n^{log₂ 7}), około n^2,81
DΘ(n²)

11.Struktury danychŚredni

Drzewo binarne ma korzeń 1 z lewym dzieckiem 2 i prawym dzieckiem 3; węzeł 2 ma dzieci 4 (lewe) i 5 (prawe). Jaki jest wynik przejścia preorder?

A1 2 4 5 3
B4 2 5 1 3
C4 5 2 3 1
D1 2 3 4 5

12.Struktury danychTrudny

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

AZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
BZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy
CUsunięcie całego poddrzewa
DZamianę go z korzeniem

13.Teoria grafówŚredni

Drzewo ma 3× wierzchołek stopnia 3, 3× wierzchołek stopnia 4, 3× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?

3 × deg 33 × deg 43 × deg 2

L =

14.Teoria grafówTrudny

Ile jest marszów o długości 2 z D do A? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.

M = macierz sąsiedztwaL = 2

N =

15.Bazy danych i SQLŚredni

Czym jest wyzwalacz (trigger) w bazie danych?

ARodzajem indeksu przyspieszającym wyszukiwanie
BZaplanowaną kopią zapasową bazy danych
CKodem uruchamianym automatycznie, gdy w tabeli zajdzie określone zdarzenie, takie jak INSERT, UPDATE lub DELETE
DZapytaniem uruchamianym ręcznie przez użytkownika

16.Bazy danych i SQLTrudny

Istnieje indeks złożony na (last_name, first_name). Który warunek może z niego skorzystać najskuteczniej?

AWHERE first_name LIKE '%a'
BWHERE last_name = 'Jansen'
CWHERE first_name = 'Eva'
DWHERE UPPER(first_name) = 'EVA'

17.Sieci komputeroweŚredni

Jaka jest główna różnica między metodami HTTP GET i POST?

AGET usuwa zasób, a POST odczytuje go z bazy danych serwera
BGET używa UDP, POST używa TCP
CGET jest szyfrowane, POST nie
DGET pobiera zasób, POST przesyła dane w treści żądania

18.Sieci komputeroweTrudny

Użytkownik może wykonać ping do 8.8.8.8, ale nie może otworzyć żadnej strony po nazwie. Gdzie najprawdopodobniej leży problem?

AW kablu fizycznym
BW rozwiązywaniu nazw (DNS)
CW bramie domyślnej
DW sterowniku karty sieciowej

19.Podsieci IPv4Średni

Dział potrzebuje 1744 adresów hostów w jednej podsieci. Jaki jest najdłuższy prefiks p (najmniejsza podsieć), który wystarczy?

1744 hosts

p =

20.Podsieci IPv4Trudny

Host ma adres 10.20.190.226/30. Jaka jest ostatnia liczba (czwarty oktet) x adresu rozgłoszeniowego jego podsieci?

10.20.190.226/30

x =

3Roztwory

1.Systemy liczbowe

Odpowiedź: U = 230

Ustawianie bitów: każdy bit ma wartość będącą potęgą dwójki (128, 64, …, 1). Jedna cyfra szesnastkowa to dokładnie cztery bity, a w 8-bitowym kodzie uzupełnień do dwóch skrajny lewy bit ma wartość −128. Operacje bitowe działają osobno na każdej pozycji bitu.

Odwróć i dodaj jeden

26 = 0001 1010

odwrócone: 1110 0101

+1 → 1110 0110

Odczytaj bez znaku

1110 0110₂ = 256 − 26 = 230

Odpowiedź

U = 230

2.Systemy liczbowe

Odpowiedź: R = 28

Bit po bicie

Przesunięcie w prawo o 3 przesuwa każdy bit o 3 pozycji w prawo; bity, które wypadną z prawego końca, są tracone, a z lewej wchodzą zera.

1110 0101 >> 3

= 0001 1100

Wartość wyniku

0001 1100₂ = 28

Odpowiedź

R = 28

3.Rachunek zdań i dowody

Odpowiedź: N = 3

Tablice prawdy: formuła z n różnymi zmiennymi ma 2ⁿ wierszy, po jednym dla każdej kombinacji wartości logicznych (1 = prawda, 0 = fałsz). Pracuj od wewnątrz na zewnątrz i każdej podformule daj osobną kolumnę. ¬a odwraca wartość; a ∧ b jest równe 1 tylko wtedy, gdy oba są równe 1; a ∨ b jest równe 0 tylko wtedy, gdy oba są równe 0; a → b jest równe 0 tylko wtedy, gdy a = 1 i b = 0; a ↔ b jest równe 1, gdy obie strony są równe.

Tablica prawdy wiersz po wierszu

p = 1, q = 1, r = 1: p ∧ r = 1, r ∨ (p ∧ r) = 1, ¬q = 0, ¬q → p = 1, (¬q → p) ∨ q = 1, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 1

p = 1, q = 1, r = 0: p ∧ r = 0, r ∨ (p ∧ r) = 0, ¬q = 0, ¬q → p = 1, (¬q → p) ∨ q = 1, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 0

p = 1, q = 0, r = 1: p ∧ r = 1, r ∨ (p ∧ r) = 1, ¬q = 1, ¬q → p = 1, (¬q → p) ∨ q = 1, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 1

p = 1, q = 0, r = 0: p ∧ r = 0, r ∨ (p ∧ r) = 0, ¬q = 1, ¬q → p = 1, (¬q → p) ∨ q = 1, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 0

p = 0, q = 1, r = 1: p ∧ r = 0, r ∨ (p ∧ r) = 1, ¬q = 0, ¬q → p = 1, (¬q → p) ∨ q = 1, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 1

p = 0, q = 1, r = 0: p ∧ r = 0, r ∨ (p ∧ r) = 0, ¬q = 0, ¬q → p = 1, (¬q → p) ∨ q = 1, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 0

p = 0, q = 0, r = 1: p ∧ r = 0, r ∨ (p ∧ r) = 1, ¬q = 1, ¬q → p = 0, (¬q → p) ∨ q = 0, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 0

p = 0, q = 0, r = 0: p ∧ r = 0, r ∨ (p ∧ r) = 0, ¬q = 1, ¬q → p = 0, (¬q → p) ∨ q = 0, (r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q) = 0

Policz wiersze z wartością 1

(r ∨ (p ∧ r)) ∧ ((¬q → p) ∨ q): 1, 0, 1, 0, 1, 0, 0, 0

N = 3

Odpowiedź

N = 3

4.Rachunek zdań i dowody

Odpowiedź: c

Kwantyfikatory i wnioskowania: ¬∀x P(x) ≡ ∃x ¬P(x) oraz ¬∃x P(x) ≡ ∀x ¬P(x). Przesuń negację do środka, zamień każdy kwantyfikator, który mija, i zaneguj formułę wewnętrzną prawami rachunku zdań, takimi jak ¬(a → b) ≡ a ∧ ¬b. Wnioskowanie jest poprawne, gdy wniosek jest równy 1 w każdym wierszu, w którym wszystkie przesłanki są równe 1. Pojedynczy wiersz z prawdziwymi przesłankami i fałszywym wnioskiem jest kontrprzykładem i pokazuje, że wnioskowanie jest niepoprawne.

Wiersze z wszystkimi prawdziwymi przesłankami

a = 1, b = 1, c = 1: b = 1, b ∧ a = 1, ¬c = 0, c = 1

a = 1, b = 0, c = 1: b = 0, b ∧ a = 0, ¬c = 0, c = 1

a = 0, b = 1, c = 1: b = 1, b ∧ a = 0, ¬c = 0, c = 1

Wniosek

c (dowód przez rozpatrzenie przypadków)

Odpowiedź

5.Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki

Odpowiedź: N = 4

Mapy Karnaugha: komórki są ułożone w kodzie Graya (00, 01, 11, 10), więc sąsiednie komórki, także te przez brzegi, różnią się dokładnie jedną zmienną. Grupuj jedynki w prostokąty po 1, 2, 4, 8 lub 16 komórek, jak największe i jak najmniej, aż każda jedynka będzie pokryta. Każda grupa to jeden iloczyn: zmienne, które wewnątrz niej pozostają stałe. Grupa 2ᵏ komórek traci k zmiennych. Stany nieokreślone (X) można wykorzystać, by powiększyć grupy, ale nigdy nie trzeba ich pokrywać. Grupowanie zer daje minimalną postać POS.

Zgrupuj zera

Każda grupa to prostokąt z 2ᵏ komórek; komórki na brzegu sąsiadują z komórkami na przeciwległym brzegu.

(C + D)

(B + D)

(B + C)

(A + B)

Minimalna postać POS

F = (C + D)(B + D)(B + C)(A + B)

N = 4

Odpowiedź

N = 4

6.Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki

Odpowiedź: N = 3

Implikanty proste

Największe grupy, jakie można utworzyć z jedynek i X.

ABD′, A′B′C, AB′C′D

Istotne implikanty proste

ABD′, A′B′C, AB′C′D

N = 3

Odpowiedź

N = 3

7.Teoria liczb i arytmetyka modularna

Odpowiedź: φ(1183) = 936

Elementy odwrotne i kongruencje: a ma element odwrotny modulo n dokładnie wtedy, gdy NWD(a, n) = 1. Rozszerzony algorytm Euklidesa zapisuje 1 = s·n + t·a, a wtedy a⁻¹ ≡ t (mod n). Kongruencja a·x ≡ b (mod n) przy NWD(a, n) = 1 ma rozwiązanie x ≡ a⁻¹·b. Dwie kongruencje x ≡ r₁ (mod m₁) i x ≡ r₂ (mod m₂) o względnie pierwszych modułach mają jedno rozwiązanie modulo m₁·m₂ (chińskie twierdzenie o resztach). Funkcja φ(n) Eulera zlicza liczby od 1 do n względnie pierwsze z n: φ(n) = n·∏(1 − 1/p).

Czynniki pierwsze

1183 = 7·13²

Funkcja φ

φ(1183) = φ(169)·φ(7) = 156·6 = 936

Odpowiedź

φ(1183) = 936

8.Teoria liczb i arytmetyka modularna

Odpowiedź: 22⁶¹⁵⁰⁶ mod 29 = 23

Potęgi modularne i RSA: oblicz aᵏ mod n przez wielokrotne podnoszenie do kwadratu: zapisz k binarnie, podnoś do kwadratu, redukuj po każdym kroku i mnóż potęgi, których bit jest równy 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) dla liczby pierwszej p niedzielącej a, więc wykładnik można redukować modulo p − 1. RSA: wybierz liczby pierwsze p i q, n = p·q i φ(n) = (p − 1)(q − 1); wykładnik publiczny e jest względnie pierwszy z φ(n), a wykładnik prywatny to d = e⁻¹ mod φ(n). Szyfruj wzorem c = mᵉ mod n, a odszyfrowuj wzorem m = cᵈ mod n.

A · Zastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła

13.Teoria grafów

Odpowiedź: L = 11

Euler, Hamilton i drzewa: graf spójny ma cykl Eulera (każda krawędź raz, powrót do startu), gdy każdy wierzchołek ma stopień parzysty, oraz ścieżkę Eulera, która nie jest cyklem, gdy dokładnie dwa wierzchołki mają stopień nieparzysty; ścieżka biegnie wtedy od jednego wierzchołka nieparzystego do drugiego. Cykl Hamiltona odwiedza każdy wierzchołek raz; K_n ma ich (n − 1)!/2. Drzewo o n wierzchołkach ma n − 1 krawędzi, a graf spójny o m krawędziach zachowuje drzewo rozpinające po usunięciu m − n + 1 krawędzi.

Lemat o uściskach dłoni dla drzewa

L + 27 = 2(L + 9) − 2

L = 11

Odpowiedź

L = 11

Skrót: L = 2 + Σ (d − 2) po wierzchołkach o stopniu d ≥ 3.

14.Teoria grafów

Odpowiedź: N = 1

Stopnie: stopień wierzchołka to liczba krawędzi, które się w nim stykają. Każda krawędź ma dwa końce, więc stopnie sumują się do dwukrotności liczby krawędzi: Σ deg(v) = 2|E| (lemat o uściskach dłoni). Liczba wierzchołków o nieparzystym stopniu jest zatem parzysta. K_n ma n(n − 1)/2 krawędzi, graf k-regularny o n wierzchołkach ma nk/2, a drzewo o n wierzchołkach ma n − 1 krawędzi.

Macierz sąsiedztwa

A: 0 1 1 0 0 0

B: 1 0 1 1 0 0

C: 1 1 0 0 1 0

B · W rozwiązywaniu nazw (DNS)

19.Podsieci IPv4

Odpowiedź: p = 21

Podsieci IPv4: adres ma 32 bity. Prefiks /p mówi, ile początkowych bitów wskazuje sieć; pozostałe 32 − p bitów numeruje hosty. Podsieć ma 2³²⁻ᵖ adresów, ale pierwszego (adres sieci) i ostatniego (adres rozgłoszeniowy) nie można przydzielić hostom, więc mieści się 2³²⁻ᵖ − 2 hostów. Wyjątki: /31 (łącze punkt-punkt, RFC 3021) wykorzystuje oba swoje 2 adresy dla hostów, a /32 to jeden adres (pojedynczy host lub loopback).

Potrzebne bity hosta

2¹⁰ − 2 = 1022 < 1744

2¹¹ − 2 = 2046 ≥ 1744 → h = 11

Długość prefiksu

p = 32 − 11 = 21

Odpowiedź

p = /21

20.Podsieci IPv4

Odpowiedź: x = 227

Rozmiar bloku

2² = 4

Podsieć tego hosta

sieć: ⌊226/4⌋·4 = 224

rozgłoszeniowy: 224 + 4 − 1 = 227

użyteczne hosty: 225 … 226

Odpowiedź

x = 227

ExamProblems · examproblems.com/courses/computer-science-fundamentals