C1-ALGO-01 : Introduction à l’algorithmique
Contents
C1-ALGO-01 : Introduction à l’algorithmique#
Objectifs pédagogiques#
comprendre ce qu’est un algorithme
appréhender les différentes classes d’algorithmes
Définition : Algorithme#
Un algorithme est une succession d’instructions permettant d’aboutir à un résultat souhaité (résoudre un problème ou une classe de problèmes). Il possède les caractéristiques suivantes :
il doit toujours se terminer après un nombre fini d’étapes
chaque étape d’un algorithme doit être définie précisément, les actions à mener doivent être spécifiées rigoureusement et sans ambigüité pour chaque cas
un algorithme a des entrées, zéro ou plus, quantités qui lui sont données avant ou pendant son exécution
un algorithme a une ou plusieurs sorties, quantités qui ont une relation spécifiée avec les entrées
les instructions doivent être suffisament basiques pour pouvoir être en principe exécutées de manière exacte, en un temps fini par une personne utilisant un papier et un crayon.
Exemple introductif : le stylo qui tombe#
Problème : Un stylo est tombé par terre depuis une table. Quelles sont les étapes pour le ramasser ?
Algorithme :
Se baisser
Ouvrir la main
Fermer la main sur le stylo
Se relever
Déposer le stylo sur la table
Sortie : le stylo est sur la table
Il est possible de généraliser cet algorithme à l’ensemble des objets de la taille d’un stylo en ajoutant une Entrée
Algorithme :
Entrée : objet à ramasser
Se baisser
Ouvrir la main
Fermer la main sur l’objet à ramasser
Se relever
Déposer l’objet à ramasser sur la table
Sortie : l’objet à ramasser est sur la table
Il est possible de généraliser cet algorithme à l’ensemble des meubles similaires à une table en ajoutant une Entrée
Algorithme :
Entrée 1 : objet à ramasser
Entrée 3 : meuble sur lequel déposer l’objet
Se baisser
Ouvrir la main
Fermer la main sur l’objet à ramasser
Se relever
Déposer l’objet à ramasser sur le meuble sur lequel déposer l’objet à ramasser
Sortie : l’objet à ramasser est sur le meuble
Exemple introductif mathématique : l’algorithme d’Euclide#
Historiquement, c’est probablement le plus ancien non trivial a avoir été décrit (au IIIème siècle avant JC)
L’algorithme d’Euclide est utilisé pour calculer le PGCD (Plus Grand Commun Diviseur) de deux entiers naturels m et n.
Entrée : m, n
Etape 1 : on divise m par n et on note r le reste (0 <= r < n)
Etape 2 : si r == 0, c’est terminé. Le PGCD est n
Etape 3 : sinon, on remplace m et n par n et r et on recommence à l’étape 1.
Sortie : n est le PGCD
Algorigramme#
Un algorigramme est une représentation visuelle d’un algorithme. On parle parfois d’algorigramme. Il montre les enchaînements de décisions et d’opérations à faire pour un algorithme donné.
Exemple d’un algorigramme#
Voici un exemple d’un algorigramme
Exercice 2 : observation#
Qu’observez-vous dans l’exemple d’algorigramme ci-dessus ?
sens de lecture
flèches, différentes structures
conditions
Symboles d’un algorigramme#
Les différentes structures utilisables sont les suivantes :
Règles de création d’un algorigramme#
Il existe différentes règles pour construire un algorigramme :
Il faut centrer l’algorigramme au centre de la feuille ou du programme informatique pour le créer
Il faut que la lecture de l’algorigramme puisse se faire verticalement
Les lignes de liaisons entre les symboles ne doivent pas se couper.
Une ligne de liaison doit toujours arriver sur le haut et au centre d’un symbole.
Les commentaires sont à placer de préférence à droite et les renvois de branchement à gauche.
Exercice 3 : un premier algorigramme#
A l’aide des différentes règles et symboles, créer sur une feuille de papier l’algorigramme décrivant l’algorithme en français suivant :
Logiciel pour créer des algorigrammes#
Il existe beaucoup de logiciels pour créer des algorigramme. L’un des plus populaires est diagrams.net qui existe sous la forme d’un site web interactif ou d’une application à installer sur son ordinateur :