Basis informatica: samenvattingspakket

Bits instellen: elke bit is een macht van twee waard (128, 64, …, 1). Eén hexadecimaal cijfer is precies vier bits, en in 8-bits tweecomplement is de meest linkse bit −128 waard. Bitsgewijze bewerkingen werken op elke bitpositie apart.

Positionele talstelsels: elk cijfer is zijn waarde maal een macht van het grondtal waard. Binair zijn de posities 1, 2, 4, 8, 16, … waard, hexadecimaal 1, 16, 256, …, met A–F voor 10–15. In 8-bits two's complement is het meest linkse bit −128 waard in plaats van +128; zo worden negatieve getallen opgeslagen.

Logische equivalentie: twee formules zijn equivalent (≡) als ze in elke rij van de waarheidstabel dezelfde waarde hebben. Een tautologie is in elke rij 1, een contradictie in elke rij 0, en een contingentie is geen van beide. Nuttige wetten: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b en ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositie); ¬(a → b) ≡ a ∧ ¬b; en de distributieve wetten, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Kwantoren en redeneringen: ¬∀x P(x) ≡ ∃x ¬P(x) en ¬∃x P(x) ≡ ∀x ¬P(x). Schuif een ontkenning naar binnen, verwissel elke kwantor die ze passeert en ontken de binnenste formule met de propositiewetten, zoals ¬(a → b) ≡ a ∧ ¬b. Een redenering is geldig als de conclusie 1 is in elke rij waarin alle premissen 1 zijn. Eén rij met ware premissen en een onware conclusie is een tegenvoorbeeld en toont aan dat de redenering ongeldig is.

Booleaanse algebra: de regels die uitdrukkingen vereenvoudigen zijn X + X′ = 1 en X·X′ = 0, X + X = X, absorptie X + X·Y = X, de samenvoegregel X·Y + X·Y′ = X, X + X′Y = X + Y en de consensusstelling XY + X′Z + YZ = XY + X′Z. De wetten van De Morgan veranderen (X·Y)′ in X′ + Y′ en (X + Y)′ in X′·Y′. Een Karnaugh-kaart past deze regels grafisch toe: elke groep van twee naburige cellen is één toepassing van XY + XY′ = X.

Karnaugh-kaarten: de cellen staan in Gray-code (00, 01, 11, 10), dus naburige cellen, ook die over de randen heen, verschillen in precies één variabele. Groepeer de enen in rechthoeken van 1, 2, 4, 8 of 16 cellen, zo groot en zo weinig mogelijk, totdat elke 1 gedekt is. Elke groep is één productterm: de variabelen die erin constant blijven. Een groep van 2ᵏ cellen verliest k variabelen. Don’t-cares (X) mogen worden gebruikt om groepen groter te maken maar hoeven nooit gedekt te worden. Groepeer je in plaats daarvan de nullen, dan krijg je de minimale POS-vorm.

Inversen en congruenties: a heeft een inverse modulo n precies als ggd(a, n) = 1. Het uitgebreide algoritme van Euclides schrijft 1 = s·n + t·a, en dan is a⁻¹ ≡ t (mod n). Een congruentie a·x ≡ b (mod n) met ggd(a, n) = 1 heeft de oplossing x ≡ a⁻¹·b. Twee congruenties x ≡ r₁ (mod m₁) en x ≡ r₂ (mod m₂) met onderling ondeelbare moduli hebben één oplossing modulo m₁·m₂ (Chinese reststelling). Eulers φ(n) telt de getallen van 1 tot n die onderling ondeelbaar zijn met n: φ(n) = n·∏(1 − 1/p).

Modulaire machten en RSA: bereken aᵏ mod n door herhaald kwadrateren: schrijf k binair, kwadrateer, reduceer na elke stap en vermenigvuldig de machten waarvan de bit 1 is. Fermat: aᵖ⁻¹ ≡ 1 (mod p) voor een priemgetal p dat a niet deelt, dus de exponent kan modulo p − 1 gereduceerd worden. RSA: kies priemgetallen p en q, n = p·q en φ(n) = (p − 1)(q − 1); de publieke exponent e is onderling ondeelbaar met φ(n), en de privé-exponent is d = e⁻¹ mod φ(n). Versleutel met c = mᵉ mod n en ontsleutel met m = cᵈ mod n.

Euler, Hamilton en bomen: een samenhangende graaf heeft een Eulercircuit (elke kant één keer, terug naar het begin) als elk hoekpunt even graad heeft, en een Eulerpad dat geen circuit is als precies twee hoekpunten oneven graad hebben; het pad loopt dan van het ene oneven hoekpunt naar het andere. Een Hamiltoncircuit bezoekt elk hoekpunt één keer; K_n heeft er (n − 1)!/2. Een boom op n hoekpunten heeft n − 1 kanten, en een samenhangende graaf met m kanten houdt een opspannende boom over na het verwijderen van m − n + 1 kanten.

Graden: de graad van een hoekpunt is het aantal kanten dat erin samenkomt. Elke kant heeft twee uiteinden, dus de graden tellen op tot twee keer het aantal kanten: Σ deg(v) = 2|E| (het handenschudlemma). Het aantal hoekpunten met oneven graad is daarom even. K_n heeft n(n − 1)/2 kanten, een k-reguliere graaf op n hoekpunten heeft nk/2, en een boom op n hoekpunten heeft n − 1 kanten.

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

VLSM: elk LAN krijgt het kleinste subnet met 2ʰ − 2 ≥ het aantal hosts, dus prefix 32 − h. Door de grootste subnetten eerst toe te wijzen begint elk blok op een veelvoud van zijn eigen grootte, zodat de netwerkadressen volgen door de blokgroottes op te tellen.