Chapitre 14 : Algorithmique

Algorithme

Que veut dire « Savoir programmer » ?

L'informatique a pour objectif de faire réaliser par une machine des tâches répétitives de façon automatique. Face à cela, plusieurs questions se posent et notamment celle de la communication avec l'ordinateur. Rappelons en effet que l'ordinateur ne manipule que des 0 et des 1 (le binaire est le langage avec le plus bas niveau d'abstraction) tandis que l'être humain peut exprimer ses idées à l'aider de phrases complexes (plus haut niveau d'abstraction).

Exemple de programmation :

Demander un entier et l'affecter à age
si age est inférieur à 18 alors
    répondre "Vous êtes mineur."
sinon
    répondre "Vous êtes majeur."

age = input("Quel est votre âge ?")
if int(age) < 18:
    print("Vous êtes mineur.")
else:
    print("Vous êtes majeur.")
    

var age = prompt("Quel est votre âge ?");
if (age < 18) {
  alert("Vous êtes mineur.");
} else {
  alert("Vous êtes majeur.");
}

001010001010001000011101110010100010100110101011
100110010010100101010010010101001111011010101101
000101010100101001001010010101110110100101001010
010111101101010111010101001010111111111111110001

Complexité d'un algorithme

La rapidité d'un ordinateur dans l'exécution d'un algorithme dépend de la fréquence de calcul de son processeur, mais aussi de la complexité de l'algorithme utilisé.

La complexité (temporelle) d'un algorithme est le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées. Ce nombre s'exprime en fonction de la taille n des données à traiter et permet d'estimer le coût en calcul d'un algorithme. Cette fonction est notée sous la forme O(n) « grand O de n » et indique en quelque sorte « l'ordre de grandeur » de la complexité de l'algorithme.

Définir la complexité d'un algorithme permet de le comparer aux autres afin de déterminer lequel est le plus performant.

La recherche de l'algorithme ayant la plus faible complexité, pour résoudre un problème donné, fait partie du travail régulier de l'informaticien. Il est aidé pour cela par les mathématiciens.

Remarques :

• Un algorithme de complexité linéaire `O(n)` nécessite un nombre d'opérations proportionnel à la quantité de données (taille du problème) : `n`.
• Un algorithme de complexité quadratique `O(n^2)` nécessite un nombre d'opérations proportionnel au carré de la quantité de données : `n^2`.
• Vous rencontrerez également des complexités constantes `O(1)`, linéarithmiques `O(n*log(n))` ou exponentielles `O(2^n)`.

Un algorithme de complexité linéaire est plus performant qu'un algorithme de complexité quadratique.

Retrouver les différents types de complexité sur : Analyse de la complexité des algorithmes (Wikipédia)

print("Hello world!")
      

for element in liste : # liste contient n éléments
    ...
      

for element in liste : # liste contient n éléments
    for element in liste :
        ...
      

for i in range(len(liste)) :  # liste contient n éléments
    for element in liste[i+1:] :
        ...
      

def fibo(n) :
    """ Calcul du n-ième terme de la suite de fibonaci par une méthode récursive"
    if n <= 1:     # Cas triviaux (multiple)
        return n
    else:          # Cas récursif double
        return fibo(n-2) + fibo(n-1)
      

Preuve d'un algorithme

Pour tester si vos programmes fonctionnent, vous le testez avec quelques exemples. Or, vous savez que mathématiquement et d'un point de vue logique, un exemple ne suffit souvent pas à constituer une preuve générale. Le nombre de tests à réaliser pour prouver un programme devrait être infini. Ce qui est dans la pratique impossible.

Pourquoi s'assurer de la preuve du bon fonctionnement d'un algorithme ? Il existe malheureusement des exemples où une erreur informatique a pu coûter cher, en matériel (explosion de Ariane 5 en 1996) et parfois en vies humaines (crash du Boeing 737 Max en 2018). On peut aussi comprendre que le logiciel impliqué dans la sécurité d'une centrale nucléaire doit être sans faille.

La preuve d'un algorithme est constituée de deux éléments à valider séparément :

• La preuve de terminaison : Un programme doit avoir une fin : toutes les conditions d'arrêt doivent pouvoir être remplies au cours de l'exécution. Un programme n'est jamais infini : même en cas d'exécution en continu, il doit exister un bouton d'arrêt (condition de terminaison).
• La preuve de correction : En supposant qu'il termine, le programme doit bien réaliser ce pour quoi il a été écrit.

Faillir à une seule de ces deux conditions remet en question la validité de l'algorithme.

Exemple simple : Calcul de la longueur du segment AB dans le plan

xA, yA, xB, yB sont des nombres
longueurAB = sqrt ((xB – xA)**2 + (yB – yA)**2)

Exemple avec une boucle : Calcul de la somme des éléments d'une liste numérique

liste ← une liste numérique
somme ← 0
pour i allant de 0 à longueur de liste - 1
	somme ← somme + liste[ i ]
afficher somme

def somme(liste):
    som = 0
    for val in liste:
        som += val
    return som

def somme(liste):
    """Calcule la somme des valeurs de la liste"""
    som = 0

    # Précondition sur l'invariant de boucle
    i = 0
    assert som == 0, "Erreur sur la précondition de l'invariant de boucle"

    for val in liste:
        som += val

        # Conservation de l'invariant
        assert som == sum(liste[0:i + 1]), "Non-conservation de l'invariant de boucle"
        i += 1

    # Postcondition sur l'invariant de boucle
    assert som == sum(liste), "Erreur sur la postcondition de l'invariant de boucle"

    return som

Algorithmes de recherche

Algorithme de recherche séquentielle

Prenons 7 cartes portant un numéro différent compris entre 1 et 10 (Jeu de 54 cartes). Les cartes sont désordonnées et retournées face cachée. L'objectif est de retrouver la carte portant le numéro 4.

def recherche_sequentielle(liste, element):
    for i, val in enumerate(liste):
        if val == element: return i
    return False
        

Algorithme de recherche dichotomique

Considérons désormais 7 cartes triées par ordre croissant.

L'idée de l'algorithme de recherche dichotomique date de l'antiquité (-220) dans la ville mésopotamienne : Babylone. Il applique le principe du diviser pour régner (divide and conquer) qui permet généralement d'obtenir de meilleurs algorithmes.
La méthode "diviser pour régner" se déroule en 3 étapes :

• Diviser : Découper le problème initial en sous-problème.
• Régner : Résoudre les sous-problèmes.
• Combiner : Calculer la solution du problème initial à partir des solutions des sous-problèmes.

liste ← liste de valeurs triée                           
valeur ← la valeur à chercher
a ← 0                           (indice du 1re élément de la liste)                                                                
b ← longueur de liste – 1       (indice du dernier élément de la liste)
m ← (a+b)//2                    (indice de l'élément au milieu de la liste)
tant que a < b
        si liste[m] est égal à valeur
                répondre m
        si liste[m] > valeur 
                b ← m-1
        sinon
                a ← m+1
        m ← (a+b)//2
fin tant que
répondre a

def recherche_dichotomique(liste_triee, valeur):
    a = 0
    b = len(liste_triee) - 1
    m = (a + b) // 2
    while a < b:
        if liste_triee[m] == valeur:
            return m
        elif liste_triee[m] > valeur:
            b = m - 1
        else:
            a = m + 1
        m = (a + b) // 2
    if liste_triee[m] == valeur:
        return m
    else:
        return -1 # absent de la liste
  

def recherche_dichotomique2(liste_triee, valeur):
    """Renvoie l'indice de la valeur recherchée dans la liste triée."""
    a = 0
    b = len(liste_triee) - 1
    m = (a + b) // 2

    # Variant de boucle
    d0 = b - a

    while a < b:
        if liste_triee[m] == valeur:
            return m
        elif liste_triee[m] > valeur:
            b = m - 1
        else:
            a = m + 1
        m = (a + b) // 2

        # Vérification du variant de boucle
        d1 = b - a
        assert d1 < d0, "La variant n'évolue pas !"
        d0 = d1

    if liste_triee[m] == valeur:
        return m
    else:
      return -1 # absent de la liste
  

Autres algorithmes de recherche

On peut aussi imaginer des algorithmes de recherche qui nécessite un traitement des données.

def recherche_min(liste):
    if len(liste) == 0: 
        return None
    rep = float("+inf")
    for val in liste:
        if val < rep:
            rep = val
    return rep

def recherche_max(liste):
    if len(liste) == 0: 
        return None
    rep = float("-inf")
    for val in liste:
        if val > rep:
            rep = val
    return rep

def moyenne(liste):
    if len(liste) == 0: 
        return None
    som = 0
    for val in liste:
        som += val
    return som/len(liste)
 

Algorithmes de tri

Reprenons 5 cartes portant chacune un numéro différent compris entre 1 et 10 (Jeu de 54 cartes). Les cartes sont désordonnées et retournées face cachée. L'objectif est de les trier.

Il existe un grand nombre d'algorithme de tri que vous pouvez découvrir en allant sur le site interstices.

Tri par sélection

Cet algorithme de tri est le plus naturel. Son principe consiste à rechercher la plus petite valeur (ou la plus grande) de la liste et à la placer en premier (ou en dernier), et ainsi de suite …

Voir le tri par sélection interprété par des danseurs folkloriques Gypsy : Youtube

Pseudo-code de l'algorithme de tri par sélection :

L ← liste de nombres
pour i allant de 0 à longueur(L) - 2 
      indiceMin ← i                                          
      pour j allant de i + 1 à longueur(L) - 1 
            si L[ j ] < L[indiceMin] alors indiceMin ← j      
      fin pour
      échanger L[i] et L[indiceMin]                   
fin pour

def tri_selection(liste):
    for i in range(len(liste)-1):
        imin = i
        for j in range(i+1, len(liste)):
            if liste[j] < liste[imin]:
                imin = j
        liste[i], liste[imin] = liste[imin], liste[i]
    return liste
  

Tri par insertion

Cet algorithme de tri est relativement naturel. Son principe est le suivant : Pour chaque élément de la liste, on le compare à tous ceux qui le précèdent jusqu'à déterminer sa bonne position (entre un plus petit et un plus grand que lui) et l'y insérer.

Voir le tri par insertion interprété par des danseurs folkloriques Roumain : Youtube

L ← une liste de nombres
pour i allant du deuxième terme à la fin de la liste
    v ← L[i]
    j ← i-1
    tant que j est positif et que v < L[i]  
        décaler le terme d'indice j en j+1
        décrémenter j
    fin tant que
    place v en position d'indice j+1 dans la liste
fin pour
  

def tri_insertion(liste): 
    for i in range(1, len(tab)): 
        k = tab[i] 
        j = i-1
        while j >= 0 and k < tab[j] : 
            tab[j + 1] = tab[j] 
            j -= 1
        tab[j + 1] = k

En moyenne, la complexité des algorithmes de tri par sélection et par insertion est quadratique `O(n^2)`. Ils sont tous deux peu efficaces lorsque le nombre de données devient important.

Le principe « diviser pour régner » peut être appliqué dans le domaine des tris notamment avec le tri fusion de complexité linéarithmique `O(n*log n)` et qui sera étudié en terminale.

Visualiser différents tris sur www.toptal.com.

Algorithmes gloutons

Les algorithmes gloutons répondent à des problèmes d'optimisation. L'idée est qu'à chaque étape de l'algorithme, celui-ci fasse le choix qui lui semble le plus optimal, sans réfléchir à la suite, en espérant que la solution finale au problème soit elle-même la plus optimale. Attention cela n'est pas forcément toujours le cas et dépend du problème à traiter.
L'exemple classique d'application d'un algorithme glouton est le problème du rendu de monnaie. L'objectif est, à partir d'un système de monnaie, de trouver comment rendre une somme de façon optimale, c'est-à-dire avec le moins de pièces et de billets possible.

POUR chaque type de monnaie présent dans la caisse, de la plus grande à la plus petite :
    TANT QUE la valeur à rendre est supérieur à la valeur de la monnaie :
        Compter le nombre de cette monnaie à rendre
        Soustraire la valeur de la monnaie à la somme à rendre
  

def rendre_monnaie(caisse, x):
    """Calcul d'un rendu de monnaie en fonction des valeurs de monnaie disponible
       dans la liste caisse et de la valeur à rendre x."""
    n = len(caisse)
    choix = [0] * n # Pour stocker le nombre de chaque type de monnaie à rendre
    ###################
    # A VOUS DE JOUER #
    ###################

    return choix

# Batterie de tests
caisse = [500, 200, 100, 50, 20, 10, 5, 2, 1]
assert rendre_monnaie(caisse, 800) == [1, 1, 1, 0, 0, 0, 0, 0, 0]
assert rendre_monnaie(caisse, 6) == [0, 0, 0, 0, 0, 0, 1, 0, 1]
assert rendre_monnaie(caisse, 49) == [0, 0, 0, 0, 2, 0, 1, 2, 0]
  

def rendre_monnaie(caisse, x):
    """Calcul d'un rendu de monnaie en fonction des valeurs de monnaie disponible
       dans la liste caisse et de la valeur à rendre x."""
    n = len(caisse)
    choix = [0] * n
    for i in range(n):
        while x >= caisse[i]:
            x -= caisse[i]
            choix[i] += 1
    return choix

def traduire_rendu(caisse, choix):
    """Traduit le choix de rendu en français."""
    for i in range(len(choix)):
        if choix[i] != 0:
            print("Rendre",choix[i],'de',caisse[i],"euros.")

# Batterie de tests
caisse = [500, 200, 100, 50, 20, 10, 5, 2, 1]
assert rendre_monnaie(caisse, 800) == [1, 1, 1, 0, 0, 0, 0, 0, 0]
assert rendre_monnaie(caisse, 6) == [0, 0, 0, 0, 0, 0, 1, 0, 1]
assert rendre_monnaie(caisse, 49) == [0, 0, 0, 0, 2, 0, 1, 2, 0]
  

Bon à savoir : Le système de monnaie a été choisi pour qu'un algorithme glouton soit optimal. Comment payer 9€ avec un système de pièces ou de billets de 1€, 2€, 5€ et 10€. Le choix optimal (moins de pièces et de billet) s'obtient en appliquant l'algorithme glouton (choisir toujours la plus grande des valeurs pour compléter) soit 5€ + 2€ + 2€ (3 pièces). Imaginons qu'il existe un billet de 7€. L'algorithme glouton n'est plus optimal. En effet si l'on souhaite payer 14€, il donnerait : 10€ + 2€ + 2€ alors que le meilleur choix serait 7€ + 7€.

Un autre problème où l'on peut appliquer un algorithme glouton est le problème du sac à dos. Vous disposez d'un ensemble d'objets unique définit par une masse et une valeur pécuniaire et d'un sac à dos ne pouvant transporter qu'une certaine masse. L'objectif est de définir quels objets mettre dans le sac en maximisant la valeur de l'ensemble.

def remplir_sac(objets, m):
    """Donne le meilleur choix des objets à prendre dans la sac 
       pour maximiser la valeur transportée."""
    choix = [0] * len(objets)
    ###################
    # A VOUS DE JOUER #
    ###################

    return choix

# Batterie de tests

objets = [[5, 0.5], [3, 4], [2, 1], [1, 0.2]]     # [[valeur, masse], ...]
assert remplir_sac(objets, 5.0) == [1, 1, 0, 1]

objets = [[6, 5.0], [5, 5.0], [4.5, 2.0], [4, 2.0], [3, 8.0], [1, 2.0], [0.5, 3.0]]
assert remplir_sac(objets, 5.0) == [1, 1, 1, 1, 1, 0, 0]
  

Algorithmes des k plus proches voisins

Abrégé en KNN (K-nearest neighbors), cet algorithme cherche à prédire la classe (ou propriété) d'un élément en fonction de la classe majoritaire de ses k plus proches voisins.
Par exemple, imaginons qu'un pixel soit manquant dans une image. L'algorithme va prédire la couleur de ce pixel en fonction de la couleur des pixels voisins.
L'algorithme KNN est un algorithme d'apprentissage (Machine Learning) supervisé. C'est-à-dire qu'à partir d'un ensemble des données étiquetées, il va pouvoir prédire l'étiquette d'une donnée inconnue.
Par exemple, à partir d'un ensemble d'images de chiens et de chats, ce type d'algorithme permet de déterminer si une photo inconnue est celle d'un chien ou d'un chat.
Un autre exemple sont les systèmes de recommandation. Un site marchand peut chercher vos k plus proches voisins en termes d'âge, de lieu, etc., pour vous proposer des articles susceptibles de vous plaire.

point ← point de référence
k ← nombre de voisins souhaité
liste ← liste des points donnés
liste_points_distances ← liste vide
POUR tous les points dans la liste : 
    d ← distance entre le point de la liste et le point de référence
    ajouter le point de la liste et sa distance au point de référence dans liste_points_distance
FIN POUR
trier liste_indices_distances selon leur distance au point de référence
renvoyer les k premiers points de liste_points_distance

def recherche_KNN(point, liste, k):
    """Renvoie la liste des k plus proches voisins du point : [x, y],
       dans la liste de point donnee : 
       [[nom1, x1, y1, couleur1], [nom2, x2, y2, couleur2],   ...]."""
    liste_points_distances = []
    for p in liste:
        coord = (p[1], p[2])
        d = calculer_distance(point, coord)
        liste_points_distances.append((p, d))
    voisins = sorted(liste_points_distances, key=lambda x: x[1])[:k]    # Tri les éléments de voisins selon d croissant
    return voisins
    

def calculer_distance(p1, p2):
    """Calcule la distance entre les points p1 et p2 : [x, y]."""
    distance = ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5
    return distance

def completer_KNN(liste, k):
    """Colore tous les points manquants de l'image."""
    liste_complete = []
    i = 0
    x_max = max(liste, key=lambda x: x[1])[1]+1
    y_max = max(liste, key=lambda y: y[2])[2]+1
    for x in range(x_max):
        print(str(x*100//x_max)+"%")     # Affichage de la progression du calcul
        for y in range(y_max):
            voisins = recherche_KNN([x, y], liste, k)
            if x == 9 and y == 19:
                b=3
            couleur_retenue = predire_couleur(voisins)
            liste_complete.append(["P"+str(i), x, y, couleur_retenue])
    return liste_complete