DS 1

Barème

• moyenne : 12.16/20
• écart-type : 4.09/20
• médiane : 12.44/20
• min : 1.5/20
• max : 22/20

Vous êtes globalement une bonne promotion, avec 26 étudiants sur 46 entre 10 et 14. Quatre étudiants doivent cependant vraiment apprendre le cours (il était possible d'avoir 7 uniquement avec les questions de cours) et rien n'est perdu pour ceux qui ont entre 8 et 10, il ne manque vraiment pas grand chose (un peu de rigueur et/ou de rapidité) pour accrocher la moyenne. Enfin, comme l'examen était noté sur plus de 20 points, deux étudiants ont eu plus strictement plus que 20.

Répartition des points par exercice

L'examen était noté sur 25 points.

Exercice 1

Sur 7 points au total.

Exercice 2

Sur 6,5 points au total.

Exercice 3

Sur 6,5 points au total.

Exercice 4

Sur 6 points au total.

Corrigé

Remarques générales

Beaucoup de personnes perdent bêtement des points sur les quesions de cours. Il y avant plus de 6 points à prendre uniquement sur elles ! Il faut que vous connaissiez :

• la définition de la complexité d'un problème
• comment on calcule un minorant pour le problème de la recherche (c'est le même argument qui est repris partout)
• la complexité du problème du tri et savoir expliquer pourquoi (avec le minorant et un majorant du cours)
• connaître le principe algorithmique de diviser. Vous êtes plus de la moitié à avoir oublié qu'après la division il faut recombiner et surotut que c'est cette étape qui est crutiale pour avoir une complexité faible, pas la division.
• connaître le master theorem et son application pour le problème du tri fusion

Parfois, vos arguments deviennent un peu vaseux quand ce n'est pas clair. La plupart du temps en algoirthmie, il suffit de peu de mots bien choisi pour expliciter ce qu'on fait. Si vous avez besoin de plusieurs paragraphes c'est que soit ce n'est pas clair, soit c'est faux.

Lorsque l'on vous demande de voir ce que fait un algorithme sur des exemples, faites le ! Beaucoup décrivent ce qu'ils pensent que leur algorithme fait et pas ce qu'il fait réllement... Il faut prendre ces questions comme une oportunité de vérifier que ce que vous avez fait est juste.

Exercice 1 : encadrement du problême

1.1

Combien d'éléments majoritaires peut avoir un tableau ? Prouvez-le rigoureusement

Il ne peut y avoir qu'un seul élément majoritaire car il contient strictement plus de la moitié des éléments. S'il y en avait 2 avec respectivement $n_1$ et $n_2$ éléments on aurait $n = n_1 + n_2 \geq (E(n / 2) + 1) + (E(n / 2) + 1) \geq n + 1$ ce qui est impossible ($E()$ désignant la partie entière).

1.2.1

Montrez que quelle que soit la taille $n > 2$ du tableau et quel que soit $0 \leq i < n$, il existe un tableau $T$ d'élément majoritaire $e$ tel que $T[i] \neq e$.

Pour tout $n > 2$ on a $\frac{n}{2} + 1 < n$, on peut donc créer un tableau de taille $n$ ayant un deux valeurs distinctes une pour tous les $T[j]$ avec $j\neq i$ (qui sera donc l'élément majoritaire) et l'autre pour $T[i]$.

1.2.2

Montrez que quelle que soit la taille $n \geq 1$ du tableau et quel que soit $0 \leq i < n$, il existe un tableau $T$ d'élément majoritaire $e$ tel que $T[i] = e$.

Le tableau avec une unique valeur répond trivialement à la question.

1.2.3

Montrez que quels que soient $n>2$ et $0 \leq i < n$, il existe toujours deux tableaux d'entiers $T$ et $T'$ de taille $n$ tels que :

• $T[j] = T'[j]$ pour tout $j \neq i$,
• $T$ admet un élément majoritaire,
• $T'$ n'admet pas d'élément majoritaire.

La question 1.2.1 nous montre que l'on peut créer un tableau possédant un élément majoritaire et tel que $T[i]$ ne soit pas cet élément. On peut de plus s'arranger pour que cet élément majoritaire soit exactement présent la partie entière de $\frac{n}{2}$ plus 1 fois (on remplace si nécessaire les éléments surnuméraires par $T[i]$).

Le tableau $T'$ tel que :

• $T[j] = T'[j]$ pour tout $j \neq i$
• $T'[i]$ vaut l'élément majoritaire de $T$

Répond à la question.

1.2.4

Déduisez-en que la complexité du problème de l'élément majoritaire est en $\Omega(n)$, avec $n$ la taille du tableau (il n'existe pas d'algorithme permettant de résoudre le problème de l'élément majoritaire en strictement moins de $n$ opérations pour tout $n > N_0$).

On procède comme dans le cours pour démontrer la complexité du problème de la recherche.

On suppose qu'il existe un algorithme prenant strictement moins que $n$ opérations pour trouver l'élément majoritaire de tout tableau de taille $n > N_0$. Prenons un tableau $T$ comme dans la question précédente. On a alors deux cas :

• soit l'algorithme a parcouru toutes les cases de $T$ possédant l'élément majoritaire et il a eu besoin d'au moins $\frac{n}{2} + 1 = \Omega(n)$ opérations,
• soit il n'a pas parcouru toutes les cases de $T$ possédant l'élément majoritaire, disons $T[i]$, et on crée le tableau $T'$ identique à $T$ sauf pour la case d'indice $i$ : $T'$ ne possède pas d'élément majoritaire mais l'algorithme va donner la même réponse que pour $T$. Contradiction.

1.3.1

Donnez le pseudo-code et la preuve d'une fonction compte de complexité $\mathcal{O}(n)$ telle que compte(T, x) est le nombre d'occurrences de $x$ dans $T$ (si $x\notin T$, compte(T, x) vaut 0).

def compte(T, x):

    nombre = 0
    for element in T:
        if element == x:
            nombre += 1
    return nombre

La complexité de la fonction est en $\mathcal{O}(n)$ où $n$ est la taille de $T$ puisque :

• toutes les lignes sont de complexité $\mathcal{O}(1)$
• la boucle for est exécutée la taille de $T$ fois, c'est à dire $\mathcal{O}(n)$ fois.

L'invariant de boucle que l'on va utiliser pour prouver l'algorithme compte est : au bout de la $i$ ème itération, nombre vaut le nombres de fois où x est présent dans les $i$ premières cases de $T$.

1. l'invariant est clairement vérifié à la fin de la première itération
2. si l'invariant est vérifié à la fin de la $i$ ème itération, , comme la $i+1$ itération vérifie si x == T[i] et ajoute 1 à nombre si c'est le cas, l'invariant est toujours vérifié à la fin de la $i + 1$ ème itération.
3. l'invariant est vrai en sortie de boucle, c'est à dire après avoir parcouru tous les éléments de $T$ : nombre vaut bien le nombre de fois où x est présent dans $T$.

1.3.2

Utilisez la question précédente pour créer algorithme en $\mathcal{O}(n^2)$ qui prend un tableau d'entiers en paramètre et rend un élément majoritaire de ce tableau s'il existe, ou None sinon.

def élément_majoritaire(T):
    for x in T:
        if compte(T, x) > len(T) / 2:
            return x
    return None

Le test de la ligne 4 est en $\mathcal{O}(n)$ où $n$ est la taille de $T$ puisqu'il faut exécuter compte. Toutes les autres lignes sont de complexité $\mathcal{O}(1)$ et comme la boucle for est exécutée la taille de $T$ fois, on exécute compte $n$ fois ce qui porte la complexité de l'algorithme à $\mathcal{O}(n^2)$.

L'invariant de boucle que l'on va utiliser pour prouver l'algorithme élément_majoritaire est : au bout de la $i$ ème itération,aucun des $i$ premières cases de $T$ n'est un élément majoritaire.

1. l'invariant est clairement vérifié à la fin de la première itération
2. si l'invariant est vérifié à la fin de la $i$ ème itération, comme la $i+1$ itération vérifie si T[i] est un élément majoritaire, l'invariant est toujours vérifié à la fin de la $i + 1$ ème itération.
3. l'invariant est vrai en sortie de boucle, c'est à dire après avoir parcouru tous les éléments de $T$ : si on arrive en ligne 6, c'est que $T$ n'a pas d'élément majoritaire. Si l'on s'arrête à la fin de la $i$ ème itération c'est que T[i-1] est l'élément majoritaire de $T$.

1.3.3

Explicitez en quelques phrases le fonctionnement de l'algorithme de la question précédente si, en entrée, on lui donne les deux exemples du début de l'énoncé.

En utilisant le premier tableau, la fonction va parcourir tous les éléments de $T$ et pour chacun effectuer la fonction compte sans trouver d'élément présent 5 fois ou plus.

En utilisant le premier tableau, la fonction sortir au bout de la première itération puisque 2 est l'élément majoritaire de $T$.

1.3.4

En déduire que la complexité du problème de l'élément majoritaire est en $\mathcal{O}(n^2)$

L'algorithme de la question 1.3.2 résoud le problème de la recherche d'un élément majoritaire, sa complexité est donc un majorant de la complexité du problème.

Exercice 2 : Tris

2.1.1

Donnez le nom d'un algorithme de tri ayant une complexité de $\mathcal{O}(n\ln(n))$ avec $n$ la taille du tableau à trier. Vous expliciterez son fonctionnement en quelques phrases.

L'algorithme vu en cours qui a cette complexité est le tri fusion il utilise le principe algorithmique diviser pour régner. L'idée est de composer une liste triée à partir de deux listes elles même triées. L'algorithme est le suivant :

1. on scinde la liste en 2 parties égale que l'on trie en utilisant la récursion
2. on crée une liste triée à partir des deux sous-listes triées (ceci peut se faire en $\mathcal{O}(n)$ opérations)
3. on rend la liste finale triée

La complexité nous est donnée par le master théorème.

2.1.2

Justifiez en quelques phrases que le problème du tri est en $\Omega(n\ln(n))$.

Il faut pouvoir distinguer parmi tous les ordres possibles et il y en a $n!$. Il faut donc au moins $\Omega(\ln(n!))$ tests pour disinguer tous les cas. On conclut en remarquant que $\Omega(\ln(n!)) = \Omega(n\ln(n))$.

2.1.3

Déduisez-en que le problème du tri est en $\Theta(n\ln(n))$.

1. On a un algorithme en $\mathcal{O}(n\ln(n))$ pour résoudre le problème
2. On sait qu'il faut au moins $\Omega(n\ln(n))$ opérations

Les deux conditions ci-dessus montrent, par définiton, que le problème du tri est en $\Theta(n\ln(n))$.

2.2.1

Si $T$ est trié, démontrez l'existence d'un indice $i$ (que vous expliciterez) tel que, si $T$ admet un élément majoritaire $x$, alors $x=T[i]$.

Si le tableau T est trié et qu'il contient un élément majoritaire, alors c'est l'élément à la position len(T) // 2 (// est la division entière). Supposons en effet que T[len(T) // 2] ne soit pas un élément majoritaire de T. Comme les éléments de T strictement plus grand (resp. strictement plus petit) que T sont tous d'indices strictement plus grand (resp. strictement plus petit) que len(T) // 2 il y en a au plus len(T) // 2 : ils ne peuvent pas être majoritaire. Ainsi si T[len(T) // 2] n'est pas un élément majoritaire de T, le tableau ne possède pas d'éléments majoritaire.

2.2.2

Déduisez-en un algorithme itératif, dont vous donnerez le pseudo-code et la preuve, plus efficace que celui de l'exercice 1.3.2 pour résoudre le problème de l'élément majoritaire.

def element_majoritaire(T):
    T.sort()
    if compte(T[len(T) // 2], T) > len(T) / 2:
        return T[len(T) // 2]
    return None

L'algorithme commence par trier le tableau et compte le nombre d'occurence de l'élément au milieu. Ci cette occurence est majoritaire, on a trouvé notre élément majoritaire et si elle ne l'est pas, la question 2.2.1 montre que le tableau ne peut avoir d'élément majoritaire,

Sa complexité est ramené à la complexité du tri plus une fois la complexité de compte : la complexité est donc en $\mathcal{O}(len(T) \ln(len(T)))$.

2.2.3

Explicitez en quelques phrases le fonctionnement de l'algorithme de la question précédente si, en entrée, on lui donne les deux exemples du début de l'énoncé.

• En utilisant le premier tableau, son tri va donner le tableau T = [2, 4, 4, 4, 4, 4, 5, 5, 5] et son milieu T[4] vaut 4 qui est majoritaire.
• En utilisant le second tableau, son tri va donner le tableau T = [2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 6] et son milieu T[6] vaut 3 n'est pas majoritaire : le tableau n'a pas d'élément majoritaire.

Exercice 3 : Diviser pour régner

3.1

Expliciter le principe algorithmique de diviser pour régner

Le principe algorithmique diviser pour régner est décrit dans le cours ici :

Un algorithme de la forme diviser pour régner fonctionne en deux parties :

1. résoudre $k$ sous-problèmes du problème initial
2. combiner les $k$ solutions des sous-problèmes en une solution du problème initial

3.2.1

Montrez que si $T$ admet un élément majoritaire $x$, alors $x$ est un élément majoritaire de $T_1$ ou $T_2$.

On suppose que $T$ de taille $n$ contient un élément majoritaire $x$. Si $x$ n'est pas majoritaire dans $T_1$, c'est qu'il est présent $\frac{n}{4}$ fois ou moins dans $T_1$. On le retrouve donc au moins $\frac{n}{4}+1$ fois dans $T_2$ : c'est un élément majoritaire de $T_2$.

3.2.2

Donnez un algorithme qui détermine, quand $x$ est un élément majoritaire de $T_1$, si $x$ est un élément majoritaire de $T$.

Il suffit de regarder si compte(x, T) > len(T) // 2 avec x l'élément majoritaire de $T_1$ ou $T_2$ s'il est différent de None. Ce qui peut se traduire en pyhton en :

x = element_majoritaire(T1)
if x != None and (compte(x, T) > n / 2):
    return x

x = element_majoritaire(T2)
if x != None and (compte(x, T) > n / 2):
    return x

3.2.3

Déduisez-en un algorithme récursif, plus efficace que celui de l'exercice 1.3.2, pour résoudre le problème.

def element_majoritaire(T):
    n = len(T)
    if len(T) == 1:
        return T[0]
    x = element_majoritaire(T[:n//2])
    if x != None and compte(x, T) > n / 2:
        return x

    x = element_majoritaire(T[n//2:])
    if x != None and compte(x, T) > n / 2:
        return x

    return None

La condition d'arrêt est pour des tailles de tableaux égales à $1 = 2^0$. Pour laquelle on trouve bien l'élément majoritaire.

On suppose alors par récurrence que l'algoerithme fonctionne pour $n = 2^i$ et on vérifie qu'il continue de fnctionner pour $n'=2^{i+1}$. Ceci est évidant car on applique directement la condition de 3.2.2

La complexité $C(n)$ de l'algoirthme est régit par l'équation de récurrence : $C(n) = 2 \cdot C(n/2) + \mathcal{O}(n)$ puisque la complexité de compte est linéaire. Cette équation est la méme que pour le tri fusion, ce qui donne une complexité de $C(n) = \mathcal{O}(n\log(n))$.

3.3.1

Reprenez cet exercice sans supposer que $n$ est une puissance de 2. Que faut-il changer pour que l'algorithme continue de fonctionner ?

La taille de $T_1$ peut maintenant être différente de la taille de $T_2$. Cette différence ne peut cependant pas être plus importante que 1 et cela ne change rien pour leurs éléments majoritaires. Il ne faut donc rien changer, l'algorithme continue de fonctionner.

3.3.2

Explicitez en quelques phrases le fonctionnement de l'algorithme de la question précédente si, en entrée, on lui donne les deux exemples du début de l'énoncé.

Pour le premier exemple, le tableau [2, 4, 5, 4, 5, 4, 5, 4, 4] va être découpé en [2, 4, 5, 4] et en [5, 4, 5, 4, 4]. Le second tableau à un élément majoriaire, 4, qui est aussi un élément majoritaire du tableau initial.

Pour le second exemple, le tableau [2, 2, 3, 6, 4, 3, 2, 2, 3, 3, 2, 2] va être découpé en [2, 2, 3, 6, 4, 3] et en [2, 2, 3, 3, 2, 2].

Exercice 4 : Piles

4.1

Coder avec des listes de python la structure de pile. Vous coderez les fonctions :

• crée_pile_vide() -> list
• empile(x: int or None, pile: list)
• dépile(pile:list) -> int or None

On utilise des liste en python pour simuler des piles, avec les méthodes append et pop.

def crée_pile_vide():
    return []


def empile(x, pile):
    if x != None:
        pile.append(x)

def dépile(pile):
    if len(pile) > 0:
        x = pile.pop()
        return x
    else:
        return None

4.2.1

La valeur de $y$ à la ligne 6 est-elle une valeur de $P_1$ ? Et si oui, laquelle ?

Si $y$ est None c'est que la pile $P_1$ est vide et sinon $y$ vaut le dernier élément empilé.

4.2.2

Montrez qu'à chaque itération de la boucle for, $x$ est empilé soit dans $P_1$, soit dans $P_2$.

Il y a cinq cas possibles, mutuellement exclusifs :

• soit $y$ est None : $x$ est empilé dans $P_1$
• soit $y \neq x$ : $x$ est empilé dans $P_1$
• soit $y = x$ et la pile $P_2$ est vide : $x$ est empilé dans $P_2$
• soit $y = x$, la pile $P_2$ est non vide et on la dépile en $z$ et $z = x$ : $z$puis $x$ sont empilés dans $P_2$
• soit $y = x$, la pile $P_2$ est non vide et on la dépile en $z$ et $z \neq x$ : $z$ puis $x$ sont empilés dans $P_1$

4.2.3

Donnez le contenu des deux piles $P_1$ et $P_2$ à la fin de l'algorithme si, en entrée, on lui donne les deux exemples du début de l'énoncé.

• Pour $T = [2, 4, 5, 4, 5, 4, 5, 4, 4]$ on obtient :
  • $P_1 = [2, 4, 5, 4, 5, 4, 5, 4]$
  • $P_2=[4]$
• Pour $T = [2,2,3,6,4,3,2,2,3,3,2,2]$ on obtient :
  • $P_1 = [2, 3, 6, 4, 3, 2, 3, 2, 3, 2]$
  • $P_2 = [2, 2]$

4.2.4

Quelle est la complexité de l'algorithme ?

Puisqu'empiler et dépiler sont en $\mathcal{O}(1)$ opération, la complexité totale de l'algorithme est en $\mathcal{O}(len(T))$ opérations.

4.2.5

Montrez que tous les éléments de la pile $P_2$ sont identiques à la fin de l'algorithme.

On empile dans $P_2$ que si la pile était vide (le cas z == None) ou si le dernier élément de la pile est égal au nouvel élément (z == x). Tous les éléments de $P_2$ sont identiques.

4.2.6

Montrez qu'à la fin de l'algorithme, deux éléments consécutifs de la pile $P_1$ sont toujours différents.

On empile dans $P_1$ soit :

• dans le premier if. dans ce cas là, soit la pile était vide soit le dernier élément de la pile ($y$) est différent de $x$
• dans le second else. Dans ce cas là le denier élément de la pile ($y$) est différent de $x$ car on est dans le premier else et $z$ est différent de $x$ puisqu'on est dans le second else. On a donc $y \neq x \neq z$ et la proprété est vérifiée.

4.2.7

Déduisez-en qu'un élément majoritaire, s'il en existe, ne peut être que le dernier élément stocké dans $P_2$ ou le dernier élément stocké dans $P_1$.

Ala fin de l'algorithme, les éléments de $T$ sont répartis dans deux listes. La première, $P_1$, est alternée et la seconde, $P_2$, est composées d'éléments identiques.

Soit alors $x$ dans $P_1$ mais qui n'est pas dans $P_2$. Il ne peut apparaitre qu'au pire len(P1) // 2 + 1 fois dans $P_1$. On a alors plusieurs cas :

• $P_2$ n'est pas vide (et ne contient pas $x$). De là, $x$ est présent dans $T$ au mieux len(T) // 2. Ce ne peut être un élément majoritaire.
• $P_2$ est vide. Pour que $x$ soit un élément majoritaire de $T$ il faut qu'il apparaisse len(P1) // 2 + 1 dans $P_1$, donc que ce soit le dernier élément ajouté de $P_1$.

On en conclut que si $T$ possède un élément majoritaire, c'est :

• soit l'élément de $P_2$ si $P_2$ est non vide,
• soit le dernier élément de $P_1$ si $P_2$ est vide.

4.3.1

Déduisez de la partie précédente un algorithme linéaire en la taille du tableau en entrée pour résoudre le problème de l'élément majoritaire.

Entrées : Un tableau d'entiers T
Programme :
    Soient P1 et P2 les piles issuent de Majorité(T)
    x = dépile(P2)
    Si x == None:
        x = dépile(P1)
    
    si x == None ou si compte(T, x) <= len(T) // 2:
        return None
    return x

L'algorithme est exacte puisque'il implémente directement la question 4.2.7. Sa complexité est celle de l'exécution de l'algorithme Majorité plus celle de compte plus des instruction en $\mathcal{O}(1)$ : sa complexité totale est en $\mathcal{O}(n)$ où $n$ est la taille de $T$.

4.3.2

Quelle est la complexité du problème de l'élément majoritaire ?

L'algorithme de la question 4.3.1 résoud le problème de l'élément majoriaire en $\mathcal{O}(n)$ opérations et la quesion 1.2.4 a montré qu'il était en $\Omega(n)$, on en déduit donc que la complexité du problème est de $\Theta(n)$.