Bienvenue dans le Monde Merveilleux de l'Algorithmique^MD. Ce cours se veut une introduction à l'algorithmique et à la programmatique, deux termes que nous définirons plus loin.

Vous êtes au bon endroit si vous n'avez pas, ou à peu près pas, programmé, mais avez envie d'apprendre cette science (ou cet art, tout dépendant du point de vue).

Vous êtes au mauvais endroit si vous avez déjà un bagage en programmation ou en langage C++, ou encore si votre objectif est d'approfondir votre savoir en la matière plutôt que d'y être introduit.

En effet, si l'algorithmique est une science exacte, au même titre que les mathématiques ou la physique, la programmatique comporte de son côté une part d'investissement humain et d'esthétique, tout en étant une composante à part entière (et essentielle) de la programmation.

Les principaux éléments de la programmatique, et donc les étapes fondamentales requises pour la rédaction d'un programme, sont:

C'est pourquoi le problème lui-même fait partie intégrante de notre définition. Pas de problème, pas de plaisir pour nous.

Pour parvenir à produire un véritable algorithme, il faut d'abord procéder à une analyse du problème, mais pas n'importe quelle analyse: une analyse structurée.

Exemple: supposons que nous recherchons un algorithme qui nous permettra de nous faire cuire un oeuf.

Si notre analyse ressemble par exemple à ce qui suit:

nous ne serons pas vraiment plus avancés qu'avant même de se poser la question «comment résoudre le problème?».

Lorsque l'on veut appliquer une solution informatique pour résoudre un problème, il faut éviter de se précipiter devant un écran d'ordinateur.

Programmer sans réfléchir a priori ne cause que des problèmes. On risque, en programmant sans analyse au préalable, d'aboutir à une solution incomplète (dans la mesure où on arrive effectivement à une solution).

Chacune de ces phases comporte un certain nombre d'opérations qu'on peut regrouper en étapes.

Une fois l'étape de la compréhension du problème résolue (ce qui n'est pas toujours simple), il faut passer à l'étape suivante qui consiste à examiner différentes approches générales permettant de résoudre le problème.

Une des méthodes les plus employées en informatique (et qui sera, comme mentionné précédemment) est l'approche par sous-objectifs.

Cette méthode consiste à fractionner un problème difficile en plusieurs petits problèmes plus simples. On dit d'elle qu'elle est une «méthode descendante» (top down method), du fait qu'elle part du problème général pour en faire une décomposition.

Étant donné un problème spécifique, un algorithme est la séquence complète et ordonnée de toutes les opérations (actions) à faire pour en obtenir la solution. Cette séquence d'opérations est dictée par le problème à résoudre et par la méthode de résolution choisie.

En informatique, ce terme se réfère à une méthode de résolution de problèmes, comme nous l'avons mentionné précédemment. Nous faisons usage d'un ordinateur pour implanter nos algorithmes dans le but d'automatiser le processus de résolution de problèmes. L'idée est donc, fondamentalement, de se simplifier la vie pour longtemps en se la compliquant une fois.

Exemple: le calcul du volume d'une sphère.

L'exemple suivant décrit la structure de contrôle «séquence» à la fois sous la forme de morphogramme et de pseudo-code.

Par exemple, pour faire bouillir de l'eau, on peut:

Une personne utilise sa voiture pour se rendre au travail. Écrire le pseudo-code et le morphogramme représentant l'algorithme qui permet à cette personne de calculer et d'afficher son coût de déplacement.

Les ouvriers d'une entreprise ont reçu une augmentation de salaire de 4%. Cette augmentation est rétroactive de 6 mois.

Écrire le pseudo-code et le morphogramme de l'algorithme permettant d'échanger le contenu de deux variables, X et Y.

Écrire le pseudo-code et le morphogramme de l'algorithme permettant de calculer et d'afficher et d'afficher le salaire net d'un employé.

Un chef d'entreprise veut connaître combien lui coûte la fabrication d'un exemplaire de son produit. Écrire le pseudo-code et le morphogramme représentant l'algorithme qui permet à d'exécuter ce calcul et d'afficher le résultat.

Écrire le pseudo-code et le morphogramme de l'algorithme permettant d'échanger le contenu de trois variables: X, Y et Z.

Écrire le pseudo-code et le morphogramme de l'algorithme permettant de calculer et d'afficher le salaire net d'un employé ainsi que le détail des déductions.

Un exemple de prédicat serait «Jean est plus grand que Roger». En effet, cet énoncé est soit vrai, soit faux, au moment où il est formulé, et pour un Jean et un Roger bien précis.

Un exemple de choix de séquences étant donné la valeur d'un prédicat serait «s'il pleut dehors, alors rester à la maison et lire un livre, sinon aller au parc».

On remarquera (avec justesse) que ceci représente une pause café bien incomplète. Par exemple, s'il n'y a pas de café frais lors de l'évaluation de la condition, on fera du café, mais on ne le boira pas.

La seconde forme d'alternative peut aussi se prêter à une séquence d'opérations seulement dans le cas d'une évaluation du prédicat comme faux, avec un résultat équivalent; par contre, on tend dans ce cas à perdre un peu en élégance.

La même expression aurait pu s'écrire «si le plancher est sale, alors passer le balai» et éviter la suite «si le plancher est propre, alors (rien) sinon ...».

Pour s'assurer de jouir des fruits de nos efforts, cet algorithme n'est pas tout à fait suffisant: en effet, dans le cas où nous devons faire nous-mêmes le café, l'algorithme n'indique pas que nous en boirons.

Ainsi, mieux vaut enrichir la séquence rencontrée dans le cas où le prédicat «il y a du café frais» s'avère faux, surtout si nous sommes de fervents amateurs du breuvage en question.

