exam-data-struct-17-06-2025.md

Exercice : Notions fondamentales (3 points)

1. Pour de très grandes valeurs de $n$, lequel est plus efficace ? Justifiez votre réponse en utilisant la notion de complexité asymptotique. (0,5 pt)

Réponse :
L'algorithme B, avec complexité $O(n \log n)$, est asymptotiquement plus efficace que A en $O(n^2)$.

Justification formelle :
Par définition, $f(n) = O(g(n))$ signifie qu'il existe des constantes $c > 0$ et $n_0 > 0$ telles que pour tout $n \geq n_0$, $0 \leq f(n) \leq c \cdot g(n)$. Pour comparer, considérons le rapport $\lim_{n \to \infty} \frac{n^2}{n \log n} = \lim_{n \to \infty} \frac{n}{\log n} = \infty$ (par règle de Bernoulli ou croissance polynomiale vs logarithmique). Ainsi, pour tout $c > 0$, il existe $n_0$ tel que pour $n > n_0$, $n^2 > c \cdot n \log n$, rendant A plus lent.

En pratique, pour $n = 10^6$, $n \log_2 n \approx 2 \times 10^7$ opérations vs $10^{12}$ pour $n^2$, une différence de 5 ordres de grandeur, inacceptable en informatique.

2. Donnez un exemple simple illustrant chacun des trois types de notations asymptotiques. (1 pt)

• $O$ (grand O – borne supérieure) :
  L'algorithme de tri rapide (QuickSort) a une complexité moyenne $O(n \log n)$, mais dans le pire cas (pivot mal choisi), il est en $O(n^2)$. Exemple : pour un tableau trié, il dégénère en $n(n-1)/2$ comparaisons, borné par $c n^2$ pour $c = 1/2$.

• $\Omega$ (grand Omega – borne inférieure) :
  Tout algorithme de tri par comparaison (e.g., MergeSort) est en $\Omega(n \log n)$ dans le pire cas, car l'arbre de décision a au moins $\log_2(n!) \approx n \log_2 n - n \log_2 e$ feuilles. Pseudo-code : pour trier $n$ éléments distincts, au moins ce nombre de comparaisons est requis.

• $\Theta$ (grand Thêta – borne serrée) :
  La recherche linéaire dans un tableau non trié est en $\Theta(n)$ dans le pire cas : exactement $n$ comparaisons si l'élément est absent ou en fin.

3. Pourquoi utilise-t-on plutôt la notation $O$ dans l’analyse des algorithmes, même si elle donne une majoration approximative ? Quel serait un inconvénient potentiel ? (0,5 pt)

On privilégie $O$ car car elle fournit une borne supérieure asymptotique sur la croissance du temps d’exécution. Elle est plus facile à prouver et suffit pour classer les algorithmes en hiérarchies (polynomiale, exponentielle). Dans la littérature (e.g., ACM, SIAM), $O$ domine pour sa simplicité dans les analyses amorties ou randomisées.

Inconvénients :

$O$ masque les constantes multiplicatives et additifs, menant à des choix suboptimal en pratique. Exemple : un algorithme en $O(n \log n)$ avec constante 100 (e.g., MergeSort récursif avec overhead de fusion) peut être plus lent qu'un $O(n^2)$ avec constante 2 (e.g., InsertionSort) pour $n < 10^3$. De plus, elle ignore les effets de bas niveau (cache hierarchy, branch prediction).

Des travaux sur les algorithmes cache-oblivious montrent que deux algorithmes ayant la même complexité asymptotique peuvent avoir des performances très différentes selon leur comportement mémoire. Pour mitiger, on utilise parfois des analyses paramétrées (e.g., roofline model en HPC, ...).

4. Expliquez brièvement ce qu’elle permet de faire, avec un exemple de contexte où elle est utile. (1 pt)

La sémantique axiomatique (ou logique de Hoare) est un cadre formel pour raisonner sur la correction des programmes via des triples de Hoare ${P} , S , {Q}$, où $P$ est une précondition, $S$ un statement, et $Q$ une postcondition. Elle permet de prouver formellement la correction partielle (si termine, alors correct) ou totale (termine et correct), en utilisant des axiomes et règles d'inférence (e.g., assignation, composition, boucle).

Exemple de contexte utile :
En vérification de logiciels critiques (e.g., DO-178C pour avionique, ou smart contracts Ethereum via Solidity + Why3), où une faute peut causer des pertes humaines/financières. Par exemple, prouver qu'un algorithme de tri préserve les éléments et produit un tableau trié.

Preuve formelle**
Considérons une boucle simple pour sommer un tableau :

int sum = 0; // {true}
for (int i = 0; i < n; i++) // invariant: sum = \sum_{j=0}^{i-1} a[j] \land 0 \leq i \leq n
    sum += a[i];
