Licence CC BY-SA

Algorithmes

Dans ce cours je ne veux pas seulement vous apprendre à écrire du code Python mais plus généralement à apprendre la programmation, et donc le raisonnement qui va avec.

Un programme informatique dans la vie courante va souvent consister à résoudre un problème particulier ou de multiples sous-problèmes : calculer un score, résoudre une équation, transformer une image, etc.
Pour résoudre ces problèmes on va bien sûr utiliser les outils proposés par le langage (les constructions telles que les conditions et les boucles, les types de données, etc.) mais cela ne fait pas tout, il faut leur donner un sens.

Ainsi on va devoir développer une suite logique d’opérations, comme une recette de cuisine, pour expliquer à l’ordinateur comment résoudre le problème, quel raisonnement appliquer.
Cette recette ou ce raisonnement, c’est ce que l’on appelle un algorithme.

Il y a des algorithmes génériques pour résoudre tous types de problèmes (nous allons en voir quelques uns ici), mais il est souvent nécessaire de les adapter, de les utiliser les uns avec les autres pour en former de nouveaux.
Pour continuer sur l’analogie de la recette de cuisine, il nous faut réaliser des choux d’une part et de la crème pâtissière de l’autre pour faire des choux à la crème, et spécialiser la crème selon le parfum que l’on veut lui donner.

Dans le cas d’un programme informatique il nous faut aussi réfléchir à ce que l’on a en entrée du programme (un nombre ? un fichier ? une adresse web ?) et ce que l’on souhaite en sortie (afficher un résultat ? créer un fichier ?).

Minimum d'une liste

On a déjà réalisé quelques algorithmes dans les derniers chapitres. Pour illustrer les boucles for je vous montrais par exemple comment identifier le maximum d’une liste. Identifier le minimum suit donc le même principe.

On avait imaginé deux solutions au problème. La première consisterait à itérer sur tous les éléments de la liste, et à vérifier pour chaque élément qu’il est le minimum en le comparant avec les autres éléments.
S’il existe un autre élément plus petit, alors l’élément courant ne peut pas être le minimum.

numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
minimum = numbers[0]

for i in numbers[1:]:
    is_minimum = True
    for j in numbers:
        if j < i:
            is_minimum = False
    if is_minimum:
        minimum = i

print('Le minimum est', minimum)

Cet algorithme fonctionne mais est particulièrement inefficace : il nous faut re-parcourir la liste complète pour chaque élément. Cela revient à dire que pour une liste de N éléments on va devoir effectuer un total de N² comparaisons.

L’autre algorithme que nous avions implémenté était bien meilleur. On pouvait simplement ne comparer chaque élément qu’avec les éléments précédents.
Et comme le minimum des éléments précédents est déjà connu à chaque instant, on peut juste comparer chaque élément avec le minimum déjà connu.

numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
minimum = numbers[0]

for i in numbers[1:]:
    if i < minimum:
        minimum = i

print('Le minimum est', minimum)

En plus d’être plus efficace (on ne réalise ici que N comparaisons pour une liste de taille N), le code est bien plus concis est lisible.

Même si la différence de performances ne saute pas aux yeux, parce que nos listes sont de tailles modestes, cela peut devenir problématique quand on commence à beaucoup l’utiliser ou l’appliquer à des données en plus grande quantité.
Cette notion de nombre d’opérations effectuées en fonction du nombre d’éléments en entrée est ce que l’on appelle la complexité algorithmique1.

On dit de notre premier algorithme qu’il a une complexité quadratique (N² opérations pour N éléments), et du second qu’il a une complexité linéaire (N opérations).

Cet algorithme n’est présenté que comme un exercice, dans la vie de tous les jours il serait bien sûr inutile puisque Python possède déjà une fonction min qui fait le boulot.


  1. Pour en apprendre davantage sur la complexité algorithmique, je vous invite à consulter ce tutoriel.

Tri d'une liste

Maintenant que l’on sait identifier le plus petit élément d’une liste on peut passer à un problème un peu plus compliqué, celui du tri d’une liste. C’est un problème algorithmique très classique qui consiste à ranger dans l’ordre les éléments d’une liste.

Une approche simple consiste à trouver le minimum pour le retirer de la liste et l’ajouter à une nouvelle liste d’éléments triés. L’opération est alors recommencée jusqu’à épuiser la liste de départ.
C’est ce qu’on appelle le tri par sélection.

numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
sorted_numbers = []

while numbers:
    m = min(numbers)
    sorted_numbers.append(m)
    i = numbers.index(m)
    del numbers[i]

print(sorted_numbers)

Cet algorithme n’est pas le plus efficace puisqu’il effectue environ N² opérations (le calcul du minimum comptant comme N comparaisons) pour une liste de N éléments. Il faut savoir que d’autres algorithmes plus performants existent tels que le tri rapide et le tri fusion, mais qui sont hors de portée pour le moment.

