Algorithmique avancée

Ce document présente un examen d’algorithmique avancée, portant sur deux problèmes indépendants : l’enregistrement de morceaux d’un CD sur une cassette et la détermination d’une majorité absolue dans un vote. Il teste des compétences en conception d’algorithmes gloutons, récursifs, de programmation dynamique, ainsi qu’en analyse de complexité et paradigme diviser pour régner.

Exercice 1 : Enregistrement d’un CD sur cassette

Ce problème consiste à sélectionner des morceaux d’un CD pour les enregistrer sur une cassette à deux faces, chacune pouvant contenir au maximum d minutes de musique. Le but est de maximiser la durée totale enregistrée, sous deux politiques : avec ou sans découpage des morceaux.

1.1 Un maximum de musique, quitte à couper des morceaux

L'optimisation autorise la découpe des morceaux pour maximiser la durée totale enregistrée sur la cassette.

On peut modéliser ce problème comme un remplissage de capacité totale 2d (deux faces de d minutes chacune), avec des morceaux pouvant être fractionnés. L’algorithme glouton classique consiste à remplir la cassette en prenant les morceaux dans un ordre quelconque, en enregistrant entièrement chaque morceau tant que la capacité restante le permet, et en enregistrant un fragment du morceau suivant si la capacité restante est insuffisante.

Formellement :

Initialiser capacité restante = 2d
Pour i de 1 à n :
    Si di ≤ capacité restante :
        Enregistrer le morceau i en entier
        capacité restante ← capacité restante - di
    Sinon
        Enregistrer un fragment de longueur f = capacité restante du morceau i
        capacité restante ← 0
        Arrêter

Notation : si un morceau i est enregistré partiellement sur une face, on note i(f/di) pour indiquer que la fraction f de sa durée di est enregistrée.

L’algorithme parcourt la liste des n morceaux une seule fois, donc sa complexité est en O(n).

Réponse finale : Un algorithme glouton simple, en O(n), qui enregistre les morceaux dans l’ordre jusqu’à remplir la cassette, en autorisant la découpe du dernier morceau si nécessaire.

1.2 Un maximum de musique sans couper de morceaux

Cette variante interdit toute découpe : un morceau figure entièrement sur une face ou n’est pas enregistré.

Question 1 : Relation de récurrence

Pour chaque morceau i, trois cas sont possibles :

• Le morceau i est enregistré sur la première face, si di ≤ t1.
• Le morceau i est enregistré sur la deuxième face, si di ≤ t2.
• Le morceau i n’est pas enregistré.

La relation de récurrence s'écrit :

durée(i, t1, t2) = max { durée(i-1, t1, t2), (si di ≤ t1) di + durée(i-1, t1 - di, t2), (si di ≤ t2) di + durée(i-1, t1, t2 - di) }

avec les conditions initiales : durée(0, t1, t2) = 0 pour tous t1, t2.

Question 2 : Résolution récursive

Fonction durée(i, t1, t2):
    Si i = 0 alors
        retourner 0
    Sinon
        res ← durée(i-1, t1, t2)
        Si di ≤ t1 alors
            res ← max(res, di + durée(i-1, t1 - di, t2))
        Si di ≤ t2 alors
            res ← max(res, di + durée(i-1, t1, t2 - di))
        retourner res

Dans le pire cas, chaque appel récursif génère jusqu’à trois appels récursifs pour i-1, avec différentes valeurs de t1 et t2. Comme t1 et t2 peuvent varier entre 0 et d, le nombre d’états possibles est en O(n × d × d) = O(n d²). Cependant, sans mémoïsation, l’arbre d’appels récursifs se développe exponentiellement car les mêmes sous-problèmes sont recalculés plusieurs fois.

En particulier, si tous les morceaux durent 1 minute (di = 1), le nombre d’appels récursifs est exponentiel en n.

Réponse finale : L’algorithme récursif naïf a une complexité exponentielle (super-polynomiale) dans le pire cas.

Question 3 : Résolution par programmation dynamique « pure »

On construit un tableau tridimensionnel durée[i][t1][t2] où i varie de 0 à n, t1 et t2 de 0 à d.

Initialiser durée[0][t1][t2] = 0 pour tous t1, t2

Pour i de 1 à n:
    Pour t1 de 0 à d:
        Pour t2 de 0 à d:
            res ← durée[i-1][t1][t2]
            Si di ≤ t1 alors
                res ← max(res, di + durée[i-1][t1 - di][t2])
            Si di ≤ t2 alors
                res ← max(res, di + durée[i-1][t1][t2 - di])
            durée[i][t1][t2] ← res

Retourner durée[n][d][d]

Les trois boucles imbriquées parcourent respectivement n, d+1, d+1 éléments, ce qui donne une complexité temporelle en O(n d²).

Réponse finale : L’algorithme de programmation dynamique a une complexité en O(n d²) et calcule la durée maximale sans découpage.

Question 4 : Résolution par recensement

Le recensement consiste à représenter les états possibles par un ensemble de couples (t1, t2) correspondant aux durées utilisées sur chaque face. On commence avec l’ensemble {(0,0)} et pour chaque morceau i, on génère un nouvel ensemble en ajoutant di à t1 ou à t2 si cela ne dépasse pas d, ou en ne l’ajoutant pas.

Initialiser ensemble S = {(0,0)}

Pour i de 1 à n:
    Initialiser nouvel ensemble S' = {}
    Pour chaque (t1, t2) dans S:
        Ajouter (t1, t2) dans S'
        Si t1 + di ≤ d alors ajouter (t1 + di, t2) dans S'
        Si t2 + di ≤ d alors ajouter (t1, t2 + di) dans S'
    S ← S'

Trouver dans S le couple (t1, t2) maximisant t1 + t2

Le nombre d’états dans S est au plus (d+1)², et pour chaque morceau on génère au plus 3 fois ce nombre. La complexité reste en O(n d²).

Les deux algorithmes ont une complexité asymptotique comparable en O(n d²). Cependant, la programmation dynamique pure utilise un tableau fixe et accède directement aux états, tandis que le recensement manipule des ensembles dynamiques, ce qui entraîne une surconsommation liée à la gestion des structures dynamiques. La programmation dynamique pure est donc plus efficace en pratique.

Réponse finale : Les deux méthodes ont une complexité de O(n d²), mais la programmation dynamique pure effectue moins de calculs intermédiaires.

Question 5 : Sélection des morceaux

On enrichit l’algorithme de programmation dynamique en mémorisant, pour chaque état durée[i][t1][t2], la décision prise dans une structure auxiliaire choix[i][t1][t2] :

• Ne pas enregistrer le morceau i ("aucun").
• Enregistrer le morceau i sur la face 1 ("face1").
• Enregistrer le morceau i sur la face 2 ("face2").

Après le calcul, on remonte depuis durée[n][d][d] en suivant les choix pour reconstruire la liste des morceaux par face :

Après calcul de durée[i][t1][t2] et choix[i][t1][t2]:

Initialiser liste_face1 = []
Initialiser liste_face2 = []
i ← n
t1 ← d
t2 ← d

Tant que i > 0:
    Si choix[i][t1][t2] = "face1":
        Ajouter i à liste_face1
        t1 ← t1 - di
    Sinon si choix[i][t1][t2] = "face2":
        Ajouter i à liste_face2
        t2 ← t2 - di
    i ← i - 1

Inverser liste_face1 et liste_face2 pour obtenir l’ordre croissant des indices

Réponse finale : La mémorisation des choix permet de reconstruire la liste exacte des morceaux par face en temps O(n).

Exercice 2 : Élections présidentielles aux États-Unis

Ce problème consiste à déterminer si un candidat a obtenu la majorité absolue des voix, c’est-à-dire strictement plus de n/2 voix, dans un tableau Votes de taille n (puissance de deux).

2.1 Algorithme naïf

L'approche directe dénombre les voix reçues par chaque citoyen présent dans le tableau.

