Introduction aux Algorithmes

Nature et Rôle Fondamental des Algorithmes

Définition générale de l'algorithme :
- Un algorithme est la description formelle d'une suite finie d'étapes ordonnées permettant d'obtenir un résultat précis à partir d'éléments fournis en entrée.
- Métaphore de la recette de cuisine : Une recette constitue un algorithme du quotidien dont les ingrédients représentent les données d'entrée, les étapes de préparation forment la suite d'instructions et le plat réalisé constitue le résultat final.
Applications sociétales dans le monde numérique contemporain :
- Les algorithmes mathématiques combinent des volumes considérables d'informations hétérogènes pour générer des prédictions, des analyses et des commandes automatisées :
- Modélisation épidémiologique : Simulation dynamique de la propagation des maladies saisonnières, comme l'épidémie de grippe en période hivernale.
- Systèmes de recommandation : Sélection et proposition de livres ou d'articles personnalisés à un client en fonction de l'historique d'achats et des comportements d'autres utilisateurs.
- Biométrie et reconnaissance d'images : Comparaison automatisée d'images numériques faciales ou d'empreintes digitales à des fins d'identification.
- Robotique et systèmes autonomes : Pilotage en temps réel d'automobiles autonomes ou guidage de trajectoire pour des sondes spatiales en mission interplanétaire.
Implémentation informatique sous forme de logiciel :
- Pour être exécuté par un ordinateur ou un processeur, l'algorithme doit obligatoirement être transcrit dans un langage informatique compréhensible par la machine.
- Cette concrétisation logicielle porte le nom de logiciel ou d'application.
- Un logiciel complexe articule et imbrique en pratique une multitude d'algorithmes élémentaires dédiés à des rôles spécifiques :
- Saisie et filtrage des données d'entrée.
- Exécution séquentielle des calculs et transformations logiques.
- Rendu visuel et affichage des résultats à l'écran.
- Protocoles de communication et d'échange de flux avec d'autres programmes informatiques.

Environnements d'Implémentation et Traduction Multilangage

Comparaison de l'implémentation d'un algorithme en langage naturel, Scratch, calculatrice Casio Graph 35+ et Python

Problème algorithmique de référence :
- Réception de deux grandeurs en entrée : $A$ et $B$ .
- Calcul du produit de ces grandeurs : $C = A \times B$ .
- Calcul du double de la somme de ces grandeurs : $D = 2 \times (A + B)$ .
- Restitution en sortie des valeurs calculées $C$ et $D$ .
- Exécution numérique concrète : Pour les entrées $A = 2$ et $B = 3$ , le traitement produit $C = 2 \times 3 = 6$ et $D = 2 \times (2 + 3) = 2 \times 5 = 10$ .
Représentation en langage naturel (pseudo-code) :
- Saisir A
- Saisir B
- C ← A * B
- D ← 2 * (A + B)
- Afficher C
- Afficher D
Implémentation visuelle par blocs sous Scratch :
- Déclenchement événementiel : bloc initial quand drapeau vert cliqué.
- Interactions utilisateur : bloc demander [Valeur de A ?] et attendre, suivi du stockage mettre [A] à (réponse).
- Deuxième saisie : bloc demander [Valeur de B ?] et attendre, suivi du stockage mettre [B] à (réponse).
- Blocs d'opérations mathématiques : mettre [C] à ((A) * (B)) et mettre [D] à ((2) * ((A) + (B))).
- Sortie visuelle : blocs d'affichage de scène montrer la variable [C] et montrer la variable [D].
Implémentation sur calculatrice programmable (Casio Graph 35+) :
- En-tête du script : ======SNT======
- Saisie interactive de la première variable : "A = "? -> A
- Saisie interactive de la seconde variable : "B = "? -> B
- Calcul et affectation mémoire du produit : AxB -> C
- Calcul et affectation mémoire du périmètre double : 2x(A+B) -> D
- Affichage direct du résultat $C$ : "C=" : C
- Affichage direct du résultat $D$ : "D=" : D
Implémentation textuelle en langage Python :
- Ligne 1 : A = int(input("Valeur de A ?")) (recueille la chaîne saisie par l'utilisateur via input(), la convertit en entier au moyen du constructeur int() et l'affecte à la variable A).
- Ligne 2 : B = int(input("Valeur de B ?"))
- Ligne 3 : C = A*B
- Ligne 4 : D = 2*(A+B)
- Ligne 5 et suivantes : instructions d'affichage print("C =", C) et print("D =", D).

