Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
Scrivi −15 come sequenza a 8 bit in complemento a due. Leggi la sequenza come numero binario senza segno: qual è il suo valore U in decimale?
Qual è l'intero più negativo N memorizzabile in complemento a due a 24 bit?
Quale formula è logicamente equivalente a ¬(b ↔ c)? Clicca su di essa.
Sono date le premesse p → r; r → q; ¬q. 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) = Σm(2, 3, 7). Quanti termini prodotto N ha?
Un flip-flop JK 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 5 modulo 23: il numero x con 0 < x < 23 e 5·x ≡ 1 (mod 23).
Cifra il messaggio m = 107 con la chiave pubblica RSA (n, e) = (187, 3). Trova il testo cifrato c.
Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?
Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?
Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?
Un oggetto è memorizzato come chiave in una hash map, e poi viene modificato un campo usato dalla sua funzione hash. Qual è il risultato probabile?
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.
Che cosa restituisce SELECT SUM(amount) FROM orders quando la clausola WHERE non corrisponde ad alcuna riga?
x è NULL e y = 1. Qual è il valore della condizione (x > 5 OR y = 1)?
Qual è la differenza principale tra i metodi HTTP GET e POST?
Uno studente gestisce un server di gioco su un PC dietro un router NAT domestico. Gli amici su Internet non riescono a connettersi. Qual è la soluzione abituale?
Un reparto ha bisogno di 88 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.131.251/26. Qual è il quarto ottetto x dell'ultimo indirizzo host utilizzabile della sua sottorete?
Risposta: U = 241
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 = −8,389 × 10⁶
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 ↔ ¬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).
Le colonne dopo la barra sono le opzioni nell’ordine mostrato.
Risposta: ¬p
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 = 2
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.
Risposta: fronte di clock 4
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 JK: 00 mantiene, 01 azzera (Q = 0), 10 imposta (Q = 1), 11 commuta.
Risposta: 5−1 mod 23 = 14
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·5 (mod 23).
Risposta: c = 6
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 · Il greedy usa 3 monete; l'ottimo è 2
Il greedy prende 4 + 1 + 1 = 3 monete, ma 3 + 3 ne usa solo 2, quindi il greedy non è ottimo per questo sistema di monete; la programmazione dinamica sì.
Risposta: C · Un albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
Ogni confronto al massimo dimezza l'insieme delle possibilità rimanenti, quindi distinguere n posizioni richiede almeno log₂ n confronti.
Risposta: D · Lista di adiacenza
Una matrice richiederebbe 1010 celle, quasi tutte vuote; una lista di adiacenza memorizza solo le circa 400,000 voci degli archi.
Risposta: B · La ricerca dell'oggetto può fallire perché si trova nel bucket corrispondente al vecchio hash
La posizione della chiave è stata scelta in base al vecchio hash; con un nuovo hash le ricerche esaminano il bucket sbagliato, quindi le chiavi dovrebbero essere immutabili.
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) = 20
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: A · NULL
SUM, AVG, MIN e MAX restituiscono NULL su un insieme vuoto, mentre COUNT restituisce 0; COALESCE(SUM(amount), 0) restituisce invece 0.
Risposta: B · TRUE
x > 5 è UNKNOWN, ma OR con TRUE dà comunque TRUE, quindi la riga viene mantenuta; allo stesso modo UNKNOWN AND FALSE sarebbe FALSE.
Risposta: D · GET recupera una risorsa, POST invia dati nel corpo della richiesta
GET chiede una risorsa e non dovrebbe modificare lo stato del server. POST invia dati, come un modulo, nel corpo affinché il server li elabori.
Risposta: B · Configurare sul router il port forwarding verso l'indirizzo privato del PC
Il NAT crea associazioni solo per le connessioni avviate dall'interno. Una regola di port forwarding associa una porta pubblica all'host interno, così le connessioni in entrata possono raggiungerlo.
Risposta: p = 25
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 = 254
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