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 1011 0110 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?

1011 01108 bit

N =

2.Hệ đếmKhó

Số nguyên không dấu lớn nhất N vừa trong 20 bit là bao nhiêu?

20 bit

N =

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

Trong bao nhiêu hàng trong 8 hàng của bảng chân trị thì ¬((q ∨ ¬r) ∧ ((¬r ∧ q) ↔ ¬p)) đúng? Gọi số này là N.

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

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 ¬(¬((b → c) ∧ (b → d)) ∧ ((c → d) ∧ a)) đúng? Gọi số này là N.

¬(¬((b → c) ∧ (b → d)) ∧ ((c → d) ∧ a))

N =

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

Hãy rút gọn F = AB + BC + A′C + ABC′ về dạng tổng các tích tối thiểu. Biểu thức rút gọn chứa bao nhiêu literal L?

F = AB + BC + A′C + ABC′

L =

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

Với F(A, B, C, D) = Σm(1, 6, 9, 13) + d(2, 4, 15), trong đó d đánh dấu các điều kiện tùy định, hãy tìm số N các implicant nguyên tố cốt yếu.

F(A, B, C, D) = Σm(1, 6, 9, 13) + d(2, 4, 15)

N =

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

Hãy tìm nghịch đảo của 21 theo modulo 32: số x với 0 < x < 32 và 21·x ≡ 1 (mod 32).

a = 21n = 32

21⁻¹ mod 32 =

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

Một khóa RSA dùng p = 41, q = 47 và e = 7. Hãy giải mã bản mã c = 728: tìm thông điệp m.

p = 41q = 47e = 7c = 728

m =

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

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

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

An! tăng nhanh hơn 2ⁿ
BChúng tăng với cùng tốc độ
C2ⁿ tăng nhanh hơn n!
Dn! là O(n²)

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

Cấu trúc dữ liệu nào được dùng để kiểm tra các dấu ngoặc trong "{[()]}" có cân bằng hay không?

ACây tìm kiếm nhị phân
BHàng đợi
CNgăn xếp
DBảng băm

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

Vì sao cơ sở dữ liệu thường dùng cây B+ thay vì cây B thông thường cho chỉ mục?

ACây B+ không cần cân bằng
BCây B+ chỉ lưu dữ liệu ở gốc
CCây B+ dùng các nút trong nhị phân, giúp giảm số lần đọc đĩa
DMọi bản ghi nằm trong các lá được liên kết, giúp quét theo khoảng hiệu quả

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

Đồ thị đầy đủ K₆ có bao nhiêu chu trình Hamilton khác nhau H? Các chu trình chỉ khác nhau ở đỉnh xuất phát hoặc chiều đi được tính là một.

K₆

H =

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

Hãy tìm tổng trọng số W của một cây khung nhỏ nhất của đồ thị có trọng số.

|V| = 7|E| = 10

W =

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

Một cột chứa các giá trị 10, 20 và NULL. AVG(col) trả về gì?

ANULL
B15
C30
D10

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

FULL OUTER JOIN trả về gì?

AChỉ các hàng không khớp
BTích Descartes, ghép mỗi hàng của bảng này với mọi hàng của bảng kia
CChỉ các hàng khớp
DTất cả các hàng từ cả hai bảng, ghép khớp khi có thể và điền NULL nếu không

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

NAT (chuyển đổi địa chỉ mạng) chủ yếu được dùng để:

ATăng tốc độ của cáp mạng
BCho phép nhiều thiết bị có địa chỉ riêng cùng dùng chung một địa chỉ IP công cộng
CDịch tên miền thành địa chỉ IP cho các thiết bị trong mạng cục bộ
DMã hóa lưu lượng giữa hai địa điểm

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

Một kết nối TCP có cửa sổ 64 KB và thời gian khứ hồi 100 ms, không có tỷ lệ cửa sổ. Thông lượng tối đa xấp xỉ của nó là bao nhiêu?

AKhoảng 50 Mbit/s
BKhoảng 640 Mbit/s
CKhoảng 5 Mbit/s
DKhoảng 0,5 Mbit/s

19.Chia mạng con IPv4Trung bình

Một phòng ban cần 1073 đị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?

1073 hosts

p =

20.Chia mạng con IPv4Khó

Một máy chủ có địa chỉ 10.20.168.212/30. Số cuối cùng (octet thứ tư) x của địa chỉ quảng bá trong mạng con của nó là bao nhiêu?

10.20.168.212/30

x =

3Dung dịch

1.Hệ đếm

Đáp số: N = −74

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 + 32 + 16 + 4 + 2 = −74

Đáp số

N = −74

2.Hệ đếm

Đáp số: N = 1,049 × 10⁶

Giá trị lớn nhất

2²⁰ − 1 = 1048575

Đáp số

N = 1048575

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

