Nền tảng khoa học máy tính: gói ôn nước rút

Bảng công thức, các bước phương pháp chính cho từng chủ đề và 20 bài tập, kèm lời giải đầy đủ ở cuối.

Bài mới Quay lại môn học

Trong cửa sổ in, hãy chọn “Lưu dưới dạng PDF” để giữ một bản trên thiết bị của bạn.

1Công thức và phương pháp

Hệ đếm

Giá trị vị trí: nhị phân 2^k, bát phân 8^k, thập lục phân 16^k
Sang thập phân: Σ d_k·b^k
Từ thập phân: chia cho cơ số, đọc các số dư từ dưới lên
Thập lục phân ↔ nhị phân: một chữ số thập lục phân = 4 bit
Số bù hai: đảo các bit và cộng 1

Logic mệnh đề & chứng minh

Các hàng của bảng chân trị: 2ⁿ
Phép kéo theo: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Phủ định của phép kéo theo: ¬(p → q) ≡ p ∧ ¬q
Phép tương đương: p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Luật phân phối: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Phủ định của lượng từ: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Phương pháp

Hãy đếm số biến khác nhau: bảng chân trị có 2ⁿ hàng, bắt đầu bằng hàng toàn số 1.
Cho mỗi công thức con một cột riêng và điền các cột từ trong ra ngoài.
Áp dụng quy tắc của từng liên kết: → chỉ bằng 0 khi 1 → 0, ↔ bằng 1 khi hai vế giống nhau.
Với các tương đương, hãy so sánh các cột cuối theo từng hàng; với một suy luận, chỉ xét những hàng mà mọi tiền đề đều bằng 1.
Để phủ định một mệnh đề có lượng từ, hãy đưa ¬ vào trong, đổi ∀ và ∃, rồi phủ định công thức bên trong.

Logic số: cổng, bìa K và flip-flop

