Formulari, i passaggi chiave del metodo per ogni argomento e 20 esercizi, con le soluzioni complete in fondo.
La sequenza a 8 bit 1000 0100 memorizza un intero con segno in complemento a due. Qual è il suo valore N in decimale?
Un'immagine non compressa è di 512 × 512 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à (p ∧ ¬(q ∨ r)) ∨ (p ∨ (r → ¬q)) è vera? Chiama questo numero N.
L’argomento con premesse p → q; ¬p e conclusione ¬q non è valido. Clicca la riga della tabella di verità che è un controesempio.
Usa la mappa di Karnaugh per trovare la forma minima a prodotto di somme (POS) di F(A, B, C, D) = Σm(2, 5, 7, 8, 10, 11). Quanti termini somma (fattori) N ha?
Trova la forma SOP minima di F(A, B, C, D) = Σm(1, 3, 5, 14) + d(2, 8, 15), dove d indica le condizioni di indifferenza. Quanti letterali L contiene?
Trova il più piccolo intero positivo x con x ≡ 4 (mod 7) e x ≡ 2 (mod 11).
41 è primo. Usa il piccolo teorema di Fermat per trovare 1257319 mod 41.
Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?
Come si confrontano n! e 2ⁿ per n grande?
Un buffer circolare (ring buffer) è comunemente usato per implementare:
In un buffer circolare, front == rear può significare sia vuoto sia pieno. Qual è un modo comune per distinguere i due casi?
Quanti cicli hamiltoniani diversi H ha il grafo completo K7? I cicli che differiscono solo per il vertice iniziale o per il verso contano come lo stesso.
L’algoritmo di Dijkstra parte da A. Clicca il vertice che viene fissato (reso permanente) al passo 5; A stesso è il passo 1.
Quando WHERE EXISTS (subquery) è vera per una riga?
La query FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.status = 'paid' esclude inaspettatamente i clienti senza ordini. Perché?
A quale livello OSI opera normalmente uno switch?
Perché un browser mostra un avviso quando un sito presenta un certificato autofirmato?
La rete 10.33.52.0/22 viene divisa in sottoreti uguali con prefisso /30. Quante sottoreti N ci sono?
Un host ha l'indirizzo 10.20.90.14/25. Qual è l'ultimo numero (quarto ottetto) x dell'indirizzo di broadcast della sua sottorete?
Risposta: N = −124
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: M = 256 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 = 7
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: p = 0, q = 1
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.
Un argomento di questa forma sembra una regola valida, ma una sola riga basta a mostrare che non lo è.
Risposta: N = 5
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.
Esiste un altro raggruppamento della stessa dimensione; ha lo stesso numero di termini e di letterali.
Risposta: L = 9
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.
Esiste un altro raggruppamento della stessa dimensione; ha lo stesso numero di termini e di letterali.
Risposta: x = 46
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: 1257319 mod 41 = 24
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: D · O(n log n + k log n)
L'ordinamento costa O(n log n) e ogni query O(log n); questo batte k scansioni lineari (O(nk)) quando k è grande.
Risposta: B · n! cresce più velocemente di 2ⁿ
Per n ≥ 4, n! supera 2ⁿ, e il rapporto cresce senza limite perché ogni fattore aggiuntivo di n! è maggiore di 2.
Risposta: D · Una coda di dimensione fissa
Un buffer circolare usa indici di testa e di coda che ripartono dall'inizio, garantendo enqueue e dequeue in O(1) con memoria fissa.
Risposta: A · Mantenere un contatore separato degli elementi, oppure lasciare sempre una posizione inutilizzata
Con un contatore, vuoto significa count = 0 e pieno significa count = capacità; con una posizione sempre vuota, pieno si definisce come (rear + 1) mod n == front.
Risposta: H = 360
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: F
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.
Risposta: B · Quando la subquery restituisce almeno una riga
EXISTS verifica solo se viene prodotta almeno una riga; NOT EXISTS è vera quando la subquery non restituisce righe.
Risposta: B · La condizione WHERE su o scarta le righe riempite di NULL, trasformandolo in un inner join
Le righe senza corrispondenza hanno o.status NULL, quindi il test della WHERE non è TRUE; spostare la condizione nella clausola ON mantiene tutti i clienti.
Risposta: D · Collegamento dati (livello 2)
Uno switch standard apprende gli indirizzi MAC e inoltra i frame al livello 2. Gli switch di livello 3 effettuano anche il routing.
Risposta: A · Nessuna autorità di certificazione fidata garantisce che la chiave appartenga a quel sito
I browser si fidano dei certificati firmati, direttamente o tramite una catena, da CA presenti nel loro archivio attendibile. Un certificato autofirmato potrebbe essere creato da chiunque, per esempio da un man-in-the-middle.
Risposta: N = 256
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).
Ogni sottorete /30 ha 22 − 2 = 2 host utilizzabili.
Risposta: x = 127
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