Algoritmi, grafi, programmazione dinamica e database relazionali

32 carte di ripasso universitario su ordinamento, algoritmi sui grafi, programmazione dinamica, SQL, indici e transazioni. Richiede basi di programmazione, strutture dati e SQL.

Category
Computer Science
Level
basic
Languages
it → it
Cards
32
Markdown
Algoritmi, grafi, programmazione dinamica e database relazionali (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Che cos'è una lettura fantasma e come si impedisce?Ripetere una query con un predicato trova un diverso insieme di righe corrispondenti dopo modifiche confermate da un'altra transazione. SERIALIZABLE lo impedisce nel modello standard; alcune implementazioni, come REPEATABLE READ di PostgreSQL, lo impediscono anche a un livello inferiore.
2Come sostiene WAL la durabilità di PostgreSQL con il normale commit sincrono?I record necessari raggiungono lo storage durevole prima della conferma del commit e della scrittura delle pagine modificate. Dopo un arresto anomalo, WAL può riprodurre modifiche mancanti nelle pagine. Il commit asincrono può perdere transazioni recenti già confermate.
3Che cosa rende stabile un algoritmo di ordinamento?Gli elementi con chiavi uguali mantengono il loro ordine relativo originario. Merge sort può essere stabile scegliendo prima l'elemento sinistro in caso di parità; il quicksort usuale sul posto è generalmente instabile. Dipende dall'implementazione.
4Quando counting sort o radix sort possono essere lineari?Counting sort costa O(n+k) per n chiavi in un intervallo di k valori. Radix sort con d passate stabili sulle cifre e base b costa O(d(n+b)). Sono lineari solo se i parametri lo consentono; sfruttano la struttura delle chiavi oltre ai confronti.
5Quando è valido Dijkstra e qual è un costo usuale con heap?Con pesi non negativi, rende definitiva ogni volta la distanza del vertice con distanza provvisoria minima. Con liste di adiacenza e min-heap binario richiede O((V+E) log V). Archi negativi possono invalidare l'argomento delle distanze definitive.
6Come differiscono WHERE e HAVING in una query raggruppata?WHERE filtra le righe prima del raggruppamento. HAVING filtra i gruppi risultanti e può usare condizioni sugli aggregati, come COUNT(*)>1.
7Qual è la ricorrenza standard dello zaino 0/1 con capacità intera W?D[i,w] è il valore migliore con i primi i oggetti, capacità w e pesi interi positivi wᵢ. D[0,w]=0. Se wᵢ>w, si copia D[i−1,w]; altrimenti si prende max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Il tempo O(NW) è pseudopolinomiale.
8Come differiscono chiavi primarie ed esterne in PostgreSQL?La primaria identifica righe con valori unici e non NULL. L'esterna richiede valori corrispondenti nella chiave referenziata, secondo le proprie regole su NULL. Può riferirsi a una chiave UNIQUE idonea o primaria della stessa tabella o di un'altra.
9In che cosa differisce un algoritmo greedy dalla programmazione dinamica?Greedy si impegna in una scelta locale e richiede la prova che tali scelte preservino un ottimo. La programmazione dinamica confronta alternative tramite una ricorrenza e riutilizza risultati. L'ottimo globale richiede modello e ricorrenza corretti, non solo l'etichetta «DP».
10Che cos'è un ordine topologico e come lo trova l'algoritmo di Kahn?In un DAG, ogni arco u→v colloca u prima di v. Si estrae ripetutamente un vertice con grado entrante zero, se ne eliminano gli archi uscenti e si accodano i nuovi vertici con grado zero. Se si estraggono meno di V vertici, esiste un ciclo diretto.
11Come differiscono indici clustered e nonclustered rowstore in SQL Server?Un indice clustered memorizza le righe in ordine di chiave, quindi una tabella ne ha al massimo uno. Un indice nonclustered possiede chiavi e localizzatori di righe propri e può includere altre colonne. Terminologia e dettagli variano fra sistemi.
12Che cos'è una lettura non ripetibile e quale livello standard la impedisce?Rileggendo una riga si trovano dati modificati, oppure la riga scompare, dopo che un'altra transazione ha confermato un aggiornamento o un'eliminazione. REPEATABLE READ e SERIALIZABLE impediscono questa anomalia.
13In che cosa differiscono memoizzazione e programmazione dinamica dal basso?La memoizzazione valuta i sottoproblemi quando servono, di solito ricorsivamente, e conserva i risultati. La modalità dal basso valuta gli stati quando le loro dipendenze sono già disponibili, solitamente riempiendo una tabella.
14Perché quicksort può richiedere Θ(n²) e come aiuta la casualità?Partizioni ripetutamente sbilanciate, per esempio scegliendo sempre la chiave minima fra chiavi distinte, causano lavoro quadratico. Con chiavi distinte o una gestione adeguata dei duplicati, pivot casuali danno tempo atteso O(n log n). La mediana di tre è un'euristica utile, non una garanzia nel caso peggiore.
15Perché la programmazione dinamica è utile in molti problemi di ottimizzazione?La sottostruttura ottima permette di esprimere un ottimo mediante ottimi di sottoproblemi. Quando questi si sovrappongono, memorizzarne le risposte evita lavoro ripetuto. Stati e ricorrenza devono rappresentare correttamente il problema originario.
16Che cosa significano le proprietà ACID delle transazioni?Atomicità: tutti gli effetti o nessuno. Consistenza: transazioni corrette preservano vincoli e invarianti applicativi. Isolamento: la concorrenza rispetta il livello scelto. Durabilità: gli effetti confermati sopravvivono ai guasti coperti dalle garanzie configurate.
17Perché gli alberi B+ sono utili per indici e query su intervalli?L'elevata ramificazione limita l'altezza e gli accessi alle pagine. Chiavi ordinate e foglie collegate supportano scansioni per intervallo. Gli indici hash sono rivolti all'uguaglianza e non offrono intrinsecamente lo stesso accesso ordinato per intervalli.
18Quali sono le due fasi del locking a due fasi (2PL)?Crescita: acquisire lock senza rilasciarne. Decrescita: rilasciarli senza acquisirne di nuovi. Con lock adeguati per letture e scritture in conflitto, 2PL garantisce schedulazioni serializzabili per conflitti, ma restano possibili deadlock.
19Come gestisce Bellman–Ford gli archi negativi e rileva un ciclo negativo raggiungibile?Rilassa tutti gli archi fino a V−1 volte. Un ulteriore miglioramento da un vertice raggiungibile rivela un ciclo negativo raggiungibile dalla sorgente. Il caso peggiore costa O(VE); i vertici raggiungibili dal ciclo non hanno costo minimo finito.
20Come si confrontano matrice di adiacenza e normali liste di adiacenza?Con V vertici ed E archi, una matrice occupa O(V²) e verifica un arco in O(1). Le liste occupano O(V+E); cercare (u,v) in una lista non ordinata costa O(deg(u)), dove deg(u) è la lunghezza della lista.
21Come differiscono INNER JOIN e LEFT JOIN?INNER JOIN restituisce combinazioni di righe che soddisfano la condizione di join. LEFT JOIN conserva anche ogni riga sinistra senza corrispondenza, con NULL nelle colonne destre. Più corrispondenze possono produrre più righe per una riga sinistra.
22Che cosa richiede la ricerca binaria e quando impiega O(log n)?Dimezza ripetutamente l'intervallo di ricerca in dati ordinati secondo il criterio di confronto. In un array con accesso indicizzato O(1) e confronti a tempo costante, cercare fra n elementi richiede O(log n).
23Qual è un ordine logico semplificato di una query SQL SELECT?Senza CTE, funzioni finestra né operazioni insiemistiche: FROM/JOIN → WHERE → GROUP BY e aggregati → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. È un modello logico, non necessariamente l'ordine fisico scelto dall'ottimizzatore.
24Che cos'è una lettura sporca e quale primo livello standard la impedisce?Leggere dati non confermati di un'altra transazione, indipendentemente da un successivo rollback. READ COMMITTED e i livelli standard superiori impediscono le letture sporche.
25Che cosa richiedono prima, seconda e terza forma normale?1FN: valori atomici. 2FN: 1FN e nessun attributo non primo dipende da una parte propria di una qualsiasi chiave candidata. 3FN: 1FN e in ogni dipendenza non banale X→A, X è superchiave oppure A è primo. Un attributo primo appartiene ad almeno una chiave candidata.
26Come costruiscono Kruskal e Prim un albero ricoprente minimo?In un grafo connesso, non diretto e pesato, Kruskal considera archi per peso crescente e usa Union–Find per scartare cicli. Prim amplia un solo albero scegliendo un arco di peso minimo che collega l'albero a un vertice esterno.
27Quali sono il tempo nel caso peggiore e lo spazio aggiuntivo di heapsort sul posto?Costruire l'heap costa O(n); le estrazioni successive costano complessivamente O(n log n). Con discesa iterativa nell'array iniziale, heapsort richiede O(n log n) nel caso peggiore e O(1) spazio aggiuntivo.
28Come trova BFS i cammini minimi in un grafo non pesato?BFS usa una coda FIFO ed esplora per distanza in numero di archi. Marcare un vertice quando entra nella coda evita visite ripetute. Il primo cammino scoperto verso un vertice raggiungibile ha il minimo numero di archi.
29Come funziona l'ordinamento per inserimento e da cosa dipende il costo su dati quasi ordinati?Inserisce ogni elemento in un prefisso ordinato. La versione usuale con spostamenti o scambi adiacenti costa Θ(n+I), dove I è il numero di inversioni. È lineare se I=O(n); un input piccolo non modifica il caso peggiore Θ(n²).
30Come funziona il merge sort standard su array e quali costi ha?Ordina ricorsivamente due metà e le fonde in tempo lineare. La versione standard richiede Θ(n log n) tempo e O(n) spazio ausiliario, assumendo confronti a tempo costante.
31Qual è la ricorrenza per la lunghezza della sottosequenza comune più lunga (LCS)?L[i,j] è la lunghezza della LCS di prefissi lunghi i,j. L[0,j]=L[i,0]=0. Se gli ultimi caratteri coincidono, L[i,j]=1+L[i−1,j−1]; altrimenti L[i,j]=max(L[i−1,j],L[i,j−1]). La tabella completa usa O(mn) tempo e spazio.
32Come può DFS rilevare un ciclo in un grafo diretto?DFS esplora in profondità con ricorsione o pila esplicita. Un arco verso un vertice ancora attivo sul cammino DFS corrente è un arco all'indietro e prova un ciclo diretto; un vertice già visitato non è sufficiente.