Fondamenti di informatica: pacchetto last-minute

Sistemi di numerazione posizionali: ogni cifra vale il suo valore per una potenza della base. In binario le posizioni valgono 1, 2, 4, 8, 16, …; in esadecimale 1, 16, 256, …, con A–F per 10–15. Nel complemento a due a 8 bit il bit più a sinistra vale −128 invece di +128: così si memorizzano i numeri negativi.

Sistemi di numerazione posizionali: ogni cifra vale il suo valore per una potenza della base. In binario le posizioni valgono 1, 2, 4, 8, 16, …; in esadecimale 1, 16, 256, …, con A–F per 10–15. Nel complemento a due a 8 bit il bit più a sinistra vale −128 invece di +128: così si memorizzano i numeri negativi.

Equivalenza logica: due formule sono equivalenti (≡) quando hanno lo stesso valore in ogni riga della tabella di verità. Una tautologia vale 1 in ogni riga, una contraddizione vale 0 in ogni riga, e una contingenza non è né l’una né l’altra. Leggi utili: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b e ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contronominale); ¬(a → b) ≡ a ∧ ¬b; e le leggi distributive, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Quantificatori e argomenti: ¬∀x P(x) ≡ ∃x ¬P(x) e ¬∃x P(x) ≡ ∀x ¬P(x). Sposta una negazione verso l’interno, scambia ogni quantificatore che attraversa e nega la formula interna con le leggi proposizionali, come ¬(a → b) ≡ a ∧ ¬b. Un argomento è valido quando la conclusione vale 1 in ogni riga in cui tutte le premesse valgono 1. Una sola riga con premesse vere e conclusione falsa è un controesempio e mostra che l’argomento non è valido.

Mappe di Karnaugh: le celle sono ordinate in codice Gray (00, 01, 11, 10), quindi le celle vicine, comprese quelle attraverso i bordi, differiscono per esattamente una variabile. Raggruppa gli 1 in rettangoli di 1, 2, 4, 8 o 16 celle, i più grandi e il meno numerosi possibile, finché ogni 1 non è coperto. Ogni gruppo è un termine prodotto: le variabili che restano costanti al suo interno. Un gruppo di 2ᵏ celle perde k variabili. Le condizioni di indifferenza (X) possono servire a ingrandire i gruppi ma non devono mai essere coperte. Raggruppando invece gli 0 si ottiene la forma POS minima.

Mappe di Karnaugh: le celle sono ordinate in codice Gray (00, 01, 11, 10), quindi le celle vicine, comprese quelle attraverso i bordi, differiscono per esattamente una variabile. Raggruppa gli 1 in rettangoli di 1, 2, 4, 8 o 16 celle, i più grandi e il meno numerosi possibile, finché ogni 1 non è coperto. Ogni gruppo è un termine prodotto: le variabili che restano costanti al suo interno. Un gruppo di 2ᵏ celle perde k variabili. Le condizioni di indifferenza (X) possono servire a ingrandire i gruppi ma non devono mai essere coperte. Raggruppando invece gli 0 si ottiene la forma POS minima.

Inversi e congruenze: a ha un inverso modulo n esattamente quando MCD(a, n) = 1. L’algoritmo di Euclide esteso scrive 1 = s·n + t·a, e allora a⁻¹ ≡ t (mod n). Una congruenza a·x ≡ b (mod n) con MCD(a, n) = 1 ha la soluzione x ≡ a⁻¹·b. Due congruenze x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂) con moduli coprimi hanno una soluzione modulo m₁·m₂ (teorema cinese del resto). La φ di Eulero φ(n) conta i numeri da 1 a n coprimi con n: φ(n) = n·∏(1 − 1/p).

Potenze modulari e RSA: calcola aᵏ mod n con il quadrato ripetuto: scrivi k in binario, eleva al quadrato, riduci a ogni passaggio e moltiplica le potenze il cui bit è 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) per un primo p che non divide a, quindi l’esponente si può ridurre modulo p − 1. RSA: scegli i primi p e q, n = p·q e φ(n) = (p − 1)(q − 1); l’esponente pubblico e è coprimo con φ(n), e l’esponente privato è d = e⁻¹ mod φ(n). Cifra con c = mᵉ mod n e decifra con m = cᵈ mod n.

Eulero, Hamilton e alberi: un grafo connesso ha un circuito euleriano (ogni lato una volta, di nuovo al punto di partenza) quando ogni vertice ha grado pari, e un cammino euleriano che non è un circuito quando esattamente due vertici hanno grado dispari; il cammino va allora da un vertice dispari all’altro. Un ciclo hamiltoniano visita ogni vertice una volta; K_n ne ha (n − 1)!/2. Un albero con n vertici ha n − 1 lati, e un grafo connesso con m lati mantiene un albero di copertura dopo aver tolto m − n + 1 lati.

Gradi: il grado di un vertice è il numero di lati che vi arrivano. Ogni lato ha due estremi, quindi i gradi sommano al doppio del numero di lati: Σ deg(v) = 2|E| (il lemma delle strette di mano). Il numero di vertici di grado dispari è quindi pari. K_n ha n(n − 1)/2 lati, un grafo k-regolare con n vertici ne ha nk/2, e un albero con n vertici ha n − 1 lati.

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