Cette exam test votre analyse (nuancée) des algorithmes de tri, encourageant une réflexion sur les implications pratiques tout en restant accessible mais rigoureuse.
- Durée : 1 heure 30 min
- 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és dans des langages du même paradigme que C, tels que Python, C++ ou Java. (Attention aux coûts cachés).
- Expliquez le concept de complexité asymptotique
- Définissez les trois notations asymptomatiques
- Quels sont les vanatages et incovénients de ces notations ?
- A quoi correspond la sémantique axiomatique ?
- Qu'est ce que cela permet de faire de plus ou de moins ?
- Complexité Asymptotique :
- C’est une mesure de la performance d’un algorithme (temps ou espace) en fonction de la taille de l’entrée (n), en ignorant les constantes et les petits termes.
- Rôle : Comparer les algorithmes pour prédire leur comportement sur de grandes entrées.
- Définitions des Notations :
- O (grand O) : Borne supérieure, le pire cas possible (e.g., O(n²) signifie "pas pire que n²").
- Ω (grand Oméga) : Borne inférieure, le meilleur cas ou minimum garanti (e.g., Ω(n) signifie "au moins n").
- Θ (thêta) : Borne exacte, quand le pire et le meilleur cas sont équivalents (e.g., Θ(n) signifie "exactement n").
- Avantages et Limites :
- Avantages : Simple à utiliser, permet de comparer les algorithmes indépendamment des machines, focus sur la scalabilité.
- Limites : Ignore les constantes et les performances réelles pour petites tailles, peut masquer des différences pratiques (e.g., O(n) vs O(n) lent).
- Sémantique Axiomatique :
- C’est une méthode pour prouver formellement le comportement d’un programme en utilisant des assertions logiques (préconditions, postconditions).
- Exemple : Dire "si n > 0, alors la boucle termine" et le prouver.
- Complémentarité/Différence :
- Elle permet de vérifier ce que fait éxactement un algorithme, le npmbre d'opération réel, pas seulement sa complexité.
- C'est utilisé pour prouvez formellement des temps d'éxécutions, ce qui est demandé pour la certification des systeme temps réel critique.
- Complexité Asymptotique :
- La complexité asymptotique analyse la croissance du temps ou de l’espace requis par un algorithme lorsque la taille de l’entrée n tend vers l’infini.
- Elle utilise des fonctions limites pour décrire le comportement dominant (e.g., n² domine n).
- Fournit une abstraction pour évaluer l’efficacité relative des algorithmes, indépendamment des détails d’implémentation ou du matériel (e.g., processeur, cache).
- Définitions des Notations :
- O(f(n)) : Ensemble des fonctions g(n) telles qu’il existe des constantes c > 0 et n₀ telles que g(n) ≤ c·f(n) pour tout n ≥ n₀. Représente la borne supérieure asymptotique (pire cas).
- Ω(f(n)) : Ensemble des fonctions g(n) telles qu’il existe c > 0 et n₀ telles que g(n) ≥ c·f(n) pour tout n ≥ n₀. Représente la borne inférieure asymptotique (meilleur cas ou minimum).
- Θ(f(n)) : Intersection de O(f(n)) et Ω(f(n)), i.e., g(n) = Θ(f(n)) si c₁·f(n) ≤ g(n) ≤ c₂·f(n) pour des constantes c₁, c₂ > 0 et n ≥ n₀. Représente une borne exacte.
- Exemple : Une boucle simple sur n éléments est O(n), Ω(n), donc Θ(n).
- Avantages et Limites :
- Avantages :
- Simplification : Élimine les détails matériels (e.g., cycles CPU) et constantes (e.g., 2n vs 3n → O(n)).
- Universalité : Permet des comparaisons entre algorithmes sur des entrées théoriquement infinies.
- Prédiction : Utile pour anticiper la scalabilité (e.g., O(n log n) vs O(n²)).
- Trouver du travaille : c'est utilisé dans les tests de recrutement.
- Limites :
- Perte de précision : Ignore les constantes critiques dans la pratique (e.g., 100n vs n², où n² gagne pour n < 100).
- Petites tailles : Inexact pour n faible (e.g., O(n²) peut être plus rapide que O(n) si constantes élevées).
- Dans la très grande majorité des cas on utilise des petites tailles, donc produisant une contre optimisation.
- Hypothèses : Suppose un modèle de calcul uniforme, négligeant cache, I/O, etc.
- Sémantique Axiomatique :
- La sémantique axiomatique est une approche formelle pour spécifier et vérifier le comportement d’un programme via des assertions logiques (Hoare triples : {P} S {Q}).
- Précondition (P) : Ce qui est vrai avant l’exécution.
- Postcondition (Q) : Ce qui est vrai après.
- S : Le code ou l’instruction.
- Exemple : Pour une boucle for (i = 0; i < n; i++), {n ≥ 0} → {i = n après exécution}.
- Elle repose sur des axiomes et règles d’inférence (e.g., règle de la boucle : invariant maintenu).
- On comprend finement l'algorithme, toute les boucles, tous les cycles et on prouve "mathématiquement" et presuqe "éxactement" les couts.
- Complémentarité/Différence :
- Complémentarité :
- Les notations asymptotiques mesurent l’efficacité (temps/espace), tandis que la sémantique axiomatique prouve ce que l’algorithme calcule.
- Exemple : O(n log n) pour un tri, mais la sémantique axiomatique prouve que le tableau est trié ({T non trié} sort {T trié}) et en combiens d'étapes éxactement.
- Plus :
- Permet de détecter des erreurs logiques (e.g., débordement, invariants faux) que O(n) ne voit pas.
- Fournit une preuve formelle exploitable dans des systèmes critiques (e.g., aéronautique).
- Moins :
- Plus complexe à appliquer (nécessite des invariants manuels) que les notations asymptotiques.
- Différence clé : Focus quantitatif (asymptotique) vs qualitatif (sémantique).
Dans les algorithmes de tri, on sépare parfois la complexité temporelle en deux, notamment pour le nombre de comparaison et le nombre de swap. Expliquez cette distinction
- Comparaisons : C’est le nombre de fois qu’on compare deux éléments pour déterminer leur ordre (e.g., if (T[i] > T[j])). Cela mesure la logique de décision du tri.
- Swaps : C’est le nombre d’échanges d’éléments dans le tableau (e.g., permuter T[i] et T[j]). Cela mesure les modifications physiques.
- Les comparaisons sont souvent plus fréquentes et influencent le temps total.
- Les swaps coûtent plus cher (accès mémoire, écriture) que les comparaisons (lecture seule).
- Un algorithme avec moins de swaps peut être plus rapide en pratique, même avec le même O(n²), comme le tri par insertion vs le tri à bulles.
Nombre de Comparaisons : Représente le nombre d’opérations de comparaison entre éléments (e.g., <, >, =), qui détermine l’ordre relatif. C’est une mesure de la complexité décisionnelle, liée à la structure de l’algorithme (e.g., arbre de décision). Exemple : Tri à bulles compare chaque paire adjacente → O(n²) comparaisons dans le pire cas.
Nombre de Swaps : Représente le nombre d’échanges ou déplacements d’éléments dans le tableau pour atteindre l’ordre final. C’est une mesure de la complexité des modifications physiques, impactant les accès mémoire et les écritures. Exemple : Tri à bulles échange à chaque inversion → O(n²) swaps, tandis que le tri par insertion déplace en ajustant → O(n²) mais souvent moins.
Coût Opérationnel Différent : Sur une architecture moderne, une comparaison coûte ~1-2 cycles (CMP), tandis qu’un swap coûte ~6-9 cycles (lecture + écriture, e.g., 3 LDR + 3 STR sur 64-bit).
Les swaps impliquent des écritures en mémoire, sensibles aux cache misses (~50 cycles), contrairement aux comparaisons (lectures, souvent cache hits).
Séparer ces métriques permet d’identifier les goulots d’étranglement spécifiques (e.g., tri par insertion : O(n²) comparaisons, mais swaps réduits si presque trié → Ω(n)). Donc cela permet de favoriser des algorithmes adaptés au matériel.
Exemple Concret :
- Tri à bulles : n(n-1)/2 comparaisons et swaps dans le pire cas → O(n²).
- Tri par insertion : n(n-1)/2 comparaisons, mais ~n²/4 swaps en moyenne → plus performant en pratique.
Limite : La complexité globale O(n²) masque ces différences, rendant cette distinction cruciale pour des tailles moyennes ou des contraintes spécifiques.
Analysez la complexité temporelle et spatiale de la fonction récursive suivante. Donnez la notation asymptotique.
int mystery(int n) {
if (n <= 1) return n;
return mystery(n / 2) + n;
}- Analyse Temporelle : La fonction divise n par 2 à chaque appel récursif et ajoute n au résultat.
- Nombre d’appels : jusqu’à ce que n ≤ 1, soit environ log₂(n) étapes (e.g., n = 8 → 4 → 2 → 1).
- Calcule par appel : une addition O(1), mais on additionne n + n/2 + n/4 + ..., une série géométrique.
- Complexité : O(log(n)), Ω(log(n)), donc Θ(log(n)).
- Analyse Spatiale :
- Chaque appel récursif ajoute une frame à la pile.
- Profondeur : log₂(n) (nombre de divisions par 2).
- Complexité : O(log(n)), Ω(log(n)), donc Θ(log(n)).
Écrivez une fonction en C pour effectuer une rotation à droite d'une liste simplement chaînée (le dernier noeud devient le premier). Définissez la structure de données utilisée. Quelle est la complexité ?
typedef struct Node {
int data;
struct Node* next;
} Node;
void rotate_right(Node** head) {
// Vérifier si la liste est vide ou a un seul noeud
if (*head == NULL || (*head)->next == NULL) {
return;
}
// Trouver le dernier et l’avant-dernier nœud
Node* current = *head;
while (current->next->next != NULL) {
current = current->next;
}
// Effectuer la rotation
Node* last = current->next; // Dernier noeud
current->next = NULL; // Avant-dernier devient fin
last->next = *head; // Dernier pointe sur ancien premier
*head = last; // Dernier devient tête
}Complexité :
- Temporelle : O(n), car on parcourt la liste pour trouver l’avant-dernier noeud (n-1 étapes).
- Spatiale : O(1), car on utilise seulement deux pointeurs (current et last).
La traversée d'un arbre binaire peut s'effectuer selon trois méthodes : Pre-order, In-order et Post-order. Voici un exemple de signature de fonction pour effectuer cette traversée, complétez-la pour les différents cas de figure. Donnez un exemple d'arbre et de sortie en utilisant les trois fonctions.
void pre_order(Node *tree) {
if (!tree) return;
printf("%c ", tree->data);
pre_order(tree->left);
pre_order(tree->right);
}
void in_order(Node *tree) {
if (!tree) return;
in_order(tree->left);
printf("%c ", tree->data);
in_order(tree->right);
}
void post_order(Node *tree) {
if (!tree) return;
post_order(tree->left);
post_order(tree->right);
printf("%c ", tree->data);
}Si on considère l'arbre suivant :
1
/ \
2 3
/ \ \
4 5 6
/ \ /
7 8 9
- Pre-order : 1, 2, 4, 5, 7, 8, 3, 6, 9
- Visite d’abord la racine, puis les sous-arbres.
- In-order : 4, 2, 7, 5, 8, 1, 3, 9, 6
- Donne un ordre croissant pour un BST
- Post-order : 4, 7, 8, 5, 2, 9, 6, 3, 1
- Visite la racine en dernier, utile pour supprimer un arbre.
Complexité Spatiale et temporel :
- Pile de récursion : profondeur maximale = hauteur h de l’arbre.
- Pire cas (arbre dégénéré) : h = n → O(n).
- Meilleur cas (arbre équilibré) : h ≈ log n → O(log n).
Analysez la complexité du code de tri boustrophédon ci-dessous, en termes de temps (comparaison et swap) et d'espace (pire cas et meilleur cas). Expliquez comment la complexité pourrait être améliorée. Proposez des suggestions pour réduire le nombre de comparaisons et de swaps inutiles. Modifiez le code pour optimiser ces aspects et donnez les nouvelles complexités.
void boustrophedonsort(void *data, int count, size_t size, CompareFunc compare) {
int start = 0, end = count - 1;
char *cdata = (char*)data;
while (end != start)
{
for (int i = start; i < end; ++i)
if (compare(cdata + i * size, cdata + (i + 1) * size) > 0)
memswap(cdata + i * size, cdata + (i + 1) * size, size);
end--;
if(end == start)
break;
for (int i = end; i >= start; --i)
if (compare(cdata + (i - 1) * size, cdata + i * size) > 0)
memswap(cdata + (i - 1) * size, cdata + i * size, size);
start++;
}
}- Temporelle :
- Comparaisons : Deux passes par itération →
$n(n-1 + n-2)/2$ → O(n^2). - Swaps : Jusqu’à n(n-1 + n-2)/2 dans le pire cas (inversé) → O(n^2).
- Meilleur cas (trié) : O(n^2) comparaisons, O(1) swaps.
- Comparaisons : Deux passes par itération →
- Spatiale : O(size) pour memswap (espace temporaire).
- Optimisation : détecter directement le min et le max en une passe →
$n(n-1)/2$ → O(n^2).- Swaps : Jusqu’à n (explicitement 2n/2) dans le pire cas (inversé) → O(n).
- Meilleur cas (trié) : O(n^2) comparaisons, O(1) swaps.
- Même complexité O(n^2) MAIS pire cas 2x plus rapide
void boustrophedonsort(void *data, int count, size_t size, CompareFunc compare) {
int start = 0, end = count - 1;
char *cdata = (char*)data;
while (end != start) {
int min_idx = start, max_idx = start;
for (int i = start + 1; i <= end; i++) {
if (compare(cdata + i * size, cdata + min_idx * size) < 0)
min_idx = i;
if (compare(cdata + i * size, cdata + max_idx * size) > 0)
max_idx = i;
}
// Placer min à start
if (min_idx != start)
memswap(cdata + min_idx * size, cdata + start * size, size);
// Placer max à end
if (max_idx != end)
memswap(cdata + max_idx * size, cdata + end * size, size);
start++;
end--;
}
}Une composante connexe dans un graphe non orienté est un sous-graphe où chaque paire de noeuds est connectée par un chemin. En d'autres termes, tous les noeuds d'une composante connexe sont accessibles les uns aux autres via des arêtes.
Considérons un graphe non orienté avec deux groupes de noeuds séparés. Chaque groupe forme une composante connexe, car les noeuds à l'intérieur d'un groupe sont tous connectés, mais il n'existe aucun chemin entre les deux groupes.
Comment pouvez-vous procéder pour compter le nombre de composantes connexes ? Sur quels algorithmes pouvez-vous vous appuyer ? Sachant que cette fonction est disponible, proposez un pseudo-code pour compter les composantes connexes dans une matrice d'adjacence. Sur quelle structure de données cet algorithme repose-t-il ?
Méthode pour Compter les Composantes Connexes :
- Parcourez tous les noeuds du graphe et explorez chaque composante connexe non visitée.
- Parcours en profondeur (DFS) ou parcours en largeur (BFS)
- Ces algoithmes permettent d'explorer une composante connexe à partir d’un noeud initial.
- Tous les noeud visités sont dans la même composantes connexe
- Reinitialisé l'algorithm a partir d'un noeud non visité.
- Incrémentez un compteur à chaque fois qu’une nouvelle composante est trouvée.
Pseudo-Code :
Fonction compter_composantes_connexes(matrice[N][N], N):
visited[N] ← faux pour tout i
composantes ← 0
Pour i de 0 à N-1:
Si non visited[i]:
DFS(matrice, N, i, visited)
composantes ← composantes + 1
Retourner composantes
Fonction DFS(matrice[N][N], N, noeud, visited[]):
visited[noeud] ← vrai
Pour j de 0 à N-1:
Si matrice[noeud][j] = 1 ET non visited[j]:
DFS(matrice, N, j, visited)
Complexité Associée :
- Espace :
- O(N²) pour la matrice
- O(N) pour visited
- Total O(N²)
- Temps :
- O(N) pour DFS (vérifie toutes les arêtes connectés)
- O(N) boucles externes (réinitialisation)
- Total O(N²)
- MAIS DFS n'est éxécuté qu'une seul fois pour chaque noeud
- donc cout marginal de la boucle externe (vrai coût plus proche de O(n))
Un min-heap est une structure de données arborescente complète qui satisfait deux propriétés fondamentales : la forme et la propriété du tas. Donc (1) un min-heap est un arbre binaire complet, ce qui signifie qu'il est rempli à tous les niveaux, sauf peut-être le dernier niveau, qui est rempli de gauche à droite. Cela implique que tous les noeuds internes ont deux enfants, sauf ceux du dernier niveau, qui peuvent avoir zéro ou un enfant droit. Et (2) la propriété du tas stipule que la valeur de chaque noeud parent est inférieure ou égale à celle de ses enfants. Cela garantit que le minimum de l'arbre se trouve toujours à la racine.
La constitution d'un tas à partir d'un tableau existant implique plusieurs étapes clés :
- Initialisation : On commence avec un tableau d'éléments non triés.
- Construction du Tas : On itère à travers le tableau, en commençant par le dernier noeud non-feuille (c'est-à-dire le parent du dernier noeud) et en remontant vers la racine. Pour chaque noeud, on applique l'opération sieving pour s'assurer que la propriété du tas est respectée.
- Sieving : Cette opération consiste à comparer la valeur du noeud actuel avec celles de ses enfants. Si un enfant a une valeur inférieure, on échange le noeud avec cet enfant et on répète l'opération récursivement (ou mieux itérativement) jusqu'à ce que la propriété du tas soit satisfaite.
Code de base
Pour vous aidez, vous pouvez utilisé ces fonctions, et complétez les parties manquantes :
void swap(int* a, int* b);
int sieving(int* array, int element, int max) { # TODO }
int main() {
int arr[] = {10, 5, 15, 2, 20, 30};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = #TODO#)
sieving(arr, i, n);
return 0;
}Travail demandé
- Proposez un exemple de min-heap (tableau + petit diagramme).
- Complétez la boucle \texttt{for}, telle qu'expliquée pour la \textbf{constitution du tas}.
- Définissez la position des enfants en fonction de l'indice
$i$ , soit (left et right). - Écrivez la fonction de \textbf{réorganisation du tas} (sieving).
- Donnez la \textbf{complexité temporelle} (comparaisons et swaps) de sieving.
- Donnez la \textbf{complexité spatiale} de sieving.
- Utilisez cette fonction sieving pour construire une stratégie de tri.
- Déduisez la complexité de cet algorithme de tri.
Tableau : {2, 5, 10, 20, 30, 15}
Diagramme :
2
/ \
5 10
/ \ /
20 30 15
- Complexité Temporelle de sieving :
- Comparaisons : O(log n) (hauteur de l’arbre)
- Swaps : O(log n) (un par niveau dans le pire cas)
- Complexité Spatiale de sieving :
- O(1) (seulement des variables locales, pas d’allocation supplémentaire)
- Stratégie de Tri (Heapsort) :
- Construire le tas avec sieving
- Extraire le min (racine), le placer à la fin, et réorganiser le tas
- Complexité du Tri :
- Construction : O(n log n)
- Tri : O(n log n)
- Total : O(n log n)
int sieving(void *array, int element, int max, size_t size, CompareFunc compare) {
char *carray = (char*)array;
while ((element << 1) < max)
{
int j = (element << 1);
if (j + 1 < max && compare(carray + j * size, carray + (j + 1) * size) < 0)
j++; // take right child
if (compare(carray + element * size, carray + j * size) < 0)
{
// bring to the top
memswap(carray + element * size, carray + j * size, size);
element = j;
}
else
return element;
}
return element;
}
void heapsort(void *array, int size, size_t elem_size, CompareFunc compare) {
if (size < 2)
return;
char *virtualArray = (char*)array - elem_size;
int virtualSize = size + 2;
for (int i = ((size - 1) / 2); i >= 0; --i)
sieving(virtualArray, i + 1, virtualSize - 1, elem_size, compare);
for (int i = size - 1; i > 0; --i)
{
memswap(array, (char*)array + i * elem_size, elem_size);
sieving(virtualArray, 1, i + 1, elem_size, compare);
}
}