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.

Waarheidstabellen: een formule met n verschillende variabelen heeft 2ⁿ rijen, één voor elke combinatie van waarheidswaarden (1 = waar, 0 = onwaar). Werk van binnen naar buiten en geef elke deelformule een eigen kolom. ¬a draait de waarde om; a ∧ b is alleen 1 als beide 1 zijn; a ∨ b is alleen 0 als beide 0 zijn; a → b is alleen 0 als a = 1 en b = 0; a ↔ b is 1 als beide kanten gelijk zijn.

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.

Multiplexer: een 2ⁿ-naar-1-multiplexer geeft één van zijn data-ingangen door aan de uitgang; de selectielijnen, gelezen als binair getal, kiezen welke. Voor een 4-naar-1-MUX met selecties S₁S₀ = AB is F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Door de data-ingangen aan 0, 1, C of C′ te koppelen, maakt de MUX elke functie van A, B en C, wat een veelgebruikte manier is om logica met één chip te bouwen.

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

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

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

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