Algorithmes, graphes, programmation dynamique et bases de données relationnelles
32 cartes de révision universitaire sur les tris, les algorithmes de graphes, la programmation dynamique, SQL, les index et les transactions. Prérequis : bases de programmation, structures de données et SQL.
- Category
- Computer Science
- Level
- basic
- Languages
- fr → fr
- Cards
- 32
- Markdown
- Algorithmes, graphes, programmation dynamique et bases de données relationnelles (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | Qu'est-ce qu'une lecture fantôme et comment l'éviter ? | Répéter une requête avec le même prédicat donne un ensemble différent de lignes après des changements validés par une autre transaction. SERIALIZABLE l'empêche dans le modèle standard ; certaines implémentations, dont REPEATABLE READ de PostgreSQL, le font aussi à un niveau inférieur. | ||
| 2 | Pourquoi les arbres B+ conviennent-ils aux index et aux requêtes par intervalle ? | Leur forte arité limite la hauteur et les accès aux pages. Les clés ordonnées et les feuilles chaînées permettent de parcourir un intervalle. Les index de hachage visent les recherches par égalité et n'offrent pas intrinsèquement ce même accès ordonné. | ||
| 3 | Comment fonctionne le tri fusion standard sur tableau et quels sont ses coûts ? | Il trie récursivement deux moitiés puis les fusionne en temps linéaire. La version standard prend Θ(n log n) en temps et O(n) en mémoire auxiliaire, avec des comparaisons de durée constante. | ||
| 4 | Quelle différence entre WHERE et HAVING dans une requête groupée ? | WHERE filtre les lignes avant le regroupement. HAVING filtre les groupes produits et peut employer des conditions sur les agrégats, comme COUNT(*)>1. | ||
| 5 | Quelle récurrence calcule la longueur de la plus longue sous-séquence commune (LCS) ? | L[i,j] est la longueur pour les préfixes de longueurs i,j. L[0,j]=L[i,0]=0. Si les derniers caractères concordent, L[i,j]=1+L[i−1,j−1] ; sinon L[i,j]=max(L[i−1,j],L[i,j−1]). Le tableau complet utilise O(mn) en temps et en mémoire. | ||
| 6 | Quelle différence entre mémoïsation et programmation dynamique ascendante ? | La mémoïsation évalue les sous-problèmes à la demande, souvent récursivement, et conserve les résultats. La méthode ascendante évalue les états dans un ordre où leurs dépendances sont déjà disponibles, souvent en remplissant un tableau. | ||
| 7 | Comment le parcours en largeur trouve-t-il les plus courts chemins d'un graphe non pondéré ? | BFS utilise une file FIFO et explore par distance en nombre d'arêtes. Marquer un sommet lors de son ajout à la file évite les visites répétées. Le premier chemin découvert vers un sommet accessible comporte le minimum d'arêtes. | ||
| 8 | Qu'est-ce qu'une lecture sale et quel premier niveau standard l'interdit ? | Lire les données non validées d'une autre transaction, qu'elle soit ensuite annulée ou non. READ COMMITTED et les niveaux standard supérieurs interdisent les lectures sales. | ||
| 9 | Quand le tri par comptage ou par base peut-il être linéaire ? | Le comptage coûte O(n+k) pour n clés dans un domaine de k valeurs. Le tri par base avec d passes stables sur les chiffres en base b coûte O(d(n+b)). Ils sont linéaires seulement si ces paramètres le permettent et exploitent la structure des clés au-delà des comparaisons. | ||
| 10 | Comment Kruskal et Prim construisent-ils un arbre couvrant minimal ? | Dans un graphe connexe, non orienté et pondéré, Kruskal examine les arêtes par poids croissant et utilise Union–Find pour éviter les cycles. Prim agrandit un arbre en choisissant une arête de poids minimal reliant l'arbre à un sommet extérieur. | ||
| 11 | Comment WAL assure-t-il la durabilité de PostgreSQL avec la validation synchrone normale ? | Les enregistrements nécessaires atteignent le stockage durable avant l'accusé de validation et avant l'écriture des pages modifiées. Après une panne, WAL rejoue les changements absents des pages. La validation asynchrone peut perdre des transactions récentes déjà acquittées. | ||
| 12 | Pourquoi le tri rapide peut-il coûter Θ(n²) et que permet la randomisation ? | Des partitions très déséquilibrées répétées, par exemple en choisissant toujours la plus petite clé parmi des clés distinctes, entraînent un coût quadratique. Avec des clés distinctes ou une gestion adaptée des doublons, des pivots aléatoires donnent un temps espéré O(n log n). La médiane de trois est une heuristique, pas une garantie dans le pire cas. | ||
| 13 | Que signifie la stabilité d'un algorithme de tri ? | Les éléments de même clé conservent leur ordre relatif initial. Le tri fusion peut être stable en choisissant l'élément de gauche en cas d'égalité ; le tri rapide usuel en place est généralement instable. Cela dépend de l'implémentation. | ||
| 14 | Que demandent les première, deuxième et troisième formes normales ? | 1FN : valeurs atomiques. 2FN : 1FN et aucun attribut non premier ne dépend d'une partie propre d'une clé candidate. 3FN : 1FN et, pour toute dépendance non triviale X→A, X est une superclé ou A est premier. Un attribut premier appartient à une clé candidate. | ||
| 15 | Quand Dijkstra est-il valide et quel est son coût usuel avec un tas ? | Avec des poids non négatifs, il fixe successivement le sommet de plus petite distance provisoire. Avec listes d'adjacence et tas binaire minimum, le coût est O((V+E) log V). Un arc négatif peut invalider l'argument de distance définitive. | ||
| 16 | Comment le parcours en profondeur détecte-t-il un cycle dans un graphe orienté ? | DFS explore en profondeur par récursion ou pile explicite. Un arc vers un sommet encore actif sur le chemin courant est un arc de retour et prouve un cycle orienté ; viser un sommet déjà visité ne suffit pas. | ||
| 17 | Quelles sont les deux phases du verrouillage à deux phases (2PL) ? | Croissance : acquérir des verrous sans en libérer. Décroissance : en libérer sans en acquérir de nouveaux. Avec des verrous adaptés aux lectures et écritures conflictuelles, 2PL garantit des ordonnancements sérialisables par conflits, mais des interblocages restent possibles. | ||
| 18 | Quel est un ordre logique simplifié d'une requête SQL SELECT ? | Sans CTE, fonctions de fenêtre ni opérations ensemblistes : FROM/JOIN → WHERE → GROUP BY et agrégats → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Il s'agit d'un modèle logique, pas nécessairement de l'ordre physique choisi par l'optimiseur. | ||
| 19 | Que nécessite la recherche dichotomique et quand coûte-t-elle O(log n) ? | Elle divise par deux l'intervalle de recherche dans des données triées selon l'ordre de comparaison. Dans un tableau avec accès indexé en O(1) et comparaisons de durée constante, rechercher parmi n éléments coûte O(log n). | ||
| 20 | Comment Bellman–Ford traite-t-il les poids négatifs et détecte-t-il un cycle négatif accessible ? | Il relâche tous les arcs jusqu'à V−1 fois. Une amélioration supplémentaire depuis un sommet accessible révèle un cycle négatif accessible depuis la source. Le pire cas est O(VE) ; les sommets accessibles depuis ce cycle n'ont pas de coût minimal fini. | ||
| 21 | Qu'est-ce qu'un ordre topologique et comment l'algorithme de Kahn le calcule-t-il ? | Dans un DAG, tout arc u→v place u avant v. On extrait successivement un sommet de degré entrant nul, supprime ses arcs sortants et ajoute à la file les nouveaux sommets de degré nul. Si moins de V sommets sortent, le graphe contient un cycle. | ||
| 22 | Quelle différence entre clé primaire et clé étrangère dans PostgreSQL ? | La clé primaire identifie les lignes par des valeurs uniques et non NULL. La clé étrangère exige une correspondance avec la clé référencée, selon ses règles pour NULL. Elle peut référencer une clé UNIQUE admissible ou primaire de la même table ou d'une autre. | ||
| 23 | Quelle différence entre un algorithme glouton et la programmation dynamique ? | Le glouton s'engage sur un choix local et exige une preuve que ces choix préservent un optimum. La programmation dynamique compare des possibilités par récurrence et réutilise les résultats. Un optimum global exige un modèle et une récurrence corrects, pas seulement cette étiquette. | ||
| 24 | Quelle est la récurrence standard du sac à dos 0/1 de capacité entière W ? | D[i,w] est la meilleure valeur avec les i premiers objets, une capacité w et des poids entiers positifs wᵢ. D[0,w]=0. Si wᵢ>w, recopier D[i−1,w] ; sinon prendre max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Le temps O(NW) est pseudo-polynomial. | ||
| 25 | Qu'est-ce qu'une lecture non répétable et quel niveau standard l'interdit ? | Relire une ligne donne des données modifiées, ou la ligne a disparu, après validation d'une modification ou suppression concurrente. REPEATABLE READ et SERIALIZABLE interdisent cette anomalie. | ||
| 26 | Quelle différence entre INNER JOIN et LEFT JOIN ? | INNER JOIN renvoie les combinaisons de lignes satisfaisant la condition de jointure. LEFT JOIN garde aussi chaque ligne gauche sans correspondance, avec NULL dans les colonnes droites. Plusieurs correspondances peuvent produire plusieurs lignes par ligne gauche. | ||
| 27 | Quels sont les coûts temporel au pire et spatial supplémentaire du tri par tas en place ? | Construire le tas coûte O(n), puis les extractions coûtent au total O(n log n). Avec une descente itérative dans le tableau initial, le tri par tas coûte O(n log n) au pire et O(1) de mémoire supplémentaire. | ||
| 28 | Quelle différence entre index cluster et non cluster en stockage par lignes dans SQL Server ? | L'index cluster stocke les lignes dans l'ordre des clés : une table en possède au plus un. Un index non cluster possède ses clés et localisateurs de lignes, avec éventuellement d'autres colonnes incluses. Les termes et détails varient selon le système. | ||
| 29 | Comment fonctionne le tri par insertion et quel est son coût sur des données presque triées ? | Il insère chaque élément dans un préfixe trié. La version usuelle par décalages ou échanges adjacents coûte Θ(n+I), où I est le nombre d'inversions. Elle est linéaire si I=O(n) ; une petite entrée ne change pas le pire cas Θ(n²). | ||
| 30 | Comment comparer matrice d'adjacence et listes d'adjacence ordinaires ? | Pour V sommets et E arêtes, la matrice occupe O(V²) et teste une arête en O(1). Les listes occupent O(V+E) ; chercher (u,v) dans une liste non triée coûte O(deg(u)), où deg(u) est la longueur de cette liste. | ||
| 31 | Pourquoi la programmation dynamique est-elle utile dans beaucoup de problèmes d'optimisation ? | La sous-structure optimale permet d'exprimer un optimum à partir d'optima de sous-problèmes. S'ils se recoupent, mémoriser leurs réponses évite de répéter le travail. Les états et la récurrence doivent représenter correctement le problème initial. | ||
| 32 | Que signifient les propriétés ACID d'une transaction ? | Atomicité : effets complets ou aucun. Cohérence : les transactions correctes préservent contraintes et invariants applicatifs. Isolation : la concurrence respecte le niveau choisi. Durabilité : les effets validés survivent aux pannes couvertes par les garanties configurées. |