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

Lượng từ và suy luận: ¬∀x P(x) ≡ ∃x ¬P(x) và ¬∃x P(x) ≡ ∀x ¬P(x). Đưa phép phủ định vào trong, đổi mọi lượng từ mà nó đi qua, và phủ định công thức bên trong bằng các luật logic mệnh đề, chẳng hạn ¬(a → b) ≡ a ∧ ¬b. Một suy luận hợp lệ khi kết luận bằng 1 ở mọi hàng mà tất cả tiền đề đều bằng 1. Chỉ một hàng có tiền đề đúng mà kết luận sai là một phản ví dụ và cho thấy suy luận không hợp lệ.

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.

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.

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.

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.

IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).

IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).