Examen AAC 1ère session

Exercice 1 : Quelques questions de compréhension du cours

Question 1 - Complexité des problèmes

On nous donne six problèmes et une série de réductions polynomiales. Faisons le point sur la chaîne des réductions énoncées par les étudiants :

• L'étudiant 3 nous donne : P3 ≤p P2
• L'étudiant 2 nous donne : P2 ≤p P1
• L'étudiant 5 nous donne : P5 ≤p P4
• L'étudiant 4 nous donne : P4 ≤p P2

On peut donc établir les chaînes de réduction suivantes :

1. P3 ≤p P2 ≤p P1
2. P5 ≤p P4 ≤p P2 ≤p P1

Analysons maintenant l'appartenance aux différentes classes (P, NP, NP-dur) grâce aux autres étudiants :

Pour la classe NP : L'étudiant 1 affirme que P1 est dans NP. La relation de réduction polynomiale (≤p) conserve l'appartenance à NP (si A ≤p B et B ∈ NP, alors A ∈ NP). Puisque tous les problèmes se réduisent directement ou indirectement à P1, tous les problèmes (P1, P2, P3, P4, P5, P6) sont dans NP.

Pour la classe NP-dur : L'étudiant 6 affirme que P3 est NP-dur. La réduction polynomiale propage la "difficulté" vers la droite (si A ≤p B et A est NP-dur, alors B est NP-dur). Puisque P3 ≤p P2 ≤p P1, on peut affirmer que P3, P2 et P1 sont NP-durs. (Notez qu'étant à la fois dans NP et NP-durs, P1, P2 et P3 sont donc NP-complets).

Pour la classe P : L'étudiant 7 affirme que P4 est dans P. La réduction polynomiale propage la "facilité" vers la gauche (si A ≤p B et B ∈ P, alors A ∈ P). Puisque P5 ≤p P4, on peut affirmer que P5 et P4 sont dans P.

Question 2 - Ratios de garantie d'heuristiques

Nous avons deux heuristiques pour un problème de minimisation. Leurs ratios de garantie (3 pour H1, 6 pour H2) se traduisent par les inégalités suivantes :

• f_opt(I) ≤ f_h1(I) ≤ 3 × f_opt(I)
• f_opt(I) ≤ f_h2(I) ≤ 6 × f_opt(I)

Où f_opt(I) est la valeur optimale, et f_h1(I), f_h2(I) sont les valeurs retournées par les heuristiques.

Question 2.1 - H1 donne 7, H2 donne 2 ?

Non. D'après la garantie de H1, on sait que f_h1(I) ≤ 3 × f_opt(I). Or, l'optimal est toujours inférieur ou égal à toute solution proposée, donc f_opt(I) ≤ f_h2(I). En combinant les deux, on obtient : f_h1(I) ≤ 3 × f_h2(I). Si H2 donne 2, H1 ne peut pas dépasser 3 × 2 = 6. Il est donc impossible que H1 donne 7.

Question 2.2 - H1 donne 2, H2 donne 7 ?

Oui. C'est tout à fait possible. Par exemple, si la solution optimale est f_opt(I) = 2. H1 trouve la solution optimale (2 ≤ 2 ≤ 3 × 2), ce qui est valide. H2 trouve une solution moins bonne de coût 7 (2 ≤ 7 ≤ 6 × 2, c'est-à-dire 2 ≤ 7 ≤ 12), ce qui respecte parfaitement sa garantie. Les inégalités nous imposent seulement que 7/6 ≤ f_opt(I) ≤ 2.

Question 2.3 - H1 donne 7, H2 donne 3 ?

Oui. Les contraintes de H2 impliquent que f_opt(I) ≤ 3. Les contraintes de H1 impliquent que 7 ≤ 3 × f_opt(I), soit f_opt(I) ≥ 7/3 (environ 2,33). Il suffit que la valeur optimale soit comprise entre 7/3 et 3. Par exemple, si f_opt(I) = 3 (H2 a trouvé l'optimal), alors H1 = 7 respecte bien 3 ≤ 7 ≤ 9.

Question 2.4 - H2 donne 7, H1 donne 3 ?

Oui. De la même manière, si f_h1(I) = 3, l'optimal est tel que f_opt(I) ≤ 3 et f_opt(I) ≥ 3/3 = 1. Si f_h2(I) = 7, il faut f_opt(I) ≥ 7/6 (environ 1,16). Donc toute instance où l'optimal est compris entre 7/6 et 3 rend cette situation possible (par exemple si f_opt(I) = 3).

Question 3 - Décidabilité et langages récursifs

Rappel préliminaire : un langage est récursif s'il existe un algorithme (une machine de Turing qui s'arrête toujours) pour décider si un mot appartient ou non à ce langage.

1. L'ensemble des mots ayant un nombre pair de b est récursif. (VRAI) Il est même rationnel (reconnaissable par un automate fini déterministe). Un automate se simule facilement par un algorithme.

2. L'ensemble des mots ayant autant de a que de b est récursif. (VRAI) Il est algébrique (reconnaissable par un automate à pile). Il suffit de compter les 'a' et les 'b' en parcourant le mot, ce qui est trivialement un algorithme qui s'arrête.

3. Si L1 et L2 ne sont pas récursifs, L1 ∪ L2 ne l'est pas non plus. (FAUX) Prenons L1 un langage non récursif (comme le problème de l'arrêt) et L2 son complémentaire. La classe des langages récursifs est close par complémentation, donc L2 n'est pas récursif non plus. Cependant, leur union L1 ∪ L2 est l'ensemble de tous les mots possibles sur l'alphabet ({a, b}*), ce qui est trivialement décidable et donc récursif.

4. Si L1 ∪ L2 n'est pas récursif, L1 ne l'est pas non plus. (FAUX) Prenons L1 = ∅ (le langage vide, qui est récursif) et L2 un langage non récursif. Leur union est L2, qui n'est pas récursif. Pourtant L1 l'est.

5. Si L1 ∩ L2 n'est pas récursif, L1 ne l'est pas non plus. (FAUX) Prenons L1 = {a, b}* (l'ensemble de tous les mots, récursif) et L2 un langage non récursif. Leur intersection est L2, qui n'est pas récursif. Pourtant L1 l'est.

6. Si L1 ∪ L2 n'est pas récursif, L1 ou L2 ne l'est pas non plus. (VRAI) Pour le démontrer, utilisons la contraposée : "Si L1 et L2 sont récursifs, alors L1 ∪ L2 est récursif". Cette contraposée est vraie car la classe des langages récursifs est close par union (on lance l'algorithme pour L1, puis celui pour L2, si l'un dit oui, on accepte).

7. Si L1 ∩ L2 n'est pas récursif, L1 ou L2 ne l'est pas non plus. (VRAI) Même logique, par la contraposée : "Si L1 et L2 sont récursifs, alors L1 ∩ L2 est récursif". C'est vrai car les langages récursifs sont clos par intersection (on lance l'algorithme pour L1 puis pour L2, si les deux disent oui, on accepte).

Exercice 2 : Maximum

Nous devons trouver le "pic" p dans un tableau bitonique (qui croît strictement puis décroît strictement) en complexité temporelle O(log n). Cette contrainte de complexité indique immédiatement qu'il faut adapter la recherche dichotomique.

Correction par rapport au corrigé source : Le corrigé original comportait une erreur classique de priorité des opérateurs en écrivant m = a + b / 2, ce qui calcule a + (b/2). Il faut écrire m = (a + b) / 2. Voici le code corrigé en Java :

public int trouverPic(int[] T) {
    int a = 0;
    int b = T.length - 1;
    
    while (a < b) { 
        // Invariant : le pic p se trouve toujours entre les indices a et b (inclus)
        int m = (a + b) / 2; // a <= m < b car a < b
        
        // On compare l'élément du milieu avec son voisin de droite
        // C'est sans danger d'accès hors limite car m < b, donc m+1 <= b
        if (T[m] < T[m + 1]) {
            // La séquence est encore croissante, le pic est strictement à droite de m
            a = m + 1;
        } else {
            // La séquence commence à décroître (ou on est sur le pic)
            // Le pic est à gauche de m, ou est m lui-même
            b = m;
        }
    }
    // A la fin de la boucle, a == b, qui pointe sur le pic p
    return a;
}

La taille de l'intervalle b - a diminue strictement à chaque itération (soit a augmente, soit b diminue strictement car m < b). Cela garantit l'arrêt de l'algorithme en O(log n) étapes.

Exercice 3 : Au suivant

L'objectif est d'énumérer les mots dans l'ordre lexicographique (alphabétique) court (les mots plus courts d'abord, puis les mots de même taille par ordre alphabétique normal) avec un alphabet {a, b}. La logique est la suivante :

1. Si le mot n'a pas atteint sa longueur maximale, le "suivant" consiste simplement à ajouter la première lettre de l'alphabet à la fin (ajouter un 'a').
2. Si le mot a atteint sa longueur maximale, il faut l'incrémenter comme un compteur binaire : de la droite vers la gauche, on transforme les 'b' en effaçant la fin, jusqu'à trouver un 'a' qu'on transforme en 'b'.

Voici le code Java complété, en rectifiant quelques syntaxes de la source pour produire un code propre et fonctionnel :

class Mot {
    private char[] cont;
    private int longueur;
    private int longueurmaxi;

    Mot(int longueurmaxi){
        this.cont = new char[longueurmaxi];
        this.longueur = 0;
        this.longueurmaxi = longueurmaxi;
    }

    // Transforme le mot en son suivant pour l'ordre alphabétique
    void Suivant(){
        // Cas 1 : On peut encore rallonger le mot
        if (longueur < longueurmaxi) {
            longueur++;
            cont[longueur - 1] = 'a';
        } 
        // Cas 2 : La longueur max est atteinte
        else {
            // On remonte depuis la fin en retirant les 'b'
            while (longueur > 0 && cont[longueur - 1] == 'b') {
                longueur--;
            }
            // Si on a appelé Suivant() alors que EstDernier() était vrai,
            // la longueur vaudrait 0 ici. L'énoncé précise qu'on suppose
            // EstDernier() faux avant l'appel.
            
            // On change le dernier 'a' rencontré en 'b'
            cont[longueur - 1] = 'b';
        }
    }

    // Retourne vrai si et seulement si le mot est le dernier (ex: "bbb...b" de longueur max)
    boolean EstDernier(){
        // Si la longueur n'est pas au max, on n'est pas au bout
        if (longueur < longueurmaxi) return false;
        
        // Si on trouve un 'a' quelque part, on peut encore l'incrémenter
        for (int i = 0; i < longueur; i++) {
            if (this.cont[i] == 'a') return false;
        }
        
        // Uniquement des 'b' sur la longueur maximale
        return true;
    }
}

Exercice 4 : Plaques

Question 1 - Empilement maximal

Question 1.1 - Condition d'empilement total

Pour que toutes les plaques puissent être empilées (de la plus grande à la plus petite), il faut qu'en les classant de manière à respecter l'ordre d'une dimension (par exemple x[i] ≤ x[j]), la contrainte sur la seconde dimension soit toujours respectée (y[i] ≤ y[j]). Formellement : pour tout couple i, j, si x[i] ≤ x[j], alors il faut obligatoirement que y[i] ≤ y[j].

Question 1.2 - Heuristique gloutonne

L'algorithme glouton propose de trier les plaques par longueur (x) décroissante, puis d'empiler chaque plaque dès que sa largeur (y) le permet. Cet algorithme ne donne pas toujours la solution optimale. Considérons le contre-exemple fourni : (10, 1), (8, 3), (7, 2).

• L'algorithme trie d'abord par x décroissant, l'ordre est déjà bon : P0=(10, 1), P1=(8, 3), P2=(7, 2).
• Étape 1 : Ajoute P0. largeur = 1.
• Étape 2 : Évalue P1. y[1] = 3. 3 n'est pas ≤ 1, on ignore P1.
• Étape 3 : Évalue P2. y[2] = 2. 2 n'est pas ≤ 1, on ignore P2. L'algorithme trouve une pile de 1 plaque : { P0 }. Pourtant, on pourrait empiler P2 sur P1 : (8, 3) puis (7, 2). La hauteur optimale est donc de 2 plaques. Le glouton a fait le mauvais choix en prenant la première plaque qui a bloqué toutes les autres à cause de sa largeur trop petite.

Question 1.3 - Algorithme par programmation dynamique

En triant préalablement les plaques par longueur x décroissante, le problème se ramène exactement à trouver la Plus Longue Sous-Suite Décroissante sur la dimension y. Voici l'algorithme en O(n²) écrit proprement :

public List<Integer> hauteurMaxPlaques(int n, int[] x, int[] y) {
    // On suppose les tableaux x et y déjà triés par x décroissant.
    int[] nb = new int[n];   // nb[i] = taille de la plus haute pile se terminant par la plaque i
    int[] prec = new int[n]; // prec[i] = index de la plaque en dessous de i pour reconstituer la pile
    
    int maxPile = 0;
    int indMax = 0;
    
    for (int i = 0; i < n; i++) {
        nb[i] = 1;      // Une plaque seule forme une pile de hauteur 1
        prec[i] = i;    // Par défaut, pas de prédécesseur
        
        // On regarde toutes les plaques j plus grandes (placées avant i dans le tableau trié par x)
        for (int j = 0; j < i; j++) {
            // Si i peut se poser sur j et que ça améliore la hauteur de la pile pour i
            if (y[i] <= y[j] && nb[j] + 1 > nb[i]) {
                nb[i] = nb[j] + 1;
                prec[i] = j;
            }
        }
        
        if (nb[i] > maxPile) {
            maxPile = nb[i];
            indMax = i;
        }
    }
    
    // Reconstitution de la solution à l'envers
    List<Integer> solution = new ArrayList<>();
    int courant = indMax;
    while (prec[courant] != courant) {
        solution.add(courant);
        courant = prec[courant];
    }
    solution.add(courant);
    
    // Pour l'avoir de la base au sommet
    Collections.reverse(solution);
    return solution;
}

Note pédagogique : La source parcourait le tableau de la fin vers le début (recherche des successeurs). La version présentée ici, de la gauche vers la droite avec recherche des prédécesseurs, est la forme canonique et souvent plus intuitive du calcul de la plus longue sous-suite, tout en gardant strictement la même complexité.

Question 2 - Couverture de plaques

Question 2.1 - Solution optimale de l'exemple

L'ensemble (17, 5), (12, 7), (9, 5), (9, 7), (8, 6). Toutes ces plaques peuvent être recouvertes par les deux plus grandes plaques sur les deux dimensions : (17, 5) et (12, 7).

Question 2.2 - Unicité de la solution