Opérations Arithmétiques, Variables et Interactions Utilisateur en Python

Opérations fondamentales et comportement selon les types de données :
- Addition (A + B) :
- Réalise la somme arithmétique classique entre deux grandeurs numériques $A$ et $B$ .
- Si $A$ et $B$ sont de type chaîne de caractères (str), l'opérateur réalise une concaténation (fusion textuelle des deux chaînes bout à bout).
- Multiplication (A * B) :
- Réalise le produit arithmétique de $A$ par $B$ .
- Si l'une des opérandes est une chaîne de caractères et l'autre un entier positif, l'opérateur réalise une répétition de la chaîne le nombre de fois spécifié.
- Division standard (A / B) :
- Renvoie le quotient de la division de $A$ par $B$ , noté formellement $\frac{A}{B}$ .
- Élévation à la puissance (A ** B) :
- Calcule la puissance de $A$ exposant $B$ , notée mathématiquement $A^B$ .
- Racine carrée (sqrt(a)) :
- Calcule $\sqrt{a}$ .
- Cette fonction nécessite impérativement le chargement de la bibliothèque standard dédiée aux mathématiques via la commande from math import sqrt ou import math.
Affectation de variables :
- Syntaxe : x = 12.5 ou x = c.
- Rôle : Stocke en mémoire la valeur littérale flottante $12{,}5$ ou le contenu déjà existant de la variable $c$ dans l'espace mémoire identifié par le nom de variable $x$ .
Instructions d'entrée de données (interactions clavier) :
- Saisie d'un entier : x = int(input("Entrer x :"))
- Suspend l'exécution du programme, affiche l'invite "Entrer x :", attend la saisie clavier de l'utilisateur, convertit la chaîne saisie en nombre entier (int pour integer) et affecte la valeur finale à la variable $x$ .
- Saisie d'un nombre décimal / flottant : x = float(input("Entrer x :"))
- Sollicite la saisie de l'utilisateur, la transtype en nombre à virgule flottante (float) et l'enregistre dans $x$ .
- Saisie universelle avec évaluation d'expression : x = eval(input("Entrer x :"))
- Attend une saisie numérique pouvant être une fraction de la forme $\frac{a}{b}$ ou une expression contenant des fonctions mathématiques telles que sqrt(a), interprète et évalue mathématiquement l'expression avant de stocker le résultat dans la variable $x$ .
Instructions de sortie console :
- print(x) : Affiche sur la console standard la valeur courante contenue dans la variable $x$ .
- print("Bonjour ") : Affiche textuellement la chaîne de caractères (ou message) délimitée par les guillemets.

Structures Conditionnelles en Python : Les Instructions if, elif et else

Rôle et fonctionnement des instructions conditionnelles :
- Permettent d'aiguiller le flux d'exécution d'un programme informatique selon différentes directions logiques.
- Déterminent de manière dynamique si les blocs d'instructions subordonnés doivent être exécutés ou ignorés en fonction de la validité d'une ou plusieurs conditions booléennes.
Correspondances syntaxiques entre langage naturel et langage Python :
- Le motif traditionnel de langage naturel Si condition alors : Instruction(s) 1 Sinon : Instruction(s) 2 se traduit par le couple if - else.
- Le mot-clé « alors » n'existe pas en Python. Il est rigoureusement remplacé par l'indentation, c'est-à-dire un décalage automatique vers la droite des lignes de code dépendantes.
- Pour déclencher cette indentation, il est obligatoire de clore la ligne de test conditionnel par le caractère deux-points :.
- L'opérateur de test d'égalité stricte entre deux expressions s'écrit == (à distinguer impérativement du signe d'affectation unique =).
- Le mot-clé elif constitue une contraction syntaxique propre à Python de l'expression anglaise else if (« sinon si »), autorisant l'enchaînement de conditions additionnelles sans empilement excessif d'indentations.
Les trois niveaux de structures conditionnelles :
- Structure 1 : Une seule condition isolée
- Syntaxe formelle Python : python if condition: instruction(s)       
Énoncé en langage naturel : Si $x$ est supérieur ou égal à $3$ alors $m \leftarrow 2 \times x$ .
Transcription Python : python if x >= 3: m = 2*x       
Structure 2 : Une condition assortie d'une alternative exclusive
- Syntaxe formelle Python : python if condition: instruction(s) 1 else: instruction(s) 2       
Énoncé en langage naturel : Si $x$ est supérieur ou égal à $3$ alors $m \leftarrow 2 \times x$ Sinon $m \leftarrow 2 \times x + 1$ .
Transcription Python : python if x >= 3: m = 2*x else: m = 2*x + 1       
Structure 3 : Deux conditions ou plus (branchements multiples)
- Syntaxe formelle Python : python if condition 1: instruction(s) 1 elif condition 2: instruction(s) 2 else: instruction(s) 3       
Énoncé en langage naturel : Si $x$ est inférieur ou égal à $2$ alors $m \leftarrow 2 \times x$ Sinon si $x$ est strictement compris entre $2$ et $5$ alors $m \leftarrow 2 \times x + 5$ Sinon $m \leftarrow x^2$ .
Transcription Python : python if x <= 2: m = 2*x elif 2 < x < 5: m = 2*x + 5 else: m = x**2