// {sum = \sum_{j=0}^{n-1} a[j]}

Preuve par induction sur l'invariant de boucle (règle WHILE) :

• Base : Avant boucle, i=0, sum=0 = somme vide.
• Hypothèse : Invariant vrai à i=k.
• Étape : Après sum += a[k], sum = somme jusqu'à k, i=k+1 → invariant préservé.
• Terminaison : Variant v = n - i > 0, diminue de 1 → termine.

Analyse plus stricte de la complexité via règles axiomatiques avec coûts :
On étend la logique de Hoare avec une fonction coût (e.g., WCET – Worst-Case Execution Time) assignée à chaque axiome, comme dans la sémantique axiomatique quantitative.

Exemple : Définit un coût c(S) pour chaque statement S.

• Axiome assignation : c(x := e) = 1 (coût unitaire).
• Composition : c(S1; S2) = c(S1) + c(S2).
• Boucle : c(while B do S) = 1 + max_{itérations} (c(B) + c(S) + 1) (test + corps + retest).

Pour la boucle somme ci-dessus :

• Si coût = cycles CPU (e.g., LOAD=5 cycles, ADD=1, STORE=3, CMP=2, JMP=1).
• Par itération : c(corps) ≈ 5 (load a[i]) + 1 (add) + 3 (store sum) + 2 (i<n) + 1 (jmp) ≈ 12 cycles.
• Total : n \times 12 + overhead ≈ 12n cycles (proche assembleur sur x86).

Choix de la fonction coût et approximations :

• Si coût unitaire par opération abstraite (e.g., additions/comparaisons), on retombe sur complexité asymptotique : $\Theta(n)$.
• Si coût réaliste (cycles, incluant cache-miss ≈200 cycles), on obtient une bound pratique : e.g., si 10% cache-miss, coût ≈ 12n + 0.1n \times 188 ≈ 30.8n cycles, plus précis pour embedded systems, systeme critiques, etc.
• Avantage : Lie correction et performance. Inconvénient : Sensible à l'architecture et aux options de compilations (optimisation codes).

Choix d’algorithmes (3 points)

1. Donnez la complexité asymptotique, en notation $O$, des deux algorithmes. (1 pt)

• Tri à bulles : $O(n^2)$ (pire/meilleur cas ; moyenne $\Theta(n^2)$).
• Tri par fusion récursif : $O(n \log n)$ (tous cas ; espace $O(n)$).

2. En tenant compte du contexte (tailles de listes entre 5 et 50 éléments), quel algorithme recommanderiez-vous ? Justifiez. (1 pt)

Recommandation : En théorie l'algo tri par fusion récursif est meilleur que le trie bulle dans tous les cas. D'un point de vue complexite temporelle. Bien que le cout spatial soit élevé. En pratique le trie bulle auras de meilleur performances pour $n$ petit car il a l'avantage de la localite du cache et ne pert pas de temps avec la getion de la pile.

Justification :
Pour petites n (5–50), les constantes dominent. Bubble Sort : ~n^2/4 comparaisons/swaps, mais implémentation simple (pas de récursion, O(1) espace extra). Merge Sort : overhead récursif (stack depth \log n ≈5–6, risque stack overflow en embarqué) + allocations temporaires (O(n) espace, fragmentation).

Empiriquement : Pour n<64, Insertion/Bubble outperform Merge/Quick en temps réel (meilleure localité, moins branch-mispredictions). En embarqué (e.g., Arduino/ESP32, RAM <1MB), éviter récursion/allocation, il existe evidement des alternatives plus interessant a bulle sort dans ce context. Tel que heap sort.

3. Expliquez pourquoi un algorithme de complexité temporelle théorique plus élevée peut être plus efficace en pratique. (1 pt)

Explication :
La complexité asymptotique assume n→∞ et coûts unitaires, ignorant constantes, overhead hardware, et distributions de données. Un O(n^2) avec faible constante (e.g., 0.25 n^2 opérations simples) peut surpasser O(n log n) avec haute constante (e.g., 10 n log n + allocations) pour n modéré. Facteurs pratiques : Cache effects, SIMD/vectorization, data locality.

Distance minimale sur une grille 1D (2 points)

1. Complexité temporelle de la fonction. (1 pt)

$O(n)$ (ou $\Theta(n)$ précisément : exactement n itérations, chacune $O(1)$).

2. Formule analytique en $O(1)$. (1 pt)

La distance minimale est $\min_{i=0}^{n-1} |x_0 - i s| = |x_0 - k s|$, où $k = \max(0, \min(n-1, \round(x_0 / s)) )$.

Preuve :
La grille est arithmétique, le plus proche est l'arrondi. Pour bornes : si x_0 < 0, k=0 ; si x_0 > (n-1)s, k=n-1 (projection sur intervalle). Complexité : O(1) ops flottantes. Robuste aux erreurs flottantes via floor(x_0/s + 0.5).

