Aller au contenu

Algorithmes de référence 🎯

Les algorithmes marqués d'un ❤ sont à connaître sur le bout des doigts, les autres sont des classiques qu'il est bon d'avoir rencontré au moins une fois.

Tableaux dynamiques / listes Python⚓︎

Tous ces algorithmes prennet en entrée un tableau de \(n\) éléments de même type. On note \(C(n)\) le coût en opérations élémentaires de l'algorithme. Une opération est élémentaire si elle est de coût constant (comparaison de deux valeurs d'un des types de base, affectation etc ...)

Complexité logarithmique⚓︎

Définition

Une complexité logarithmique dans le pire des cas signifie qu'il existe une constante \(k\) telle que : \(C(n) \leqslant k \log(n)\). Il est équivalent de dire que le coût \(C(n)\) de l'algorithme est majoré par le produit d'une constante fois le nombre de chiffres de \(n\) (cela ne dépend pas de la base choisie).

C'est une complexité excellente !

Recherche dichotomique ❤
Entrée Précondition Sortie Spécification
Tableau d'entiers Trié dans l'ordre croissant Entier Renvoie l'indice d'une occurrence de elt dans tab ou \(-1\) sinon
Taille de l'entrée Complexité dans le pire des cas
tableau de \(n\) éléments logarithmique en \(O(\log(n))\)

Voir le mémo spécial Dichotomie.

🐍 Script Python
def recherche_dicho(tab, elt):
    g = 0
    d = len(tab) - 1
    while g <= d:
        # Invariant : tab[k] < elt si k < g  et t[k] > elt si k > d
        m = (g + d) // 2
        if tab[m] < elt:
            g = m + 1
        elif tab[m] > elt:
            d = m - 1
        else:
            return m
    return -1
🐍 Script Python
def dicho_rec(tab, elt, g, d):
    if g > d: # cas de base : zone de recherche vide
        return -1
    m = (g + d) // 2
    if tab[m] == elt:  # cas de base : élément trouvé
        return m
    elif tab[m] < elt:
        return dicho_rec(tab, elt, m + 1, d)
    else:  # sous-problème 2  tab[m] > elt:
        return dicho_rec(tab, elt, g, m - 1)


def recherche_dicho(tab, elt):
    return dicho_rec(tab, elt, 0, len(tab) - 1)

Complexité linéaire⚓︎

Définition

Une complexité linéaire dans le pire des cas signifie qu'il existe une constante \(k\) telle que : \(C(n) \leqslant k n\). Il est équivalent de dire que le coût \(C(n)\) de l'algorithme est majoré par le coût de la lecture de son entrée (à une constante près).

C'est une très bonne complexité !

Recherche linéaire ❤
Entrée Précondition Sortie Spécification
Tableau Non vide Booléen Détermine si elt appartient au tableau tab
Taille de l'entrée Complexité dans le pire des cas
tableau de \(n\) éléments linéaire en \(O(n)\)
🐍 Script Python
def recherche(tab, elt):
    for e in tab:
        if e == elt:
            return True
    return False
Recherche de maximum ❤
Entrée Précondition Sortie Spécification
Tableau Non vide Type d'élément de tableau Renvoie la valeur maximale du tableau tab
Taille de l'entrée Complexité dans le pire des cas
tableau de \(n\) éléments linéaire \(O(n)\)
🐍 Script Python
def maximum(tab):
    m = tab[0]
    for e in tab: # parcours par valeur
        if e > m:
            m = e
    return m
Positions du maximum ❤
Entrée Précondition Sortie Spécification
Tableau Non vide Tableau Renvoie la listes des positions du maximum de tab
Taille de l'entrée Complexité dans le pire des cas
tableau de \(n\) éléments linéaire en \(O(n)\)
🐍 Script Python
def pos_maximum(tab):
    lis = [0]
    m = tab[0]
    for k in range(len(tab)): # parcours par index
        if tab[k] > m:
            m = tab[k]
            lis = [k]
        elif tab[k] == m:
            lis.append(k)
    return lis
