Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
La sequenza a 8 bit 1000 0000 memorizza un intero con segno in complemento a due. Qual è il suo valore N in decimale?
Qual è l'intero più negativo N memorizzabile in complemento a due a 16 bit?
Quale formula è logicamente equivalente a ¬(q ∧ r)? Clicca su di essa.
Quale enunciato è equivalente a ¬∀x ∃y R(x, y), con la negazione spostata fino in fondo all’interno? Clicca su di esso.
In questa mappa di Karnaugh esattamente un 1 non ha 1 vicini, quindi resta un gruppo di una cella (un mintermine completo di quattro letterali) nella forma SOP minima. Contano anche i vicini attraverso i bordi della mappa. Clicca su quella cella.
Un contatore binario progressivo a 4 bit parte da 14 (decimale, Q = 1110). Quale valore Q (in decimale) mostra dopo 20 impulsi di clock?
Trova l’inverso di 36 modulo 67: il numero x con 0 < x < 67 e 36·x ≡ 1 (mod 67).
Risolvi 26x ≡ 2 (mod 30). Dai la più piccola soluzione positiva x.
Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?
Quale affermazione sulla selezione del k-esimo elemento più piccolo di un array non ordinato è corretta?
Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?
La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:
Un grafo connesso ha 17 vertici e 24 lati. Quanti lati k vanno tolti per ottenere un albero di copertura?
Quanti cammini di lunghezza 3 vanno da E a C? Un cammino può ripetere vertici e lati. Chiama il numero N.
Quale istruzione rimuove tutte le righe di una tabella, ne mantiene la struttura e non ammette una clausola WHERE?
Il locking a due fasi (2PL) garantisce:
Un segnale percorre 2000 km in fibra a circa 2 × 10⁸ m/s. Qual è il ritardo di propagazione?
Le query DNS usano normalmente UDP. Quando il DNS usa invece tipicamente TCP?
La rete 192.168.10.0/24 va divisa in almeno 12 sottoreti uguali. Prendendo in prestito il minor numero possibile di bit, quanti host utilizzabili H ha ogni sottorete?
Un host ha l’indirizzo 172.20.121.139/22. Qual è il terzo ottetto x del suo indirizzo di rete?
Risposta: N = −128
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: N = −32768
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: ¬q ∨ ¬r
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: ∃x ∀y ¬R(x, y)
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.
Le altre opzioni lasciano invariato un quantificatore, cambiano l’ordine dei quantificatori oppure negano in modo errato la formula interna.
Risposta: AB = 11, CD = 00
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.
Un 1 con un 1 vicino può far parte di un gruppo di due o più.
Risposta: Q = 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.
Ogni 16 impulsi riportano il contatore allo stesso stato.
Risposta: 36−1 mod 67 = 54
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·36 (mod 67).
Risposta: x = 7
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).
Risposta: D · O(n)
Ci sono n livelli, ciascuno con lavoro costante, come nella somma ricorsiva di un array.
Risposta: D · Il quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore
Il lavoro atteso del quickselect è n + n/2 + n/4 + ... = O(n) con pivot casuali; scegliere il pivot come mediana delle mediane rende lineare il caso peggiore.
Risposta: B · All'indice 4
10 mod 7 = 3 e 17 mod 7 = 3; l'indice 3 è occupato, quindi la scansione lineare prova la posizione successiva, l'indice 4.
Risposta: D · O(log n)
Dopo aver diminuito la chiave, l'elemento risale (sift-up) al massimo per l'altezza dell'heap. Gli heap di Fibonacci ottengono decrease-key in O(1) ammortizzato.
Risposta: k = 8
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.
Risposta: N = 5
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. Kn 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.
Risposta: A · TRUNCATE TABLE
TRUNCATE svuota rapidamente una tabella e ne mantiene la definizione; DELETE può rimuovere righe selezionate e DROP rimuove la tabella stessa.
Risposta: A · Schedule serializzabili rispetto ai conflitti
Il 2PL garantisce la serializzabilità, ma i deadlock restano possibili e devono essere rilevati o prevenuti.
Risposta: C · 10 ms
2 × 10⁶ m / 2 × 10⁸ m/s = 0,01 s = 10 ms. Il ritardo di propagazione dipende dalla distanza e dal mezzo, non dalla dimensione del pacchetto.
Risposta: A · Per risposte troppo grandi per UDP e per i trasferimenti di zona
Se una risposta UDP è troncata, il resolver ritenta su TCP. Anche i trasferimenti di zona tra name server usano TCP perché trasportano molti dati.
Risposta: H = 14
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 = 120
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