Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
La sequenza a 8 bit 0000 0011 memorizza un intero con segno in complemento a due. Qual è il suo valore N in decimale?
Qual è il più grande intero senza segno N che sta in 16 bit?
(p → q) → (q → p) è una tautologia, una contraddizione o una contingenza? Clicca la tua risposta.
Sono date le premesse p ∨ r; ¬p. Quale conclusione ne segue? Clicca su di essa.
Usa la mappa di Karnaugh per trovare la forma minima a prodotto di somme (POS) di F(A, B, C) = Σm(2, 3, 4, 5, 7). Quanti termini somma (fattori) N ha?
Un clock da 8 kHz pilota un contatore modulo 100. Trova la frequenza fout della sua uscita più significativa, che completa un ciclo per ogni ciclo di conteggio.
Trova l’inverso di 72 modulo 79: il numero x con 0 < x < 79 e 72·x ≡ 1 (mod 79).
Una chiave RSA usa i primi p = 17 e q = 43 e l’esponente pubblico e = 23. Trova l’esponente privato d (0 < d < φ(n)).
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?
Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?
Quale struttura dati si usa per verificare se le parentesi in "{[()]}" sono bilanciate?
Nel BST con radice 50, sottoalbero sinistro 30 (figli 20, 40) e sottoalbero destro 70 (figli 60, 80), la radice viene eliminata usando il successore in ordine. Quale chiave diventa la nuova radice?
Un grafo connesso ha 13 vertici e 20 lati. Quanti lati k vanno tolti per ottenere un albero di copertura?
Usa l’algoritmo di Dijkstra per trovare la lunghezza d(E) del cammino minimo da A a E nel grafo pesato.
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?
Esiste un indice composto su (last_name, first_name). Quale condizione può usarlo nel modo più efficace?
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?
La rete 192.168.85.0/24 è divisa in sottoreti /28, numerate 1, 2, 3, … a partire dall’indirizzo più basso (la sottorete 1 inizia da .0). Qual è il quarto ottetto x dell’indirizzo di rete della sottorete 4?
Un host ha l’indirizzo 172.20.252.191/23. Qual è il terzo ottetto x dell’indirizzo di broadcast della sua sottorete?
Risposta: N = 3
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 = 65535
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: contingenza
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).
Risposta: r
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: fout = 0,08 kHz
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.
Risposta: 72−1 mod 79 = 45
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·72 (mod 79).
Risposta: d = 263
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 · 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: D · Dopo V − 1 turni controlla se qualche arco può ancora essere rilassato
Tutte le vere distanze minime si trovano entro V − 1 turni; se un arco può ancora essere migliorato, deve esistere un ciclo negativo.
Risposta: A · Una pila
Si inserisce (push) ogni parentesi aperta e si estrae (pop) quando compare una parentesi chiusa; questa deve corrispondere a quella estratta e alla fine la pila deve essere vuota.
Risposta: A · 60
Il nodo più a sinistra del sottoalbero destro è 60, quindi 60 sostituisce 50 e la sua vecchia posizione viene rimossa; usando il predecessore si otterrebbe 40.
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: d(E) = 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: C · 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: C · WHERE last_name = 'Jansen'
Un indice B-tree composto è ordinato per last_name e poi per first_name, quindi una ricerca sulla colonna iniziale funziona, ma first_name da sola non può sfruttare l'ordinamento.
Risposta: C · 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: x = 48
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 = 253
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