Algorithmes classiques

Cours/Algorithmie/Algorithmes classiques

Prérequis :

Algorithmes classiques dont l'intérêt est à la fois esthétique (ce sont de jolis algorithmes),pratiques (ils mettent en oeuvre des techniques facilement réutilisables) et didactiques (trouver et prouver leurs fonctionnement vous fera progresser).

Pour tous ces exercices, si la structure de donnée n'est pas précisé, vous utiliserez des listes.

Dichotomie

Utilité : brique de base à connaître par cœur

Difficulté : trivial

On l'a déjà vu. Uniquement un rappel car fondamental.

Fibonacci

Utilité : à connaître car :

exemple de transformation d'un algo de complexité exponentiel à linéaire.

un algo dont la complexité vaut son retour dans le cas récursif simple

Difficulté : facile pour la création et la complexité de base

On l'a déjà vu. Uniquement un rappel.

Triangle de Pascal

On a déjà vu les 2 premiers. Le troisième est un peu plus compliqué

Rappel

Utilité : à connaître car exercice classique réduction de complexité spatiale.

Difficulté : facile

Optimisé

Utilité : classique d'optimisation

Difficulté : moyen.

Triangle de Pascal : complexité spatiale minimale

Suppression d'éléments

Suppression de valeurs

Utilité : utilisation d'une liste

Difficulté : facile.

On a déjà vu comment faire avec un tableau.

Tableau

Liste

Regardons comment tout ceci peut fonctionner avec une liste :

Suppression de valeurs

Suppression de doublons

Utilité : classique et simple.

Difficulté : facile

Suppression des doublons

Complexité

Exercices de base de complexité. Il est important de les connaître pour éviter les fautes idiotes.

Erreur bête

Utilité : crucial à comprendre

Difficulté : moyen

Noob trap

$X$ marks the spot

Utilité : crucial à comprendre

Difficulté : dur

Un robot se déplace sur une droite d'une unité par unité. Il doit chercher un endroit particulier sur cette droite à $X$ unités de 0, $X$ pouvant être positif ou négatif. Cette endroit est inconnu pour le robot, mais s'il passe sur cet endroit il le reconnaîtra.

Donnez un algorithme en $\mathcal{O}(X)$ permettant au robot d'atteindre $X$ à partir de sa position initiale qui vaut $0$.

corrigé

Remarquer que l'on ne peut pas :

avancer uniquement dans une direction : il faut osciller
osciller en incrémentant d'un pas constant : on est de complexité au carré de $X$ (c'est facile à montrer)

L'idée est d'osciller autour de l'origine en puissances de 2 :

avancer de $2^0 = 1$ : position finale $+1$
reculer de $2^0 + 2^0$ : position finale $-1$
avancer de $2^0 + 2^1$ : position finale $+2$
reculer de $2^1 + 2^1$ : position finale $-2$
avancer de $2^1 + 2^2$ : position finale $+4$
reculer de $2^2 + 2^2$ : position finale $-4$
avancer de $2^2 + 2^3$ : position finale $+8$
reculer de $2^3 + 2^3$ : position finale $-8$
...

Au pire, le robot arrivera sur la marque $X$ au bout de $2 \cdot \log_2(X)$ itérations.

Il aura effectué un déplacement d'au plus : $2 \cdot (X + X/2 + X/4 + \dots + 1)$ unités. Or $2 \cdot (X + X/2 + X/4 + \dots + 1) = 2\cdot X \cdot \sum_{i=0}^{i=\log_2(X)} 1/2^i = 2\cdot X \cdot(1- 1/2^{\log_2(X)}) = \mathcal{O}(X)$.

L'astuce de se déplacer par puissance de 2 permet de majorer la distance par $X$ car la série des $\sum 1/2^i$ est convergente. Il est crucial de connaître cette technique qui vous tirera de nombreux mauvais pas en algorithmie.

Équations de récurrence

Quelques équations de récurrences sont à connaître car elles donnent de complexités très différentes.

Que vaut $C(n)$ si :

$$ C(n) = \mathcal{O}(1) + C(n - K) $$

corrigé

TBD $C(n) = \mathcal{O}(n)$

Que vaut $C(n)$ si :

$$ C(n) = \mathcal{O}(n) + C(n - K) $$

corrigé

TBD $C(n) = \mathcal{O}(n^2)$

Que vaut $C(n)$ si :

$$ C(n) = \mathcal{O}(1) + C(\frac{n}{2}) $$

corrigé

TBD $C(n) = \mathcal{O}(\ln(n))$

Que vaut $C(n)$ si :

$$ C(n) = \mathcal{O}(n) + C(\frac{n}{2}) $$

corrigé

TBD $C(n) = \mathcal{O}(n)$

Que vaut $C(n)$ si :

$$ C(n) = \mathcal{O}(1) + 2\cdot C(\frac{n}{2}) $$

corrigé

TBD $C(n) = \mathcal{O}(n)$

Que vaut $C(n)$ si :

$$ C(n) = \mathcal{O}(n) + 2\cdot C(\frac{n}{2}) $$

corrigé