Mais on se retrouve à insérer une forme de redondance dans notre algorithme: en effet, peu importe le chemin emprunté, on finit dans chaque cas par «prendre un café», et ce en dernier lieu dans chaque cas.

Vous devez calculer et afficher la note finale d'un étudiant, ainsi que la mention succès ou échec. Cet étudiant a passé trois (3) examens et la note de passage est soixante (60).

La note finale est calculée comme étant la moyenne des examens.

Vous devez calculer et afficher la note finale d'un étudiant, ainsi que la mention succès ou échec. Cet étudiant a passé trois (3) examens et la note de passage est soixante (60).

La note finale est calculée comme étant la moyenne des examens. Si l'étudiant obtient une note finale se situant entre 55% et 60%, il a droit à un examen de reprise, et obtiendra la note de 60% dans la mesure où il réussit ce dernier.

La forme générale de la répétitive se prête aux énoncés suivant le modèle «tant que (condition) faire (opérations)».

Le morphogramme d'une répétitive est intéressant car il permet de bien saisir son aspect dynamique. La figure précédente permet de bien représenter le mouvement qui anime cette structure.

Le point d'entrée est en haut. Tant que la condition à évaluer représentée par le losange reste vraie, il y a exécution de l'opération représentée par le rectangle. La ligne qui remonte à gauche indique qu'il faut retourner évaluer la condition.

Le terme boucle qu'on emploie dans le cas de répétitives désigne surtout ce mouvement quasi circulaire.

Quand que la condition devient fausse, on quitte la répétitive en passant par la voie à droite du losange pour atteindre le point de sortie en bas (voir l'exemple de la pile d'examens à corriger, plus bas).

Dans notre exemple, le prédicat à satisfaire est «la crème ne bout pas». Tant que ce prédicat est vrai, l'algorithme indique que la séquence d'opérations à exécuter comprend une seule opération, soit «brasser la crème».

Bien entendu, s'il y a des séquence d'opérations simples comme «brasser la crème», il y en a aussi de plus longues et de plus complexes.

Prenons par exemple le cas d'un pauvre professeur face à une pile d'examens à corriger, où chaque examen comporte quatre questions. Il est possible, si l'on sait combien d'examens se trouvent dans la pile, de rédiger un algorithme permettant la correction de chacun d'entre eux avec une séquence. Toutefois, cette séquence pourrait devenir arbitrairement longue en fonction du nombre d'examens dans la pile.

Vous devez calculer la moyenne des examens d'un groupe de dix-huit (18) étudiants. Chaque étudiant a passé trois (3) examens.

Vous désirez obtenir la moyenne aux examens de chacun des étudiants, ainsi qu'un commentaire qui variera selon la moyenne obtenue (voir tableau de la question précédente). Créez le pseudo-code et le morphogramme de l'algorithme permettant de résoudre ce problème.

La méthode du développement graduel

Changer de lunettes

• formuler différemment un problème donné en posant la question autrement. Certaines questions paraissent très complexes (ou même, à la limite, insolubles) à moins que l'on les aborde sous un autre angle;
• schématiser le problème, le traduire, utiliser un langage différent pour l'exprimer. On peut ainsi concevoir la résolution d'un problème sous forme de pseudo-code ou de morphogramme, sans le changer en tant que tel, mais voir graphiquement le flot de notre méthode de résolution de problème peut définitivement être un pas dans la bonne direction;
• subdiviser le problème en modules, soit des sous problèmes du problème initial qui peuvent se résoudre en eux-mêmes. En fait, puisqu'on peut subdiviser un problème en modules, et qu'un module est aussi un problème à résoudre, on peut subdiviser un module en modules plus simples, et ainsi de suite, dans la mesure où il y a une fin à cette subdivision.

• poser la bonne question est nécessaire: ai-je toutes les données pour répondre au problème qui m'est présenté? Comprends-je l'énoncé du problème? Sa formulation est-elle ambiguë? Parfois, la question porte en elle sa réponse...;
• la subdivision en modules du problème permet de prendre celui-ci «de haut», pour en voir d'abord l'essentiel et se préoccuper seulement par la suite des détails;
• la traduction du problème en un langage se prêtant à un formalisme accru, comme les morphogrammes ou le pseudo-code, aide à formuler le raisonnement qui mène à une solution claire et pouvant être reproduite.

Exercices de développement graduel

Pour résoudre les exercices 31 à 35, inspirez-vous de cet exemple de la technique du développement graduel.

Écrire le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire à l'écran un rectangle de 10 lignes sur 8 colonnes identique à celui présenté ci-dessous:

********
********
********
********
********
********
********
********
********
********

Écrire, en utilisant la technique du développement graduel, le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire à l'écran un triangle identique à celui présenté ci-dessous:

*
**
***
****
*****
******
*******
********
*********
        

Écrire, en utilisant la technique du développement graduel, le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire à l'écran un triangle identique à celui présenté ci-dessous:

**********
*********
********
*******
******
*****
****
***
**
*
          

Écrire, en utilisant la technique du développement graduel, le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire à l'écran un triangle identique à celui présenté ci-dessous:

<****>
<<****>>
<<<****>>>
<<<<****>>>>
<<<<<****>>>>>
<<<<<<****>>>>>>
<<<<<<<****>>>>>>>
<<<<<<<<****>>>>>>>>
<<<<<<<<<****>>>>>>>>>
<<<<<<<<<<****>>>>>>>>>>

Écrire, en utilisant la technique du développement graduel, le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire à l'écran un triangle identique à celui présenté ci-dessous:

         *
        ---
       *****
      -------
     *********
    -----------
   *************
  ---------------
 *****************
-------------------