Conversion en base 2 d'un entier donné en base dix ❤
Entrée Sortie Spécification
Entier Tableau Renvoie le tableau des chiffres d'un entier en base 2, par bit de poids croissant de gauche à droite
Taille de l'entrée Complexité dans le pire des cas
Nombre de chiffres de l'entier \(n\) (peu importe la base) soit \(p=\log(n)\) le nombre de chiffres de \(n\) soit \(O(\log(n))=O(p)\), donc du même ordre de grandeur que l'entrée, donc linéaire
Attention

L'ordre de grandeur \(O(\log(n))\) peut nous inciter à classer naïvement cet algorithme parmi ceux de complexité logarithmique. Cependant l'ordre de grandeur de la taille de l'entrée n'est pas \(n\) mais le nombre de bits pour stocker l'entier en mémoire donc \(\log(n)\) à une constante près. Dans un ordinateur, la base de représentation choisie est la base 2 mais les nombres de chiffres dans deux bases distinctes sont proportionnels donc la taille de l'entrée ne dépend pas de la base et le coût de l'algorithme en opérations élémentaires, en \(O(\log(n))=O(p)\) est bien du même ordre de grandeur que celui de l'entrée \(p= \log(n)\), ce qui caractérise une complexité linéaire.

On collecte d'abord les bits de poids faibles, donc il faut renverser la liste de bits quand elle est complète.

🐍 Script Python
def decimal_vers_binaire(n):
    bits = []
    while n >= 2:
        bits.append(n % 2)
        n = n // 2
    bits.append(n)
    bits.reverse()
    return bits

On collecte un bit de poids plus faible dans la fonction que dans l'appel récursif mais en l'ajoutant à la fin de la liste renvoyée par l'appel récursif, il est à sa place.

