Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
La sequenza a 8 bit 1100 1011 memorizza un intero con segno in complemento a due. Qual è il suo valore N in decimale?
Un sistema deve assegnare a ciascuno di 2428 elementi un proprio codice binario della stessa lunghezza. Qual è il numero minimo di bit b necessario?
Quale formula è logicamente equivalente a a ↔ b? Clicca su di essa.
Sono date le premesse a → b; ¬b. Quale conclusione ne segue? Clicca su di essa.
Usa la mappa di Karnaugh per trovare la forma minima a somma di prodotti (SOP) di F(A, B, C, D) = Σm(1, 3, 5, 6, 10, 12, 13, 14). Quanti termini prodotto N ha?
Un flip-flop T sensibile al fronte di salita parte con Q = 0 e riceve gli ingressi mostrati in 7 fronti di salita del clock. Quante volte N Q cambia stato?
Trova l’inverso di 17 modulo 23: il numero x con 0 < x < 23 e 17·x ≡ 1 (mod 23).
Usa il quadrato ripetuto per trovare 2196 mod 37.
Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?
Perché l'algoritmo di Dijkstra può dare risultati errati quando alcuni pesi degli archi sono negativi?
In una coda circolare memorizzata in un array di capacità n, come si calcola la posizione successiva all'indice i?
Un albero di Fenwick (binary indexed tree) su un array di n numeri supporta quali operazioni in O(log n)?
Il grafo connesso ha un circuito euleriano, un cammino euleriano che non è un circuito, oppure nessuno dei due? Clicca la tua risposta.
Usa l’algoritmo di Dijkstra per trovare la lunghezza d(F) del cammino minimo da A a F nel grafo pesato.
Un LEFT JOIN restituisce:
Quale funzionalità SQL è più adatta a trovare tutti i dipendenti sotto un responsabile in un organigramma di profondità sconosciuta?
Il NAT (traduzione degli indirizzi di rete) serve principalmente a:
Devi suddividere 192.168.1.0/24 in almeno 5 sottoreti con fino a 25 host ciascuna. Quale lunghezza di prefisso è la più adatta?
Un reparto ha bisogno di 204 indirizzi host in un'unica sottorete. Qual è la lunghezza di prefisso più lunga p (la sottorete più piccola) sufficiente?
Un host ha l’indirizzo 172.20.181.146/22. Qual è il terzo ottetto x del suo indirizzo di rete?
Risposta: N = −53
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.
Gli altri bit mantengono i loro normali valori positivi.
Risposta: b = 12 bit
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.
Risposta: (a → b) ∧ (b → a)
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).
Le colonne dopo la barra sono le opzioni nell’ordine mostrato.
Risposta: ¬a
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.
Risposta: N = 5
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.
Ogni gruppo è un rettangolo di 2ᵏ celle; le celle di bordo sono vicine alle celle del bordo opposto.
Esiste un altro raggruppamento della stessa dimensione; ha lo stesso numero di termini e di letterali.
Risposta: N = 2
Flip-flop e contatori: un flip-flop cambia solo sul fronte attivo del clock. D copia il suo ingresso (Q⁺ = D); T commuta quando T = 1; JK mantiene per 00, azzera per 01, imposta a 1 per 10 e commuta per 11. Un contatore binario a n bit ha 2ⁿ stati e conta modulo 2ⁿ; un contatore modulo N conta 0, 1, …, N − 1 e torna a 0, e richiede il minimo n con 2ⁿ ≥ N flip-flop. Ogni stadio di un contatore asincrono (ripple) dimezza la frequenza, quindi l’ultima uscita di un contatore modulo N ha frequenza fclk/N. Un contatore Johnson di n flip-flop ha 2n stati, un contatore ad anello n.
Un flip-flop T commuta a ogni fronte di salita con T = 1 e mantiene con T = 0.
Risposta: 17−1 mod 23 = 19
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).
Ogni resto r si scrive r ≡ t·17 (mod 23).
Risposta: 2196 mod 37 = 10
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.
Risposta: C · I cammini minimi tra tutte le coppie di vertici in O(V³)
Floyd–Warshall è un algoritmo di programmazione dinamica che ammette a turno ogni vertice come punto intermedio, con tempo O(V³).
Risposta: D · Un vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve
Il passo greedy si basa su pesi non negativi perché le distanze estratte siano definitive; quando i pesi possono essere negativi si usa Bellman–Ford.
Risposta: C · (i + 1) mod n
L'operazione modulo riporta l'indice n − 1 a 0, così l'array viene riutilizzato senza spostare elementi.
Risposta: C · Interrogazioni di somme prefisse e aggiornamenti di singoli elementi
Un albero di Fenwick memorizza somme parziali su intervalli determinati dai bit meno significativi di ogni indice, quindi sia le somme prefisse sia gli aggiornamenti puntuali richiedono O(log n).
Risposta: Cammino euleriano, nessun circuito
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.
Il cammino euleriano parte da un vertice dispari e termina nell’altro.
Risposta: d(F) = 11
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.
Ogni riga: il vertice fissato, la sua distanza definitiva e i vertici adiacenti la cui distanza migliora.
Risposta: B · Tutte le righe della tabella di sinistra e le righe corrispondenti di quella di destra, con NULL dove non c'è corrispondenza
Un left outer join mantiene ogni riga di sinistra; le colonne di destra senza corrispondenza vengono riempite con NULL.
Risposta: A · Una common table expression ricorsiva (WITH RECURSIVE)
Una CTE ricorsiva parte da una query di ancoraggio e unisce ripetutamente il risultato precedente alla tabella, quindi gestisce gerarchie di qualsiasi profondità.
Risposta: D · Permettere a molti dispositivi con indirizzi privati di condividere un unico indirizzo IP pubblico
Il NAT riscrive gli indirizzi (e le porte) in modo che le reti private possano accedere a internet tramite un numero minore di indirizzi pubblici.
Risposta: A · /27
/27 dà 8 sottoreti con 30 host utilizzabili ciascuna. /26 dà solo 4 sottoreti, e /28 consente solo 14 host per sottorete.
Risposta: p = 24
Sottoreti IPv4: un indirizzo ha 32 bit. Il prefisso /p indica quanti bit iniziali identificano la rete; i restanti 32 − p bit numerano gli host. Una sottorete ha 2³²⁻ᵖ indirizzi, ma il primo (indirizzo di rete) e l'ultimo (broadcast) non si possono assegnare agli host, quindi ci stanno 2³²⁻ᵖ − 2 host. Eccezioni: una /31 (collegamento punto-punto, RFC 3021) usa entrambi i suoi 2 indirizzi per gli host, e una /32 è un solo indirizzo (un singolo host o un’interfaccia di loopback).
Risposta: x = 180
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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals