Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Vade-mecum de l'informatique contemporaine
  3. mecum de l'informatique contemporaine
Extrait - Vade-mecum de l'informatique contemporaine (TCP, SOA, Linux, Python, Docker, HDFS, RDF, Adam, OWASP, KPI, UML, Scrum…)
Extraits du livre
Vade-mecum de l'informatique contemporaine (TCP, SOA, Linux, Python, Docker, HDFS, RDF, Adam, OWASP, KPI, UML, Scrum…)
1 avis
Revenir à la page d'achat du livre

Découvrir l’algorithmique

Notions élémentaires

1. Un premier exemple d’algorithme

Si le bourgeois gentilhomme de Molière, monsieur Jourdain, pratiquait la prose sans en avoir conscience, nous utilisons tous, sans le savoir, un mode de pensée rationnelle et analytique, assimilable, en un certain sens, à un algorithme. En effet, nos vies personnelles et professionnelles sont remplies d’objectifs que nous nous fixons, ou qui nous sont attribués, et que nous essayons d’atteindre au mieux. Pour y parvenir, nous décomposons généralement en étapes et actions le chemin, parfois le labyrinthe, permettant de passer de l’idée de l’objectif à sa réalisation. Illustrons ceci avec un exemple trivial, emprunté à notre quotidien : celui de la recette de cuisine.

Admettons que vous soyez un cuisinier débutant, disposant de plaques de cuisson et capable d’utiliser des ustensiles de cuisine, notamment une casserole. L’heure du déjeuner approchant, vous décidez de préparer rapidement un plat de pâtes au beurre. Pour ce faire, vous réalisez la séquence d’actions suivantes :

Prendre une casserole 
La remplir d'eau 
Porter la casserole à ébullition 
Prendre des pâtes 
Les plonger dans l'eau lorsque l'eau bout 
Régler votre minuteur sur 7 minutes 
Éteindre les plaques de cuisson lorsque le minuteur sonne 
Retirer la casserole des plaques de cuisson 
Égoutter les pâtes à l'aide d'une passoire 
Servir les pâtes dans une assiette 
Prendre le pain de beurre 
Prendre un couteau 
Découper une noix de beurre avec le couteau 
Mélanger la noix de beurre avec les pâtes 

En préparant ce déjeuner, vous venez d’exécuter un algorithme, ceci sans vous en rendre compte ; c’est-à-dire, formulé sommairement, une séquence d’actions réalisant un objectif.

Le résultat de cet algorithme est un plat de pâtes au beurre réalisé à partir de deux ingrédients : des pâtes et du beurre.

Nous dirons que les ingrédients (pâtes et beurre) constituent les entrées de l’algorithme tandis que le plat préparé...

Algorithme et programmation

Nous exposerons un modèle simple de pseudo-code dans la section suivante de ce chapitre, mais avant cela, intéressons-nous à la création ou conception de l’algorithme. Comment faciliter cette étape-clé ? Les trois prochaines sections décrivent les composantes de ce que nous appellerons le cadre de l’algorithme. Nous pensons que produire ce cadre constitue en soi une méthode facilitant la phase de création algorithmique.

1. L’objectif de l’algorithme

Le point de départ est naturellement l’objectif du programme et donc celui de l’algorithme. L’objectif répond à la question du quoi ?, qui elle-même dérive de la raison d’être du programme, correspondant au pourquoi. Rappelons que l’algorithme répond lui à la question du comment, c’est-à-dire comment implémenter l’objectif ou, par quel chemin relier les entrées à la sortie, ce chemin s’écrivant comme une séquence de primitives.

Il est impératif que l’objectif décrive le plus précisément possible la sortie attendue du programme. De plus, il est possible, et même souhaitable, d’expliciter des contraintes sur cette sortie. La formulation de l’objectif peut également décrire les entrées du programme, mais il est possible qu’à ce stade, les entrées nécessaires à la production de la sortie ne soient pas encore parfaitement claires dans l’esprit du développeur.

Considérons l’objectif simple suivant : « Calculer le reste de la division entière de deux entiers naturels ».

Dans cet exemple, on a clairement décrit la sortie attendue (le reste d’une division entière), on a aussi indiqué les entrées de l’algorithme (deux entiers naturels). Nous pourrions ajouter une contrainte, par exemple « Le reste doit être un entier naturel », ce qui sous-entendrait qu’il ne peut être négatif.

