Què signifiquen les propietats ACID d'una transacció?

Atomicitat: tots els efectes o cap. Consistència: les transaccions correctes preserven restriccions i invariants de l'aplicació. Aïllament: la concurrència respecta el nivell escollit. Durabilitat: els efectes confirmats sobreviuen als errors coberts per les garanties configurades.

Quan és vàlid Dijkstra i quin és un cost habitual amb monticle?

Amb pesos no negatius, fixa repetidament el vèrtex amb la distància provisional més petita. Una implementació amb llistes d'adjacència i monticle binari mínim triga O((V+E) log V). Les arestes negatives poden invalidar l'argument de distància definitiva.

En què es diferencien INNER JOIN i LEFT JOIN?

INNER JOIN retorna les combinacions de files que compleixen la condició d'unió. LEFT JOIN conserva també cada fila esquerra sense coincidència, amb NULL a les columnes dretes. Diverses coincidències dretes poden produir diverses files per una fila esquerra.

Per què és útil la programació dinàmica en molts problemes d'optimització?

La subestructura òptima permet expressar un òptim a partir d'òptims dels subproblemes. Si se superposen, emmagatzemar-ne les respostes evita feina repetida. La definició dels estats i la recurrència han de representar correctament el problema original.

En què difereixen les claus primàries i foranes a PostgreSQL?

La primària identifica files amb valors únics i no NULL. La forana exigeix coincidència amb els valors d'una clau referenciada, segons les seves regles de NULL. Pot referenciar una clau UNIQUE apta o una primària de la mateixa taula o d'una altra.

En què difereixen els índexs agrupats i no agrupats de magatzem per files a SQL Server?

L'agrupat desa les files en ordre de clau, de manera que només n'hi pot haver un per taula. El no agrupat té claus i localitzadors de files propis i pot incloure altres columnes. La terminologia i els detalls varien entre sistemes.

En què es diferencien WHERE i HAVING en una consulta agrupada?

WHERE filtra les files d'entrada abans d'agrupar. HAVING filtra els grups resultants i admet condicions amb agregats, com COUNT(*)>1.

Com troba BFS els camins més curts en un graf no ponderat?

BFS usa una cua FIFO i explora per distància en nombre d'arestes. Marcar un vèrtex en encuar-lo evita visites repetides. El primer camí descobert fins a un vèrtex accessible té el mínim nombre d'arestes.

Què és un ordre topològic i com el troba l'algorisme de Kahn?

En un DAG, cada aresta u→v situa u abans de v. S'extreu repetidament un vèrtex de grau d'entrada zero i se n'eliminen les arestes sortints, encuant els nous vèrtexs de grau zero. Si surten menys de V vèrtexs, hi ha un cicle dirigit.

En què difereix un algorisme voraç de la programació dinàmica?

El voraç adopta una decisió local i cal demostrar que aquestes decisions conserven un òptim. La programació dinàmica compara alternatives amb una recurrència i reutilitza resultats. L'òptim global exigeix un model i una recurrència correctes, no només l'etiqueta «programació dinàmica».

Com funciona l'ordenació per inserció i de què depèn el cost amb dades gairebé ordenades?

Insereix cada element en un prefix ordenat. La versió habitual amb desplaçaments o intercanvis adjacents triga Θ(n+I), on I és el nombre d'inversions. És lineal si I=O(n); una entrada petita no canvia el pitjor cas Θ(n²).

Quina és la recurrència dinàmica de la longitud de la subseqüència comuna més llarga (LCS)?

L[i,j] és la longitud de la LCS de prefixos de longituds i,j. L[0,j]=L[i,0]=0. Si coincideixen els darrers caràcters, L[i,j]=1+L[i−1,j−1]; si no, L[i,j]=max(L[i−1,j],L[i,j−1]). La taula completa requereix temps i espai O(mn).

Com manté WAL la durabilitat a PostgreSQL amb confirmació síncrona normal?

Els registres pertinents arriben a l'emmagatzematge durador abans de reconèixer la confirmació i abans d'escriure les pàgines modificades. Després d'un error, WAL pot reproduir els canvis que falten a les pàgines. La confirmació asíncrona pot perdre transaccions recents ja reconegudes.

