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.

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.

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

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