Complexité Algorithmique

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é.

Exercice 1 : Hachage et algorithmes de tri

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.

Complexité asymptotique d’une recherche par hachage

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).

Problème de collision et politique de gestion

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.

Comparaison du tri-fusion et du tri-rapide

En termes de complexité asymptotique :

• Le tri-fusion a une complexité garantie de O(n log n) dans tous les cas.
• Le tri-rapide a une complexité moyenne de O(n log n), mais dans le pire cas peut atteindre O(n²).

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 :

• Le tri-fusion nécessite un espace supplémentaire proportionnel à la taille du tableau (O(n)) pour les tableaux temporaires.
• Le tri-rapide est en général un tri en place, utilisant un espace mémoire constant O(log n) pour la pile d’appels récursifs.

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.

Exercice 2 : Problème du sac à dos

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.

Évaluation de toutes les solutions possibles et complexité

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 2ⁿ, car chaque objet peut être soit inclus soit exclu.

Par conséquent, la complexité asymptotique d’une recherche exhaustive est O(2ⁿ). La complexité est exponentielle en n.

Solution gloutonne

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.

Complexité asymptotique de l’algorithme glouton

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).

Exercice 3 : Plus longue sous-séquence commune (PLSC)

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.

Nombre de sous-séquences d’une séquence U de taille n

Chaque élément peut être soit inclus soit exclu dans une sous-séquence. Donc, le nombre total de sous-séquences est 2ⁿ.

Complexité d’un algorithme naïf par énumération

Un algorithme qui énumère toutes les sous-séquences de U (2ⁿ) et les compare à toutes les sous-séquences de V (2^m) pour trouver la plus longue commune aurait une complexité au moins de O(2ⁿ × 2^m) = O(2^n+m). La complexité est exponentielle en n et m.

Fonction récursive PLSSC_recursive

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(2^n+m) dans le pire cas.

Fonction PLSSC_dynamique par programmation dynamique

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.

Complexité asymptotique de la solution dynamique

La matrice L est remplie en parcourant tous les indices i et j, donc en O(n × m).

Conseils de méthode

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 :

• Confusion entre complexité moyenne et pire cas.
• Omission des étapes intermédiaires dans le raisonnement.
• Manque de précision dans la définition des algorithmes.
• Ne pas justifier la complexité ou ne pas distinguer les cas pratiques et théoriques.

Pour réussir, il faut expliciter clairement chaque étape, justifier les choix d’algorithmes, et montrer la maîtrise des notations de complexité.