Què és una lectura fantasma i com s'evita?

Repetir una consulta per predicat troba un conjunt diferent de files coincidents després de canvis confirmats per una altra transacció. SERIALIZABLE ho impedeix en el model estàndard; algunes implementacions, com REPEATABLE READ de PostgreSQL, també ho impedeixen en un nivell inferior.

En què difereixen la memoització i la programació dinàmica ascendent?

La memoització avalua els subproblemes quan calen, normalment recursivament, i en desa els resultats. La programació dinàmica ascendent avalua els estats quan les seves dependències ja estan disponibles, normalment omplint una taula.

Quin és un ordre lògic simplificat de processament d'una consulta SQL SELECT?

Sense CTE, funcions de finestra ni operacions entre conjunts: FROM/JOIN → WHERE → GROUP BY i agregats → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. És un model lògic, no necessàriament l'ordre físic triat per l'optimitzador.

Quina és la recurrència habitual de la motxilla 0/1 amb capacitat entera W?

D[i,w] és el millor valor amb els primers i objectes, capacitat w i pesos enters positius wᵢ. D[0,w]=0. Si wᵢ>w, es copia D[i−1,w]; altrament, max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). El temps O(NW) és pseudopolinòmic.

Quan poden l'ordenació per comptatge i per radix trigar temps lineal?

El comptatge costa O(n+k) per a n claus en un rang de k valors. Radix amb d passades estables per dígits i base b costa O(d(n+b)). Només són lineals quan els paràmetres ho permeten; aprofiten l'estructura de les claus més enllà de les comparacions.

Què és una lectura bruta i quin és el primer nivell estàndard que la impedeix?

Llegir dades no confirmades d'una altra transacció, tant si després es desfà com si no. READ COMMITTED i els nivells estàndard superiors prohibeixen les lectures brutes.

Què vol dir que un algorisme d'ordenació sigui estable?

Els elements amb claus iguals conserven l'ordre relatiu original. La fusió pot ser estable si en els empats es pren primer l'element de l'esquerra; el quicksort habitual in situ sol ser inestable. Depèn de la implementació.

Per què quicksort pot trigar Θ(n²) i com hi ajuda l'aleatorització?

Les particions repetidament desequilibrades, com triar sempre la clau més petita entre claus diferents, causen treball quadràtic. Amb claus diferents o un tractament adequat dels duplicats, els pivots aleatoris donen temps esperat O(n log n). La mediana de tres és una heurística útil, no una garantia per al pitjor cas.

Com funciona l'ordenació per fusió estàndard per a vectors i quins costos té?

Ordena recursivament dues meitats i les fusiona en temps lineal. La versió estàndard triga Θ(n log n) i necessita O(n) d'espai auxiliar, amb comparacions de temps constant.

Què requereix la cerca binària i quan triga O(log n)?

Redueix a la meitat l'interval de cerca en dades ordenades segons el criteri de comparació. En un vector amb accés per índex O(1) i comparacions de temps constant, cercar entre n elements costa O(log n).

Per què els arbres B+ són útils per a índexs i consultes per rang?

L'alt factor de ramificació manté poca alçada i redueix accessos a pàgines. Les claus ordenades i les fulles enllaçades permeten recórrer rangs. Els índexs hash s'orienten a la igualtat i no ofereixen intrínsecament el mateix accés ordenat per rangs.

Què és una lectura no repetible i quin nivell estàndard la impedeix?

En rellegir una fila, les dades han canviat o la fila ha desaparegut després que una altra transacció confirmi una actualització o eliminació. REPEATABLE READ i SERIALIZABLE impedeixen aquesta anomalia.

Com pot DFS detectar un cicle en un graf dirigit?

DFS aprofundeix mitjançant recursió o una pila explícita. Una aresta cap a un vèrtex encara actiu en el camí actual és una aresta de retorn i demostra un cicle dirigit; no n'hi ha prou que el vèrtex ja hagi estat visitat.

Com tracta Bellman–Ford les arestes negatives i detecta un cicle negatiu accessible?