Đáp số: N = 5

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.

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

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

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

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

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

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

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

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

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

Đếm các hàng có giá trị 1

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

N = 5

Đáp số

N = 5

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

Đáp số: N = 14

Các cột

b → c; b → d; (b → c) ∧ (b → d); ¬((b → c) ∧ (b → d)); c → d; (c → d) ∧ a; ¬((b → c) ∧ (b → d)) ∧ ((c → d) ∧ a); ¬(¬((b → c) ∧ (b → d)) ∧ ((c → d) ∧ a))

Chia theo a

a = 1: 6

a = 0: 8

N = 6 + 8 = 14

Đáp số

N = 14

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

Đáp số: L = 4

Đại số Boole: các quy tắc rút gọn biểu thức là X + X′ = 1 và X·X′ = 0, X + X = X, hấp thụ X + X·Y = X, quy tắc kết hợp X·Y + X·Y′ = X, X + X′Y = X + Y và định lý đồng thuận XY + X′Z + YZ = XY + X′Z. Các luật De Morgan biến (X·Y)′ thành X′ + Y′ và (X + Y)′ thành X′·Y′. Một bìa Karnaugh áp dụng các quy tắc này bằng hình ảnh: mỗi nhóm hai ô kề nhau là một lần dùng XY + XY′ = X.

Các minterm của biểu thức

AB → m(6, 7)

BC → m(3, 7)

A′C → m(1, 3)

ABC′ → m(6)

Nhóm và đọc kết quả

F = A′C + AB

Đếm các literal

L = 4

Đáp số

L = 4

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

Đáp số: N = 1

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.

Các implicant nguyên tố

Các nhóm lớn nhất có thể tạo từ các số 1 và các X.

B′C′D, A′CD′, AC′D, A′BD′, ABD

Các implicant nguyên tố cốt yếu

B′C′D

N = 1

Đáp số

N = 1

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

Đáp số: 21⁻¹ mod 32 = 29

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).

Thuật toán Euclid mở rộng

Mỗi số dư r được viết là r ≡ t·21 (mod 32).

r = 32, t = 0

r = 21, q = 1, t = 1

r = 11, q = 1, t = −1

r = 10, q = 1, t = 2

r = 1, q = 10, t = −3

Nghịch đảo

1 ≡ −3·21 (mod 32)

x = 29

kiểm tra: 21·29 = 609 = 19·32 + 1

Đáp số

21⁻¹ mod 32 = 29

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

Đáp số: m = 1255

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ũ bí mật

n = 1927, φ(n) = 1840

d = 7⁻¹ mod 1840 = 263

Giải mã bằng bình phương lặp

263 = 256 + 4 + 2 + 1

728¹ ≡ 728 (mod 1927)

728² ≡ 59 (mod 1927)

728⁴ ≡ 1554 (mod 1927)

728⁸ ≡ 385 (mod 1927)

728¹⁶ ≡ 1773 (mod 1927)

728³² ≡ 592 (mod 1927)

728⁶⁴ ≡ 1677 (mod 1927)

728¹²⁸ ≡ 836 (mod 1927)

728²⁵⁶ ≡ 1322 (mod 1927)

728²⁶³ ≡ 728·59·1554·1322 ≡ 1255 (mod 1927)

Tin nhắn

m = 1255

Đếm

H = (6 − 1)!/2 = 120/2 = 60

Đáp số

H = 60

14.Lý thuyết đồ thị

Đáp số: W = 35

Đường đi ngắn nhất và cây khung: thuật toán Dijkstra chốt một đỉnh mỗi vòng: đỉnh chưa chốt có khoảng cách tạm thời nhỏ nhất. Khoảng cách của nó khi đó là cuối cùng, và mỗi đỉnh kề v được d(v) = min(d(v), d(u) + w(u, v)). Thuật toán Kruskal xây dựng cây khung nhỏ nhất bằng cách lấy các cạnh từ nhẹ đến nặng và bỏ qua mọi cạnh tạo thành chu trình; thuật toán Prim mở rộng một cây từ một đỉnh xuất phát bằng cách luôn thêm cạnh nhẹ nhất đi ra khỏi cây. Một cây khung của n đỉnh có n − 1 cạnh.

Thuật toán Kruskal

EF (1): lấy

GB (2): lấy

DE (4): lấy

GE (5): lấy

C · Khoảng 5 Mbit/s

19.Chia mạng con IPv4

Đáp số: p = 21

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 = 1022 < 1073

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

Độ dài tiền tố

p = 32 − 11 = 21

Đáp số

p = /21

20.Chia mạng con IPv4

Đáp số: x = 215

Kích thước khối

2² = 4

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

mạng: ⌊212/4⌋·4 = 212

quảng bá: 212 + 4 − 1 = 215

máy chủ khả dụng: 213 … 214

Đáp số

x = 215

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