— Durée : 1h30 heures — Note totale / maximale : 20 points — Des points bonus peuvent être cachés ! — Les réponses doivent être argumentées — Prenez uniquement un stylo
Pour la rédaction des codes, ils peuvent être rédigées dans des languages de même paradigme au C telque python, C++ ou Java. (attention aux coûts caché, particulièrement par la JVM).
Définissez les notations O, Ω, et Θ, et appliquez-les à l’algorithme suivant en C. Expliquez pourquoi les constantes sont ignorées dans ces notations.
int sum_array(int *array, int size) {
int sum = 0;
for (int i = 0; i < size; i++)
sum += array[i] * 2; // Multiplication par 2
return sum;
}Définitions :
- O (Big O) : Limite supérieure, pire cas (e.g., O(n) = jamais plus que n).
- Ω (Big Omega) : Limite inférieure, meilleur cas (e.g., Ω(1) = au moins constant).
- Θ (Theta) : Limite exacte quand O = Ω (e.g., Θ(n) = exactement linéaire).
Application :
- O(n) : Dans le pire cas, parcourt tous les éléments une fois.
- Ω(n) : Même dans le meilleur cas, parcourt tout (pas de sortie anticipée).
- Θ(n) : Complexité exacte est linéaire, car toujours n itérations.
Constantes : La multiplication par 2 est ignorée car, pour de grandes valeurs de n, elle devient négligeable face à la croissance linéaire.
Expliquez pourquoi ignorer les constantes dans les notations asymptotiques peut être problématique dans un contexte réel.
Les constantes sont ignorées car elles deviennent suposément négligeables pour de grandes données, mais dans la pluspart des cas les tailles sont petites (e.g., 100 plantes). Une constante élevée (e.g., accès mémoire coûteux) peut dominer le temps réel. Exemple : O(log(n)) avec 100 accès RAM vs O(n) avec 10 calculs simples : le premier peut être plus lent.
Les notations asymptotiques se concentrent sur n → ∞, mais on travail souvent avec de petites tailles e.g., 100-1000 plantes. Les constantes (cycles par opération, latence mémoire) impactent directement les performances. Un accès RAM (50-100 cycles) peut surpasser le cout d'une opération "optimisée" (3-5 cycles LOAD/ADD/STORE).
Exemple :
- O(n) : 100 additions (~300 cycles)
- O(log n) : log₂(100) ≈ 7 lectures (~700 cycles)
Réalité : O(log n) perd face O(n).
Écrivez une fonction en C pour insérer un nœud au début d’une liste chaînée simple (push_front). Quelle est sa complexité temporelle et spatiale ?
typedef struct IntNode {
int data;
struct IntNode* next;
} IntNode;
void push_front(IntNode** head, int value) {
IntNode* new_node = malloc(sizeof(IntNode));
new_node->data = value;
new_node->next = *head;
*head = new_node;
}- Temporelle : O(1), insertion en tête immédiate.
- Spatiale : O(1), un seul nœud alloué.
typedef struct IntNode {
int data;
struct IntNode* next;
} IntNode;
void push_front(IntNode** head, int value) {
IntNode* new_node = malloc(sizeof(IntNode));
if (new_node) {
new_node->data = value;
new_node->next = *head;
*head = new_node;
}
}- Temporelle : Θ(1), 3 affectations (data, next, head = 3 cycle) + malloc (amortie O(1) ~ 300 cycles).
- Spatiale : Θ(1), 16 octets (4 pour data, 8 pour next, aligné sur 8).
Expliquez la différence entre une liste chaînée circulaire et un circular buffer. Dans une situation ou l'espace mémoire est limité, quelle structure utiliserier vous ?
- Liste Circulaire : Nœuds liés (non contigus), next du dernier pointe au premier.
- Circular Buffer : Tableau contigue, indices modulo taille pour boucler.
- Un Circular Buffer semble plus adapté dans le cas d'une mémoire limité.
- Liste Circulaire : Structure chaînée, mémoire dynamique, chaque nœud a un next et prev (si double), dernier next = premier nœud. Complexité temporel O(1) pour insertion (head/tail), O(n) pour accès. Complexité spatial en
O(3n)doncO(n). - Inconvénient : plein de petite allocation, disparate. Probleme de cache-miss.
- Circular Buffer : Tableau statique ou dynamique, mémoire contiguë, utilise un curseur (head/tail) avec modulo (e.g., head % size). O(1) pour insertion et accès.
- Avantage : accès rapide (cache-friendly), idéal pour un pipeline de traitement où capture écrit et segment lit en continu, particulièrement quand la taille est connue.
Même si les deux structures montre une complexité spatial identique O(n), en réalité la Liste Circulaire prend 3x plus de place en mémoire. De plus, les soucis de cache-miss inhérent a une structure non contigüe donne des temps d'access mémoire plus long.
Liste chaine :
- Accès imprévisible à la mémoire : Les nœuds sont dispersés dans la mémoire.
- Manque de localité : Pas d'accès aux emplacements de mémoire direct [index].
- Augmentation du temps d'accès à la mémoire : Les échecs de mise en cache entraînent un ralentissement des performances en raison de l'attente des données de la mémoire principale.
- Chargement inefficace des blocs de mémoire : Un seul nœud par bloc de cache est utilisé
- Impact : Ralentissement de la traversée, recherche très lente.
Définissez ce qu’est un arbre binaire de recherche et expliquez une application pratique dans un système informatique. Pourquoi le problème de balancement peut-il affecter les performances ?
Un arbre binaire est une structure où chaque nœud a au maximum deux enfants (gauche et droit), organisée hiérarchiquement. On associe également une propriété d'ordonencement à chaque noeud. Telque, par exemple left < x < right ce qui permet de retrouver une donnée plus rapidement.
Gestion d’un annuaire téléphonique : les noms (ou numéros) sont stockés dans un BST, permettant une recherche rapide par ordre alphabétique ou numérique.
Un arbre déséquilibré (e.g., une liste linéaire où chaque nœud n’a qu’un enfant droit) augmente la profondeur, rendant la recherche plus lente. Dans le pire cas, la complexité passe de O(log n) (hauteur logarithmique) à O(n) (hauteur linéaire), car il faut parcourir tous les nœuds.
Un arbre binaire de recherche (BST) est une structure de données hiérarchique où chaque nœud a au plus deux enfants (left, right), avec une contrainte d’ordre : pour tout nœud avec une clé x, toutes les clés du sous-arbre gauche satisfont k < x, et celles du sous-arbre droit satisfont k > x, avec unicité des clés. Cette propriété permet une recherche dichotomique efficace en divisant l’espace de recherche à chaque niveau.
Implémentation d’un index de base de données : un BST stocke des clés (e.g., ID d’utilisateur) pour un accès rapide aux enregistrements. Par exemple, dans un système de gestion de fichiers, les métadonnées (taille, date) sont organisées dans un BST, permettant des requêtes ordonnées (e.g., "trouver tous les fichiers > 1 Mo") en O(log n) si équilibré.
Le problème de balancement survient lorsque les insertions ou suppressions déséquilibrent l’arbre, augmentant sa hauteur. Un BST équilibré a une hauteur de ⌈log₂(n+1)⌉, offrant O(log n) pour recherche, insertion, et suppression. Un arbre dégénéré (e.g., insertions dans l’ordre croissant : 1→2→3→...) devient une liste chaînée de hauteur n, dégradant la complexité à O(n).
Un arbre AVL est une variante du BST qui résout le problème de balancement en maintenant un équilibre strict : pour chaque nœud, la différence de hauteur entre les sous-arbres gauche et droit (facteur d’équilibre) est dans {-1, 0, 1}. Cet équilibre est assuré par des rotations (simple ou double) lors des insertions et suppressions. Par exemple, si une insertion de 1 dans un arbre {3, 2} déséquilibre le sous-arbre gauche (hauteur gauche = 2, droite = 0), une rotation droite sur 3 rebalance l’arbre en {2, 1, 3}. La hauteur maximale d’un AVL est bornée par 1.44·log₂(n+2) - 0.328, garantissant O(log n) pour toutes les opérations, même dans le pire cas.
Analysez la complexité temporelle et spatiale de la fonction suivante en pseudo-C, qui recherche et trie simultanément des paires dans un tableau non trié. Fournissez les notations asymptotiques O, Ω, et Θ pour le pire et le meilleur cas, et justifiez vos réponses. Pour la réponse idéale, utilisez un raisonnement basé sur la sémantique axiomatique pour prouver formellement la complexité temporelle exacte dans le pire cas, donc sans utilisé O() puis simplifier pour déterminé O().
typedef struct {
int key;
int value;
} Pair;
void search_and_sort(Pair* T, int n, int target) {
int i, j, count = 0;
Pair temp[n]; // Tableau temporaire pour stocker les paires trouvées
// Étape 1 : Recherche des paires avec key == target
for (i = 0; i < n; i++) {
if (T[i].key == target) {
temp[count] = T[i];
count++;
}
}
// Étape 2 : Tri à bulles sur les paires trouvées (par value)
for (i = 0; i < count; i++) {
for (j = 0; j < count - 1 - i; j++) {
if (temp[j].value > temp[j + 1].value) {
Pair swap = temp[j];
temp[j] = temp[j + 1];
temp[j + 1] = swap;
}
}
}
// Étape 3 : Réinjection dans T (remplace les éléments originaux)
for (i = 0; i < count; i++)
T[i] = temp[i];
}Analyse Temporelle :
- Étape 1 : Recherche
- Boucle sur n éléments, une comparaison par élément.
- Pire cas (tous égaux à target) : n comparaisons, n affectations → O(n).
- Meilleur cas (aucun égal) : n comparaisons, 0 affectations → O(n).
- Étape 2 : Tri à bulles
- Tri sur count éléments, où 0 ≤ count ≤ n.
- Pire cas (count = n) : n·(n-1)/2 comparaisons et swaps → O(n²).
- Meilleur cas (count = 0 ou 1) : 0 ou 1 comparaison → O(1).
- Étape 3 : Réinjection
- Boucle sur count éléments → O(count) ⊆ O(n).
- Total :
- Pire cas : O(n) + O(n²) + O(n) = O(n²).
- Meilleur cas : O(n) + O(1) + O(1) = O(n).
Analyse Spatiale :
- Tableau temporaire temp[n] : O(n) espace supplémentaire.
- Variables locales (i, j, count) : O(1).
- Total : O(n) dans tous les cas.
Justification : La dominante est le tri à bulles (O(n²)) quand count est grand.
Analyse Temporelle :
- Étape 1 : Recherche
- n itérations, 1 comparaison et jusqu’à 1 affectation par itération.
- Pire cas (count = n) : n comparaisons, n affectations → Θ(n).
- Meilleur cas (count = 0) : n comparaisons, 0 affectations → Θ(n).
- Comparaison (CMP) : ~2 cycles.
- Accès mémoire (lecture T[i].key) : ~1 cycle (cache hit L1), ~50 cycles (cache miss).
- Affectation (temp[count] = T[i]) : 2~3 cycles (store STR).
- Incrémentation (count++) : ~1 cycle (ADD).
- Total par itération : ~7 cycles (hit) à ~56 cycles (miss).
- Pire cas : n·56 ≈ 56n cycles (tous miss), typique : ~7n cycles (hits fréquents).
- Étape 2 : Tri à bulles
- count·(count-1)/2 comparaisons et jusqu’à autant de swaps.
- Pire cas (count = n) : n·(n-1)/2 → Θ(n²).
- Meilleur cas (count ≤ 1) : 0 ou 1 swap → Θ(1).
- Comparaison (CMP) : ~2 cycles.
- Accès mémoire (temp[j].value) : ~1 cycle (hit), ~50 cycles (miss).
- Swap (3 affectations) : ~9 cycles (3·STR, hit), ~150 cycles (miss).
- Boucle interne : ~12 cycles/comparaison (hit) à ~202 cycles (miss avec swap).
- Total pire cas : n(n-1)/2·202 ≈ 101n² cycles (miss), typique : ~6n² cycles (hits).
- Étape 3 : Réinjection
- count affectations → Θ(count) ⊆ Θ(n).
- Affectation (T[i] = temp[i]) : ~3 cycles (hit), ~50 cycles (miss).
- Total pire cas : n·50 ≈ 50n cycles (miss), typique : ~3n cycles (hits). Total :
- Pire cas : Θ(n) + Θ(n²) + Θ(n) = Θ(n²).
- Cycles : ~7n + 6n² + 3n ≈ 6n² + 10n cycles (hits), ~56n + 101n² + 50n ≈ 101n² + 106n cycles (miss).
- Meilleur cas : Θ(n) + Θ(1) + Θ(1) = Θ(n).
- Cycles : ~7n + 0 + 0 ≈ 7n cycles (hits), ~56n cycles (miss).
Analyse Spatiale :
- temp[n] : n·sizeof(Pair) = 8n octets (2 int sur 64-bit) → Θ(n).
- Variables locales (i, j, count, swap) :
3*32 + sizeof(Pair)octets → Θ(1). - Total : Θ(n) dans tous les cas.
Calculez la complexité spatiale et temporelle dans le pire cas de la fonction suivante :
int fib(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
else return fib(n - 1) + fib(n - 2);
}- Temporelle : O(2^n), car chaque appel génère deux sous-appels, formant un arbre binaire de hauteur n.
- Spatiale : O(n), profondeur maximale de la pile récursive (n stack frame).
- Pire cas : n grand (e.g., n = 40 → millions d’appels).
La fonction termine pour n ≥ 0, car chaque appel réduit n jusqu’à atteindre 1 ou 0 (conditions d’arrêt).
-
Preuve par récurrence :
- Base : fib(0) = 0, fib(1) = 1, terminent.
- Hypothèse : fib(k) et fib(k-1) terminent pour k ≥ 1.
- Étape : fib(k+1) = fib(k) + fib(k-1), les deux terminent → fib(k+1) termine.
- (alert) Pour n < 0, fib(n) = fib(n-1) + fib(n-2) appelle des valeurs toujours plus négatives sans borne → récursion infinie → non-terminaison. (stack overflow)
-
Cette fonction calcule le nombre de fibannacie, il existe donc un lien avec la formule de Binet : F_n ≈ (φ^n - (-φ)^(-n))/√5, où φ = (1 + √5)/2, mais la récursion suit la définition directe.
-
Complexité Temporelle
- Pire cas (n ≥ 0) : Θ(φ^n), où φ ≈ 1.618 (nombre d’or). Nombre d’appels = F_(n+2) - 1 ≈ φ^n/√5.
- Meilleur cas : Θ(1), n ≤ 1 → 1 comparaison (~2 cycles).
- Donc O(φ^n), Ω(1).
-
Complexité Spatiale
- Pire cas : Θ(n), profondeur de récursion = n (chemin jusqu’à fib(0)).
- Stack frame : ~16 octets (retour, n) → ~16n octets sur 64-bit.
Pour garantir la terminaison pour tout n :
int fib(int n) {
if (n <= 1) return n;
else return fib(n - 1) + fib(n - 2);
}Condition n <= 1 stoppe la récursion pour n négatif, rendant la fonction "totale".
Correction avec Boucle (Optimisation Spatiale) :
La récursion consomme O(n) en stack size et O(φ^n) en temps.
Une version itérative réduit l’espace à O(1) et le temps à O(n) :
int fib_iter(int n) {
if (n < 0) return 0;
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}- Complexité Temporelle : Θ(n), n-1 itérations, ~5 cycles/itération (addition ~1, affectations ~3, incrémentation ~1) → ~5n cycles.
- Complexité Spatiale : Θ(1), variables locales (a, b, temp, i)
4*32octets, pas de pile récursive.
On considère un tableau d’entiers T de taille n, où les éléments sont organisés selon une structure hiérarchique implicite. Pour tout indice i (en commençant à 0), une propriété mathématique garantit que les relations entre les éléments permettent de définir un arbre binaire. Par exemple T = {100, 75, 200, 20, 80, 180, 250} est en faite la représentation suivante :
100 (0)
/ \
75 200 (1, 2)
/ \ / \
20 80 180 250 (3, 4, 5, 6)
- Si un élément est à l’indice i, ses descendants (s’ils existent) sont accessibles à des positions calculées par une formule simple impliquant des multiplications et additions sur i.
- Déduisez la structure implicite et la propriété mathématique qui organise les éléments dans T suivant une hiérachie.
- Implémentez en C une fonction de recherche dichotomique pour trouver une valeur cible dans cet espace, en supposant que T est trié selon cette propriété.
- Calculez la complexité temporelle et spatiale de votre fonction dans le pire cas.
La structure est un arbre binaire représenté dans un tableau où, pour un nœud à l’indice i :
- Fils gauche : 2i + 1
- Fils droit : 2i + 2
- Propriété : Les éléments sont organisés comme un tas binaire (heap), où T[i] ≤ T[2i+1] et T[i] ≤ T[2i+2] (tas min), ou comme un arbre binaire de recherche implicite trié par niveaux.
int binary_search_heap_recursive(int* T, int n, int target, int index) {
// Si l’indice dépasse la taille, échec
if (index >= n) return -1;
// Si la valeur est trouvée, retourne l’indice
if (T[index] == target) return index;
// Si la valeur actuelle est plus grande que la cible, arrêt
if (T[index] > target) return -1;
// Recherche récursive dans le fils gauche
int left = binary_search_heap_recursive(T, n, target, 2 * index + 1);
if (left != -1) return left;
// Si non trouvé à gauche, recherche dans le fils droit
return binary_search_heap_recursive(T, n, target, 2 * index + 2);
}
// Fonction principale pour lancer la recherche
int search_heap(int* T, int n, int target) {
return binary_search_heap_recursive(T, n, target, 0);
}- Temporelle : O(log_2 n), dans le pire cas, profondeur de recherche égale à la hauteur du tas.
- Spatiale : O(log_2 n), profondeur de récursion égale à la hauteur du tas (pile d’appels).
- Pire cas : target absent, parcours complet.
La structure est un arbre binaire représenté dans un tableau où, pour un nœud à l’indice i :
- Fils gauche : 2i + 1
- Fils droit : 2i + 2
- Propriété : Les éléments sont organisés comme un tas binaire (heap), où
T[i] ≤ T[2i+1] et T[i] ≤ T[2i+2](tas min), ou comme un arbre binaire de recherche implicite trié par niveaux.
int search_heap_array(int* T, int n, int target) {
int current = 0; // Commence à la racine
while (current < n) {
// Si la valeur actuelle est la cible, retourne son indice
if (T[current] == target) {
return current;
}
// Si la valeur actuelle est plus grande que la cible, arrêt (tas min)
if (T[current] > target) {
return -1;
}
// Calcul des indices des fils
int left_child = 2 * current + 1;
int right_child = 2 * current + 2;
// Si pas de fils gauche, arrêt
if (left_child >= n) {
return -1;
}
// Si le fils gauche est trop grand, vérifie le fils droit
if (T[left_child] > target) {
if (right_child < n && T[right_child] <= target) {
current = right_child; // Descend à droite
} else {
return -1; // Aucun fils viable
}
} else {
current = left_child; // Descend à gauche
}
}
return -1; // Non trouvé
}**Complexité temporelle : **
- Hauteur du tas = ⌊log₂(n)⌋, car arbre binaire complet a au plus log₂(n+1) niveaux.
- Chaque itération descend d’un niveau → Θ(log n) dans le pire cas (chemin racine → feuille).
- Pire cas : target absent ou au niveau le plus bas. O(log n), Ω(1).
Spatiale :
- Variables locales (current, left_child, right_child) : ~12 octets → Θ(1).
- Pas de récursion ni allocation → Θ(1).