Je propose un petit cours, non pas pour apprendre à coder dans un langage de programmation précis, mais pour apprendre la logique nécessaire pour programmer.
Vous trouverez ici donc de l'algorithmie, avec une explication des outils de base qui sont à notre disposition et la manière de les imbriquer pour obtenir l'algorithme souhaité.
Prenons quelques instants pour définir ce qu'est un algorithme, car celui-ci n'est pas forcément exclusif à l'informatique. En effet, un algorithme est une suite d'instructions qui permettent de définir quoi faire en fonction de ce que nous avons au moment d'effectuer l'instruction. Prenons un exemple très simple du quotidien (qui n'est pas de l'informatique).
Nous sommes standardistes téléphoniques, voilà l'algorithme :
J'attends que le téléphone sonne.
Le téléphone sonne : je décroche et je dis "Bonjour, société Blablabla, que puis-je faire pour vous ?"
La personne au bout du fil répond :
Si sa réponse est "Désolé, je me suis trompé de numéro", alors je réponds "Au revoir".
Si sa réponse est "Je veux parler à monsieur Dupond", alors je réponds "Un instant s'il vous plaît" et je mets l'interlocuteur en attente. Je vérifie que monsieur Dupond est disponible.
Si monsieur Dupond est disponible, je transfère l'appel.
Sinon, je préviens que monsieur Dupond n'est pas disponible et je prends un message.
Je raccroche alors et je me remets en attente d'un nouvel appel.
Voilà, si vous arrivez à écrire une tâche à effectuer de cette manière, vous pouvez alors la faire exécuter par un programme. En conclusion, nous reviendrons sur cet exemple pour en déterminer les différentes parties au vu de ce qui va suivre.
Voici la liste et la description des outils de base qui sont à notre disposition.
Les variables sont la base des outils nécessaires à tout programme. Elles permettent de stocker des informations, qui seront utilisées et réutilisées pour les différentes opérations, pour stocker les résultats, etc. Mais il ne faut pas oublier que l'ensemble de ces variables est stocké de manière binaire dans la machine, alors que nous, nous réfléchissons de manière décimale.
Les entiers : Ils représentent un nombre entier, donc sans virgule. Exemples : 1, 5, 8, 1563135, 12, …
les réels, Ils représentent les nombres entiers et à virgule. Exemples : 1.0, 12.0, 52.12, 1/9, …
les caractères, Ils représentent un seul caractère. Exemples : a, B, p, z, …
les chaines de caractères, Elles représentent des suites de caractères. Exemples : bonjour, fjdskldfj, il était une fois, abcde, …
les booléens, Ils représentent les variables Vrai ou Faux.
En lisant la liste des variables précédente, vous pourriez être étonné de faire une différence entre les entiers et les réels. En effet, les réels peuvent représenter tous les entiers, mais pour une machine, ils ne sont pas représentés de la même manière. Prenons un exemple : dans la mémoire de la machine, l'entier 2 et le réel 2.0 ne sont pas stockés de la même manière. En effet, l'entier 2, écrit en binaire, vaut : 0000 0010, alors que le réel 2.0 vaut 0 10000000 00000000000000000000000.
L'utilisation de la mémoire est beaucoup plus importante pour la représentation d'un réel que d'un entier, et c'est un élément extrêmement important à comprendre afin de bien optimiser son code. Mais nous reparlerons plus tard des notions d'optimisation, ainsi que de la manière dont on stocke les variables en mémoire.
On donne alors un nom à notre variable, celui que l'on souhaite, et on y met la valeur voulue. Les variables sont alors définies comme ceci :
entier a = 2
réels b = 2.0
caractère car = 'a'
chaine maChaine = "Bonjour tout le monde"
booléen Bol = "Vrai"
Ce sont des outils qui permettent de faire des opérations de logique avec les variables booléennes, mais aussi dans les instructions avec des conditions.
Et logique : Il retourne vrai si les deux opérandes sont vraies, sinon il retourne faux. Exemples :
vrai et vrai = vrai
faux et vrai = faux
faux et faux = faux
Ou logique : Il retourne vrai si au moins une des deux opérandes est vraie, sinon il retourne faux. Exemples :
vrai ou vrai = vrai
faux ou vrai = vrai
faux ou faux = faux
Ou exclusif : Il retourne vrai si une seule des deux opérandes est vraie, sinon il retourne faux. Exemples :
vrai ou(x) vrai = faux
vrai ou(x) faux = vrai
faux ou(x) faux = faux
Non : Il retourne l'opposé de l'opérande. Si c'est vrai, il retourne faux, et si c'est faux, il retourne vrai. Exemples :
non vrai = faux
non faux = vrai
Il s'agit des outils qui permettent de faire des tests sur nos variables. Ils retournent une réponse booléenne, c'est-à-dire vrai ou faux.
Si, Alors, Sinon, Le "Sinon" n'est pas obligatoire et dépendra de votre besoin. Il s'utilise de la manière suivante : je fais un test sur une variable, Si mon test est vrai, je fais ce qu'il y a dans "Alors", et si mon test est faux, je fais ce qu'il y a dans "Sinon".
Exemple : j'ai deux variables que je nomme a et b, je fait le test suivant
Si a = b, Alors j'affiche à l'écran "les valeurs sont égales" Sinon j'affiche à l'écran "les valeurs sont différentes".
L'instruction de sélection est un outil qui permet de mettre une condition sur une variable et de traiter différentes possibilités. Elle va tester toutes les possibilités une par une jusqu'à trouver la bonne. Une commande "Stop" doit être mise pour arrêter les tests. On peut ajouter une valeur par défaut en fin de test.
Exemple :
Chaine test
Sélection test
Cas "bonjour" : affiche "la valeur est bonjour"
Stop
Cas "au revoir" : affiche "la valeur est au revoir"
Stop
Cas "salut" : affiche "la valeur est salut"
Stop
défaut : affiche "pas de valeur reconnu"
Ici, on teste la valeur de la chaîne "test" et on affiche un message en fonction de la valeur.
Il s'agit d'outils permettant de répéter du code jusqu'à ce que leurs conditions soient validées.
La boucle Tant que : Cette boucle est suivie d'une condition, qui est testée au début de chaque tour de la boucle. Elle s'exécute tant que sa condition est vraie. Une fois la condition fausse, elle se termine et le code qui la suit est alors exécuté.
Exemple : booléen continue= vrai
entier i = 0
Tant que continue:
i = i + 1
si i > 100 alors continue= faux
fin Tant que
affiche "i est à 100"
Ici, on teste au début de la boucle si "continue" est vrai. Si c'est le cas, on ajoute 1 à l'entier i, puis on teste si i est supérieur à 100. Si oui, alors on met "continue" à faux, ce qui arrête la boucle au test de "continue" suivant.
la boucle Répéter jusqu'à, Cette boucle a exactement le même comportement que la boucle Tant que, à la différence que le test de la condition ne se fait pas au début de chaque boucle mais à la fin.
Exemple : booléen continue = vrai
entier i = 0
Répéter
i = i + 1
si i > 100 alors continue = faux
jusqu'à continue
affiche "i est à 100"
La boucle Pour, Cette boucle fonctionne différemment des deux autres. Elle incrémente un entier jusqu'à une limite donnée et s'arrête. Un équivalent des exemples précédents s'écrit alors comme suit :
Pour i = 0 jusqu'à i >100 avec i = i + 1
fin pour
affiche "i est à 100"
Il s'agit de conteneurs permettant de stocker plusieurs variables ou même des structures. En informatique, on commence toujours par compter depuis 0. Donc, le premier nombre est 0.
Les listes sont des conteneurs à une dimension où l'on peut accéder aux valeurs qu'elles contiennent par l'intermédiaire de leurs indices.
Exemple: liste Prenom = [Pierre, Paul, Victor, Marie, Juliette, Ambre] si je veux avoir la valeur "Ambre" j'écrit alors Prenom [5]
Les piles, sont également des conteneurs à une dimension, mais leur fonctionnement est différent. Dans une pile, on ne peut pas choisir directement l'élément que l'on souhaite. On ajoute les valeurs les unes à la suite des autres, on empile, et on les sort dans l'ordre inverse de leur empilement, on dépile.
Cela signifie que si j'empile Ambre, puis Juliette, puis Marie, puis Victor, puis Paul, puis Pierre, lorsque je dépile, j'obtiens Pierre, puis Paul, puis Victor, puis Marie, puis Juliette, puis Ambre. Ambre, qui a été le premier élément à être empilé, est le dernier à être dépilé. Pour accéder à la valeur Ambre, il faut donc dépiler toute la pile.
Dans une pile, le principe "dernier entré, premier sorti" (LIFO - Last In, First Out) est appliqué.
Les tableaux sont des conteneurs à deux dimensions où l'on accède aux éléments par leurs coordonnées d'indices.
Exemple : Tableau PrenomNom = [Pierre, Paul, Victor, Marie, Juliette, Ambre]
[Dupond, Durant, Dujardin, Buisson, Dumoulin, Martin]
si je veux la valeur "Ambre" alors j'écrit Prenom[0,5] et si je veux "Buisson" j'écrit Prenom[1,3].
Les tableaux à deux dimensions sont couramment utilisés pour stocker des données structurées comme des grilles, des matrices, ou des tableaux de valeurs associées.
les files sont similaires aux piles : on ajoute les éléments les uns à la suite des autres, on les enfile. Cependant, contrairement aux piles, le premier élément enfilé sera le premier à être sorti ou défilé.
Dans une file, on suit le principe FIFO (First In, First Out), ce qui signifie que le premier élément ajouté à la file est le premier à être retiré.
les arbres, sont des structures de données hiérarchiques composées de nœuds, où chaque nœud a un parent et des enfants liés par des branches. Il existe plusieurs types d'arbres :
Les arbres binaires : Pour chaque nœud parent, il y a un enfant à gauche et un enfant à droite.
Les arbres généraux : Les nœuds peuvent avoir autant d'enfants que nécessaire. Chaque enfant peut être à son tour parent de nouveaux enfants.
Un exemple très concret d'arbre est l'arbre généalogique, où chaque individu peut être considéré comme un nœud avec des enfants (descendants) et un parent (prédécesseur).
Dans un arbre généalogique, par exemple :
Chaque personne peut être un nœud.
Les parents sont connectés à leurs enfants par des branches.
Chaque enfant peut à son tour devenir parent de nouveaux enfants, formant ainsi une structure arborescente.
Ces outils permettent d'aller plus loin et de simplifier le code, mais demandent une abstraction plus importante. Ils ne sont pas indispensables pour la compréhension des algorithmes de base, mais je les mentionne ici pour les personnes souhaitant approfondir leurs connaissances.
Il s'agit d'un outil un peu particulier qui permet de stocker un ensemble de variables et de tableaux que l'on crée en fonction de nos besoins.
Exemple :
Structure personne
chaine nom
chaine prénom
entier age
réel taille
fin Structure
Il s'agit d'un bloc d'instructions que l'on peut appeler en nommant simplement le nom de la fonction. On peut choisir librement le nom des fonctions que l'on utilise. Une fonction peut avoir ou non des variables en entrée et peut retourner un résultat. Cela permet d'alléger son code et d'éviter d'écrire plusieurs fois la même chose de manière inutile
Exemple : On créer une fonction qui va nous dire si l'entier test est compris entre l'entier a et l'entier b
maFonction ( entier test, entier a, entier b)
retourne test>a et test<b
fin maFonction
Les dictionnaires sont des conteneurs plus complexes utilisés pour des recherches rapides. Ils permettent de stocker des paires clé-valeur, où chaque clé est unique et est associée à une valeur. Ils sont similaires aux listes de structures (cf. structures dans les outils avancés) où les données peuvent être modifiées, et où l'on peut ajouter ou supprimer des éléments à volonté.
L'efficacité des dictionnaires repose sur le fait que les clés sont stockées dans un tableau. Lors d'une recherche ou d'un accès, on recherche d'abord la clé dans ce tableau, puis on accède à la valeur associée. Cela permet de ne pas manipuler l'ensemble des données lors de la recherche ou de l'accès, mais seulement les clés qui y sont associées.
Un inconvénient des dictionnaires est l'utilisation accrue de mémoire nécessaire pour stocker toutes ces informations, notamment en raison du tableau de clés.
Compréhension du problème :
Quel est le problème à résoudre ?
Quelles sont les entrées (données d'entrée) du problème ?
Quelles sont les sorties attendues (résultats) ?
Analyse des exigences :
Quelles sont les contraintes ou limitations à prendre en compte ? (par exemple : limites de temps, de mémoire, précision requise, etc.)
Y a-t-il des règles spécifiques à respecter ? (par exemple : règles métier, contraintes de format des données, etc.)
Définition des cas particuliers :
Y a-t-il des cas particuliers ou des scénarios spécifiques à considérer ? (par exemple : traitement des valeurs nulles, cas de bord, situations exceptionnelles, etc.)
Choix des structures de données :
Quelles structures de données sont les plus appropriées pour représenter les entrées et les sorties ? (par exemple : tableaux, listes, dictionnaires, piles, files, arbres, etc.)
Stratégie de résolution :
Quelle approche ou quel algorithme pourrait être le plus efficace pour résoudre le problème ? (par exemple : recherche linéaire, tri, algorithme glouton, programmation dynamique, etc.)
Est-il nécessaire de diviser le problème en sous-problèmes ?
Planification des étapes :
Comment vais-je structurer l'algorithme ? (par exemple : séquence d'étapes, boucles, conditions, appels de fonctions, etc.)
Voici une liste non exhaustive mais indispensable des questions à se poser avant la réalisation de son algorithme. Ces questions aident à structurer la réflexion et à s'assurer que tous les aspects importants sont pris en compte avant de commencer à écrire l'algorithme proprement dit. Cela permet également d'éviter les erreurs de conception et d'assurer une mise en œuvre efficace et correcte de l'algorithme.
Quel est le but de cet algorithme ?
Quelles sont les données d'entrée et comment sont-elles structurées ?
Quelles sont les données de sortie attendues ?
Quelles sont les contraintes de performance ou de complexité ?
Y a-t-il des contraintes spécifiques de sécurité ou de traitement des données ?
Comment vais-je tester et valider cet algorithme ?
Quelles sont les ressources nécessaires (mémoire, temps de calcul) ?
Comment gérer les erreurs ou les cas inattendus ?
Y a-t-il des améliorations possibles ou des optimisations à envisager ?
Comme nous l'avons vu précédemment, le choix des variables est essentiel pour optimiser efficacement un algorithme. Le code résultant sera exécuté sur diverses machines qui peuvent différer en termes de capacité mémoire et de vitesse d'exécution. Il est donc primordial de toujours en tenir compte et de s'imposer éventuellement des contraintes supplémentaires, telles que limiter l'utilisation mémoire à une quantité spécifique (par exemple, "je ne veux pas que mon code n'utilise pas plus de X mémoire").
Conseils supplémentaires pour l'optimisation des variables :
Minimiser l'utilisation de la mémoire :
Utilisez des types de données appropriés et évitez de surdimensionner vos variables.
Limitez la création de variables temporaires non nécessaires.
Optimiser l'accès aux variables :
Utilisez des variables locales plutôt que globales lorsque cela est possible, car les variables locales sont souvent plus rapides à accéder.
Éviter les variables redondantes :
Ne créez pas de variables dont les valeurs peuvent être déduites ou calculées à partir d'autres variables existantes.
Utiliser des structures de données efficaces :
Choisissez la structure de données la mieux adaptée au problème spécifique que vous résolvez (tableaux, listes, dictionnaires, etc.).
Tester la performance :
Effectuez des tests de performance pour évaluer l'impact des choix de variables sur la vitesse d'exécution et la consommation de mémoire de votre algorithme.
Considérer les contraintes du système :
Prenez en compte les spécificités du système sur lequel votre algorithme sera déployé, telles que la capacité mémoire disponible et la puissance de calcul.
En appliquant ces conseils, vous pouvez non seulement améliorer l'efficacité de votre algorithme mais aussi garantir une meilleure adaptabilité à différentes plateformes et conditions d'exécution.
La manière dont vous allez organiser l'écriture de votre algorithme est extrêmement importante. Si vous avez besoin d'y retourner pour le mettre à jour ou le modifier, ou si quelqu'un d'autre doit le faire, un code brouillon est pratiquement impossible à améliorer sans le réécrire. Voici quelques conseils :
Utiliser des noms de variables descriptifs :
Choisissez des noms de variables qui décrivent clairement leur rôle et leur contenu. Évitez les noms génériques comme a, b, x, etc., sauf s'ils sont utilisés dans un contexte très spécifique et évident.
Diviser en étapes claires :
Séparez votre algorithme en étapes distinctes, chacune accomplissant une tâche spécifique. Utilisez des commentaires pour décrire chaque étape si nécessaire.
Écrire des commentaires pertinents :
Ajoutez des commentaires explicatifs là où l'algorithme pourrait sembler complexe ou ambigu. Expliquez le but de chaque bloc de code et les décisions prises.
Formater correctement le code :
Utilisez une indentation cohérente pour montrer la structure du code (par exemple, 2 ou 4 espaces par niveau d'indentation).
Alignez correctement les blocs de code pour faciliter la lecture.
Éviter les lignes trop longues :
Limitez la longueur des lignes de code pour éviter la nécessité de faire défiler horizontalement. Une règle courante est de limiter les lignes à environ 80-100 caractères.
Utiliser des structures de contrôle claires :
Utilisez des structures de contrôle telles que les boucles (pour, tant que) et les instructions conditionnelles (si , alors switch) de manière claire et concise.
Simplifier les expressions complexes :
Divisez les expressions complexes en étapes plus simples, en utilisant des variables temporaires si nécessaire pour clarifier le processus.
Tester et refactoriser :
Testez votre algorithme avec différentes entrées pour vous assurer qu'il fonctionne correctement dans tous les cas prévus. Si nécessaire, refactorisez le code pour améliorer sa lisibilité.
Adopter un style de codage cohérent :
Choisissez un style de codage cohérent et suivez-le tout au long de votre algorithme. Cela inclut le choix de la casse pour les noms de variables, l'utilisation des espaces et des lignes vides pour séparer les blocs logiques.
Simplifier lorsque possible :
Évitez la complexité excessive en optant pour des solutions simples et directes lorsque cela est possible. La simplicité améliore généralement la lisibilité.
Pour commencer je veux préciser que j'ai volontairement simplifié certaines parties afin qu'elles soient le plus accessibles possible et parce qu'ici je m'intéresse plus au fonctionnement global des algorithmes.
Nous avons vu un aperçu non exhaustif de la manière de concevoir un algorithme et de la réflexion nécessaire pour le réaliser. J'aimerais maintenant revenir sur l'exemple que nous avions vu en introduction et le découper pour reconnaître les différentes instructions utilisées.
Nous sommes standardistes téléphoniques, voilà l'algorithme :
J'attends que le téléphone sonne.
Ici commence une boucle Tant que ma journée de travail n'est pas finie.
Le téléphone sonne : je décroche et je dis "Bonjour, société Blablabla, que puis-je faire pour vous ?"
Fonction qui est appelée dès que le téléphone sonne.
La personne au bout du fil répond :
Événement qui apporte une nouvelle variable.
Si sa réponse est "Désolé, je me suis trompé de numéro", alors je réponds "Au revoir".
Condition Si.
Si sa réponse est "Je veux parler à monsieur Dupond", alors je réponds "Un instant s'il vous plaît" et je mets l'interlocuteur en attente. Je vérifie que monsieur Dupond est disponible.
Deuxième condition Si.
Si monsieur Dupond est disponible, je transfère l'appel.
Déclenchement du Alors avec une troisième condition Si qui appelle la fonction "transfert d'appel".
Sinon, je préviens que monsieur Dupond n'est pas disponible et je prends un message.
Le Sinon de la troisième condition Si qui appelle la fonction "je prends un message".
Je raccroche alors et je me remets en attente d'un nouvel appel.
Fin de la boucle.
J'espère que cette mini initiation à l'algorithmie et au code vous aura donné envie d'essayer. Pour toutes questions, vous pouvez me contacter via le formulaire présent sur le site. Je ferai de mon mieux pour vous répondre le plus rapidement possible. Au bientôt :)