Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
Imposta i bit in modo che memorizzino −113 in complemento a due a 8 bit. Letto come numero senza segno, qual è il valore U dello schema?
Un'immagine non compressa è di 640 × 480 pixel con 8 bit per pixel. Quanta memoria M occupa, in KiB (1 KiB = 1024 byte)?
In quante delle 8 righe della sua tabella di verità (c → (b ↔ ¬a)) ∧ (b ↔ ¬a) è vera? Chiama questo numero N.
Quale enunciato è equivalente a ¬∃x (P(x) ∧ Q(x)), 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 flip-flop D sensibile al fronte di salita parte con Q = 0 e riceve gli ingressi mostrati. Clicca il primo fronte di clock in cui Q passa da 1 a 0.
Trova l’inverso di 46 modulo 59: il numero x con 0 < x < 59 e 46·x ≡ 1 (mod 59).
79 è primo. Usa il piccolo teorema di Fermat per trovare 2645972 mod 79.
In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?
Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?
Come si trova la chiave minima in un albero binario di ricerca?
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.
Quanti cammini chiusi di lunghezza 2 partono e terminano in E? Un cammino può ripetere vertici e lati. Chiama il numero N.
Una tabella employees ha una colonna manager_id che fa riferimento a un altro dipendente. Come si elenca ogni dipendente accanto al nome del suo responsabile?
R(A, B, C, D) ha le dipendenze funzionali A → B e C → D. Qual è la chiave candidata?
Quale metodo di accesso al mezzo usava la classica Ethernet condivisa (half-duplex)?
Secondo il teorema di Shannon, qual è la capacità di un canale da 1 MHz con un rapporto segnale/rumore di 255?
Un reparto ha bisogno di 1825 indirizzi host in un'unica sottorete. Qual è la lunghezza di prefisso più lunga p (la sottorete più piccola) sufficiente?
Un host ha l'indirizzo 10.20.200.180/26. Qual è il quarto ottetto x del suo indirizzo di rete?
Risposta: U = 143
Impostare i bit: ogni bit vale una potenza di due (128, 64, …, 1). Una cifra esadecimale è esattamente quattro bit, e nel complemento a due a 8 bit il bit più a sinistra vale −128. Le operazioni bit a bit lavorano su ogni posizione di bit separatamente.
Risposta: M = 300 KiB
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: N = 4
Tabelle di verità: una formula con n variabili distinte ha 2ⁿ righe, una per ogni combinazione di valori di verità (1 = vero, 0 = falso). Procedi dall’interno verso l’esterno e dai a ogni sottoformula una colonna propria. ¬a inverte il valore; a ∧ b vale 1 solo quando entrambi valgono 1; a ∨ b vale 0 solo quando entrambi valgono 0; a → b vale 0 solo quando a = 1 e b = 0; a ↔ b vale 1 quando i due lati sono uguali.
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.
Le altre opzioni lasciano invariato un quantificatore, cambiano l’ordine dei quantificatori oppure negano in modo errato la formula interna.
Risposta: AB = 01, CD = 11
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: fronte di clock 3
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 D copia D a ogni fronte di salita: Q⁺ = D.
Risposta: 46−1 mod 59 = 9
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·46 (mod 59).
Risposta: 2645972 mod 79 = 67
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: B · O(n)
Se la somma è troppo piccola il puntatore sinistro si sposta a destra, se è troppo grande il puntatore destro si sposta a sinistra, quindi ci sono al massimo n passi.
Risposta: D · Al massimo il doppio della dimensione di una copertura dei vertici minima
Gli archi del matching non condividono vertici, quindi l'ottimo ha bisogno di almeno un vertice per arco, mentre questo metodo ne prende due: una 2-approssimazione.
Risposta: A · Si seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
Il nodo più a sinistra non ha chiavi minori nell'albero, quindi è il minimo; il costo è proporzionale all'altezza.
Risposta: A · 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: nessuna delle due
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 = 3
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 · Unendo la tabella employees con se stessa usando due alias
Un self-join come FROM employees e JOIN employees m ON e.manager_id = m.id permette a un alias di rappresentare il dipendente e all'altro il responsabile.
Risposta: A · {A, C}
A e C non sono determinati da nulla, quindi ogni chiave deve contenerli entrambi, e {A, C}+ = {A, B, C, D}.
Risposta: A · CSMA/CD
Carrier sense multiple access with collision detection: le stazioni si fermano quando rilevano una collisione e riprovano dopo un backoff casuale. L'Ethernet commutata full-duplex non ha collisioni.
Risposta: D · 8 Mbit/s
C = 10⁶ × log₂(256) = 10⁶ × 8 = 8 Mbit/s. È il limite superiore della velocità di trasmissione senza errori su un canale rumoroso.
Risposta: p = 21
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 = 128
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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals