Principes d'Algorithmique et de Programmation

1. Qu'est-ce qu'un algorithme ?

Un algorithme est une séquence finie et non ambiguë d'instructions ou d'opérations permettant de résoudre un problème donné ou d'accomplir une tâche spécifique. Il s'agit d'une méthode pas à pas, indépendante de tout langage de programmation, qui décrit la logique de résolution.

Méthode
Comprendre le problème : Identifier clairement l'objectif, les données d'entrée (ce que l'algorithme reçoit) et les données de sortie (ce qu'il doit produire).
Décomposer le problème : Diviser le problème en sous-problèmes plus petits et plus gérables.
Établir la séquence d'opérations : Définir l'ordre logique des étapes à suivre pour passer des entrées aux sorties.
Utiliser un pseudo-code ou un organigramme : Représenter l'algorithme de manière structurée et compréhensible, en évitant toute ambiguïté.
Tester l'algorithme : Vérifier son fonctionnement avec des exemples concrets pour s'assurer qu'il produit les résultats attendus dans différents scénarios.

Exemple
Écrire un algorithme pour calculer la moyenne de trois nombres saisis par l'utilisateur.

Corrigé pas à pas
Voici l'algorithme en pseudo-code :

Algorithme CalculMoyenneTroisNombres

Début
Variables :
nombre1, nombre2, nombre3 : Nombres réels
somme : Nombre réel
moyenne : Nombre réel

Entrée :
Afficher "Veuillez saisir le premier nombre : "
Lire nombre1
Afficher "Veuillez saisir le deuxième nombre : "
Lire nombre2
Afficher "Veuillez saisir le troisième nombre : "
Lire nombre3

Traitement :
somme \leftarrow nombre1 + nombre2 + nombre3
moyenne \leftarrow somme / 3

Sortie :
Afficher "La moyenne des trois nombres est : ", moyenne
Fin

Erreurs fréquentes
Ambiguïté des instructions : Une instruction doit être claire et ne laisser aucune place à l'interprétation. Par exemple, "Prendre un nombre" est ambigu ; "Saisir un nombre entier" est précis.
Instructions manquantes : Omettre une étape essentielle peut rendre l'algorithme incomplet ou incorrect. Par exemple, oublier l'initialisation d'une variable.
Boucle infinie : Une condition de sortie de boucle mal définie peut entraîner l'exécution indéfinie de l'algorithme.
Ordre incorrect des opérations : L'ordre des instructions est crucial. Une inversion peut altérer le résultat final.

2. Les structures algorithmiques fondamentales

Pour construire des algorithmes efficaces, on utilise des structures de contrôle qui permettent d'organiser le flux d'exécution. Les trois structures fondamentales sont la séquence, la conditionnelle et l'itérative.

Méthode
Identifier la nature du problème : Déterminer si les instructions doivent être exécutées séquentiellement, sous certaines conditions, ou répétées un certain nombre de fois.
Choisir la structure adaptée :
• Séquence : Pour des instructions exécutées l'une après l'autre.
• Conditionnelle (Si...Alors...Sinon) : Pour exécuter des blocs d'instructions différents selon qu'une condition est vraie ou fausse.
• Itérative (Pour, Tant Que) : Pour répéter un bloc d'instructions plusieurs fois.
Définir précisément les conditions et les bornes : Pour les structures conditionnelles et itératives, les conditions logiques et les critères d'arrêt doivent être formulés sans ambiguïté.
Combiner les structures : Les algorithmes complexes sont souvent construits en imbriquant ou en combinant ces structures de base.

Exemple
Écrire un algorithme qui calcule la somme des entiers de 1 jusqu'à un nombre $N$ saisi par l'utilisateur.

Corrigé pas à pas
Voici l'algorithme en pseudo-code utilisant une structure itérative :

Algorithme SommeNPremiersEntiers

Début
Variables :
N : Nombre entier (le nombre jusqu'où sommer)
somme : Nombre entier (initialisée à 0)
i : Nombre entier (compteur de boucle)

Entrée :
Afficher "Veuillez saisir un nombre entier positif N : "
Lire N

Traitement :
somme \leftarrow 0
Pour i allant de 1 à N faire
somme \leftarrow somme + i
Fin Pour

Sortie :
Afficher "La somme des entiers de 1 à ", N, " est : ", somme
Fin

Erreurs fréquentes
Condition de boucle incorrecte : Utiliser un opérateur de comparaison erroné (par exemple, `<` au lieu de `<=`) peut entraîner une exécution trop courte ou trop longue de la boucle.
Initialisation ou mise à jour manquante : Oublier d'initialiser une variable avant une boucle ou de la mettre à jour à l'intérieur de la boucle peut provoquer des résultats incorrects ou des boucles infinies.
Inversion des branches conditionnelles : Exécuter le bloc "Alors" quand la condition est fausse, et inversement, mène à un comportement inattendu.
Indentation incorrecte (en programmation) : Dans de nombreux langages, l'indentation définit les blocs d'instructions. Une indentation erronée peut modifier la logique de l'algorithme.

3. Introduction à la programmation avec Python

La programmation consiste à traduire un algorithme, écrit en pseudo-code, en un langage de programmation spécifique (comme Python, C++, Java, etc.) que l'ordinateur peut comprendre et exécuter. Python est un langage de programmation interprété, de haut niveau, largement utilisé pour sa simplicité et sa lisibilité.

Méthode
Comprendre la syntaxe du langage : Chaque langage a ses propres règles d'écriture (mots-clés, ponctuation, indentation).
Déclarer les variables : En Python, les variables sont créées lors de leur première affectation. Le type est dynamique.
Utiliser les opérateurs : Appliquer les opérateurs arithmétiques ($+,-,*,/,\%$) et logiques ($==, !=, <, >, <=, >=, \text{and}, \text{or}, \text{not}$).
Implémenter les structures de contrôle : Traduire les structures séquentielles, conditionnelles (`if/elif/else`) et itératives (`for`, `while`) en code Python.
Gérer les entrées/sorties : Utiliser des fonctions comme `input()` pour les entrées utilisateur et `print()` pour afficher les résultats.
Tester et déboguer : Exécuter le programme et corriger les erreurs (bugs) de syntaxe ou de logique.

Exemple
Traduire l'algorithme de calcul de la moyenne de trois nombres en Python.

Corrigé pas à pas
```python
# Algorithme CalculMoyenneTroisNombres en Python

# Entrée :
nombre1 = float(input("Veuillez saisir le premier nombre : "))
nombre2 = float(input("Veuillez saisir le deuxième nombre : "))
nombre3 = float(input("Veuillez saisir le troisième nombre : "))

# Traitement :
somme = nombre1 + nombre2 + nombre3
moyenne = somme / 3

# Sortie :
print("La moyenne des trois nombres est :", moyenne)
```

Explication des fonctions Python utilisées :
• `input("message")` : Affiche le message et attend que l'utilisateur saisisse une valeur au clavier. Cette valeur est toujours une chaîne de caractères (string).
• `float(valeur)` : Convertit la `valeur` (ici, une chaîne de caractères) en un nombre décimal (flottant).
• `print(valeur1, valeur2, ...)` : Affiche les valeurs à l'écran, séparées par des espaces par défaut.

Erreurs fréquentes
Erreurs de syntaxe : Fautes de frappe, oubli de parenthèses, de deux-points (`:`) ou de guillemets, utilisation incorrecte des mots-clés du langage.
Erreurs de type : Tenter d'effectuer une opération arithmétique sur une chaîne de caractères sans la convertir préalablement en nombre (par exemple, `input()` renvoie toujours une chaîne).
Erreurs d'indentation : En Python, l'indentation (les espaces ou tabulations au début d'une ligne) est cruciale pour définir les blocs de code (conditions, boucles, fonctions). Une indentation incorrecte génère une erreur.
Logique incorrecte : Le programme s'exécute sans erreur de syntaxe, mais ne produit pas le résultat attendu car la logique de l'algorithme est mal traduite ou erronée.

1. Écrire un algorithme séquentiel (Entrée-Traitement-Sortie)

1. Étape 1 : Identifier les entrées. Déterminer quelles informations l'algorithme a besoin de recevoir de l'utilisateur ou d'une source externe.
2. Étape 2 : Définir le traitement. Établir la série d'opérations mathématiques ou logiques à effectuer sur les entrées pour obtenir le résultat souhaité. Utiliser des variables pour stocker les valeurs intermédiaires.
3. Étape 3 : Spécifier les sorties. Indiquer quelles informations l'algorithme doit afficher ou renvoyer à l'utilisateur une fois le traitement terminé.

Exemple
Écrire un algorithme pour calculer le périmètre d'un rectangle, connaissant sa longueur et sa largeur.

Corrigé pas à pas
Algorithme CalculPerimetreRectangle

Début
Variables :
longueur : Nombre réel
largeur : Nombre réel
perimetre : Nombre réel

Entrée :
Afficher "Veuillez saisir la longueur du rectangle : "
Lire longueur
Afficher "Veuillez saisir la largeur du rectangle : "
Lire largeur

Traitement :
perimetre \leftarrow 2 \times (longueur + largeur)

Sortie :
Afficher "Le périmètre du rectangle est : ", perimetre
Fin

2. Utiliser la structure conditionnelle "Si...Alors...Sinon"

1. Étape 1 : Définir la condition. Identifier l'expression logique qui doit être évaluée (vraie ou fausse). Cette condition utilise souvent des opérateurs de comparaison ($<, >, <=, >=, ==, !=$).
2. Étape 2 : Spécifier l'action "Alors". Décrire le bloc d'instructions à exécuter si la condition est vraie.
3. Étape 3 : Spécifier l'action "Sinon" (optionnel). Décrire le bloc d'instructions à exécuter si la condition est fausse. Si aucune action spécifique n'est requise lorsque la condition est fausse, la partie "Sinon" peut être omise.

Exemple
Écrire un algorithme qui détermine si un nombre entier saisi par l'utilisateur est pair ou impair.

Corrigé pas à pas
Algorithme PairOuImpair

Début
Variable :
nombre : Nombre entier

Entrée :
Afficher "Veuillez saisir un nombre entier : "
Lire nombre

Traitement et Sortie :
Si nombre \% 2 == 0 Alors
Afficher "Le nombre est pair."
Sinon
Afficher "Le nombre est impair."
Fin Si
Fin

Note : L'opérateur `%` (modulo) donne le reste de la division euclidienne. Si `nombre % 2` est égal à 0, le nombre est pair.

3. Utiliser la structure itérative "Pour" ou "Tant Que"

1. Étape 1 : Choisir le type de boucle.
   • Utiliser "Pour" lorsque le nombre d'itérations est connu à l'avance (par exemple, répéter 10 fois).
   • Utiliser "Tant Que" lorsque le nombre d'itérations dépend d'une condition qui peut changer pendant l'exécution (par exemple, répéter tant qu'une condition est vraie).
2. Étape 2 : Initialiser les variables de boucle. Pour une boucle "Pour", définir la valeur de départ du compteur. Pour une boucle "Tant Que", s'assurer que la condition de la boucle est initialement vraie (ou fausse si la boucle ne doit pas s'exécuter).
3. Étape 3 : Définir la condition de continuation/d'arrêt. Pour une boucle "Pour", spécifier la valeur finale du compteur. Pour une boucle "Tant Que", définir la condition qui, lorsqu'elle devient fausse, arrête la boucle.
4. Étape 4 : Définir le corps de la boucle. Écrire les instructions à répéter à chaque itération.
5. Étape 5 : Mettre à jour les variables de boucle. Pour une boucle "Pour", l'incrémentation du compteur est souvent automatique. Pour une boucle "Tant Que", s'assurer qu'une instruction dans le corps de la boucle modifie la condition pour qu'elle puisse éventuellement devenir fausse et éviter une boucle infinie.