Fonction compter_voix(Votes, i, j, x):
    compteur ← 0
    Pour k de i à j:
        Si Votes[k] = x alors
            compteur ← compteur + 1
    Retourner compteur

La fonction compter_voix parcourt la tranche [i, j] du tableau, soit une complexité de O(j - i + 1).

L'algorithme Majorité-Absolue s'appuie sur cette fonction :

Fonction Majorité-Absolue(Votes, n):
    Pour chaque citoyen x apparaissant dans Votes:
        nb_voix ← compter_voix(Votes, 0, n-1, x)
        Si nb_voix > n/2 alors
            Retourner (Vrai, x)
    Retourner (Faux, 0)

Dans le pire cas, chaque vote est attribué à un citoyen différent (n citoyens distincts). Pour chacun, on exécute un comptage en O(n), ce qui donne une complexité globale de O(n²).

Réponse finale : L’algorithme naïf a une complexité quadratique O(n²).

2.2 Algorithme « diviser pour régner »

L'approche par division réduit la complexité en exploitant les propriétés des sous-ensembles du tableau.

On divise le tableau Votes en deux moitiés, on trouve récursivement le candidat majoritaire dans chaque moitié, puis on combine les résultats :

• Si les deux moitiés ont le même candidat majoritaire x, alors x est candidat majoritaire pour le tableau complet.
• Sinon, on compte le nombre de voix de chaque candidat potentiel dans tout le sous-tableau pour déterminer s’il atteint la majorité absolue.
• Si aucun candidat n’obtient strictement plus de n/2 voix, on retourne l'absence de majorité.

Fonction Majorité-Absolue-DIV(Votes, i, j):
    Si i = j alors
        Retourner (Vrai, Votes[i])
    Milieu ← (i + j) // 2
    (existe_gauche, x_gauche) ← Majorité-Absolue-DIV(Votes, i, milieu)
    (existe_droite, x_droite) ← Majorité-Absolue-DIV(Votes, milieu+1, j)

    Si existe_gauche et existe_droite et x_gauche = x_droite alors
        Retourner (Vrai, x_gauche)

    Compter nb_gauche ← nombre de voix de x_gauche dans Votes[i..j] si existe_gauche
    Compter nb_droite ← nombre de voix de x_droite dans Votes[i..j] si existe_droite

    Si existe_gauche et nb_gauche > (j - i + 1)/2 alors
        Retourner (Vrai, x_gauche)
    Sinon si existe_droite et nb_droite > (j - i + 1)/2 alors
        Retourner (Vrai, x_droite)
    Sinon
        Retourner (Faux, 0)

L'analyse de complexité donne la récurrence T(n) = 2 T(n/2) + O(n). En appliquant le théorème de maîtrise avec a = 2, b = 2 et f(n) = O(n), on obtient f(n) = Θ(n^(log_b a)) = Θ(n). Nous sommes dans le cas 2 du théorème.

La complexité globale est donc T(n) = Θ(n log n).

Réponse finale : L’algorithme diviser pour régner résout le problème en Θ(n log n).

Méthode

Ce sujet évalue la maîtrise des concepts suivants :

• Formuler des relations de récurrence adaptées à des contraintes combinatoires.
• Analyser la complexité d'algorithmes récursifs et identifier les risques d'explosion combinatoire.
• Appliquer la programmation dynamique pour éliminer les recalculs redondants.
• Comparer la programmation dynamique classique et le recensement d’états.
• Reconstruire une solution optimale à partir de structures de données auxiliaires.
• Concevoir un algorithme diviser pour régner et déterminer sa complexité via le théorème de maîtrise.

Les erreurs courantes à éviter :

• Omettre les contraintes de capacité dans la relation de récurrence.
• Confondre complexité polynomiale et complexité exponentielle sans mémoïsation.
• Oublier de mémoriser les choix d'états lors de la reconstruction de la solution.
• Mal appliquer les cas du théorème de maîtrise sur la récurrence du diviser pour régner.