Peut-il y avoir deux solutions optimales différentes ? Non. La démonstration repose sur l'hypothèse de l'énoncé : "deux plaques différentes ont au moins une dimension différente". Raisonnons par l'absurde : Imaginons deux solutions optimales S1 et S2 distinctes. Il y a donc forcément une plaque i qui appartient à S1 mais pas à S2. S2 étant une couverture valide, la plaque i doit être couverte par une autre plaque j présente dans S2. Donc x[i] ≤ x[j] et y[i] ≤ y[j]. Comme elles sont différentes, l'une des inégalités est stricte. S1 étant aussi une couverture valide, la plaque j (qui n'est pas forcément dans S1) doit y être couverte par une plaque k de S1. Donc x[j] ≤ x[k] et y[j] ≤ y[k]. Par transitivité, x[i] ≤ x[k] et y[i] ≤ y[k] (avec au moins une inégalité stricte). Donc la plaque k couvre strictement la plaque i. Mais i et k appartiennent toutes les deux à S1 ! Cela signifie que S1 contient une plaque i totalement redondante (couverte par k). On pourrait la retirer de S1 sans casser la couverture, ce qui contredit le fait que S1 soit de taille minimale (optimale). La solution optimale est donc unique.

Question 2.3 - Algorithme glouton de couverture

Le glouton consiste à trier les plaques par la dimension x décroissante (et y décroissant en cas d'égalité). On garde en mémoire la largeur maximale y des plaques qu'on a sélectionnées. Toute plaque suivante (qui aura un x plus petit ou égal) sera couverte si son y est plus petit ou égal à ce maximum. Si ce n'est pas le cas, on est obligé de la sélectionner pour la couverture.

public List<Integer> couverture(int n, int[] x, int[] y) {
    // On suppose un tri préalable par x décroissant, puis y décroissant
    List<Integer> J = new ArrayList<>();
    if (n == 0) return J;
    
    J.add(0);
    int largeurMaxi = y[0];
    
    for (int i = 1; i < n; i++) {
        // La plaque i a un x inférieur ou égal à la dernière ajoutée.
        // Si son y dépasse la largeur maximale couverte jusqu'ici, 
        // aucune plaque précédente ne peut la couvrir, il faut l'ajouter.
        if (y[i] > largeurMaxi) {
            J.add(i);
            largeurMaxi = y[i];
        }
    }
    return J;
}

Correction : L'algorithme est correct car si une plaque n'est pas ajoutée, c'est que son y est inférieur ou égal au y d'une plaque précédemment sélectionnée. Comme le tableau est trié, son x est également inférieur ou égal. Elle est donc bien couverte. L'optimalité est garantie car chaque fois qu'on ajoute une plaque i, elle possède un y strictement supérieur à toutes les plaques précédentes (qui avaient pourtant des x plus grands). Aucune plaque précédente ne pouvait donc la couvrir, elle est absolument indispensable. Complexité : Le tri initial prend O(n log n). Le parcours linéaire prend O(n). La complexité globale est donc O(n log n).

Exercice 5 : Processus

Question 1 - DecProc est dans NP

Pour montrer qu'un problème de décision est dans NP, il faut prouver qu'une solution proposée (un certificat) peut être vérifiée par un algorithme en temps polynomial par rapport à la taille de l'instance.

• Le certificat : un sous-ensemble de k processus choisis pour être activés. Ce certificat peut être encodé par un tableau de n booléens (taille O(n)). La taille du problème est au moins n + m. Le certificat est donc de taille polynomiale (linéaire) par rapport à l'entrée.
• La vérification : L'algorithme doit vérifier que le sous-ensemble contient exactement k processus, et qu'aucune ressource n'est partagée (l'intersection des ensembles de ressources demandées par toute paire de processus choisis est vide).
  • On compte les processus (O(n)).
  • On maintient un ensemble des ressources déjà allouées (ex: tableau de booléens de taille m). Pour chaque processus choisi, on vérifie que ses ressources ne sont pas déjà marquées (O(m) par processus).
  • La vérification se fait en O(k × m) ≤ O(n × m), ce qui est strictement polynomial par rapport à l'entrée. DecProc est donc bien dans NP.

Question 2 - DecProc est NP-dur (Réduction)

Il faut réduire le problème Independent Set (connu NP-dur) vers DecProc. Règle d'or de la réduction : on transforme l'instance du problème connu (Independent Set) vers l'instance de notre problème (DecProc).

Soit une instance de Independent Set : un graphe G=(Sommets, Arcs) et un entier k0 (cherche-t-on k0 sommets indépendants ?). On construit l'instance équivalente de DecProc de la manière suivante :

• Nombre de processus n = nombre de Sommets.
• Nombre de ressources m = nombre d'Arcs.
• Ressources du processus Pi = l'ensemble des arcs incidents au sommet i dans le graphe.
• Nombre de processus à activer k = k0.

Cette transformation nécessite de parcourir le graphe, ce qui se fait en temps polynomial. Preuve d'équivalence :

• Si G possède un ensemble indépendant de k sommets : ces sommets ne partagent aucun arc. Dans DecProc, cela signifie que les k processus correspondants ne partagent aucune ressource. On peut donc activer k processus simultanément.
• Réciproquement, si on peut activer k processus simultanément : ils ne partagent aucune ressource (donc aucun arc). Les k sommets correspondants dans le graphe n'ont donc aucune arête en commun, formant un ensemble indépendant de taille k. Le problème DecProc est donc au moins aussi difficile qu'Independent Set, il est NP-dur.

Question 3 - 1 ressource par processus

Si chaque processus ne demande qu'une seule ressource, le problème devient polynomial (dans la classe P). Un simple algorithme glouton suffit : on groupe les processus par la ressource qu'ils demandent, et pour chaque ressource demandée au moins une fois, on choisit un seul processus (n'importe lequel, cela n'empêche aucun autre choix ailleurs). Si le total des processus qu'on a pu sélectionner ainsi est supérieur ou égal à k, c'est Oui, sinon Non.

Question 4 - Au plus 2 processus par ressource

Le problème reste NP-dur. Regardez attentivement la réduction de la Question 2 : chaque ressource correspond à un arc du graphe. Or, par définition, un arc relie exactement deux sommets (extrémités). Donc, dans les instances générées par notre réduction, chaque ressource est demandée par exactement deux processus. Puisque le problème est NP-dur sur ces instances spécifiques, il reste NP-dur avec cette contrainte.

Question 5 - Complexité du problème d'optimisation (OptProc)

OptProc demande de trouver le k maximum. Ce problème est NP-dur (et NP-équivalent). La preuve est directe : si on disposait d'un algorithme polynomial pour résoudre OptProc (qui nous donnerait le k_max), on pourrait s'en servir pour résoudre DecProc en temps polynomial (il suffirait de vérifier si k_max ≥ k). DecProc étant NP-complet (dans NP et NP-dur), l'existence d'un tel algorithme polynomial impliquerait P = NP. Le problème d'optimisation est donc NP-dur.

Méthode

Voici comment aborder efficacement ce type d'épreuve (Algorithmique Avancée et Complexité) :

1. Repérez les problèmes classiques : Derrière des histoires de "plaques" ou de "processus", se cachent presque toujours des problèmes fondamentaux étudiés en cours. L'exercice 4 est une variation de la Plus Longue Sous-Suite Croissante, l'exercice 5 est Independent Set. Les identifier immédiatement permet de mobiliser les bonnes structures de données (programmation dynamique, réduction de graphe).
2. Ne confondez pas le sens des réductions : C'est l'erreur la plus coûteuse en examen. Pour prouver qu'un problème cible est NP-dur, vous devez prendre une instance quelconque d'un problème connu NP-dur et la transformer en une instance de votre problème cible. L'inverse n'a aucune valeur démonstrative.
3. Prouvez les heuristiques gloutonnes par l'absurde ou par échange : Quand un algorithme glouton est optimal (Ex 4.Q2), il faut démontrer qu'un choix différent ne peut pas produire de meilleure solution (ou qu'on ne peut retirer aucun élément choisi). Quand il ne l'est pas, un contre-exemple simple et petit suffit.
4. Attention aux indices dans les structures : En écrivant le code (recherche dichotomique, programmation dynamique), vérifiez rigoureusement vos bornes (a < b vs a <= b, accès à i-1). Faites tourner votre code mentalement sur un tableau de taille 2 ou 3 pour vérifier l'arrêt et l'absence de dépassement mémoire.