Arbres binaires de recherche (6 points)

Partie 1 : Compréhension et représentation (3 points)

1. Propriété mathématique d’un BST : Structure binaire où pour tout nœud x, le sous-arbre gauche satisfait $\forall y, y.key &lt; x.key$, droit $\forall y, y.key &gt; x.key$ (ordre total, unicité optionnelle).
2. BST parfaitement équilibré : Pour S = [2,4,6,8,10,11,13,15,18,22,24,26], racine médiane ≈13, gauche médiane 6-8, droit 22, etc. Hauteur 3-4 (AVL-like).
3. BST dégénéré : Insertion ordonnée : racine 2, droit 4, droit 6, ..., hauteur 11.
4. Hauteur h : Équilibré : $h = \lfloor \log_2 n \rfloor \approx 3$ (n=12, log2(13)≈3.7). Dégénéré : h = n-1 =11.
5. Complexité recherche pire cas : $O(h)$ (chemin racine-feuille). Équilibré : $O(\log n)$. Dégénéré : $O(n)$.
6. Méthode pour rééquilibrer : AVL trees avec rotations (e.g., LL/RR simple, LR/RL double). Impact : Maintient |balance| ≤1, h ≤ 1.44 log_2(n+2) -0.328 (Fibonacci bound), garantissant O(log n) worst-case.

Partie 2 : Programmation (3 points)

Fonction récursive :

#include <limits.h> // pour INT_MIN/MAX, mais char → CHAR_MIN/MAX

bool isBSTUtil(struct Node* node, char min, char max) {
    if (node == NULL) return true;
    if (node->data <= min || node->data >= max) return false;
    return isBSTUtil(node->left, min, node->data) &&
           isBSTUtil(node->right, node->data, max);
}

bool isBST(struct Node* root) {
    return isBSTUtil(root, CHAR_MIN, CHAR_MAX);
}

Optimisation (3 points)

Analyse complexité :
Boustrophédon = Cocktail Shaker Sort (bidirectional bubble).
Temps : Pire $O(n^2)$ (n passes, ~n-i par pass). Meilleur $O(n)$ si trié, mais sans flag → O(n^2) inutile.
Espace : O(1).

TODO : Code

FIFO et LIFO (3 points)

1. Acronymes :
LIFO : Last In First Out (pile). FIFO : First In First Out (file).

2. Associations :

• Récursifs : LIFO (call stack).
• Impression : FIFO (équité).
• Navigateur : LIFO (undo last).
• Embouteillage : FIFO (premier arrivé sort premier).

3. Complexités :

Avant de donner la complexité temporelle pour les différents cas, définissons le cadre d’analyse.

L’analyse amortie consiste à regarder le coût moyen d’une opération sur une longue suite d’opérations, plutôt que le coût d’une seule opération isolée. Dans un tableau dynamique, l’opération push est généralement (O(1)) car on ajoute simplement l’élément à la fin. Cependant, lorsque le tableau est plein, il faut allouer un nouveau tableau plus grand (souvent de taille doublée) et copier tous les éléments, ce qui coûte (O(n)). Ce cas est coûteux, mais il arrive rarement : après un redimensionnement, beaucoup d’insertions pourront se faire sans nouvelle copie. Si on considère une longue séquence de (n) insertions, le coût total des copies reste proportionnel à (n), donc le coût moyen par insertion est (O(1)). On dit alors que push est (O(1)) amorti. Le même raisonnement vaut pour enqueue si la file est implémentée avec un tableau dynamique. En pratique, les tableaux sont souvent rapides grâce à la mémoire contiguë (meilleure utilisation du cache), tandis que les listes chaînées ont un vrai (O(1)) théorique mais des accès mémoire moins efficaces.

Dans un système pratique (par exemple une gestion de paquets réseau), où les opérations push et pop se produisent à des vitesses comparables, on peut considérer que le coût effectif est $O(1)$ dans la majorité des cas. Si un pic temporaire de production de données survient, le buffer va momentanément s’agrandir pour absorber ce surplus. Si un autre pic similaire arrive plus tard, le buffer dispose déjà d’une capacité suffisante, ce qui évite un nouveau redimensionnement immédiat.

Ainsi, même si certaines opérations coûtent ponctuellement $O(n)$, leur fréquence reste faible, ce qui justifie la complexité $O(1)$ amortie.

A partir de cette definition on pourras considerer les complexites suivantes :

• Liste chaînée : Push/pop O(1), enqueue O(1) si tail ptr, dequeue O(1). (Pas de changement ici)
• Tableau dynamique : Push O(1) amorti, pop O(1) ; enqueue O(1) amorti, dequeue O(n) sans circular ou O(1) avec.
• En pratique, listes → cache-poor ; arrays → resize costly (amorti par doubling, expected O(1)).