Python implémente lui-même son propre algorithme de tri inspiré des tris précédents, le Tim sort (du nom de Tim Peters, contributeur de Python). Ce tri est accessible par la fonction sorted.

>>> numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
>>> sorted(numbers)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Ainsi, avant de vous lancer tête baissée dans un algorithme, pensez à regarder si Python ne propose pas déjà une solution pour vous.

Un peu de dessin

Et si nous nous intéressions à des algorithmes un peu plus visuels ? Dans cette section je vous propose de dessiner diverses formes géométriques, à l’aide de caractères affichés dans le terminal.

Affichons un rectangle

Un premier exercice simple consiste à afficher un rectangle dans le terminal. À partir d’une largeur et d’une hauteur données (par exemple via des input()), on peut afficher les différents caractères pour dessiner les bords de notre rectangle.

On pourrait par exemple utiliser le caractère + pour les coins, - pour les lignes horizontales et | pour les lignes verticales.

Voici ce que donnerait un rectangle de dimensions 10×5 :

+--------+
|        |
|        |
|        |
+--------+
Rectangle 10×5

Comme vous le voyez, les coins sont compris dans les dimensions du rectangle.
Pensez alors aux cas « dégénérés » tels que des rectangles de dimensions 5×1, 5×2, 1×5, 1×1, 0×0, etc.

Et voici une solution possible pour cet exercice :

width = int(input('Entrez la largeur : '))
height = int(input('Entrez la hauteur : '))

for y in range(height):
    line = ''

    if y == 0 or y == height - 1:
        if width > 0:
            line += '+'
        line += '-' * (width - 2)
        if width > 1:
            line += '+'
    else:
        if width > 0:
            line += '|'
        line += ' ' * (width - 2)
        if width > 1:
            line += '|'

    print(line)
Passons au triangle

Augmentons un peu la difficulté et cherchons maintenant à afficher un triangle. Il s’agit d’un triangle équilatéral défini par sa hauteur. Voici par exemple un triangle de hauteur 10 :

         *
        * *
       *   *
      *     *
     *       *
    *         *
   *           *
  *             *
 *               *
*******************
Triangle de hauteur 10

Chaque ligne du triangle fait ainsi toujours deux caractères de plus que la précédente : * donne suite à * * puis *   *, etc.

Et comme vous le voyez, les lignes devront être centrées pour avoir un joli résultat.

Pour connaître la marge à appliquer à gauche de chaque ligne, pensez à calculer en amont la taille de la dernière ligne.

Sans plus attendre, la solution :

height = int(input('Entrez la hauteur : '))

max_len = 2 * height - 1

width = 1

for y in range(height):
    padding = (max_len - width) // 2
    line = ' ' * padding

    if width > 2 and y != height - 1:
        line += '*' + ' ' * (width - 2) + '*'
    else:
        line += '*' * width

    print(line)
    width += 2
Mon beau sapin, roi des forêts

Encore un cran de difficulté supplémentaire, mais le code du précédent triangle va nous être bien utile. On voudrait maintenant faire dessiner un sapin à notre programme.

Un sapin serait composé de triangle et trapèzes empilés, ainsi qu’un rectangle pour le tronc. Il serait là encore défini par une hauteur, désignant le nombre de sections du sapin ainsi que la taille de son tronc.

Vous trouverez ci-dessous des exemples de sapins de différentes tailles.

   *
  ***
 *****
*******
   |
Sapin de taille 1
          *
         ***
        *****
       *******
        *****
       *******
      *********
     ***********
    *************
     ***********
    *************
   ***************
  *****************
 *******************
*********************
         |||
         |||
         |||
Sapin de taille 3
              *
             ***
            *****
           *******
            *****
           *******
          *********
         ***********
        *************
         ***********
        *************
       ***************
      *****************
     *******************
    *********************
      *****************
     *******************
    *********************
   ***********************
  *************************
 ***************************
*****************************
            |||||
            |||||
            |||||
            |||||
Sapin de taille 4

Triangles et trapèzes se dessinent à peu près de la même manière.

Attention aux tailles paires pour les dimensions du tronc.

Je ne vous propose pas de solution pour cet exercice, mais sachez que vous pouvez le retrouver sur la plateforme HackInScience : Le sapin.

HackInScience est un site d’exercices algorithmiques à réaliser avec Python où vous trouverez beaucoup d’exercices de ce genre. Vous pouvez y exécuter directement vos codes et valider vos solutions.
Un exercice validé permet d’accéder aux solutions partagées par les autres membres du site.


Voilà ce qui conclut ce chapitre, mais n’hésitez pas à vous reporter aux exercices ou à des plateformes comme HackInScience ou exercism.io pour continuer à vous entraîner et pratiquer l’algorithmique.