# 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.

- **Canonical URL:** https://flashcards.world/flashcards/sets/d221cee3-7287-43cb-a9fc-d5ca09f109a1/
- **Markdown URL:** https://flashcards.world/flashcards/sets/d221cee3-7287-43cb-a9fc-d5ca09f109a1.md
- **Level:** basic
- **Languages:** ca → ca
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 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. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/d221cee3-7287-43cb-a9fc-d5ca09f109a1/).