2. Exécution pas à pas d’un exemple pour induire un principe plus général

Le principe de l’algorithme exprime, idéalement en une phrase, l’idée permettant...

Rudiments de formalisation

Nous allons voir comment écrire des algorithmes simples grâce à un pseudo-code simple. À la fin du chapitre, un exemple illustrera la traduction du pseudo-code vers deux langages cibles, nous avons choisi R et Python.

Précisons que le formalisme présenté s’inspire fortement de l’ouvrage, déjà ancien, Introduction à la programmation de J. Biondi et G. Clavel (aux Éditions Masson), dans lequel l’auteur de ces lignes, alors étudiant, a lui-même appris l’algorithmique. Il va sans dire que je recommande cet ouvrage (et ses deux autres tomes) au lecteur souhaitant aller plus loin dans l’étude de l’algorithmique.

1. Données et actions élémentaires

Comme nous l’avons dit, les algorithmes manipulent des données en entrée pour calculer la ou les données de sortie. De plus, d’autres données internes sont généralement nécessaires aux calculs intermédiaires.

Toutes ces données peuvent être des constantes ou des variables. Par définition, les données constantes sont invariables.

Si les constantes peuvent apparaître « en dur » dans l’algorithme, c’est-à-dire explicitement, nous préconisons de leur donner un nom pour faciliter la lecture du pseudo-code. À l’évidence, le nombre π se lit plus aisément que 3,14159265358979.

Une donnée est donc une constante ou une variable, elle possède un nom et une valeur peut lui être affectée ou assignée, la première affectation s’appelle l’initialisation ; avant celle-ci, la donnée a une valeur indéterminée, c’est-à-dire inconnue.

Nous noterons l’affectation d’une valeur à une donnée nommée NOM_DE_LA_DONNÉE comme suit :

NOM_DE_LA_DONNÉE <- valeur 

La valeur affectée à une donnée peut résulter d’une opération :

SOMME <- 10 + 5 

Le type de la valeur affectée doit être identique ou compatible avec celui de la donnée. Lorsqu’ils sont différents mais compatibles, une conversion est effectuée implicitement.

Par exemple NUM NOMBRE <- ‘4’ suppose...

Micro boîte à outils d’algorithmes

Nous avons sélectionné un petit nombre de thèmes, pour illustrer la puissance de la pensée algorithmique et vous doter de quelques exemples utiles à connaître.

Dans cette boîte à outils se trouve, bien entendu, l’algorithme MapReduce que nous avons vu plus haut et sur lequel nous ne revenons pas. Par ailleurs, dans le chapitre Python - "starter" TL;DR, nous abordons succinctement le thème du tri d’une liste.

La plupart des algorithmes de référence font l’objet de packages dédiés et vous aurez plus souvent à choisir parmi ces implémentations plutôt qu’à implémenter vous-même leur code. À notre avis, ce choix sera d’autant plus pertinent que vous aurez pris soin d’en comprendre les caractéristiques et que vous aurez passé un peu de temps à écrire vos propres versions de certains d’entre eux. Cela étant dit, nous avons constaté à plusieurs reprises qu’il était parfois plus sain de rédiger une version simple d’un algorithme que l’on maîtrise bien, plutôt qu’utiliser sans recul un package « magique ».

1. Le load balancing

Il est courant d’avoir à répartir l’effort de traitement (CPU, volumes, etc.) sur plusieurs processeurs, disques, etc. C’est le thème de la répartition de charge (load balancing).

Ici l’objectif est donc l’équilibrage et la répartition de la charge d’un service sur plusieurs entités. On est souvent amené à choisir l’algorithme le plus adapté à son contexte, comme « comment répartir les accès à des informations situées sur plusieurs ordinateurs, entre plusieurs personnes, en parallèle et en privilégiant ou non tel ou tel comportement global ».

Ce type d’algorithme comprend deux familles (les deux listes ne sont pas exhaustives) :

  • les algorithmes statiques ;

    Round-robin (tourniquet) : les demandes des clients sont envoyées à différentes instances de service dans un ordre séquentiel. Les services doivent généralement être sans état....