Relaxa totes les arestes fins a V−1 vegades. Una millora addicional des d'un vèrtex accessible revela un cicle negatiu accessible des de l'origen. El pitjor cas costa O(VE); els vèrtexs accessibles des d'aquest cicle no tenen cost mínim finit.

Quines són les dues fases del bloqueig en dues fases (2PL)?

Creixement: adquirir bloquejos sense alliberar-ne. Decreixement: alliberar-ne sense adquirir-ne de nous. Amb bloquejos adequats per a lectures i escriptures en conflicte, 2PL garanteix planificacions serialitzables per conflictes, però hi pot haver interbloquejos.

Com es comparen una matriu d'adjacència i unes llistes d'adjacència ordinàries?

Amb V vèrtexs i E arestes, la matriu ocupa O(V²) i comprova una aresta en O(1). Les llistes ocupen O(V+E); cercar (u,v) en una llista no ordenada costa O(deg(u)), on deg(u) és la longitud d'aquella llista.

Què exigeixen la primera, segona i tercera formes normals?

1FN: valors atòmics. 2FN: 1FN i cap atribut no primer depèn d'una part pròpia de cap clau candidata. 3FN: 1FN i, en tota dependència no trivial X→A, X és superclau o A és primer. Un atribut primer pertany a alguna clau candidata.

Quins són el temps en el pitjor cas i l'espai addicional de heapsort in situ?

Construir el monticle costa O(n) i les extraccions sumen O(n log n). Amb descens iteratiu dins del vector d'entrada, heapsort triga O(n log n) en el pitjor cas i usa O(1) d'espai addicional.

Com construeixen Kruskal i Prim un arbre d'expansió mínim?

En un graf connex, no dirigit i ponderat, Kruskal considera les arestes per pes creixent i usa Union–Find per rebutjar cicles. Prim amplia un sol arbre triant una aresta de pes mínim que connecti l'arbre amb un vèrtex exterior.

Algorismes, grafs, programació dinàmica i bases de dades relacionals

32 targetes de repàs universitari sobre ordenació, algorismes de grafs, programació dinàmica, SQL, índexs i transaccions. Requereix programació bàsica, estructures de dades i SQL.