Exemple
Écrire un algorithme qui affiche tous les nombres entiers de 1 à 10.

Corrigé pas à pas
Algorithme AfficherNombres

Début
Variable :
i : Nombre entier (compteur)

Traitement et Sortie :
Pour i allant de 1 à 10 faire
Afficher i
Fin Pour
Fin

Définitions Clés

• Algorithme : Séquence finie et non ambiguë d'instructions pour résoudre un problème.
• Programmation : Traduction d'un algorithme en un langage compréhensible par une machine.
• Variable : Emplacement nommé en mémoire pour stocker une valeur qui peut changer durant l'exécution de l'algorithme/programme.

Structures Algorithmiques Fondamentales

• Séquence : Instructions exécutées dans l'ordre (ex: `instruction1; instruction2;`).
• Conditionnelle : Exécution sélective d'instructions (ex: `Si condition Alors bloc1 Sinon bloc2 Fin Si`).
• Itérative (boucle) : Répétition d'instructions (ex: `Pour i allant de 1 à N faire bloc Fin Pour` ou `Tant Que condition faire bloc Fin Tant Que`).

Opérateurs Courants (Python)

• Arithmétiques : `+` (addition), `-` (soustraction), `*` (multiplication), `/` (division), `//` (division entière), `%` (modulo), `**` (puissance).
• Comparaison : `==` (égal à), `!=` (différent de), `<` (inférieur à), `>` (supérieur à), `<=` (inférieur ou égal à), `>=` (supérieur ou égal à).
• Logiques : `and` (et), `or` (ou), `not` (non).