🐍 Script Python
def decimal_vers_binaire_rec(n):
    if n < 2:
        return [n]
    rep = decimal_vers_binaire_rec(n // 2)
    rep.append(n % 2)
    return rep
Rendu de monnaie glouton ❤
Entrée Précondition Sortie Spécification
Somme à rendre et tableau des valeurs des pièces disponibles Aucune Tableau Renvoie le tableau des pièces dont la somme égale celle qu'il faut rendre

La complexité dépend de la somme à rendre et des pièces disponibles, en particulier de la valeur minimale de pièce. Dans le pire ces cas, le nombre d'opérations sera majoré par le quotient de la somme à rendre par la valeur minimale de pièce.

⚠️ on suppose que le rendu exact est possible avec les valeurs des pièces disponibles et qu'on dispose d'un nombre infini de pièces de chaque valeur.

🐍 Script Python
def rendu_glouton(restant, pieces):
    # pieces tableau de valeurs de pièces disponibles dans l'ordre croissant
    indice_pieces = len(pieces) - 1
    rendu = []
    while restant > 0 and  indice_pieces >= 0:
        if pieces[indice_pieces] <= restant:
            restant = restant - pieces[indice_pieces]
            rendu.append(pieces[indice_pieces])
        else:
            indice_pieces = indice_pieces - 1
    # rendu possible
    return rendu
🐍 Script Python
def rendu_rec(restant, pieces, indice_pieces):
    # pieces contient les valeurs des pièces disponibles par ordre croissant
    if restant == 0:
        return []
    if pieces[indice_pieces] <= restant:
        rep = rendu_rec(restant - pieces[indice_pieces], pieces, indice_pieces)
        rep.append(pieces[indice_pieces])                
    else:
        rep = rendu_rec(restant, pieces, indice_pieces - 1)
    return rep

def rendu_glouton(restant, pieces):
    return rendu_rec(restant, pieces, len(pieces) - 1)
Fusion de deux tableaux triés dans l'ordre croissant ❤
Entrée Précondition Sortie Spécification
Deux tableaux Triés dans l'ordre croissant Tableau Fusionne les deux tableaux dans un nouveau tableau trié
Taille de l'entrée Complexité dans le pire des cas
tableaux de \(n_{1}\) et \(n_{2}\) éléments linéaire en \(O(n_{1} + n_{2})\)
🐍 Script Python
def fusion(tab1, tab2):
    i1 = 0
    i2 = 0
    tab3 = []
    while i1 < len(tab1) and i2 < len(tab2):
        if tab1[i1] <= tab2[i2]:
            tab3.append(tab1[i1])
            i1 += 1
        else:
            tab3.append(tab2[i2])
            i2 += 1
    while i1 < len(tab1):
        tab3.append(tab1[i1])
        i1 += 1
    while i2 < len(tab2):
        tab3.append(tab2[i2])
        i2 += 1
    return tab3                 
🐍 Script Python
def fusion2(tab1, tab2):
    i1 = 0
    i2 = 0
    tab3 = []
    while i1 < len(tab1) or i2 < len(tab2):
        if (i1 == len(tab1)) or (i2 < len(tab2) and tab2[i2] < tab1[i1]):
            tab3.append(tab2[i2])
            i2 += 1
        else:
            tab3.append(tab1[i1])
            i1 += 1
    return tab3

Complexité quadratique⚓︎

Définition

Une complexité quadratique dans le pire des cas signifie qu'il existe une constante \(k\) telle que : \(C(n) \leqslant k n^{2}\).

C'est une complexité acceptable uniquement pour de petites valeurs de \(n\) (inférieures à 1000).

Tri par sélection ❤
Entrée Précondition Sortie Spécification
Tableau Non vide Rien Trie en place tab dans l'ordre croissant
Taille de l'entrée Complexité dans le pire des cas (dans tous les cas en fait)
tableau de \(n\) éléments quadratique en \(O(n^{2})\)
🐍 Script Python
def tri_selection(tab):
    for i in range(len(tab)):
        imin = i
        for j in range(i + 1, len(tab)):
            if tab[i] < tab[imin]:
                imin = i
        tmp = tab[i]
        tab[i] = tab[imin]
        tab[imin] = tmp
Tri par insertion ❤
Entrée Précondition Sortie Spécification
Tableau Non vide Rien Trie en place tab dans l'ordre croissant
Taille de l'entrée Complexité dans le pire des cas Complexité dans le cas moyen Complexité dans le meilleur des cas
tableau de \(n\) éléments quadratique en \(O(n^{2})\) si tab dans l'ordre décroissant quadratique en \(O(n^{2})\) linéaire en \(O(n)\) si tab déjà dans l'ordre croissant
🐍 Script Python
def tri_insertion(tab):
    for i in range(1, len(tab)):
        elt = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > elt:
            tab[j + 1] = tab[j]
            j = j - 1
        tab[j + 1] = elt
🐍 Script Python
def tri_insertion(tab):
    for i in range(1, len(tab)):
        elt = tab[i]
        j = i
        while j > 0 and tab[j - 1] > elt:
            tab[j] = tab[j - ]
            j = j - 1
        tab[j] = elt

Comparaison des algorithmes de tri classiques

La complexité en temps du tri fusion d'un tableau de taille \(n\) est linéarithmique, en \(O(n \log_{2}(n))\).

Cette complexité est optimale pour les tris par comparaison de deux éléments.

Le tri fusion est plus efficace que les algorithmes de tri vus en classe de première qui sont de complexité quadratique, en \(O(n^{2})\). Le tri rapide est un autre algorithme Diviser pour Régner, très efficace. L'implémentation, plus délicate, sera vue en TP.

Algorithme de tri d'un tableau de taille \(n\) Complexité dans le meilleur des cas Complexité dans le cas moyen Complexité dans le pire des cas
tri par sélection \(O(n^{2})\) \(O(n^{2})\) \(O(n^{2})\)
tri par insertion \(O(n)\) (tableau déjà trié) \(O(n^{2})\) (ordre inverse) \(O(n^{2})\)
tri par bulles \(O(n^{2})\) \(O(n^{2})\) \(O(n^{2})\)
tri fusion \(O(n\log_{2}(n))\) \(O(n\log_{2}(n))\) \(O(n\log_{2}(n))\)
tri rapide \(O(n\log_{2}(n))\) \(O(n\log_{2}(n))\) \(O(n^{2})\) (tableau déjà trié)

alt

Source : https://www.hackerearth.com/practice/notes/sorting-and-searching-algorithms-time-complexities-cheat-sheet/

Dictionnaires⚓︎

Complexité linéaire⚓︎

Histogramme d'une chaîne de caractères ❤
Entrée Précondition Sortie Spécification
Chaîne de caractères Non vide Dictionnaire Renvoie le dictionnaire des occurrences des caractères dans la chaîne
Taille de l'entrée Complexité dans le pire des cas
Chaîne de \(n\) éléments linéaire en \(O(n)\)
🐍 Script Python
def histogramme(chaine):
    histo = dict()
    for c in chaine:
        if c in histo:
            histo[c] = histo[c] + 1
        else:
             histo[c] = 1
    return histo

Listes chaînées⚓︎

Complexité linéaire⚓︎

Longueur d'une liste chaînée ❤
Entrée Précondition Sortie Spécification
Liste chaînée Non vide Entier Renvoie la longueur d'une liste chaînée
Taille de l'entrée Complexité dans le pire des cas (et dans tous les cas)
liste chaînée de \(n\) éléments linéaire en \(O(n)\)

On donne un code avec une liste chaînée non mutable implémentée par des tuples et une interface fonctionnelle du type Liste.

🐍 Script Python
def longueur(lis):
    if liste_vide(lis):
        return 0
    return 1 + longueur(queue(lis))
🐍 Script Python
def longueur(lis):
    lon = 0
    courant = lis  # élément en tête
    while not liste_vide(courant):
        # si besoin traitement sur tete(courant)
        lon = lon + 1 
        courant = queue(courant)
    return lon

Piles⚓︎

Complexité linéaire⚓︎

Somme des éléments d'une pile ❤
Entrée Précondition Sortie Spécification
Pile Non vide Entier Renvoie la somme des éléments d'une pile d'entiers et reconstruit la pile initiale
Taille de l'entrée Complexité dans le pire des cas (et dans tous les cas)
pile de \(n\) éléments linéaire en \(O(n)\)

On donne un code avec une pile implémentée dans une interface objet.

🐍 Script Python
def somme_pile(p):
    s = 0
    tmp = Pile()
    while not p.pile_vide():
        x = p.depiler()
        s = s + x
        tmp.empiler(x)
    # on reconstruit la pile initiale
    while not tmp.pile_vide():
        x = tmp.depiler()
        p.empiler(x)
    return s            

Files⚓︎

Complexité linéaire⚓︎

Inverser une file avec une pile
Entrée Précondition Sortie Spécification
File Non vide File Renvoie une autre file aves les éléments dans l'ordre inverse
Taille de l'entrée Complexité dans le pire des cas (et dans tous les cas)
file de \(n\) éléments linéaire en \(O(n)\)

On donne un code avec une file et une pile implémentées dans des interfaces objets.

🐍 Script Python
def inverser_file(f):
    p = Pile()
    tmp = File()
    while not f.file_vide():
        x = f.defiler()
        p.empiler(x)
        tmp.enfiler(x)        
    finv = File()
    while not p.pile_vide():
        x = p.depiler()
        finv.enfiler(x)
    # on reconstruit la file initiale
     while not tmp.file_vide():
        x = tmp.defiler()
        f.enfiler(x)
    return finv           

Arbres binaires⚓︎

Complexité linéaire (par rapport à la taille de l'arbre)⚓︎

Taille d'un arbre binaire ❤
Entrée Précondition Sortie Spécification
Arbre binaire Aucune Entier Renvoie le nombre de noeuds stockés dans l'arbre

Avec une classe Noeud, l'arbre binaire vide représenté par None et une interface fonctionnelle. Pour l'interface voir le cours

🐍 Script Python
def taille(arbre):
    """Renvoie la taille de l'arbre"""
    if arbre is None:
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droit)

Avec une classe AB d''arbre binaire qui utilise une classe Noeud. Pour l'interface voir le cours.

⚠️ Bien lire l'interface, c'est-à-dire la définition des attributs et des méthodes de la classe avant de coder.

🐍 Script Python
def taille(self):
    """Renvoie la hauteur de l'arbre"""
    if self.est_vide():
        return 0
    return 1 + self.gauche().taille() + self.droit().taille()
Hauteur d'un arbre binaire ❤
Entrée Précondition Sortie Spécification
Arbre binaire Aucune Entier Renvoie le nombre de noeuds sur le plus long chemin entre la racine et une feuille

alt

Avec une classe Noeud, l'arbre binaire vide représenté par None et une interface fonctionnelle. Pour l'interface voir le cours

🐍 Script Python
def hauteur(arbre):
    """Renvoie la hauteur de l'arbre"""
    if arbre is None:
        return 0
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

Avec une classe AB d''arbre binaire qui utilise une classe Noeud. Pour l'interface voir le cours

⚠️ Bien lire l'interface, c'est-à-dire la définition des attributs et des méthodes de la classe avant de coder.

🐍 Script Python
def hauteur(self):
    """Renvoie la hauteur de l'arbre"""
    if self.est_vide():
        return 0
    return 1 + max(self.gauche().hauteur(), self.droit().hauteur())
Parcours en profondeur d'un arbre binaire ❤
Entrée Précondition Sortie Spécification
Arbre binaire Aucune Dépend du traitement sur les noeuds Parcourt tous les noeuds de l'arbre depuis la racine en explorant d'abord les enfants (gauche puis droite)

alt

Selon l'ordre de traitement du noeud par rapport au parcours des sous-arbres, on distingue trois types de parcours en profondeur.

Les codes sont donnés pour des arbres binaires représentés avec une classe Noeud, l'arbre binaire vide représenté par None et une interface fonctionnelle.

Dans le parcours en profondeur préfixe, on traite l'élément stocké dans le noeud avant de parcourir les sous-arbres.

🐍 Script Python
def parcours_prefixe(arbre):
    if arbre is None: # cas de l'arbre vide
        return 
    traitement(arbre.racine) # on traite le noeud racine
    parcours_prefixe(arbre.gauche) # on parcourt récursivement le fils gauche
    parcours_prefixe(arbre.droit) # on parcourt récursivement le fils droit

Pour l'arbre binaire donné en exemple, avec un parcours préfixe, l'ordre de traitement des éléments stockés serait :

📋 Texte
A - L - O - R - G - I - T - M - E - H

Dans le parcours en profondeur infixe, on taite l'élément stocké dans le noeud entre le parcours du sous-arbre/fils gauche et le parcours du sous-arbre/fils droit.

🐍 Script Python
def parcours_infixe(arbre):
    if arbre is None: # cas de l'arbre vide
        return                
    parcours_infixe(arbre.gauche) # on parcourt récursivement le fils gauche
    traitement(arbre.racine) # on traite le noeud racine
    parcours_infixe(arbre.droit) # on parcourt récursivement le fils droit

Pour l'arbre binaire donné en exemple, avec un parcours infixe, l'ordre de traitement des éléments stockés serait :

📋 Texte
O - L - R - A - G - M - T -  E - I - H

Dans le parcours en profondeur suffixe appelé aussi parcours en profondeur postfixe, on taite l'élément stocké dans le noeud après le parcours du sous-arbre/fils gauche et le parcours du sous-arbre/fils droit.

🐍 Script Python
def parcours_postfixe(arbre):
    if arbre is None: # cas de l'arbre vide
        return                
    parcours_postfixe(arbre.gauche) # on parcourt récursivement le fils gauche
    parcours_postfixe(arbre.droit) # on parcourt récursivement le fils droit
    traitement(arbre.racine) # on traite le noeud racine

Pour l'arbre binaire donné en exemple, avec un parcours postfixe, l'ordre de traitement des éléments stockés serait :

📋 Texte
O - R - L - M - E - T - H - I - G - A
Parcours en largeur d'un arbre binaire ❤
Entrée Précondition Sortie Spécification
Arbre binaire Aucune Dépend du traitement sur les noeuds Parcourt tous les noeuds de l'arbre depuis la racine en explorant d'abord les frères (de gauche à droite)

alt

On commence par enfiler l'arbre (s'il est non vide), puis tant que la file n'est pas vide :

  • on défile l'arbre en tête de file ;
  • on traite l'élément stocké dans le noeud racine puis on enfile les fils/sous-arbres (gauche puis droite) s'ils existent.

