Complexité Algorithmique
Complexité Algorithmique
Programming, Math · exam
Voir tous les documents en programmationTous les examens en programmation
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente un examen en Complexité Algorithmique, évaluant des compétences en analyse de complexité, conception d’algorithmes, et résolution de problèmes classiques comme la recherche, le tri, le sac à dos et la plus longue sous-séquence commune. Chaque exercice propose des questions demandant à la fois des explications théoriques et des algorithmes avec leur complexité.
L'exercice 1 traite de l'analyse de complexité d'une recherche par hachage, de l'explication du problème de collision et de la comparaison entre le tri-fusion et le tri-rapide.
La recherche d’un élément dans un tableau en utilisant le principe de hachage consiste à calculer une fonction de hachage qui associe une clé à un indice dans le tableau. En supposant une bonne fonction de hachage et une gestion efficace des collisions, la recherche s’effectue en temps constant en moyenne.
La complexité asymptotique moyenne est donc O(1).
Le problème de collision survient lorsque deux clés différentes ont la même valeur de hachage, donc le même indice dans le tableau. Cela empêche d’accéder directement à un élément unique.
Pour gérer les collisions, plusieurs politiques existent. L’une des plus courantes est le chaînage (ou chaining) qui consiste à stocker dans chaque case du tableau une liste chaînée des éléments ayant le même indice de hachage. Ainsi, en cas de collision, on parcourt cette liste pour retrouver l’élément recherché. Le chaînage est une politique classique pour gérer les collisions en hachage.
En termes de complexité asymptotique :
En pratique, le tri-rapide est souvent plus rapide que le tri-fusion grâce à une meilleure gestion du cache et moins de copies de données.
Concernant la gestion de l’espace mémoire :
En résumé, le tri-fusion est stable et garanti O(n log n) mais coûteux en mémoire, tandis que le tri-rapide est plus rapide en pratique et plus économe en mémoire, mais peut être moins performant dans le pire cas.
L'exercice 2 étudie le problème du sac à dos, qui vise à maximiser la valeur des objets placés dans un sac de capacité limitée.
Pour évaluer toutes les solutions possibles, il faut considérer toutes les combinaisons d’objets, c’est-à-dire tous les sous-ensembles de l’ensemble des n objets. Le nombre total de sous-ensembles est 2n, car chaque objet peut être soit inclus soit exclu.
Par conséquent, la complexité asymptotique d’une recherche exhaustive est O(2n). La complexité est exponentielle en n.
Le principe glouton consiste à construire une solution pas à pas en choisissant à chaque étape l’option qui semble la meilleure localement, sans revenir en arrière.
Pour le sac à dos, une solution gloutonne classique consiste à trier les objets par ratio valeur/poids décroissant, puis à ajouter les objets dans le sac dans cet ordre tant que la capacité le permet.
Algorithme :
1. Calculer le ratio r_i = c_i / w_i pour chaque objet i.
2. Trier les objets par ordre décroissant de r_i.
3. Initialiser poids_total = 0, valeur_totale = 0.
4. Pour chaque objet dans l’ordre trié :
a. Si poids_total + w_i ≤ Wsac, ajouter l’objet au sac.
poids_total += w_i
valeur_totale += c_i
b. Sinon, passer à l’objet suivant.
5. Retourner valeur_totale.
Cette méthode fournit une solution approximative rapidement.
Le tri des objets par ratio valeur/poids coûte O(n log n). La sélection des objets est en O(n). Donc, la complexité totale est O(n log n).
L'exercice 3 analyse l'optimisation de la recherche d'une plus longue sous-séquence commune (PLSC) entre deux séquences U et V.
Chaque élément peut être soit inclus soit exclu dans une sous-séquence. Donc, le nombre total de sous-séquences est 2n.
Un algorithme qui énumère toutes les sous-séquences de U (2n) et les compare à toutes les sous-séquences de V (2m) pour trouver la plus longue commune aurait une complexité au moins de O(2n × 2m) = O(2n+m). La complexité est exponentielle en n et m.
On note L(n,m) la longueur de la plus longue sous-séquence commune entre U et V. L’équation de récurrence est :
L(i,j) =
0 si i=0 ou j=0
L(i-1,j-1) + 1 si U[i] = V[j]
max(L(i-1,j), L(i,j-1)) sinon
La fonction récursive s’écrit :
function PLSSC_recursive(U, V, i, j):
if i == 0 or j == 0:
return 0
if U[i] == V[j]:
return PLSSC_recursive(U, V, i-1, j-1) + 1
else:
return max(PLSSC_recursive(U, V, i-1, j), PLSSC_recursive(U, V, i, j-1))
Cette solution explore tous les couples (i,j) de manière récursive sans mémorisation, ce qui conduit à une complexité exponentielle, en O(2n+m) dans le pire cas.
La programmation dynamique consiste à mémoriser les résultats intermédiaires pour éviter les calculs redondants.
On construit une matrice L de taille (n+1) × (m+1) où L[i][j] représente la longueur de la PLSC entre U[1..i] et V[1..j].
Algorithme :
function PLSSC_dynamique(U, V):
n = longueur(U)
m = longueur(V)
créer une matrice L de taille (n+1) x (m+1)
pour i de 0 à n:
L[i][0] = 0
pour j de 0 à m:
L[0][j] = 0
pour i de 1 à n:
pour j de 1 à m:
si U[i] == V[j]:
L[i][j] = L[i-1][j-1] + 1
sinon:
L[i][j] = max(L[i-1][j], L[i][j-1])
retourner L[n][m]
Cette fonction calcule la longueur de la plus longue sous-séquence commune en temps polynomial.
La matrice L est remplie en parcourant tous les indices i et j, donc en O(n × m).
Ce sujet récompense la maîtrise des notions fondamentales de complexité algorithmique, la capacité à expliquer clairement des concepts comme les collisions en hachage, et à comparer des algorithmes classiques en termes de temps et d’espace.
Il valorise aussi la compréhension des paradigms algorithmiques : recherche exhaustive, glouton, récursif, et programmation dynamique.
Les erreurs pénalisées sont :
Pour réussir, il faut expliciter clairement chaque étape, justifier les choix d’algorithmes, et montrer la maîtrise des notations de complexité.