Structures Itératives Bornées : La Boucle for et la Fonction range()

Principe de la boucle bornée for :
- Indispensable lorsqu'un programme nécessite la répétition d'un bloc d'instructions un nombre défini de fois.
- S'utilise exclusivement lorsque le nombre total d'itérations est connu à l'avance avant l'entrée dans la structure itérative.
Syntaxe générale :

  for variable in range(...):
      instruction(s)
&nbsp;&nbsp;```

- **Modes d'appel de la fonction génératrice range() :**
  - *Format à un seul argument :* `range(n)`
    - Le paramètre  $n$  représente un entier positif.
    - La variable de boucle prend successivement toutes les valeurs entières dans l'intervalle allant de  $0$  jusqu'à  $n - 1$ .
    - La boucle effectue exactement  $n$  passages au total.
  - *Format à deux arguments :* `range(m, n)`
    - Les paramètres  $m$  et  $n$  représentent deux entiers tels que  $m < n$ .
    - La variable de boucle prend successivement les valeurs entières de la borne inférieure incluse  $m$  jusqu'à la borne supérieure exclue  $n - 1$ .
    - La boucle effectue exactement  $n - m$  itérations.

- **Règle fondamentale d'indentation :**
  - Python ne possède aucune instruction de clôture explicite pour marquer l'arrêt de la boucle.
  - C'est le retour de l'alignement textuel vers la marge gauche (rupture de l'indentation) qui indique la fin du bloc d'instructions itéré.

- **Études d'exemples d'accumulation :**
  - *Cas d'un range simple :*
    ```python
    for i in range(3):
        S = S + i
&nbsp;&nbsp;&nbsp;&nbsp;```
  - Déroulement interne : La variable  $i$  prend successivement les valeurs entières  $0$ ,  $1$  et  $2$ .
  - Action : À chaque passage, la valeur courante de  $i$  est ajoutée à la variable accumulatrice  $S$ .
- *Cas d'un range borné à deux arguments :*
    ```python
    for i in range(12, 16):
        S = S + i
&nbsp;&nbsp;&nbsp;&nbsp;```
- Déroulement interne : La variable  $i$  parcourt strictement les valeurs entières  $12$ ,  $13$ ,  $14$  et  $15$ .
- Action : Chacune de ces valeurs entières est successivement additionnée à la variable accumulatrice  $S$ .


# Structures Itératives Non Bornées : La Boucle while et la Gestion des Compteurs

- **Principe de la boucle non bornée while :**
  - S'emploie lorsqu'il s'avère indispensable de réitérer une ou plusieurs instructions un nombre indéfini de fois.
  - S'applique lorsque le nombre précis de répétitions est **inconnu à l'avance** et dépend d'une condition d'arrêt dynamique.
  - Le bloc interne continue d'être parcouru tant qu'une condition logique définie demeure vraie.

- **Syntaxe générale en langage Python :**

python while condition: instruction(s) ```

