Introduction à l’algorithmique



--Téléchargez Introduction à l'algorithmique en PDF --


Définition

Un algorithme est une suite d’instructions qui, si elles sont exécutées correctement, aboutissent au résultat attendu. Le mot algorithme vient du mathématicien persan Muhammad ibn Mũsã al-Khuwãrizmĩ.

Par analogie, un algorithme est une recette du cuisine, une résolution d’un problème souvent par voie mathématique.

Un algorithme décrit formellement ce que doit faire l’ordinateur pour arriver à un but précis.diagramme1La maîtrise de l’algorithmique ainsi que l’apprentissage des algorithmes de base sont une des conditions de la réussite d’un projet en programmation, personnel ou professionnel. Avec de l’expérience, vous allez développer un schéma de pensée qui vous permettra d’optimiser les traitements, tant en vitesse qu’en occupation de la mémoire, et même de l’optimisation de l’écriture de votre code.

Formaliser ses algorithmes

Il existe deux manières de formaliser ses algorithmes. L’une est plus verbeuse, l’autre plus visuelle. Dans la pratique, nous utiliserons les deux formalismes en fonction de nos besoins. Il n’est pas rare de commencer avec un algorigramme, et de détailler en pseudo-code les parties les plus complexes.

Prenons l’exemple d’un programme qui lance un dé et qui demande à l’utilisateur de deviner la valeur du dé.

L’algorigramme

L’algorigramme est un ensemble de symboles permettant une approche visuelle d’un problème.diagramme2Le problème énoncé ci-dessus va se présenter comme suit.

Voici la signification des différents symboles :liste-symboles

  1. Terminaison. Indique le début ou la fin du processus.
  2. Procédé. Indique un processus ou une action. Elle se traduira par la création d’une méthode ou d’une fonction.
  3. Décision. Indique un choix à faire. Dans le cadre d’un choix booléen, la négation est représentée par un cercle. Dans certaines graphies, les branches sont explicitement nommées.
  4. Délai. Indique temps d’attente pendant un processus.
  5. Entrée/Sortie de données. Indique l’entrée ou la sortie d’une information dans ou depuis un processus.
  6. Document. Indique que le processus crée un fichier.
  7. Sous-procédé prédéfini. Indique un processus complexe détaillé dans un autre organigramme.
  8. Préparation. Indique un processus de préparation (setup).
  9. Affichage. Indique un affichage à l’écran.
  10. Entrée manuelle. Indique que l’utilisateur devra entrer manuellement une information dans le processus.
  11. Annotation. Utilisé pour annoter un symbole.
  12. Opération manuelle. Indique une opération non automatisée.
  13. Connecteur. Rassemble les différents processus en une seule sortie.
  14. Connecteur hors page. Pareil que son prédécesseur, mais permet de séparer un flowchart en plusieurs sections. Idéal pour les flowcharts kilométriques !
  15. Séquence. Le trait liant les différents symboles. Peut être annoté.
  16. Fusion. Fusionne les informations de différents processus *\*parallèles**** en une seule sortie.
  17. Séparation. Sépare un processus en plusieurs processus *\*parallèles****.
  18. Jonction additive. Équivalent au ET logique.
  19. Ou. OU logique.
  20. Stockage interne. Stockage de l’information en RAM.
  21. Stockage externe. Stockage de l’information en base de données.

Le pseudo-code

Le pseudo-code est un peu la recette de cuisine. Il s’agit donc d’un texte structuré. Il peut s’écrire dans votre langue maternelle. Toutefois, il est préférable de l’écrire en anglais. Ici aussi, tout le monde peut créer ses propres règles de pseudo-code. Je détaillerai les nouveautés au fur et à mesure des leçons.

Voici comment représenter le kata du lancé de dé en pseudo-code.

Détaillons un peu ce code.

Le pseudo-code va débuter par le mot ALGORITHM ou PROGRAM, suivi du nom du programme. Vient ensuite la déclaration des variables et de leur type. Ces variables sont déclarées dans la section VAR.

L’éxécution de l’algorithme se fera avec les mots clés BEGIN et END. L'[affectation]6] des variables est représentée par la flèche <-. Vient ensuite une boucle (WHILE / END WHILE) qui va demander à l’utilisateur d’entrer un nombre au clavier (via INPUT).

Le mot clé PRINT sert à afficher une information à l’écran.