TBD $C(n) = \mathcal{O}(n\ln(n))$

Tours de Hanoï

Utilité : classique parmi les classique. La preuve que la complexité est minimale est à connaître

Difficulté : moyen

Tours de Hanoi

Compteur binaire

Utilité : algorithme à la base de nombreux autres algorithme d'énumération.

Difficulté : moyen

Compteur binaire

Col de listes

Utilité : à connaître car un classique des concours (on le donne sans indications...)

Difficulté : moyen

Cols de listes et de matrices

Tris

Utilité : tris pouvant être utile dans des cas particuliers et surtout à la base de nombreux pièges

Difficulté : moyen

Des tris utiles dans des cas spécifiques, et dont la complexité semble plus petite que $n\log(n)$. Connaître pourquoi ce n'est (bien sur) pas le cas.

Tris spéciaux

Min et max d'un tableau d'entiers

Utilité : une optimisation élégante et une astuce utile à garder dans sa poche, car elle se retrouve dans plusieurs algorithmes optimaux classiques.

Difficulté : moyen

Un algo

Donnez un algorithme avec $T.\mbox{\small longueur} - 1$ comparaisons permettant de trouver le minimum d'un tableau d'entier.

Que faut-il modifier pour trouver le maximum ?

corrigé

TBD simple

Complexité du Problème

Montrer que si l'on cherche à trouver l'élément minimum d'un tableau d'entiers $T$ il faut au moins $T.\mbox{\small longueur} - 1$ comparaisons

corrigé

TBD graphe connexe.

On veut minimiser le nombre de comparaisons dans la recherche d'un élément min et max d'un tableau.

Une astuce

Montrer que si l'on cherche à trouver à la fois le minimum et le maximum d'un tableau d'entiers $T$, on peut s'en sortir avec $3/2 \cdot T.\mbox{\small longueur} - 1$ comparaisons.

corrigé

Si on fait les deux à la suite on a 2n comparaisons.

On commence par trier les éléments $T[i]$ et $T[i+1]$ pour tout $i$ ($n/2$ comparaisons)

Puis on cherche le min sur les $T[2i]$ ($n/2$ comparaisons) et le max sur les $T[2i +1]$ ($n/2$ comparaisons)

Piles

Utilité : les piles ça sert toujours. Ces exercices vous montrerons des cas classiques d'utilisation

Difficulté : moyen

File avec pile

On reprend l'exercice sur la création d'une file avec 2 piles.

Montrer que la complexité amortie d'ajout et de suppression d'un élément dans la structure de file créée avec 2 pile est en $\mathcal{O}(1)$

corrigé

On procède comme pour le compteur, on associe une complexité amortie de +2 lorsque l'on empile dans P1 et de 0 lorsque l'on empile dans P2.

Parenthésage

Soit $C$ une expression arithmétique avec des parenthèses et des crochets. On cherche à savoir si le parenthésage est équilibré :

[3 + 3 * (1 + 3)] sera Ok
[3 + 3 * (1 + 3]) sera pas Ok

On ne vérifiera pas que l'expression est arithmétiquement correcte, c'est à dire que pour nous, [3 + + 3 (1 + 3)] sera Ok.

Montrer que l'on peut utiliser une pile pour savoir si un parenthésage est équilibré entre les () et les [].

corrigé

algorithme parenthèse(C):
    P ← une nouvelle pile de caractères
    pour chaque c de C:
        si c == "(" ou c == "[":
            P.empile(c)
        sinon si c == ")":
            si P.vide() ou P.dépile() ≠ "(":
                rendre Faux
        sinon si c == "]":
            si P.vide() ou P.dépile() ≠ "[":
                rendre Faux
    rendre Vrai

Calcul d'une expression avec deux piles

Soit $C$ une expression arithmétique avec uniquement des parenthèses, des + et des *. On suppose qu'elle est arithmétiquement correcte, comme (3 + 3 * (1 + 3))

Montrer que l'on peut utiliser deux piles (une pour les opérateurs et les parenthèses et l'autre pour les nombres) pour calculer $C$.

corrigé

Il faut faire attention au fait que * a une priorité supérieure à + : 3 + 4 * 3 = 15.

On lit l'expression de gauche à droite :

si le caractère lu est un nombre on le place dans la pile P2
sinon si le caractère lu est un opérateur O :
1. on évalue l'expression comme on la fait avec la notation polonaise inversée :
  1. pop de P1 dans op
  2. pop de p2 dans y
  3. pop de p2 dans x
  4. x op y = z
  5. push de z dans P2
2. jusqu'à ce que :
  1. P1 est vide ou
  2. l'opérateur O a une priorité supérieure à celle sur P1
3. place O dans P1
sinon si le caractère lu est une parenthèse ouvrante : on la place dans P1
sinon si le caractère lu est une parenthèse fermante :
1. on évalue l'expression jusqu'à trouver une parenthèse ouvrante
2. on push le résultat dans P2

Si on a fini de lire l'expression on évalue le reste des deux piles.

à 9min13 https://www.youtube.com/watch?v=2vBVvQTTdXg

2-sum et 3-sum

