Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
Scrivi −55 come sequenza a 8 bit in complemento a due. Leggi la sequenza come numero binario senza segno: qual è il suo valore U in decimale?
Un sistema deve assegnare a ciascuno di 2782 elementi un proprio codice binario della stessa lunghezza. Qual è il numero minimo di bit b necessario?
In quante delle 8 righe della sua tabella di verità ¬(¬r ∨ p) ∧ ((p ∨ q) → q) è vera? Chiama questo numero N.
Quale enunciato è equivalente a ¬∀x ∀y (R(x, y) → R(y, 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.
Per F(A, B, C, D) = Σm(0, 2, 4, 6, 8, 10, 14) + d(9, 12, 15), dove d indica le condizioni di indifferenza, trova il numero N di implicanti primi essenziali.
Trova l’inverso di 15 modulo 67: il numero x con 0 < x < 67 e 15·x ≡ 1 (mod 67).
Usa il quadrato ripetuto per trovare 2765 mod 41.
Come costruisce l'algoritmo di Prim un albero ricoprente minimo?
L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?
Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?
Come si può rilevare se una lista concatenata semplice contiene un ciclo usando O(1) memoria aggiuntiva?
Il grafo connesso ha un circuito euleriano, un cammino euleriano che non è un circuito, oppure nessuno dei due? Clicca la tua risposta.
Quanti cammini di lunghezza 2 vanno da D a B? Un cammino può ripetere vertici e lati. Chiama il numero N.
Quale query elenca i clienti che non hanno mai effettuato un ordine?
La forma normale di Boyce-Codd (BCNF) richiede che, per ogni dipendenza funzionale non banale X → Y:
Quale metrica usa RIP per scegliere le rotte?
In un attacco SYN flood, quale risorsa cerca di esaurire l'attaccante?
Una sottorete usa la maschera 255.255.255.192. Quanti indirizzi host utilizzabili H ha?
Un host ha l'indirizzo 10.20.151.229/27. Qual è il quarto ottetto x del suo indirizzo di rete?
Risposta: U = 201
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: 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: N = 2
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 ∃y (R(x, y) ∧ ¬R(y, 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: N = 1
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.
I gruppi più grandi che si possono formare con 1 e X.
Risposta: 15−1 mod 67 = 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·15 (mod 67).
Risposta: 2765 mod 41 = 27
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 · Fa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero
L'algoritmo di Prim, con una coda di priorità degli archi di attraversamento, richiede O(E log V) con uno heap binario.
Risposta: A · Θ(nlog₂ 7), circa n2,81
Con a = 7 e b = 2, nlog₂ 7 domina il lavoro di addizione O(n²), da cui circa n2,81.
Risposta: C · Uno stack
La DFS esplora il più in profondità possibile, usando naturalmente uno stack (o lo stack delle chiamate della ricorsione); la BFS usa una coda.
Risposta: C · Si muove un puntatore di un passo e un altro di due passi e si verifica se si incontrano
Nell'algoritmo di Floyd, se c'è un ciclo il puntatore veloce prima o poi raggiunge quello lento; altrimenti il puntatore veloce arriva a null.
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 = 1
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: B · SELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
Il left join mantiene tutti i clienti e riempie le colonne degli ordini con NULL quando non c'è corrispondenza; IS NULL seleziona poi proprio quei clienti.
Risposta: C · X sia una superchiave
La BCNF richiede che ogni determinante sia una chiave candidata (superchiave); la 3NF ammette un'eccezione quando Y fa parte di una chiave candidata.
Risposta: D · Il numero di hop
RIP è un protocollo distance-vector che conta gli hop, con 16 che significa irraggiungibile. Ciò lo limita alle reti piccole.
Risposta: C · La tabella delle connessioni semiaperte del server
Ogni SYN fa sì che il server riservi uno stato e attenda un ACK che non arriva mai. I SYN cookie evitano di memorizzare lo stato finché l'handshake non è completato.
Risposta: H = 62
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).
Risposta: x = 224
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