Formulas: Computer science

Number systems and encoding

• N = Σ aibi

• bytes = bits / 8, bits = 8 · bytes

• i = ⌈log2N⌉ — minimum code length

• I = K · i


Logic and information theory

• A ∧ B, A ∨ B, A ⊕ B, ¬A

• A → B ≡ ¬A ∨ B

• I = log2N — Hartley formula

• I(x) = −log2p(x)

• H = −Σ pi log2 pi

• r = 1 − H / Hmax


Architecture and algorithms

• v = I / t

• TCPU = N · CPI / f

• T(n) = kn, kn², kn log2n — common models

• S = T1 / Tp, E = S / p

• SAmdahl = 1 / ((1 − α) + α / p)


Graphs and networks

• For a tree: |E| = |V| − 1

• For a complete graph: |E| = n(n − 1) / 2

• Σ deg(v) = 2|E|

• In IPv4: total = 232−m, hosts = 232−m − 2

• mask = /m, wildcard = 255.255.255.255 − mask