Level: basic
Languages: ca → ca
Cards: 32
Markdown: Algorismes, grafs, programació dinàmica i bases de dades relacionals (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Què signifiquen les propietats ACID d'una transacció?	Atomicitat: tots els efectes o cap. Consistència: les transaccions correctes preserven restriccions i invariants de l'aplicació. Aïllament: la concurrència respecta el nivell escollit. Durabilitat: els efectes confirmats sobreviuen als errors coberts per les garanties configurades.
2	Quan és vàlid Dijkstra i quin és un cost habitual amb monticle?	Amb pesos no negatius, fixa repetidament el vèrtex amb la distància provisional més petita. Una implementació amb llistes d'adjacència i monticle binari mínim triga O((V+E) log V). Les arestes negatives poden invalidar l'argument de distància definitiva.
3	En què es diferencien INNER JOIN i LEFT JOIN?	INNER JOIN retorna les combinacions de files que compleixen la condició d'unió. LEFT JOIN conserva també cada fila esquerra sense coincidència, amb NULL a les columnes dretes. Diverses coincidències dretes poden produir diverses files per una fila esquerra.
4	Per què és útil la programació dinàmica en molts problemes d'optimització?	La subestructura òptima permet expressar un òptim a partir d'òptims dels subproblemes. Si se superposen, emmagatzemar-ne les respostes evita feina repetida. La definició dels estats i la recurrència han de representar correctament el problema original.
5	En què difereixen les claus primàries i foranes a PostgreSQL?	La primària identifica files amb valors únics i no NULL. La forana exigeix coincidència amb els valors d'una clau referenciada, segons les seves regles de NULL. Pot referenciar una clau UNIQUE apta o una primària de la mateixa taula o d'una altra.
6	En què difereixen els índexs agrupats i no agrupats de magatzem per files a SQL Server?	L'agrupat desa les files en ordre de clau, de manera que només n'hi pot haver un per taula. El no agrupat té claus i localitzadors de files propis i pot incloure altres columnes. La terminologia i els detalls varien entre sistemes.
7	En què es diferencien WHERE i HAVING en una consulta agrupada?	WHERE filtra les files d'entrada abans d'agrupar. HAVING filtra els grups resultants i admet condicions amb agregats, com COUNT(*)>1.
8	Com troba BFS els camins més curts en un graf no ponderat?	BFS usa una cua FIFO i explora per distància en nombre d'arestes. Marcar un vèrtex en encuar-lo evita visites repetides. El primer camí descobert fins a un vèrtex accessible té el mínim nombre d'arestes.
9	Què és un ordre topològic i com el troba l'algorisme de Kahn?	En un DAG, cada aresta u→v situa u abans de v. S'extreu repetidament un vèrtex de grau d'entrada zero i se n'eliminen les arestes sortints, encuant els nous vèrtexs de grau zero. Si surten menys de V vèrtexs, hi ha un cicle dirigit.
10	En què difereix un algorisme voraç de la programació dinàmica?	El voraç adopta una decisió local i cal demostrar que aquestes decisions conserven un òptim. La programació dinàmica compara alternatives amb una recurrència i reutilitza resultats. L'òptim global exigeix un model i una recurrència correctes, no només l'etiqueta «programació dinàmica».
11	Com funciona l'ordenació per inserció i de què depèn el cost amb dades gairebé ordenades?	Insereix cada element en un prefix ordenat. La versió habitual amb desplaçaments o intercanvis adjacents triga Θ(n+I), on I és el nombre d'inversions. És lineal si I=O(n); una entrada petita no canvia el pitjor cas Θ(n²).
12	Quina és la recurrència dinàmica de la longitud de la subseqüència comuna més llarga (LCS)?	L[i,j] és la longitud de la LCS de prefixos de longituds i,j. L[0,j]=L[i,0]=0. Si coincideixen els darrers caràcters, L[i,j]=1+L[i−1,j−1]; si no, L[i,j]=max(L[i−1,j],L[i,j−1]). La taula completa requereix temps i espai O(mn).
13	Com manté WAL la durabilitat a PostgreSQL amb confirmació síncrona normal?	Els registres pertinents arriben a l'emmagatzematge durador abans de reconèixer la confirmació i abans d'escriure les pàgines modificades. Després d'un error, WAL pot reproduir els canvis que falten a les pàgines. La confirmació asíncrona pot perdre transaccions recents ja reconegudes.
14	Què és una lectura fantasma i com s'evita?	Repetir una consulta per predicat troba un conjunt diferent de files coincidents després de canvis confirmats per una altra transacció. SERIALIZABLE ho impedeix en el model estàndard; algunes implementacions, com REPEATABLE READ de PostgreSQL, també ho impedeixen en un nivell inferior.
15	En què difereixen la memoització i la programació dinàmica ascendent?	La memoització avalua els subproblemes quan calen, normalment recursivament, i en desa els resultats. La programació dinàmica ascendent avalua els estats quan les seves dependències ja estan disponibles, normalment omplint una taula.
16	Quin és un ordre lògic simplificat de processament d'una consulta SQL SELECT?	Sense CTE, funcions de finestra ni operacions entre conjunts: FROM/JOIN → WHERE → GROUP BY i agregats → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. És un model lògic, no necessàriament l'ordre físic triat per l'optimitzador.
17	Quina és la recurrència habitual de la motxilla 0/1 amb capacitat entera W?	D[i,w] és el millor valor amb els primers i objectes, capacitat w i pesos enters positius wᵢ. D[0,w]=0. Si wᵢ>w, es copia D[i−1,w]; altrament, max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). El temps O(NW) és pseudopolinòmic.
18	Quan poden l'ordenació per comptatge i per radix trigar temps lineal?	El comptatge costa O(n+k) per a n claus en un rang de k valors. Radix amb d passades estables per dígits i base b costa O(d(n+b)). Només són lineals quan els paràmetres ho permeten; aprofiten l'estructura de les claus més enllà de les comparacions.
19	Què és una lectura bruta i quin és el primer nivell estàndard que la impedeix?	Llegir dades no confirmades d'una altra transacció, tant si després es desfà com si no. READ COMMITTED i els nivells estàndard superiors prohibeixen les lectures brutes.
20	Què vol dir que un algorisme d'ordenació sigui estable?	Els elements amb claus iguals conserven l'ordre relatiu original. La fusió pot ser estable si en els empats es pren primer l'element de l'esquerra; el quicksort habitual in situ sol ser inestable. Depèn de la implementació.
21	Per què quicksort pot trigar Θ(n²) i com hi ajuda l'aleatorització?	Les particions repetidament desequilibrades, com triar sempre la clau més petita entre claus diferents, causen treball quadràtic. Amb claus diferents o un tractament adequat dels duplicats, els pivots aleatoris donen temps esperat O(n log n). La mediana de tres és una heurística útil, no una garantia per al pitjor cas.
22	Com funciona l'ordenació per fusió estàndard per a vectors i quins costos té?	Ordena recursivament dues meitats i les fusiona en temps lineal. La versió estàndard triga Θ(n log n) i necessita O(n) d'espai auxiliar, amb comparacions de temps constant.
23	Què requereix la cerca binària i quan triga O(log n)?	Redueix a la meitat l'interval de cerca en dades ordenades segons el criteri de comparació. En un vector amb accés per índex O(1) i comparacions de temps constant, cercar entre n elements costa O(log n).
24	Per què els arbres B+ són útils per a índexs i consultes per rang?	L'alt factor de ramificació manté poca alçada i redueix accessos a pàgines. Les claus ordenades i les fulles enllaçades permeten recórrer rangs. Els índexs hash s'orienten a la igualtat i no ofereixen intrínsecament el mateix accés ordenat per rangs.
25	Què és una lectura no repetible i quin nivell estàndard la impedeix?	En rellegir una fila, les dades han canviat o la fila ha desaparegut després que una altra transacció confirmi una actualització o eliminació. REPEATABLE READ i SERIALIZABLE impedeixen aquesta anomalia.
26	Com pot DFS detectar un cicle en un graf dirigit?	DFS aprofundeix mitjançant recursió o una pila explícita. Una aresta cap a un vèrtex encara actiu en el camí actual és una aresta de retorn i demostra un cicle dirigit; no n'hi ha prou que el vèrtex ja hagi estat visitat.
27	Com tracta Bellman–Ford les arestes negatives i detecta un cicle negatiu accessible?	Relaxa totes les arestes fins a V−1 vegades. Una millora addicional des d'un vèrtex accessible revela un cicle negatiu accessible des de l'origen. El pitjor cas costa O(VE); els vèrtexs accessibles des d'aquest cicle no tenen cost mínim finit.
28	Quines són les dues fases del bloqueig en dues fases (2PL)?	Creixement: adquirir bloquejos sense alliberar-ne. Decreixement: alliberar-ne sense adquirir-ne de nous. Amb bloquejos adequats per a lectures i escriptures en conflicte, 2PL garanteix planificacions serialitzables per conflictes, però hi pot haver interbloquejos.
29	Com es comparen una matriu d'adjacència i unes llistes d'adjacència ordinàries?	Amb V vèrtexs i E arestes, la matriu ocupa O(V²) i comprova una aresta en O(1). Les llistes ocupen O(V+E); cercar (u,v) en una llista no ordenada costa O(deg(u)), on deg(u) és la longitud d'aquella llista.
30	Què exigeixen la primera, segona i tercera formes normals?	1FN: valors atòmics. 2FN: 1FN i cap atribut no primer depèn d'una part pròpia de cap clau candidata. 3FN: 1FN i, en tota dependència no trivial X→A, X és superclau o A és primer. Un atribut primer pertany a alguna clau candidata.
31	Quins són el temps en el pitjor cas i l'espai addicional de heapsort in situ?	Construir el monticle costa O(n) i les extraccions sumen O(n log n). Amb descens iteratiu dins del vector d'entrada, heapsort triga O(n log n) en el pitjor cas i usa O(1) d'espai addicional.
32	Com construeixen Kruskal i Prim un arbre d'expansió mínim?	En un graf connex, no dirigit i ponderat, Kruskal considera les arestes per pes creixent i usa Union–Find per rebutjar cicles. Prim amplia un sol arbre triant una aresta de pes mínim que connecti l'arbre amb un vèrtex exterior.