UA5 : Introduction à l'algorithmique

# UA5 : Introduction à l'algorithmique ## Objectifs et prérequis Ce chapitre vise à initier les élèves de Seconde à l'algorithmique, discipline fondamentale de l'informatique. À l'issue de ce cours, l'élève sera capable de : - Comprendre ce qu'est un algorithme et ses caractéristiques essentielles ; - Traduire un problème simple en une suite d'instructions ordonnées ; - Utiliser les structures de contrôle séquentielles, conditionnelles et itératives ; - Écrire des algorithmes en pseudocode clair et structuré ; - Vérifier la correction d'un algorithme par des exemples de traces ; - Résoudre des problèmes concrets en décomposant les étapes logiques. **Prérequis** : Maîtrise des opérations arithmétiques de base, notion de variable (en mathématiques), capacité à suivre une consigne étape par étape, familiarité avec l'idée de consigne ou de règle (comme dans un jeu ou une recette). --- ## I. Notions de base en algorithmique ### Définition d'un algorithme Un algorithme est une suite finie et non ambiguë d'opérations bien définies, permettant de résoudre un problème ou d'accomplir une tâche, en passant d'un état initial à un état final attendu. > Un algorithme doit satisfaire cinq propriétés essentielles : > - **Finitude** : il se termine après un nombre fini d'étapes. > - **Déterminisme** : à chaque étape, l'action à exécuter est clairement définie. > - **Entrées** : il peut recevoir des données d'entrée (zéro ou plus). > - **Sorties** : il produit un résultat (une ou plusieurs valeurs). > - **Efficacité** : chaque étape doit être réalisable en principe par un agent humain ou mécanique avec des moyens simples. > Exemple : L'algorithme de la division euclidienne pour trouver le PGCD de deux nombres est fini, déterministe, prend deux entrées (a, b), produit une sortie (le PGCD), et chaque étape (soustraction ou division) est élémentaire. ### Représentation d'un algorithme Un algorithme peut être représenté de plusieurs façons : - En langage naturel (ex : recette de cuisine) ; - En pseudocode (langage intermédiaire entre naturel et code de programmation) ; - En diagramme de flux (flowchart) ; - En langage de programmation réel (Python, Scratch, etc.). En classe de Seconde, nous privilégions le **pseudocode** pour sa lisibilité et son indépendance par rapport à un langage de programmation spécifique. ### Structure d'un algorithme en pseudocode Un algorithme en pseudocode suit généralement cette structure : ``` Algorithme : [Nom de l'algorithme] Variables : [liste des variables avec leur type si nécessaire] Début [instructions] Fin ``` > Les variables sont des noms qui représentent des valeurs pouvant changer pendant l'exécution. Elles doivent être déclarées avant utilisation. > Exemple : Pour calculer la moyenne de deux notes : ``` Algorithme : MoyenneDeuxNotes Variables : note1, note2, moyenne : réel Début Ecrire "Entrez la première note : " Lire note1 Ecrire "Entrez la deuxième note : " Lire note2 moyenne ← (note1 + note2) / 2 Ecrire "La moyenne est : ", moyenne Fin ``` ### Trace d'un algorithme La trace consiste à suivre pas à pas l'exécution d'un algorithme en notant les valeurs des variables à chaque étape. Elle permet de vérifier le comportement et de détecter les erreurs. > Exemple : Trace de l'algorithme ci-dessus avec note1 = 12, note2 = 14 : | Étape | Instruction | note1 | note2 | moyenne | Affichage | |-------|---------------------------|-------|-------|---------|-------------------------------| | 1 | Lire note1 | 12 | ? | ? | "Entrez la première note : " | | 2 | Lire note2 | 12 | 14 | ? | "Entrez la deuxième note : " | | 3 | moyenne ← (12+14)/2 | 12 | 14 | 13 | | | 4 | Ecrire moyenne | 12 | 14 | 13 | "La moyenne est : 13" | ### Exercices d'application corrigés **Exercice 1** : Écrire un algorithme qui demande l'âge d'une personne et affiche si elle est majeure (âge ≥ 18) ou mineure. **Correction** : ``` Algorithme : VerificationMajorite Variables : age : entier Début Ecrire "Entrez votre âge : " Lire age Si age >= 18 Alors Ecrire "Vous êtes majeur." Sinon Ecrire "Vous êtes mineur." FinSi Fin ``` Trace avec age = 20 : | Étape | Instruction | age | Affichage | |-------|----------------------|-----|-------------------------------| | 1 | Lire age | 20 | "Entrez votre âge : " | | 2 | Si 20 >= 18 → Vrai | 20 | | | 3 | Ecrire "majeur" | 20 | "Vous êtes majeur." | Trace avec age = 15 : | Étape | Instruction | age | Affichage | |-------|----------------------|-----|-------------------------------| | 1 | Lire age | 15 | "Entrez votre âge : " | | 2 | Si 15 >= 18 → Faux | 15 | | | 3 | Ecrire "mineur" | 15 | "Vous êtes mineur." | **Exercice 2** : Écrire un algorithme qui lit trois nombres et affiche le plus grand. **Correction** : ``` Algorithme : PlusGrandDeTrois Variables : a, b, c, max : réel Début Ecrire "Entrez le premier nombre : " Lire a Ecrire "Entrez le deuxième nombre : " Lire b Ecrire "Entrez le troisième nombre : " Lire c max ← a Si b > max Alors max ← b FinSi Si c > max Alors max ← c FinSi Ecrire "Le plus grand nombre est : ", max Fin ``` Trace avec a=5, b=9, c=3 : | Étape | Instruction | a | b | c | max | Action | |-------|----------------------|---|---|---|-----|----------------------------| | 1 | Lire a | 5 | ? | ? | ? | | | 2 | Lire b | 5 | 9 | ? | ? | | | 3 | Lire c | 5 | 9 | 3 | ? | | | 4 | max ← a | 5 | 9 | 3 | 5 | | | 5 | Si b>max (9>5) → Vrai| 5 | 9 | 3 | 9 | max ← b | | 6 | Si c>max (3>9) → Faux| 5 | 9 | 3 | 9 | | | 7 | Ecrire max | 5 | 9 | 3 | 9 | "Le plus grand est : 9" | --- ## II. Structures de contrôles Les structures de contrôle permettent de modifier le flux d'exécution d'un algorithme selon des conditions ou de répéter des actions. Il en existe trois types fondamentaux : séquentielle, conditionnelle et itérative. ### Structure séquentielle C'est l'exécution linéaire des instructions, une après l'autre, dans l'ordre d'écriture. > Dans une structure séquentielle, chaque instruction est exécutée exactement une fois, dans l'ordre où elle apparaît. Exemple : L'algorithme de la moyenne de deux notes (section précédente) est entièrement séquentiel sauf pour les entrées/sorties, mais le cœur du calcul `(note1+note2)/2` suit une séquence fixe. ### Structure conditionnelle Elle permet d'exécuter une instruction ou un bloc d'instructions seulement si une condition est vraie. Elle introduit un choix dans le flux d'exécution. > La structure conditionnelle simple s'écrit : > `Si <condition> Alors` > `<instructions>` > `FinSi` > La structure conditionnelle complète (avec alternative) s'écrit : > `Si <condition> Alors` > `<instructions si vrai>` > `Sinon` > `<instructions si faux>` > `FinSi` > Une condition est une expression logique qui vaut Vrai ou Faux. Elle peut comparer des valeurs (`>`, `<`, `>=`, `<=`, `=`, `≠`) ou combiner des propositions avec `Et`, `Ou`, `Non`. > Exemple : Pour vérifier si un nombre est pair : ``` Algorithme : EstPair Variables : n : entier Début Ecrire "Entrez un entier : " Lire n Si n Mod 2 = 0 Alors Ecrire n, " est pair." Sinon Ecrire n, " est impair." FinSi Fin ``` > Ici, `n Mod 2` donne le reste de la division de `n` par 2. Si ce reste est 0, le nombre est pair. **Exercice corrigé** : Écrire un algorithme qui lit une note sur 20 et affiche la mention selon le barème : - < 10 : Insuffisant - 10 ≤ note < 12 : Passable - 12 ≤ note < 14 : Assez bien - 14 ≤ note < 16 : Bien - ≥ 16 : Très bien **Correction** : ``` Algorithme : MentionNote Variables : note : réel Début Ecrire "Entrez la note sur 20 : " Lire note Si note < 10 Alors Ecrire "Insuffisant" Sinon Si note < 12 Alors Ecrire "Passable" Sinon Si note < 14 Alors Ecrire "Assez bien" Sinon Si note < 16 Alors Ecrire "Bien" Sinon Ecrire "Très bien" FinSi Fin ``` Trace avec note = 13,5 : | Étape | Instruction | note | Action | |-------|---------------------------|------|----------------------------| | 1 | Lire note | 13,5 | | | 2 | Si 13,5 < 10 ? Faux | 13,5 | → aller au Sinon Si | | 3 | Si 13,5 < 12 ? Faux | 13,5 | → aller au Sinon Si | | 4 | Si 13,5 < 14 ? Vrai | 13,5 | Ecrire "Assez bien" | | 5 | Fin du Sinon Si | | | ### Structure itérative Elle permet de répéter un bloc d'instructions tant qu'une condition est vérifiée, ou un nombre fixé de fois. Elle évite la répétition manuelle du code. > La structure tant que s'écrit : > `TantQue <condition> Faire` > `<instructions>` > `FinTantQue` > La condition est testée **avant** chaque exécution du bloc. > La structure répéter jusqu'à ce que s'écrit : > `Repéter` > `<instructions>` > ` JusquÀ <condition>` > Le bloc est exécuté **au moins une fois**, puis la condition est testée en fin. > La structure pour s'écrit souvent comme : > `Pour i de <valeur_init> à <valeur_final> Faire` > `<instructions>` > `FinPour` > Elle répète le bloc un nombre fixé de fois, avec une variable d'incrémentation automatique. > Exemple : Afficher les nombres de 1 à 5. ``` Algorithme : CompterUnCinq Variables : i : entier Début Pour i de 1 à 5 Faire Ecrire i FinPour Fin ``` Trace : | Étape | i | Action | |-------|---|----------------| | Début | | i ← 1 | | 1 | 1 | Ecrire 1 | | FinIt | | i ← 2 | | 2 | 2 | Ecrire 2 | | FinIt | | i ← 3 | | 3 | 3 | Ecrire 3 | | FinIt | | i ← 4 | | 4 | 4 | Ecrire 4 | | FinIt | | i ← 5 | | 5 | 5 | Ecrire 5 | | FinIt | | i ← 6 → fin | **Exercice corrigé** : Écrire un algorithme qui demande des notes successivement et s'arrête quand l'utilisateur entre une note négative. À la fin, il affiche la somme des notes valides (≥ 0). **Correction** : ``` Algorithme : SommeNotes Variables : note, somme : réel Début somme ← 0 Repéter Ecrire "Entrez une note (négative pour terminer) : " Lire note Si note >= 0 Alors somme ← somme + note FinSi JusquÀ note < 0 Ecrire "La somme des notes valides est : ", somme Fin ``` Trace avec entrées : 12, 8, 15, -1 : | Étape | Instruction | note | somme | Action | |-------|----------------------|------|-------|----------------------------------------| | Init | somme ← 0 | ? | 0 | | | 1 | Lire note | 12 | 0 | | | 2 | Si 12>=0 → Vrai | 12 | 12 | somme ← 0+12 | | 3 | JusquÀ 12<0 ? Faux | | | → répéter | | 4 | Lire note | 8 | 12 | | | 5 | Si 8>=0 → Vrai | 8 | 20 | somme ← 12+8 | | 6 | JusquÀ 8<0 ? Faux | | | → répéter | | 7 | Lire note | 15 | 20 | | | 8 | Si 15>=0 → Vrai | 15 | 35 | somme ← 20+15 | | 9 | JusquÀ 15<0 ? Faux | | | → répéter | |10 | Lire note | -1 | 35 | | |11 | Si -1>=0 → Faux | -1 | 35 | somme inchangée | |12 | JusquÀ -1<0 ? Vrai | | | → sortir de la boucle | |13 | Ecrire somme | -1 | 35 | "La somme est : 35" | ### Tableau récapitulatif des structures de contrôle | Type | Mot-clé(s) | Condition testée | Nombre d'exécutions minimum | Cas d'usage typique | |-------------------|------------------------|------------------|------------------------------|------------------------------------------| | Séquentielle | — | Aucune | 1 | Suite d'actions indépendantes | | Conditionnelle | Si…Alors…Sinon…FinSi | Avant exécution | 0 ou 1 | Choix entre deux ou plusieurs chemins | | Itérative (TantQue)| TantQue…Faire…FinTantQue| Avant exécution | 0 | Répétition tant qu'une condition vaut vrai | | Itérative (Répéter)| Repéter…JusquÀ | Après exécution | 1 | Au moins une exécution, puis vérification | | Itérative (Pour) | Pour…de…à…Faire…FinPour| Implicite (compteur) | Valeur fixe (ex: 5 fois) | Répétition un nombre connu de fois | > Pour éviter les boucles infinies, toute structure itérative doit modifier une variable intervenant dans la condition de sortie. ### Exercices d'application corigés **Exercice 3** : Écrire un algorithme qui demande un entier positif n et affiche la somme des entiers de 1 à n. **Correction** (avec boucle Pour) : ``` Algorithme : SommeUnAN Variables : n, i, somme : entier Début Ecrire "Entrez un entier positif n : " Lire n somme ← 0 Pour i de 1 à n Faire somme ← somme + i FinPour Ecrire "La somme des entiers de 1 à ", n, " est : ", somme Fin ``` Trace avec n=4 : | Étape | i | somme avant | somme après (somme+i) | Action | |-------|---|-------------|------------------------|----------------------------| | Init | | 0 | | somme ← 0 | | Boucle| 1 | 0 | 1 | somme ← 0+1 | | Boucle| 2 | 1 | 3 | somme ← 1+2 | | Boucle| 3 | 3 | 6 | somme ← 3+3 | | Boucle| 4 | 6 | 10 | somme ← 4+6 | | Fin | | | 10 | Ecrire "somme est : 10" | **Exercice 4** : Écrire un algorithme qui vérifie si un nombre entier n (>1) est premier. Un nombre premier n'a que deux diviseurs : 1 et lui-même. **Correction** (optimisée : test jusqu'à √n) : ``` Algorithme : EstPremier Variables : n, i : entier estPremier : booléen Début Ecrire "Entrez un entier n > 1 : " Lire n estPremier ← Vrai Pour i de 2 à n//2 Faire // n//2 est la partie entière de n/2 Si n Mod i = 0 Alors estPremier ← Faux FinSi FinPour Si estPremier Alors Ecrire n, " est un nombre premier." Sinon Ecrire n, " n'est pas un nombre premier." FinSi Fin ``` > On teste jusqu'à n//2 car aucun diviseur de n ( sauf n lui-même) ne peut être supérieur à n/2. > Alternative plus efficace : tester jusqu'à ⌊√n⌋, mais nécessite la notion de racine carrée, parfois introduite plus tard. Trace avec n=7 : | Étape | i | n Mod i | estPremier avant | estPremier après | Action | |-------|---|---------|------------------|------------------|----------------------------| | Init | | | Vrai | | estPremier ← Vrai | | Boucle| 2 | 1 | Vrai | Vrai | 7 Mod 2 ≠ 0 → pas de change| | Boucle| 3 | 1 | Vrai | Vrai | 7 Mod 3 ≠ 0 | | Boucle| 4 | 3 | Vrai | Vrai | 7 Mod 4 ≠ 0 | | Boucle| 5 | 2 | Vrai | Vrai | 7 Mod 5 ≠ 0 | | Boucle| 6 | 1 | Vrai | Vrai | 7 Mod 6 ≠ 0 | | Fin | | | Vrai | Vrai | Ecrire "7 est premier" | Trace avec n=9 : | Étape | i | n Mod i | estPremier avant | estPremier après | Action | |-------|---|---------|------------------|------------------|----------------------------| | Init | | | Vrai | | estPremier ← Vrai | | Boucle| 2 | 1 | Vrai | Vrai | | | Boucle| 3 | 0 | Vrai | **Faux** | 9 Mod 3 = 0 → estPremier ← Faux | | Boucle| 4 | 1 | Faux | Faux | (pas de changement utile) | | Fin | | | Faux | Faux | Ecrire "9 n'est pas premier" | --- ## Synthèse du chapitre - Un algorithme est une procédure finie, non ambiguë et efficace pour résoudre un problème. - Il se compose d'entrées, d'un traitement séquentiel de instructions, et d'une sortie. - Les variables permettent de stocker et modifier des valeurs pendant l'exécution. - La trace est un outil essentiel pour vérifier le comportement d'un algorithme pas à pas. - Les trois structures de contrôle fondamentales sont : - **Séquentielle** : exécution linéaire ; - **Conditionnelle** (`Si…Alors…Sinon…FinSi`) : choix basé sur une condition ; - **Itérative** (`TantQue…Faire…FinTantQue`, `Repéter…JusquÀ`, `Pour…de…à…Faire…FinPour`) : répétition d'actions. - Toute structure itérative doit faire évoluer une variable liée à la condition de sortie pour éviter les boucles infinies. - Le pseudocode est une représentation intermédiaire, lisible et indépendante d'un langage de programmation spécifique. - Les opérateurs de comparaison (`=`, `≠`, `<`, `>`, `≤`, `≥`) et logiques (`Et`, `Ou`, `Non`) permettent de construire des conditions. - L'opérateur modulo (`Mod`) donne le reste d'une division entière et est utile pour tester la parité ou la divisibilité. ## Glossaire - **Algorithme** : Suite finie et non ambiguë d'opérations permettant de résoudre un problème. - **Variable** : Nom symbolique représentant une valeur pouvant changer pendant l'exécution d'un algorithme. - **Instruction** : Action élémentaire que l'algorithme exécute (lire, écrire, calculer, affecter). - **Condition** : Expression logique qui évalue à Vrai ou Faux, utilisée pour diriger le flux d'exécution. - **Structure de contrôle** : Moyen de modifier l'ordre d'exécution des instructions (séquentielle, conditionnelle, itérative). - **Boucle** : Structure itérative qui répète un bloc d'instructions tant qu'une condition est vérifiée. - **Trace** : Tableau montrant l'évolution des variables et le déroulement pas à pas de l'exécution d'un algorithme. - **Pseudocode** : Représentation d'un algorithme proche du langage naturel, structurée et indépendante d'un langage de programmation spécifique. - **Affectation** : Opération qui assigne une valeur à une variable (notée ←). - **Modulo** : Opération qui donne le reste de la division entière d'un nombre par un autre (noté `Mod`). - **Booléen** : Type de donnée pouvant prendre deux valeurs : Vrai ou Faux. - **Diviseur** : Entier qui divise un autre entier sans laisser de reste.