Utilité : un classique des concours !

Difficulté : dur

TBD un classique des concours, sans aucune indications bien sur.

3-SUM est la base de bien d'autres problèmes. On en reparlera bien plus tard, mais ce problème est une des bases algorithmique de la géométrie algébrique.

2-SUM

Problème

nom : 2-SUM
données : Un tableau T d'entiers relatifs
question : Existe-t-il deux indices $i$ et $j$ (ils peuvent être égaux) tels que $T[i] + T[j] = 0$ ?

On a déjà vu une variante de ce problème lorsque l'on a étudié les dictionnaires. Si vous ne vous en rappelez plus, refaites le :

Exercice fondamental des dictionnaires

Regardons maintenant ce problème d'un point de vue complexité spatiale et temporelle.

Donnez une solution au problème 2-SUM avec comme complexité :

temporelle de $\mathcal{O}(T.\mbox{\small longueur}^2)$
spatiale en $\mathcal{O}(1)$

corrigé

TBD : brute force

Donnez une solution au problème 2-SUM avec comme complexité :

temporelle de $\mathcal{O}(T.\mbox{\small longueur}\ln(T.\mbox{\small longueur}))$
spatiale en $\mathcal{O}(T.\mbox{\small longueur})$

corrigé

TBD : tri

Donnez une solution au problème 2-SUM avec comme complexité :

temporelle de $\mathcal{O}(T.\mbox{\small longueur})$ en moyenne
spatiale en $\mathcal{O}(T.\mbox{\small longueur})$

corrigé

TBD : dictionnaire

Un nouvel algorithme :

Donnez une solution au problème 2-SUM avec comme complexité $\mathcal{O}(\max(T))$.

Est-ce réaliste ?

corrigé

TBD : bucket sort de la valeur absolue. Dès que l'on rencontre la case la deuxième fois on sort. TBD attention : même si on ne visite pas toutes les cases du tableau il faut les initialiser à 0 (le contenu de la mémoire est inconnu à l'affectation).

TBD complexité spatiale $\mathcal{O}(\max(T))$ ce qui est déraisonnable car cela peut être aussi grand que l'on veut. TBD c'est même exponentiel en la taille du tableau ($\log_2(n)$ bits pour stocker l'entier $n$). TBD : même si la complexité de créer un tableau de taille arbitraire est en $\mathcal{O}(2)$, et que l'on ne fait de boucle que sur la taille du tableau, l'algorithme est tout de même en $\mathcal{O}(\max(T))$ car il faut initialiser les cases : à la création d'un tableau ses valeurs sont indéterminées.

3-SUM

Problème

nom : 3-SUM
données : Un tableau T d'entiers relatifs
question : Existe-t-il trois indices $i$, $j$ et $k$ (ils peuvent être égaux) tel que $T[i] + T[j] + T[k] = 0$ ?

Donnez une solution au problème 3-SUM avec comme complexité :

temporelle de $\mathcal{O}(T.\mbox{\small longueur}^3)$
spatiale en $\mathcal{O}(1)$

corrigé

TBD : brute force

Donnez une solution au problème 3-SUM avec comme complexité :

temporelle de $\mathcal{O}(T.\mbox{\small longueur}^2)$ en moyenne
spatiale en $\mathcal{O}(T.\mbox{\small longueur})$

corrigé

TBD : dictionnaire

Le dictionnaire est souvent la meilleure réponse en moyenne, mais ce n'est pas le cas avec un 3-SUM :

Donnez une solution au problème 3-SUM avec comme complexité :

temporelle de $\mathcal{O}(T.\mbox{\small longueur}^2)$
spatiale en $\mathcal{O}(T.\mbox{\small longueur})$

corrigé

TBD : un tri puis on cherche en $\mathcal{O}(T.\mbox{\small longueur})$ s'il existe i et j pour lesquels $T[i] + T[j] = -T[k]$ pour k allant de 0 à la taille du tableau ($\mathcal{O}(T.\mbox{\small longueur})$ boucles)

Chaînes de caractères

Utilité : classique mais pas indispensable

Difficulté : ?

Chaines de caractères

Suites de caractères

créer toutes les suite de caractères possibles. TBD On commence par afficher le tout

0/1

TBD on utilise une fonction auxiliaire récursive comme pour ds 1 2025

Alphabet

TBD on généralise

liste

TBD On stocke dans une liste.

variable globale hors algo

abec une liste et des appends

Algorithmes classiques

Dichotomie

Fibonacci

Triangle de Pascal

Rappel

Optimisé

Suppression d'éléments

Suppression de valeurs

Tableau

Liste

Suppression de doublons

Complexité

Erreur bête

$X$ marks the spot

Équations de récurrence

Tours de Hanoï

Compteur binaire

Col de listes

Tris

Min et max d'un tableau d'entiers

Un algo

Complexité du Problème

Une astuce

Piles

File avec pile

Parenthésage

Calcul d'une expression avec deux piles

2-sum et 3-sum

2-SUM

3-SUM

Chaînes de caractères

Suites de caractères

0/1

Alphabet

liste

Autres séries d'exercices