Délimitation syntaxique du bloc :
- De manière identique à la boucle for, aucune commande textuelle spécifique ne décrète la fin de la boucle while.
- L'indentation (retrait des lignes vers la droite après les deux-points :) délimite les instructions qui tournent en boucle. Dès que le code se réaligne sur la gauche, la boucle est terminée.
Distinction majeure avec la boucle for et gestion manuelle du compteur :
- Contrairement à la boucle for, la boucle while ne possède pas de variable d'itération interne s'incrémentant automatiquement.
- Pour empêcher l'exécution d'une boucle infinie (blocage du programme), le développeur doit impérativement instaurer une variable compteur initialisée en amont et veiller à insérer dans le corps de la boucle une instruction d'incrémentation explicite du type n = n + 1 afin de modifier la condition d'arrêt à chaque passage.

Modularité et Sous-Programmes : Les Fonctions en Python

Définition et rôle d'une fonction :
- Une fonction est un sous-programme intermédiaire autonome conçu pour accomplir une tâche spécifique au sein d'un programme informatique plus large.
- Elle porte un nom explicite unique et opère sur zéro, une ou plusieurs variables d'entrée nommées arguments (ou paramètres).
Syntaxe de déclaration d'une fonction :python def nom_de_la_fonction(argument1, argument2, etc): instruction(s) return resultat   
- Le mot-clé réservé def signale l'initialisation et la déclaration du bloc fonctionnel.
- Le nom de la fonction est immédiatement suivi de parenthèses englobant les arguments attendus, puis d'un caractère deux-points : en fin de première ligne.
- L'indentation doit être rigoureusement respectée pour l'ensemble des instructions constitutives du corps de la fonction.
- Le mot-clé return ordonne la fin de la fonction et renvoie le résultat calculé vers le programme principal ou l'instruction appelante.
Exemple détaillé : Calcul de la somme de deux carrés :
- Implémentation du sous-programme : python def somme_carres(a, b): somme = a**2 + b**2 return somme     
Analyse opérationnelle : La fonction somme_carres reçoit deux arguments numériques $a$ et $b$ , calcule la somme de leurs carrés respectifs ( $a^2 + b^2$ ), l'affecte à la variable locale somme, puis transmet cette valeur finale via la clause return.
Appel et affichage : Dans le corps du script appelant, l'utilisateur sollicite la fonction par une syntaxe telle que print(somme_carres(a, b)) pour faire afficher le résultat final dans la console.

Études de Cas, Analyse d'Algorithmes et Exercices Pratiques

Étude de cas 1 : Seuil d'accumulation dans une boucle non bornée (SNT Lycée Saint-Jacques) :
- Script Python examiné : python n = 0 somme = 0 while somme <= 1000: n = n + 1 somme = somme + n     
- Rôle de la variable somme : La variable somme calcule l'accumulation progressive de la suite des entiers consécutifs non nuls, modélisant la somme arithmétique $1 + 2 + 3 + \dots + n$ .
- Interprétation de la valeur terminale $n = 45$ :
- La condition d'itération impose la poursuite du cycle tant que $\text{somme} \le 1000$ .
- À l'étape $n = 44$ , la somme cumulée s'établit à $\frac{44 \times 45}{2} = 990$ . Comme $990 \le 1000$ , le programme exécute un passage supplémentaire dans la boucle.
- Au passage suivant, le compteur passe à $n = 45$ , et la somme devient $990 + 45 = 1035$ .
- La condition $1035 \le 1000$ devenant fausse, l'exécution s'interrompt avec la valeur $n = 45$ .
- Interprétation mathématique : L'entier $45$ représente le plus petit entier naturel non nul pour lequel la somme des entiers consécutifs de $1$ à $n$ dépasse strictement le seuil de $1000$ .
Étude de cas 2 : Fonction de calcul de cinématique (vitesse) :
- Signature du sous-programme : def vitesse(distance, temps):
- Analyse de fonctionnement : Reçoit en arguments une distance parcourue et une durée temporelle écoulée, applique la formule physique fondamentale $\frac{\text{distance}}{\text{temps}}$ , puis restitue le résultat calculé par l'intermédiaire de l'instruction return.
Étude de cas 3 : Conditionnement par encadrement d'intervalle :
- Script conditionnel avec intervalle : python if 0 <= x < 1: y = 2*x     
Analyse de fonctionnement : Vérifie si la variable réelle $x$ appartient à l'intervalle semi-ouvert $[0, 1[$ . Si la double condition $x \ge 0$ et $x < 1$ est simultanément validée, le programme affecte le double de sa valeur ( $2 \times x$ ) à la variable $y$ .