Basis informatica: samenvattingspakket

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.

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.

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.

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.

Flip-flops en tellers: een flip-flop verandert alleen op de actieve klokflank. D kopieert zijn ingang (Q⁺ = D); T wisselt als T = 1; JK houdt vast bij 00, reset bij 01, zet bij 10 en wisselt bij 11. Een n-bits binaire teller heeft 2ⁿ toestanden en telt modulo 2ⁿ; een mod-N-teller telt 0, 1, …, N − 1 en dan weer 0, en heeft de kleinste n met 2ⁿ ≥ N flip-flops nodig. Elke trap van een ripple-teller halveert de frequentie, dus de laatste uitgang van een mod-N-teller loopt op f_klok/N. Een Johnson-teller van n flip-flops heeft 2n toestanden, een ringteller n.

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: een adres heeft 32 bits. Het prefix /p geeft aan hoeveel voorste bits het netwerk aanduiden; de overige 32 − p bits nummeren de hosts. Een subnet heeft 2³²⁻ᵖ adressen, maar het eerste (netwerkadres) en het laatste (broadcastadres) kunnen niet aan hosts worden gegeven, dus er passen 2³²⁻ᵖ − 2 hosts in. Uitzonderingen: een /31 (point-to-pointverbinding, RFC 3021) gebruikt allebei zijn 2 adressen voor hosts, en een /32 is één enkel adres (één host of een 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.