Writing and Testing Algorithms

# Writing and Testing Algorithms ## Objectifs et prérequis Ce chapitre vise à fournir aux élèves de Lower Sixth (anglophone) une compréhension approfondie des algorithmes : leur définition, leur représentation, leur construction, leur test et leur évaluation. À l’issue de ce chapitre, l’élève sera capable de : - Définir un algorithme et expliquer son rôle dans la résolution de problèmes informatiques. - Identifier et utiliser les instructions algorithmiques de base (entrée, sortie, affectation, calcul). - Représenter un algorithme sous forme de diagramme de flux (flowchart) et de pseudocode. - Appliquer les structures de contrôle : séquence, sélection (si/alors/sinon) et boucle (tant que, pour). - Concevoir et analyser des algorithmes de tri et de recherche. - Établir la correction d’un algorithme par raisonnement logique ou test de cas. - Évaluer la performance d’un algorithme en termes de complexité temporelle et spatiale. - Préparer et répondre à des questions d’examen type du GCE Advanced Level ICT. **Prérequis** : Maîtrise des notions de base en résolution de problèmes, familiarité avec les opérations arithmétiques et logiques, capacité à suivre des consignes étape par étape (déjà acquises en Form 5 ICT ou équivalent). --- ## I. Introduction to Algorithms Un algorithme est une suite finie et non ambiguë d’instructions clairement définies, permettant de résoudre un problème ou d’accomplir une tâche spécifique en un nombre fini d’étapes. Il doit être efficace, correct et généralisable. > **À retenir** : Un algorithme doit posséder cinq propriétés essentielles : finitude, déterminisme, entrée, sortie et efficacité. Les algorithmes sont au cœur de l’informatique : ils traduisent la logique de résolution de problèmes en une forme exécutable par une machine ou un humain. Ils ne dépendent pas d’un langage de programmation spécifique : un même algorithme peut être implémenté en Python, Java, ou même exécuté manuellement. **Contexte camerounais** : Dans les zones rurales du Nord-Ouest ou du Sud-Ouest, un algorithme peut être utilisé pour optimiser la distribution de l’eau potable par pompe solaire : déterminer le meilleur horaire de pompage en fonction de l’ensoleillement et de la demande villageoise. Un autre exemple : un algorithme pour calculer le prix du café vendu par les coopératives de producteurs dans la région de l’Ouest, en intégrant les coûts de transport, de traitement et la marge bénéficiaire souhaitée. **Vocabulaire à retenir** : algorithme, entrée, sortie, étape, finitude, déterminisme, efficacité, problème calculable. **Exemple de sujet type examen** : *Expliquez ce qu’est un algorithme et citez trois propriétés essentielles qu’il doit posséder. Donnez un exemple d’algorithme non informatique utilisé dans la vie quotidienne au Cameroun.* **Plan de réponse** : 1. Définition d’un algorithme (suite finie d’instructions non ambiguës). 2. Trois propriétés : finitude, déterminisme, efficacité (ou entrée/sortie). 3. Exemple : recette de préparation du ndolé (étapes : laver les feuilles, piler les arachides, cuire la viande, mélanger, servir) — finie, déterministe, efficace. --- ## II. Algorithmic Instructions Les instructions algorithmiques de base sont les éléments constitutifs de tout algorithme. Elles permettent de manipuler des données et de contrôler le flux d’exécution. Les cinq types fondamentaux sont : 1. **Entrée (Input)** : lecture de données depuis l’extérieur (clavier, capteur, fichier). 2. **Sortie (Output)** : affichage ou transmission de résultats (écran, imprimante, réseau). 3. **Affectation (Assignment)** : stockage d’une valeur dans une variable (ex. `total ← total + prix`). 4. **Calcul (Computation)** : opération arithmétique ou logique (ex. `moyenne ← somme / n`). 5. **Échange (Swap)** : échange des valeurs de deux variables (souvent utilisé dans le tri). > **À retenir** : Toute variable doit être initialisée avant son utilisation pour éviter les comportements indéfinis. **Exemple concret** : Un algorithme pour calculer le coût total d’achat de manuels scolaires dans une école de Bamenda : - Entrée : nombre de manuels, prix unitaire. - Affectation : `total ← 0`. - Boucle (à venir) : pour chaque manuel, `total ← total + prix`. - Sortie : afficher `total`. **Vocabulaire à retenir** : entrée, sortie, affectation, variable, constante, calcul, échange, initialisation. **Exemple de sujet type examen** : *Écrivez les instructions algorithmiques nécessaires pour lire l’âge d’un élève et afficher s’il est majeur (18 ans ou plus) au Cameroun.* **Plan de réponse** : 1. Entrée : lire `âge`. 2. Affectation : aucune nécessaire ici. 3. Calcul : comparer `âge` à 18 (opération logique). 4. Sortie : afficher « Majeur » si `âge >= 18`, sinon « Mineur ». *(Note : la sélection sera développée dans la leçon suivante, mais l’instruction de comparaison appartient au calcul.)* --- ## III. Representing Algorithms — Flowcharts Un diagramme de flux (flowchart) est une représentation graphique d’un algorithme utilisant des symboles normalisés pour montrer la séquence des étapes et le flux de contrôle. Les symboles standards (ISO 5807 / ANSI) sont : - **Ovale** : début ou fin. - **Parallélogramme** : entrée ou sortie. - **Rectangle** : processus (affectation, calcul). - **Losange** : décision (sélection). - **Flèche** : flux de contrôle. - **Petit cercle** : connecteur (pour éviter les croisements de lignes sur de grands diagrammes). > **À retenir** : Un flowchart doit avoir un seul point de départ et un ou plusieurs points d’arrivée ; il ne doit pas contenir de boucles infinies non intentionnelles. **Exemple camerounais** : Flowchart pour déterminer si un étudiant est admis au GCE Advanced Level selon sa moyenne : - Début → Lire moyenne → Moyenne ≥ 5.0 ? → Oui → Afficher « Admis » → Fin Non → Afficher « Refusé » → Fin. **Avantages** : Intuitif, utile pour les débutants, facilite la détection d’erreurs logiques. **Inconvénients** : Encombrant pour les algorithmes complexes, difficile à modifier, pas adapté à la programmation directe. **Vocabulaire à retenir** : symbole, ovale, parallélogramme, rectangle, losange, flèche, connecteur, flux de contrôle, décision. **Exemple de sujet type examen** : *Dessinez un flowchart pour un algorithme qui lit trois notes d’un élève et affiche la moyenne, puis indique si l’élève a réussi (moyenne ≥ 5.0) ou échoué.* **Plan de réponse** : 1. Ovale : Début. 2. Parallélogramme : Lire note1, note2, note3. 3. Rectangle : Somme ← note1 + note2 + note3. 4. Rectangle : Moyenne ← Somme / 3. 5. Parallélogramme : Afficher Moyenne. 6. Losange : Moyenne ≥ 5.0 ? - Oui → Parallélogramme : Afficher « Réussi » → Ovale : Fin. - Non → Parallélogramme : Afficher « Échoué » → Ovale : Fin. *(Le tableau n’est pas nécessaire ici car la réponse est descriptive ; on peut toutefois faire un tableau des symboles utilisés si demandé.)* --- ## IV. Representing Algorithms — Pseudocode Le pseudocode est une description informelle d’un algorithme utilisant une syntaxe proche des langages de programmation, mais indépendante de toute langue spécifique. Il privilégie la lisibilité et la structure logique. Il utilise des mots-clés anglais standards : `INPUT`, `OUTPUT`, `SET`, `IF`, `THEN`, `ELSE`, `ENDIF`, `FOR`, `TO`, `NEXT`, `WHILE`, `ENDWHILE`. > **À retenir** : Le pseudocode doit être unambigu, structuré, et éviter les détails de bas niveau (comme la syntaxe exacte d’un langage réel). **Exemple** : Algorithme de calcul de la moyenne de trois notes : ``` INPUT note1, note2, note3 SET total ← note1 + note2 + note3 SET average ← total / 3 OUTPUT average IF average >= 5.0 THEN OUTPUT "Passed" ELSE OUTPUT "Failed" ENDIF ``` **Exemple camerounais** : Algorithme pour déterminer si un récolteur de cacao a atteint son quota journalier : ``` INPUT quota, collected IF collected >= quota THEN OUTPUT "Quota reached" ELSE OUTPUT "Quota not reached: ", quota - collected, " kg remaining" ENDIF ``` **Avantages** : Proche du code réel, facile à traduire en langage de programmation, compact. **Inconvénients** : Pas de norme universelle (légères variations selon les manuels), nécessite une traduction pour l’exécution. **Vocabulaire à retenir** : pseudocode, mot-clé, entrée, sortie, affectation, condition, boucle, indentation, lisibilité. **Exemple de sujet type examen** : *Écrivez en pseudocode un algorithme qui lit le prix d’un article et la quantité achetée, calcule le total à payer, puis applique une remise de 10% si le total dépasse 5000 FCFA.* **Plan de réponse** : 1. INPUT prix, quantité 2. SET total ← prix × quantité 3. IF total > 5000 THEN 4. SET total ← total × 0.9 5. ENDIF 6. OUTPUT total *(Remarque : la remise de 10% équivaut à multiplier par 0.9)* --- ## V. Control Structures — Sequence and Selection La **séquence** est l’exécution linéaire des instructions, une après l’autre. C’est la structure par défaut. La **sélection** permet de choisir entre différentes voies d’exécution en fonction d’une condition. Elle repose sur des expressions booléennes (vraies/fausses). Les formes principales sont : - **SI…ALORS** (simple choix) : `IF condition THEN instruction ENDIF` - **SI…ALORS…SINON** (choix binaire) : `IF condition THEN instruction1 ELSE instruction2 ENDIF` - **SI…ALORS…SINON SI…** (choix multiple) : `IF cond1 THEN instr1 ELSEIF cond2 THEN instr2 ELSE instr3 ENDIF` > **À retenir** : Dans une sélection, une seule branche est exécutée ; les conditions doivent être évaluées dans l’ordre, et dès qu’une est vraie, les suivantes sont ignorées (dans le cas de `ELSEIF`). **Exemple camerounais** : Déterminer la catégorie d’âge pour les transports en commun à Yaoundé : ``` INPUT age IF age < 5 THEN OUTPUT "Free" ELSEIF age < 18 THEN OUTPUT "Half fare" ELSEIF age < 60 THEN OUTPUT "Full fare" ELSE OUTPUT "Half fare (senior)" ENDIF ``` **Conséquences d’une mauvaise sélection** : Oublier le `ELSE` peut conduire à aucun output dans certains cas ; des conditions mal ordonnées peuvent produire des résultats erronés (ex. vérifier `age < 60` avant `age < 18` ferait que les adolescents seraient classés comme adultes). **Vocabulaire à retenir** : séquence, sélection, condition, expression booléenne, SI…ALORS, SINON, ELSEIF, branche, flux de contrôle. **Exemple de sujet type examen** : *Écrivez en pseudocode un algorithme qui lit le nombre de jours de pluie dans un mois et affiche la saison : « Saison sèche » si moins de 5 jours, « Saison de transition » si entre 5 et 10 jours inclus, « Saison des pluies » si plus de 10 jours.* **Plan de réponse** : 1. INPUT jours 2. IF jours < 5 THEN 3. OUTPUT "Saison sèche" 4. ELSEIF jours <= 10 THEN 5. OUTPUT "Saison de transition" 6. ELSE 7. OUTPUT "Saison des pluies" 8. ENDIF --- ## VI. Control Structures — Loops Les boucles permettent de répéter un bloc d’instructions tant qu’une condition est vraie, ou pour un nombre fixé d’itérations. Elles évitent la répétition manuelle du code. Deux types principaux : - **Boucle à compteur (FOR)** : utilisée quand le nombre d’itérations est connu à l’avance. `FOR counter ← start TO end STEP step DO instruction NEXT` - **Boucle conditionnelle (WHILE)** : utilisée quand le nombre d’itérations dépend d’une condition. `WHILE condition DO instruction ENDWHILE` > **À retenir** : Toute boucle doit contenir une condition de sortie clairement définie pour éviter les boucles infinies. **Exemple camerounais (FOR)** : Calculer le total des ventes de 7 jours dans un marché de Douala : ``` INPUT ventes[1..7] // tableau hypothétique pour simplifier SET total ← 0 FOR day ← 1 TO 7 DO SET total ← total + ventes[day] NEXT OUTPUT total ``` **Exemple camerounais (WHILE)** : Déterminer combien de sacs de riz de 25 kg peuvent être remplis avec une quantité donnée : ``` INPUT total_rice SET bags ← 0 WHILE total_rice >= 25 DO SET total_rice ← total_rice - 25 SET bags ← bags + 1 ENDWHILE OUTPUT bags ``` **Attention** : Dans la boucle WHILE ci-dessus, si `total_rice` est négatif ou nul au départ, la boucle ne s’exécute pas — ce qui est correct. Mais si on oublie de mettre à jour `total_rice` à l’intérieur, on obtient une boucle infinie. **Vocabulaire à retenir** : boucle, itération, compteur, FOR, WHILE, condition de sortie, boucle infinie, indice, tableau (notion introduite ici pour contexte). **Exemple de sujet type examen** : *Écrivez en pseudocode un algorithme qui lit 10 notes d’élèves et affiche la note la plus élevée.* **Plan de réponse** : 1. SET max ← 0 // en supposant des notes entre 0 et 20 2. FOR i ← 1 TO 10 DO 3. INPUT note 4. IF note > max THEN 5. SET max ← note 6. ENDIF 7. NEXT 8. OUTPUT max *(Note : on initialise max à 0 en supposant qu’aucune note n’est négative ; en pratique, on pourrait lire la première note pour l’initialiser.)* --- ## VII. Sorting and Searching Le **tri** consiste à réarranger une collection d’éléments dans un ordre spécifique (croissant ou décroissant). La **recherche** consiste à trouver un élément spécifique dans une collection. ### Tri à bulles (Bubble Sort) Algorithme simple : comparer chaque paire d’éléments adjacents et les échanger s’ils sont dans le mauvais ordre. Répéter jusqu’à ce qu’aucun échange ne soit nécessaire. > **À retenir** : Le tri à bulles effectue au pire `n(n-1)/2` comparaisons et échanges pour `n` éléments. **Exemple camerounais** : Trier les notes de 5 élèves d’une classe de Buea : `[12, 5, 18, 9, 15]` Après première passe : `[5, 12, 9, 15, 18]` (18 remonte à la fin) Après deuxième : `[5, 9, 12, 15, 18]` Après troisième : aucun échange → tri terminé. ### Recherche linéaire (Linear Search) Parcourir la liste élément par élément jusqu’à trouver la cible ou atteindre la fin. > **À retenir** : La recherche linéaire effectue au pire `n` comparaisons pour `n` éléments. **Exemple** : Chercher si la note 18 existe dans `[5, 9, 12, 15, 18]` → trouvée à la 5e position. ### Recherche dichotomique (Binary Search) Nécessite un tableau **trié**. Comparer la cible avec l’élément du milieu ; éliminer la moitié où elle ne peut pas être. Répéter sur la moitié restante. > **À retenir** : La recherche dichotomique effectue au pire `log₂(n)` comparaisons pour `n` éléments triés. **Exemple** : Chercher 12 dans `[5, 9, 12, 15, 18]` - Milieu : index 2 → valeur 12 → trouvée en 1 étape. **Avantages / Inconvénients** : | Algorithme | Temps (pire cas) | Précondition | Utilité pratique | |----------------------|------------------|--------------------|------------------| | Tri à bulles | O(n²) | Aucune | Petits ensembles, enseignement | | Recherche linéaire | O(n) | Aucune | Listes non triées, petites tailles | | Recherche dichotomique | O(log n) | Tableau trié | Grandes listes triées (annuaires, dictionnaires) | **Exemple camerounais** : Un annuaire téléphonique de Bamenda trié par nom permet une recherche dichotomique rapide pour trouver un numéro. Une liste de prix de marché non triée nécessite une recherche linéaire. **Vocabulaire à retenir** : tri, recherche, tri à bulles, recherche linéaire, recherche dichotomique, tableau trié, ordre croissant/décroissant, comparaison, échange, pire cas, meilleur cas, complexité. **Exemple de sujet type examen** : *Expliquez pourquoi la recherche dichotomique ne peut pas être appliquée à un tableau non trié, et donnez un exemple concret où elle serait utile dans un contexte scolaire camerounais.* **Plan de réponse** : 1. La recherche dichotomique repose sur l’élimination de la moitié du tableau basée sur une comparaison avec le milieu ; cette logique échoue si le tableau n’est pas trié, car on ne peut pas garantir que la cible se trouve dans une moitié spécifique. 2. Exemple : recherche d’un élève par nom dans un classement trimestriel trié par ordre alphabétique (ex. liste des meilleurs élèves de la 6e au Lycée Bilingue de Yaoundé). --- ## VIII. Establishing Correctness of Algorithms Un algorithme est **correct** s’il produit la sortie attendue pour toutes les entrées valides possibles. La correction ne dépend pas de l’efficacité, mais de la logique. Deux méthodes principales pour établir la correction : 1. **Preuve par cas (exhaustive ou par partition)** : vérifier que l’algorithme fonctionne pour tous les types d’entrées pertinents. 2. **Preuve par invariante de boucle** : pour les boucles, montrer qu’une certaine propriété (l’invariant) est vraie avant, pendant et après chaque itération. > **À retenir** : Pour prouver la correction d’une boucle, il faut montrer : (1) l’invariant est vrai initialement, (2) si vrai avant une itération, il reste vrai après, (3) la boucle se termine, et (4) l’invariant + condition de sortie implique le post-condition souhaitée. **Exemple** : Preuve de correction de l’algorithme de recherche du maximum (voir leçon VI). - Invariant : Après `i` itérations, `max` contient le maximum des `i` premières notes. - Initialisation (i=0) : aucune note lue → on peut considérer `max` comme -∞, ou mieux, on initialise avec la première note (alors invariant vrai après 1ère itération). - Maintenance : si la nouvelle note > max, on met à jour max → invariant préservé. - Termination : après 10 itérations, toutes les notes ont été vues → `max` est le maximum global. - Post-condition : `max` est effectivement le maximum de toutes les notes. **Exemple camerounais** : Vérifier la correction d’un algorithme de calcul de la TVA (19,25%) sur un achat : ``` INPUT prix_ht SET tva ← prix_ht × 0.1925 SET prix_ttc ← prix_ht + tva OUTPUT prix_ttc ``` - Invariant (trivial ici, pas de boucle) : après chaque affectation, les variables représentent les valeurs correctes. - Précondition : `prix_ht ≥ 0`. - Post-condition : `prix_ttc = prix_ht × 1.1925` → vérifié par l’arithmétique. **Conséquences d’un algorithme incorrect** : erreurs de facturation, décisions erronées (ex. refus injustifié d’admission), perte de confiance dans les systèmes. **Vocabulaire à retenir** : correction, entrée valide, post-condition, précondition, invariant de boucle, preuve par cas, preuve par invariant, terminaison, hypothèse d’induction. **Exemple de sujet type examen** : *Énoncez les quatre conditions nécessaires pour prouver la correction d’une boucle à l’aide d’une invariante, puis appliquez-les brièvement à l’algorithme de recherche du maximum de 5 notes.* **Plan de réponse** : 1. Les quatre conditions : (a) l’invariant est vrai avant la première itération, (b) si vrai avant une itération, il reste vrai après, (c) la boucle se termine après un nombre fini d’étapes, (d) l’invariant et la négation de la condition de boucle impliquent le post-condition souhaité. 2. Application au max de 5 notes : - Invariant : après i itérations, max = max des i premières notes. - (a) Après 1ère itération (i=1), max = première note → vrai. - (b) Si max était le max des i premières, après comparaison avec la (i+1)ᵉ, il devient le max des i+1 premières → invariant préservé. - (c) La boucle va de 1 à 5 → se termine après 5 itérations. - (d) Après la boucle, i=5, invariant → max = max des 5 premières notes = max de toutes les notes → post-condition atteinte. --- ## IX. Evaluating Algorithm Performance La performance d’un algorithme se mesure principalement en termes de **complexité temporelle** (temps d’exécution) et **complexité spatiale** (mémoire utilisée). On utilise la notation **Big O** pour décrire le comportement asymptotique quand la taille de l’entrée `n` devient grande. > **À retenir** : La notation O(f(n)) décrit une borne supérieure asymptotique : l’algorithme ne prendra pas plus de temps proportionnel à f(n) pour de grandes valeurs de n. On analyse généralement le **pire cas** (worst-case), parfois le meilleur cas (best-case) et le cas moyen (average-case). ### Notations clés : - **O(1)** : temps constant (ex. accès à un élément d’un tableau par indice). - **O(n)** : temps linéaire (ex. recherche linéaire, parcours d’une liste). - **O(n²)** : temps quadratique (ex. tri à bulles, deux boucles imbriquées). - **O(log n)** : temps logarithmique (ex. recherche dichotomique). - **O(n log n)** : temps linéarithmique (ex. tri efficace comme tri fusion ou tri rapide). **Exemple camerounais** : - Rechercher un élève par numéro d’inscription dans une liste non triée de 1000 élèves : O(n) → jusqu’à 1000 vérifications. - Si la liste est triée par numéro : O(log n) → environ 10 vérifications (2¹⁰ = 1024). - Trier les notes de 100 élèves avec le tri à bulles : O(n²) → ~10 000 opérations. - Avec un tri efficace : O(n log n) → ~100 × 7 = 700 opérations. **Tableau de comparaison** : | Algorithme | Complexité temporelle (pire cas) | Complexité spatiale | Exemple d’utilisation | |--------------------------|----------------------------------|---------------------|------------------------| | Accès tableau | O(1) | O(1) | Lire la 5e note d’un élève | | Recherche linéaire | O(n) | O(1) | Trouver un nom dans un registre non trié | | Recherche dichotomique | O(log n) | O(1) | Trouver un nom dans un annuaire téléphonique trié | | Tri à bulles | O(n²) | O(1) | Trier 10 notes de classe | | Tri fusion | O(n log n) | O(n) | Trier les résultats de 500 candidats au GCE | **Conséquences** : Un algorithme O(n²) devient impraticable pour de grandes données (ex. traiter les résultats de tous les candidats au GCE au Cameroun : ~50 000 élèves → 2,5 milliards d’opérations pour le tri à bulles vs ~50 000 × 16 = 800 000 pour un tri efficace). **Vocabulaire à retenir** : performance, complexité temporelle, complexité spatiale, notation Big O, pire cas, meilleur cas, cas moyen, temps constant, linéaire, quadratique, logarithmique, linéarithmique, efficacité, évolutivité. **Exemple de sujet type examen** : *Un algorithme A a une complexité temporelle O(n²) et un algorithme B a une complexité O(n log n). Pour de grandes valeurs de n, lequel est plus efficace ? Justifiez votre réponse en vous appuyant sur la définition de la notation Big O.* **Plan de réponse** : 1. L’algorithme B (O(n log n)) est plus efficace que l’algorithme A (O(n²)) pour de grandes valeurs de n. 2. Justification : La notation O(g(n)) signifie que le temps d’exécution est borné supérieurement par une constante fois g(n) pour de suffisamment grandes n. 3. Puisque n log n croît beaucoup plus lentement que n² lorsque n augmente (car log n << n pour n > 10), il existe une valeur n₀ au-delà de laquelle n log n < k × n² pour toute constante k > 0. 4. Donc, pour de grandes entrées, B sera toujours plus rapide qu’A. *(Exemple illustratif : pour n=1000, n²=1 000 000, n log₂ n ≈ 1000×10=10 000 ; B est ~100 fois plus rapide.)* --- ## Synthèse du chapitre - Un algorithme est une procédure finie et non ambiguë pour résoudre un problème. - Les instructions de base sont : entrée, sortie, affectation, calcul, échange. - Les flowchart représentent visuellement le flux de contrôle avec des symboles normalisés. - Le pseudocode offre une représentation textuelle structurée, proche du code réel. - Les structures de contrôle sont : séquence (exécution linéaire), sélection (branchement conditionnel) et boucle (répétition). - Les boucles FOR sont à compteur connu ; les boucles WHILE dépendent d’une condition. - Le tri à bulles est simple mais inefficace (O(n²)) ; la recherche linéaire est O(n) ; la recherche dichotomique nécessite un tri préalable et est O(log n). - La correction d’un algorithme se prouve par vérification des cas ou par invariante de boucle. - La performance se mesure en complexité temporelle et spatiale via la notation Big O ; O(1) < O(log n) < O(n) < O(n log n) < O(n²) pour de grandes n. - Les exemples concrets tirés du contexte camerounais et africain (écoles, marchés, transports, agriculture) ancrent les concepts abstraits dans la réalité locale. ## Glossaire - **Algorithme** : Suite finie et non ambiguë d’instructions pour résoudre un problème. - **Entrée (Input)** : Opération de lecture de données depuis l’extérieur. - **Sortie (Output)** : Opération d’affichage ou de transmission de résultats. - **Affectation** : Opération qui stocke une valeur dans une variable (ex. `x ← 5`). - **Flux de contrôle** : Ordre dans lequel les instructions d’un algorithme sont exécutées. - **Sélection** : Structure de contrôle qui permet de choisir entre différentes voies d’exécution selon une condition. - **Boucle (Loop)** : Structure de contrôle qui répète un bloc d’instructions tant qu’une condition est vraie ou pour un nombre fixé d’itérations. - **Tri à bulles (Bubble Sort)** : Algorithme de tri simple qui compare et échange des éléments adjacents jusqu’à ce que la liste soit triée. - **Recherche dichotomique (Binary Search)** : Algorithme de recherche efficace qui fonctionne sur un tableau trié en divisant répétitivement l’intervalle de recherche en deux. - **Notation Big O** : Notation asymptotique qui décrit la borne supérieure de la complexité temporelle ou spatiale d’un algorithme. - **Invariante de boucle** : Propriété qui reste vraie avant, pendant et après chaque itération d’une boucle, utilisée pour prouver sa correction. - **Pire cas (Worst-case)** : Scénario d’entrée qui entraîne le temps d’exécution ou l’utilisation de mémoire le plus élevé pour un algorithme donné.