On donne un code avec interface fonctionnelle pour arbre binaire et file.

🐍 Script Python
    def parcours_largeur(arbre):
        f = creer_file()
        if arbre is not None:
            enfiler(f, arbre)
        while not file_vide(f):
            a = defiler(f)
            traitement(a.racine)
            if a.gauche is not None:
                f.enfiler(a.gauche)
            if a.droit is not None:
                f.enfiler(a.droit)

Arbres binaires de recherche⚓︎

Complexité logarithmique (par rapport à la taille de l'arbre)⚓︎

Recherche d'un élément dans un arbre binaire de recherche ❤

Le nombre de comparaisons effectuées lors de la recherche d'un élément dans un arbre binaire est au plus égal au nombre de noeuds dans le plus long chemin reliant la racine à une feuille. La complexité en temps de la recherche est donc majorée par une constante fois la hauteur de l'arbre binaire de recherche. On rappelle que la hauteur \(h\) d'un arbre binaire de taille \(n\) vérifie l'inégalité \(\log_{2}(n)< h \leqslant n\). La complexité en temps de la recherche dans un arbre binaire de recherche dépend donc de la forme de l'arbre, avec deux cas extrêmes :

  • Pire forme : dans un arbre binaire dégénéré, par un exemple un peigne, on aura une complexité linéaire en \(O(n)\) comme pour une recherche séquentielle dans une liste chaînée.
  • Meilleure forme : dans un arbre binaire presque complet ou parfait, on aura une complexité logarithmique, en \(O(\log_{2}(n))\) donc bien meilleure.
Forme de l'arbre binaire Complexité de la recherche d'un élément par rapport à la taille
dégénéré linéaire
presque complet ou parfait logarithmique
🐍 Script Python
def recherche(abr, elt):
    """Renvoie un booléen indiquant si elt est stocké dans un noeud 
    de l'arbre binaire de recherche abr
    """
    if est_vide(abr):
        return False
    elif elt < abr.element:
        return recherche(abr.gauche, elt)
    elif elt > abr.element:
        return recherche(abr.droit, elt)
    else:
        return True
🐍 Script Python
def recherche(self, elt):
    """Renvoie un booléen indiquant si elt est stocké dans un noeud 
    de l'arbre binaire de recherche self de la classe ABR
    """
    if self.est_vide():
        return False
    elif elt < self.element_racine():
        return self.gauche().recherche(elt):
    elif elt > abr.element:
        return self.droit().recherche(elt):
    else:
        return True
Ajout d'un élément dans un arbre binaire de recherche ❤

Pour ajouter un élément dans un arbre binaire présentant la propriété d'arbre binaire de recherche on effectue la même descente dans l'arbre que pour la recherche. Deux situations finales sont possibles :

  • Situation 1 : on atteint un arbre dont le noeud racine contient déjà l'élément stocké, dans ce cas :
    • si on ne veut pas de doublons dans l'arbre binaire initial : on termine sans rien faire
    • si on accepte les doublons dans l'arbre binaire initial : on poursuit alors l'ajout dans le fils/sous-arbre gauche
  • Situation 2 : on atteint un arbre vide :
    • on crée alors à cet emplacement libre un arbre binaire dont le noeud racine contient l'élément
Forme de l'arbre binaire Complexité de l'ajout d'un élément par rapport à la taille
dégénéré linéaire
presque complet ou parfait logarithmique
🐍 Script Python
def ajoute(abr, elt):
    """Renvoie un nouvel arbre binaire de recherche construit par ajout de  elt comme feuille dans l'arbre binaire de recherche abr
    """
    if abr is None:
        return Noeud(None, elt, None)
    elif elt <= abr.element:
        return Noeud(ajoute(abr.gauche, elt), abr.element, abr.droit)
    else:
        return Noeud(abr.gauche, abr.element, ajoute(abr.droit, elt))
🐍 Script Python
def ajoute(self, elt):
    """Ajoute elt dans une feuille de l'arbre binaire de recherche
    Maintient la propriété d'arbre binaire de recherche."""
    if self.est_vide():
        self.racine = Noeud(ABR(), elt, ABR())
    elif elt <= self.element_racine():
        self.gauche().ajoute(elt)
    else:
        self.droit().ajoute(elt)