Disegna un diagramma di Venn e decidi regione per regione che cosa appartiene all’espressione insiemistica.
Nei problemi di conteggio, riempi le regioni dal centro verso l’esterno: prima tutti gli insiemi, poi le coppie, poi i singoli insiemi, infine l’esterno.
Usa il principio di inclusione-esclusione come verifica: |A ∪ B| = |A| + |B| − |A ∩ B|.
Per una relazione, verifica ogni proprietà su ogni coppia e fornisci un controesempio quando non vale.
Per una funzione, conta le frecce che arrivano a ciascun elemento di B: al più una significa iniettiva, almeno una suriettiva.
Teoria dei grafi
Lemma delle strette di mano
Σ deg(v) = 2|E|
Grafi completi
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regolare
|E| = n·k/2
Albero e foresta
|E| = n − 1, |E| = n − c
Foglie di un albero
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Eulero
circuito: tutti i gradi pari; cammino: esattamente 2 gradi dispari
Cicli hamiltoniani in Kn
(n − 1)!/2
Aggiornamento di Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Cammini di lunghezza L
(Mᴸ)ij
Metodo
Scrivi il grado di ogni vertice; la somma dei gradi è il doppio del numero di lati.
Nelle domande su Eulero, verifica che il grafo sia connesso e conta i vertici di grado dispari.
Per gli alberi, usa n − 1 lati e il lemma delle strette di mano.
Per Dijkstra, tieni una tabella delle distanze provvisorie e a ogni passo fissa il vertice non ancora fissato con la distanza minima.
Per un albero di copertura minimo, ordina i lati per peso e salta ogni lato che chiude un ciclo (Kruskal), oppure fai crescere un solo albero a partire da un vertice iniziale (Prim).
Teoria dei numeri e aritmetica modulare
Divisione con resto
a = q·n + r, 0 ≤ r < n
Euclide
gcd(a, b) = gcd(b, a mod b)
Minimo comune multiplo
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruenza lineare
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Funzione φ di Eulero
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Metodo
Riduci prima ogni numero modulo n; i resti sono compresi tra 0 e n − 1.
Per un MCD, dividi ripetutamente con l’algoritmo di Euclide; l’ultimo resto diverso da zero è il MCD.
Per un inverso, esegui l’algoritmo esteso e tieni il coefficiente di a; aggiungi n se è negativo.
Risolvi a·x ≡ b moltiplicando per a⁻¹; combina due congruenze scrivendo x = r₁ + m₁k.
Per le potenze, scrivi l’esponente in binario ed eleva al quadrato ripetutamente; in RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
2Esercizi
1.Logica proposizionale e dimostrazioniMedia
Quale formula è logicamente equivalente a ¬(a ↔ c)? Clicca su di essa.
¬(a ↔ c)
1a ↔ ¬c
2¬a ∨ ¬c
3¬a ↔ ¬c
4a ∧ ¬c
2.Logica proposizionale e dimostrazioniDifficile
Quale enunciato è equivalente a ¬∃x (P(x) → Q(x)), con la negazione spostata fino in fondo all’interno? Clicca su di esso.
¬∃x (P(x) → Q(x))
1∀x (P(x) ∧ ¬Q(x))
2∃x (P(x) ∧ ¬Q(x))
3∀x (¬P(x) → ¬Q(x))
4∀x (P(x) → ¬Q(x))
3.Insiemi, relazioni e funzioniMedia
Ogni numero nel diagramma di Venn è il numero di elementi di quella regione. Trova |(A′ ∩ C) ∪ (B ∩ C)|.
|U| = 49
|(A′ ∩ C) ∪ (B ∩ C)| =
4.Insiemi, relazioni e funzioniDifficile
Il diagramma a frecce mostra una funzione f: A → B con A = {1, 2, 3, 4} e B = {a, b, c, d, e}. Clicca la descrizione che si adatta a f.
f = {(1, a), (2, c), (3, e), (4, d)}
1iniettiva, non suriettiva
2suriettiva, non iniettiva
3biiettiva
4nessuna delle due
5.Teoria dei grafiMedia
Un grafo connesso ha 17 vertici e 26 lati. Quanti lati k vanno tolti per ottenere un albero di copertura?
|V| = 17|E| = 26
k =
6.Teoria dei grafiDifficile
L’algoritmo di Dijkstra parte da A. Clicca il vertice che viene fissato (reso permanente) al passo 6; A stesso è il passo 1.
partenza: Apasso 6
1A
2B
3C
4D
5E
6F
7G
7.Teoria dei numeri e aritmetica modulareMedia
Trova l’inverso di 32 modulo 81: il numero x con 0 < x < 81 e 32·x ≡ 1 (mod 81).
a = 32n = 81
32−1 mod 81 =
8.Teoria dei numeri e aritmetica modulareDifficile
Una chiave RSA usa p = 7, q = 19 ed e = 7. Decifra il testo cifrato c = 80: trova il messaggio m.
p = 7q = 19e = 7c = 80
m =
3Soluzioni
1.Logica proposizionale e dimostrazioni
Risposta: a ↔ ¬c
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).
La legge
¬(a ↔ b) vale 1 esattamente quando a e b sono diversi, cioè a ↔ ¬b.
¬(a ↔ c) ≡ a ↔ ¬c
Verifica con la tabella di verità
a = 1, c = 1: 0 | 0 0 1 0
a = 1, c = 0: 1 | 1 1 0 1
a = 0, c = 1: 1 | 1 1 0 0
a = 0, c = 0: 0 | 0 1 1 0
Risposta
a ↔ ¬c
Le colonne dopo la barra sono le opzioni nell’ordine mostrato.
2.Logica proposizionale e dimostrazioni
Risposta: ∀x (P(x) ∧ ¬Q(x))
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.
Sposta la negazione verso l’interno
¬∃x (P(x) → Q(x)) ≡ ∀x (P(x) ∧ ¬Q(x))
Risposta
∀x (P(x) ∧ ¬Q(x))
Le altre opzioni lasciano invariato un quantificatore, cambiano l’ordine dei quantificatori oppure negano in modo errato la formula interna.
3.Insiemi, relazioni e funzioni
Risposta: |(A′ ∩ C) ∪ (B ∩ C)| = 19
Insiemi e diagrammi di Venn: A ∪ B contiene gli elementi in A o in B (o in entrambi), A ∩ B gli elementi in entrambi, A − B gli elementi di A che non sono in B, e il complementare A′ tutto ciò che è in U e non in A. In un diagramma di Venn ogni espressione insiemistica è un’unione di regioni, quindi contala regione per regione. Inclusione-esclusione: |A ∪ B| = |A| + |B| − |A ∩ B|, e |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Regioni dell’espressione
A′ ∩ B′ ∩ C: 6
A′ ∩ B ∩ C: 7
A ∩ B ∩ C: 6
Somma
|(A′ ∩ C) ∪ (B ∩ C)| = 6 + 7 + 6 = 19
Risposta
|(A′ ∩ C) ∪ (B ∩ C)| = 19
4.Insiemi, relazioni e funzioni
Risposta: iniettiva, non suriettiva
Funzioni e conteggio: una funzione f: A → B assegna a ogni elemento di A esattamente un’immagine in B. f è iniettiva (uno a uno) quando elementi diversi hanno immagini diverse, suriettiva (su) quando ogni elemento di B è un’immagine, e biiettiva quando valgono entrambe. Con |A| = m e |B| = n ci sono nᵐ funzioni, n!/(n − m)! iniettive (m ≤ n), e per inclusione-esclusione Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ suriettive. |𝒫(A)| = 2ᵐ e |A × B| = m·n.
Iniettiva?
ogni elemento di B è colpito al più una volta → iniettiva
Suriettiva?
b non riceve alcuna freccia → non suriettiva
Risposta
iniettiva, non suriettiva
Risposta
iniettiva, non suriettiva
5.Teoria dei grafi
Risposta: k = 10
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; Kn 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.
Lati di un albero di copertura
17 − 1 = 16
Lati da togliere
k = 26 − 16 = 10
Risposta
k = 10
6.Teoria dei grafi
Risposta: E
Cammini minimi e alberi di copertura: l’algoritmo di Dijkstra fissa un vertice per passo: il vertice non fissato con la distanza provvisoria minima. La sua distanza è allora definitiva, e ogni vertice adiacente v riceve d(v) = min(d(v), d(u) + w(u, v)). L’algoritmo di Kruskal costruisce un albero di copertura minimo prendendo i lati dal più leggero al più pesante e saltando ogni lato che chiuderebbe un ciclo; l’algoritmo di Prim fa crescere un solo albero da un vertice iniziale aggiungendo sempre il lato più leggero che ne esce. Un albero di copertura di n vertici ha n − 1 lati.
Dijkstra passo per passo
1. A (0): B: 8, C: 7
2. C (7): E: 21
3. B (8): D: 19, G: 12
4. G (12): D: 14
5. D (14): F: 23
6. E (21): F: 22
7. F (22)
passo 6
E
Risposta
E
7.Teoria dei numeri e aritmetica modulare
Risposta: 32−1 mod 81 = 38
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).
Algoritmo di Euclide esteso
Ogni resto r si scrive r ≡ t·32 (mod 81).
r = 81, t = 0
r = 32, q = 2, t = 1
r = 17, q = 1, t = −2
r = 15, q = 1, t = 3
r = 2, q = 7, t = −5
r = 1, q = 2, t = 38
Inversa
1 ≡ 38·32 (mod 81)
x = 38
verifica: 32·38 = 1216 = 15·81 + 1
Risposta
32−1 mod 81 = 38
8.Teoria dei numeri e aritmetica modulare
Risposta: m = 66
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.