Các cổng cơ bản: A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Các quy tắc Boole: X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
De Morgan: (X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Thứ tự của bìa Karnaugh: 00, 01, 11, 10 (Gray code)
Nhóm 2ᵏ ô: mất k biến
Bộ ghép kênh 4-sang-1: F = A′B′I₀ + A′BI₁ + AB′I₂ + ABI₃
Flip-flop: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Bộ đếm: n bit: 2ⁿ trạng thái; mod-N: n nhỏ nhất thỏa 2ⁿ ≥ N; f_out = f_clk/N
Bộ đếm gợn sóng: f_max = 1/(n·t_pd)
Bộ đếm vòng và Johnson: n và 2n trạng thái

Phương pháp

Với một mạch, hãy làm từ các đầu vào đến đầu ra từng cổng một và ghi giá trị trên mọi dây, hoặc viết biểu thức của nó rồi điền bảng chân trị.
Để rút gọn, hãy đặt các số 1 (và các điều kiện tùy định là X) vào một bìa Karnaugh với hàng và cột theo mã Gray: 00, 01, 11, 10.
Hãy phủ các số 1 bằng càng ít nhóm và càng lớn càng tốt gồm 1, 2, 4, 8 hoặc 16 ô, cuộn qua mép; mỗi nhóm là một số hạng tích gồm các biến không đổi. Hãy nhóm các số 0 cho dạng POS.
Với flip-flop và bộ đếm, hãy đọc các đầu vào tại mỗi sườn xung nhịp tích cực, ghi trạng thái sau mỗi sườn, và nhớ rằng bộ đếm n bit quay vòng sau 2ⁿ trạng thái.

Lý thuyết số & số học đồng dư

Phép chia có dư: a = q·n + r, 0 ≤ r < n
Euclid: gcd(a, b) = gcd(b, a mod b)
Bội chung nhỏ nhất: lcm(a, b) = a·b/gcd(a, b)
Nghịch đảo: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Đồng dư tuyến tính: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Hàm phi Euler: φ(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

Phương pháp

Trước hết hãy rút gọn mọi số theo modulo n; số dư nằm trong khoảng từ 0 đến n − 1.
Với ước chung lớn nhất, hãy chia liên tiếp theo thuật toán Euclid; số dư khác 0 cuối cùng chính là ước chung lớn nhất.
Với số nghịch đảo, hãy chạy thuật toán Euclid mở rộng và lấy hệ số của a; cộng n nếu nó âm.
Giải a·x ≡ b bằng cách nhân với a⁻¹; kết hợp hai đồng dư bằng cách viết x = r₁ + m₁k.
Với lũy thừa, hãy viết số mũ ở dạng nhị phân và bình phương liên tiếp; trong RSA, d = e⁻¹ mod φ(n) với φ(n) = (p − 1)(q − 1).

Lý thuyết đồ thị

Bổ đề bắt tay: Σ deg(v) = 2|E|
Đồ thị đầy đủ: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Đồ thị đều: |E| = n·k/2
Cây và rừng: |E| = n − 1, |E| = n − c
Lá của cây: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: chu trình: mọi bậc đều chẵn; đường đi: đúng 2 bậc lẻ
Chu trình Hamilton trong K_n: (n − 1)!/2
Cập nhật Dijkstra: d(v) = min(d(v), d(u) + w(u, v))
Đường đi độ dài L: (Mᴸ)_ij

Phương pháp

Hãy ghi bậc của mỗi đỉnh; tổng các bậc bằng hai lần số cạnh.
Với bài Euler, hãy kiểm tra đồ thị liên thông và đếm số đỉnh có bậc lẻ.
Với cây, hãy dùng n − 1 cạnh và bổ đề bắt tay.
Với Dijkstra, hãy lập bảng khoảng cách tạm thời và mỗi vòng chốt đỉnh chưa chốt có giá trị nhỏ nhất.
Với cây khung nhỏ nhất, hãy sắp xếp các cạnh theo trọng số và bỏ qua mọi cạnh tạo thành chu trình (Kruskal), hoặc mở rộng một cây từ một đỉnh xuất phát (Prim).

Chia mạng con IPv4

Máy chủ trên mỗi mạng con: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
Kích thước khối: 256 − (mask octet)
Địa chỉ mạng: IP AND mặt nạ
Địa chỉ quảng bá: IP OR (NOT mask): tất cả bit host bằng 1
Mạng con từ n bit mượn: 2ⁿ

2Bài tập

1.Hệ đếmTrung bình

Dãy 8 bit 1110 1000 lưu một số nguyên có dấu dưới dạng số bù hai. Giá trị N của nó trong hệ thập phân là bao nhiêu?

1110 10008 bit

N =

2.Hệ đếmKhó

Số nguyên âm nhất N có thể lưu trong số bù hai 12 bit là bao nhiêu?

12 bit

N =

3.Logic mệnh đề & chứng minhTrung bình

((q → p) ∧ (p → r)) → (q → r) là hằng đúng, mâu thuẫn hay công thức ngẫu nhiên? Hãy nhấp vào đáp án của bạn.

((q → p) ∧ (p → r)) → (q → r)

1hằng đúng
2mâu thuẫn
3công thức ngẫu nhiên

4.Logic mệnh đề & chứng minhKhó

Có bao nhiêu hàng trong 16 hàng của bảng chân trị làm ¬((p ∨ q) ∨ (p ∨ r)) ↔ (¬q → ¬s) đúng? Gọi số này là N.

¬((p ∨ q) ∨ (p ∨ r)) ↔ (¬q → ¬s)

N =

5.Logic số: cổng, bìa K và flip-flopTrung bình

Hãy dùng bìa Karnaugh để tìm dạng tổng các tích (SOP) tối thiểu của F(A, B, C) = Σm(0, 2, 3). Nó có bao nhiêu số hạng tích N?

F(A, B, C) = Σm(0, 2, 3)

N =

6.Logic số: cổng, bìa K và flip-flopKhó

Một flip-flop D kích hoạt theo sườn lên bắt đầu với Q = 0 và nhận các đầu vào như hình. Hãy nhấp vào sườn xung nhịp đầu tiên mà Q chuyển từ 1 về lại 0.

Q₀ = 0D

1sườn xung nhịp 1
2sườn xung nhịp 2
3sườn xung nhịp 3
4sườn xung nhịp 4
5sườn xung nhịp 5
6sườn xung nhịp 6
7sườn xung nhịp 7

7.Lý thuyết số & số học đồng dưTrung bình

Hãy tìm số nguyên dương nhỏ nhất x thỏa x ≡ 4 (mod 5) và x ≡ 8 (mod 11).

x ≡ 4 (mod 5)x ≡ 8 (mod 11)

x =

8.Lý thuyết số & số học đồng dưKhó

Hãy dùng bình phương lặp để tìm 73³⁷ mod 86.

a = 73k = 37n = 86

73³⁷ mod 86 =

9.Thuật toán và độ phức tạpTrung bình

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

AO(1)
BO(n)
CO(n²)
DO(log n)

10.Thuật toán và độ phức tạpKhó

Phát biểu nào về P và NP là đúng?

ACác bài toán NP không thể được kiểm chứng nhanh
BNP có nghĩa là "không đa thức"
CĐã được chứng minh rằng P ≠ NP
DMọi bài toán trong P cũng thuộc NP

11.Cấu trúc dữ liệuTrung bình

Duyệt thứ tự giữa (in-order) của cây tìm kiếm nhị phân thăm các khóa theo:

ALuôn luôn thứ tự giảm dần
BThứ tự theo mức
CThứ tự tăng dần đã sắp xếp
DThứ tự chèn

12.Cấu trúc dữ liệuKhó

Tính chất nào giữ cho mọi cây B cân bằng hoàn hảo?

AMỗi nút lưu một khóa
BMỗi nút có đúng hai con
CMọi lá ở cùng một độ sâu
DCác khóa chỉ được lưu ở gốc

13.Lý thuyết đồ thịTrung bình

Một đồ thị liên thông có 7 đỉnh và 16 cạnh. Phải bỏ bao nhiêu cạnh k để còn lại một cây khung?

|V| = 7|E| = 16

k =

14.Lý thuyết đồ thịKhó

Có bao nhiêu đường đi độ dài 2 từ C đến A? Một đường đi có thể lặp lại đỉnh và cạnh. Gọi số đó là N.

M = ma trận kềL = 2

N =

15.Cơ sở dữ liệu và SQLTrung bình

Câu lệnh nào xóa mọi hàng của một bảng, giữ nguyên cấu trúc và không thể có mệnh đề WHERE?

ADELETE FROM kèm mệnh đề WHERE
BDROP TABLE
CTRUNCATE TABLE
DALTER TABLE

16.Cơ sở dữ liệu và SQLKhó

Cho các phụ thuộc hàm A → B, B → C và C → D trên R(A, B, C, D), bao đóng A⁺ là gì?

A{A, B, C, D}
B{A, B, C}
C{A}
D{A, B}

17.Mạng máy tínhTrung bình

RIP dùng chỉ số nào để chọn tuyến?

ASố chặng (hop count)
BBăng thông liên kết
CĐộ trễ đo được
DChính sách kinh doanh

18.Mạng máy tínhKhó

Vì sao tùy chọn tỷ lệ cửa sổ TCP (window scale) được đưa ra?

AUDP cần một cách để điều khiển tốc độ gửi trên các đường truyền tắc nghẽn
BTrường cửa sổ 32 bit quá lớn và gây lãng phí chỗ trong tiêu đề của mỗi đoạn TCP được gửi
CNếu không có nó, TCP không thể phát hiện các đoạn bị mất trên các liên kết đường dài
DTrường cửa sổ 16 bit giới hạn cửa sổ ở 65,535 byte, quá nhỏ cho các đường truyền nhanh và đường dài

19.Chia mạng con IPv4Trung bình

Một phòng ban cần 249 địa chỉ máy chủ trong một mạng con. Độ dài tiền tố dài nhất p (mạng con nhỏ nhất) đủ lớn là bao nhiêu?

249 hosts

p =

20.Chia mạng con IPv4Khó

Một máy chủ có địa chỉ 10.20.103.177/27. Octet thứ tư x của địa chỉ mạng của nó là bao nhiêu?

10.20.103.177/27

x =

3Dung dịch

1.Hệ đếm

Đáp số: N = −24

Hệ đếm theo vị trí: mỗi chữ số có giá trị bằng giá trị của nó nhân với một lũy thừa của cơ số. Trong hệ nhị phân, các vị trí có giá trị 1, 2, 4, 8, 16, …; trong hệ thập lục phân 1, 16, 256, …, với A–F biểu diễn 10–15. Trong số bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128 thay vì +128, đó là cách lưu số âm.

Cộng các giá trị vị trí

Các bit còn lại giữ giá trị dương thông thường.

−128 + 64 + 32 + 8 = −24

Đáp số

N = −24

2.Hệ đếm

Đáp số: N = −2048

Giá trị âm nhất

−2¹¹ = −2048

Đáp số

N = −2048

3.Logic mệnh đề & chứng minh

Đáp số: hằng đúng

Tương đương logic: hai công thức tương đương (≡) khi chúng có cùng giá trị ở mọi hàng của bảng chân trị. Hằng đúng bằng 1 ở mọi hàng, mâu thuẫn bằng 0 ở mọi hàng, còn công thức ngẫu nhiên thì không thuộc loại nào. Các luật hữu ích: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b và ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (phản đảo); ¬(a → b) ≡ a ∧ ¬b; và các luật phân phối, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Bảng chân trị từng hàng

p = 1, q = 1, r = 1: q → p = 1, p → r = 1, (q → p) ∧ (p → r) = 1, q → r = 1, ((q → p) ∧ (p → r)) → (q → r) = 1

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

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

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

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

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

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

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

Phân loại

((q → p) ∧ (p → r)) → (q → r): 1, 1, 1, 1, 1, 1, 1, 1

Bằng 1 ở mọi hàng: hằng đúng.

Đáp số

hằng đúng

4.Logic mệnh đề & chứng minh

Đáp số: N = 4

Bảng chân trị: một công thức có n biến khác nhau có 2ⁿ hàng, mỗi hàng ứng với một tổ hợp giá trị chân trị (1 = đúng, 0 = sai). Hãy làm từ trong ra ngoài và cho mỗi công thức con một cột riêng. ¬a đảo giá trị; a ∧ b bằng 1 chỉ khi cả hai đều bằng 1; a ∨ b bằng 0 chỉ khi cả hai đều bằng 0; a → b bằng 0 chỉ khi a = 1 và b = 0; a ↔ b bằng 1 khi hai vế bằng nhau.

Các cột

p ∨ q; p ∨ r; (p ∨ q) ∨ (p ∨ r); ¬((p ∨ q) ∨ (p ∨ r)); ¬q; ¬s; ¬q → ¬s; ¬((p ∨ q) ∨ (p ∨ r)) ↔ (¬q → ¬s)

Chia theo p

p = 1: 2

p = 0: 2

N = 2 + 2 = 4

Đáp số

N = 4

5.Logic số: cổng, bìa K và flip-flop

Đáp số: N = 2

Bìa Karnaugh: các ô được sắp xếp theo mã Gray (00, 01, 11, 10), nên các ô kề nhau, kể cả những ô qua mép, khác nhau đúng một biến. Hãy nhóm các số 1 thành hình chữ nhật gồm 1, 2, 4, 8 hoặc 16 ô, lớn nhất có thể và ít nhóm nhất có thể, cho đến khi mọi số 1 đều được phủ. Mỗi nhóm là một số hạng tích: các biến không đổi bên trong nó. Một nhóm 2ᵏ ô mất k biến. Các điều kiện tùy định (X) có thể dùng để làm nhóm lớn hơn nhưng không bắt buộc phải được phủ. Nhóm các số 0 thay vào đó sẽ cho dạng POS tối thiểu.

Nhóm các số 1

Mỗi nhóm là một hình chữ nhật gồm 2ᵏ ô; các ô ở mép kề với các ô ở mép đối diện.

A′C′

A′B

Dạng SOP tối thiểu

F = A′C′ + A′B

N = 2

Đáp số

N = 2

6.Logic số: cổng, bìa K và flip-flop

Đáp số: sườn xung nhịp 3

Flip-flop và bộ đếm: một flip-flop chỉ thay đổi ở sườn tích cực của xung nhịp. D sao chép đầu vào của nó (Q⁺ = D); T đảo khi T = 1; JK giữ nguyên với 00, đặt về 0 với 01, đặt lên 1 với 10 và đảo với 11. Một bộ đếm nhị phân n bit có 2ⁿ trạng thái và đếm theo modulo 2ⁿ; một bộ đếm mod-N đếm 0, 1, …, N − 1 rồi về lại 0, và cần số flip-flop n nhỏ nhất thỏa 2ⁿ ≥ N. Mỗi tầng của bộ đếm gợn sóng chia đôi tần số, nên đầu ra cuối của bộ đếm mod-N chạy ở f_clk/N. Một bộ đếm Johnson gồm n flip-flop có 2n trạng thái, bộ đếm vòng có n.

Q sau mỗi sườn

Một flip-flop D sao chép D ở mỗi sườn lên: Q⁺ = D.

1: D = 1 → Q = 1

2: D = 1 → Q = 1

3: D = 0 → Q = 0

4: D = 1 → Q = 1

5: D = 1 → Q = 1

6: D = 1 → Q = 1

7: D = 1 → Q = 1

Lần đầu tiên đổi từ 1 xuống 0

sườn xung nhịp 3

Đáp số

sườn xung nhịp 3

7.Lý thuyết số & số học đồng dư

Đáp số: x = 19

Nghịch đảo và đồng dư: a có nghịch đảo theo modulo n đúng khi gcd(a, n) = 1. Thuật toán Euclid mở rộng viết 1 = s·n + t·a, và khi đó a⁻¹ ≡ t (mod n). Một đồng dư a·x ≡ b (mod n) với gcd(a, n) = 1 có nghiệm x ≡ a⁻¹·b. Hai đồng dư x ≡ r₁ (mod m₁) và x ≡ r₂ (mod m₂) với các modulo nguyên tố cùng nhau có một nghiệm theo modulo m₁·m₂ (định lý số dư Trung Hoa). φ(n) của Euler đếm các số từ 1 đến n nguyên tố cùng nhau với n: φ(n) = n·∏(1 − 1/p).

Đồng dư thứ nhất

x = 4 + 5k

Đồng dư thứ hai

4 + 5k ≡ 8 (mod 11) → 5k ≡ 4 (mod 11)

k ≡ 9·4 ≡ 3 (mod 11)

Kết quả

x = 4 + 5·3 = 19

x = 19

kiểm tra: 19 mod 5 = 4, 19 mod 11 = 8

Đáp số

x = 19

8.Lý thuyết số & số học đồng dư

Đáp số: 73³⁷ mod 86 = 61

Lũy thừa modulo và RSA: tính aᵏ mod n bằng bình phương lặp: viết k ở dạng nhị phân, bình phương, rút gọn sau mỗi bước và nhân các lũy thừa có bit bằng 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) với số nguyên tố p không chia hết a, nên số mũ có thể được rút gọn theo modulo p − 1. RSA: chọn các số nguyên tố p và q, n = p·q và φ(n) = (p − 1)(q − 1); số mũ công khai e nguyên tố cùng nhau với φ(n), và số mũ bí mật là d = e⁻¹ mod φ(n). Mã hóa bằng c = mᵉ mod n và giải mã bằng m = cᵈ mod n.

Số mũ nhị phân

37 = 100101₂ = 32 + 4 + 1

Bình phương lặp

73¹ ≡ 73 (mod 86)

73² ≡ 83 (mod 86)

73⁴ ≡ 9 (mod 86)

C · Mọi lá ở cùng một độ sâu

13.Lý thuyết đồ thị

Đáp số: k = 10

Euler, Hamilton và cây: một đồ thị liên thông có chu trình Euler (đi qua mỗi cạnh một lần, trở về điểm đầu) khi mọi đỉnh có bậc chẵn, và có đường đi Euler không phải chu trình khi có đúng hai đỉnh bậc lẻ; khi đó đường đi chạy từ một đỉnh lẻ đến đỉnh lẻ kia. Một chu trình Hamilton thăm mỗi đỉnh một lần; K_n có (n − 1)!/2 chu trình như vậy. Một cây trên n đỉnh có n − 1 cạnh, và một đồ thị liên thông có m cạnh còn lại một cây khung sau khi bỏ m − n + 1 cạnh.

Các cạnh của cây khung

7 − 1 = 6

Các cạnh cần bỏ

k = 16 − 6 = 10

Đáp số

k = 10

14.Lý thuyết đồ thị

Đáp số: N = 1

Bậc: bậc của một đỉnh là số cạnh gặp đỉnh đó. Mỗi cạnh có hai đầu, nên tổng các bậc bằng hai lần số cạnh: Σ deg(v) = 2|E| (bổ đề bắt tay). Do đó số đỉnh có bậc lẻ là số chẵn. K_n có n(n − 1)/2 cạnh, một đồ thị k-đều trên n đỉnh có nk/2 cạnh, và một cây trên n đỉnh có n − 1 cạnh.

Ma trận kề

A: 0 1 1 0 0

B: 1 0 1 0 1

D · Trường cửa sổ 16 bit giới hạn cửa sổ ở 65,535 byte, quá nhỏ cho các đường truyền nhanh và đường dài

19.Chia mạng con IPv4

Đáp số: p = 24

Chia mạng con IPv4: một địa chỉ có 32 bit. Tiền tố /p cho biết bao nhiêu bit đầu tiên xác định mạng; 32 − p bit còn lại đánh số các máy chủ. Một mạng con có 2³²⁻ᵖ địa chỉ, nhưng địa chỉ đầu (địa chỉ mạng) và địa chỉ cuối (địa chỉ quảng bá) không thể gán cho máy chủ, nên chứa được 2³²⁻ᵖ − 2 máy chủ. Ngoại lệ: /31 (liên kết điểm-điểm, RFC 3021) dùng cả 2 địa chỉ của nó cho host, còn /32 chỉ là một địa chỉ duy nhất (một host hoặc loopback).

Số bit máy chủ cần thiết

2⁷ − 2 = 126 < 249

2⁸ − 2 = 254 ≥ 249 → h = 8

Độ dài tiền tố

p = 32 − 8 = 24

Đáp số

p = /24

20.Chia mạng con IPv4

Đáp số: x = 160

Kích thước khối

2⁵ = 32

Mạng con của máy chủ này

mạng: ⌊177/32⌋·32 = 160

quảng bá: 160 + 32 − 1 = 191

máy chủ khả dụng: 161 … 190

Đáp số

x = 160

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