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

Đặt các bit: mỗi bit có giá trị bằng một lũy thừa của hai (128, 64, …, 1). Một chữ số hex đúng bằng bốn bit, và trong bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128. Các phép toán theo bit làm việc trên từng vị trí bit riêng biệt.

Đặt các bit: mỗi bit có giá trị bằng một lũy thừa của hai (128, 64, …, 1). Một chữ số hex đúng bằng bốn bit, và trong bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128. Các phép toán theo bit làm việc trên từng vị trí bit riêng biệt.

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ị: 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ộ ghép kênh: một bộ ghép kênh 2ⁿ-sang-1 chuyển một trong các đầu vào dữ liệu của nó ra đầu ra; các đường chọn, đọc như một số nhị phân, quyết định đầu vào nào. Với MUX 4-sang-1 có các đường chọn S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Nối các đầu vào dữ liệu với 0, 1, C hoặc C′ làm MUX tạo ra bất kỳ hàm nào của A, B và C, đó là cách phổ biến để xây dựng logic bằng một chip.

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.

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

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.

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.

Đườ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.

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

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