Les algorithmes et la résolution de problèmes

Un algorithme est une série finie et non ambiguë d'instructions ou d'opérations permettant de résoudre un problème ou d'obtenir un résultat spécifique. Imaginez une recette de cuisine : elle vous donne des étapes précises (mélanger ceci, chauffer cela) pour arriver à un plat final. Un algorithme, c'est exactement ça, mais pour un ordinateur ou même pour un humain.

Voici les caractéristiques principales d'un algorithme :

• Fini : Il doit toujours se terminer après un nombre fini d'étapes.
• Non ambigu : Chaque instruction doit être claire et interprétable d'une seule manière.
• Complet : Il doit couvrir tous les cas possibles du problème.
• Efficace : Il doit être le plus rapide et le moins coûteux possible en ressources.

Les algorithmes sont le "mode d'emploi" pour résoudre un problème, étape par étape.

• Préparer un café : Ouvrir la machine, mettre le filtre, ajouter le café, verser l'eau, appuyer sur le bouton.
• Trouver un mot dans un dictionnaire : Ouvrir au milieu, si le mot est avant, aller à gauche ; s'il est après, aller à droite ; répéter jusqu'à trouver le mot.
• Calculer une moyenne : Additionner toutes les notes, puis diviser par le nombre de notes.

Le mot "algorithme" vient du nom d'un mathématicien perse du IXe siècle, Al-Khwarizmi (vers 780-850). Il a écrit un ouvrage fondamental sur le calcul avec les chiffres indiens (ce que nous appelons aujourd'hui les chiffres arabes), qui a introduit en Occident la notion de système décimal. Ses méthodes de calcul étaient des algorithmes.

Pendant des siècles, les algorithmes sont restés des procédures mathématiques. C'est au XXe siècle, avec l'avènement de l'informatique, qu'ils prennent une dimension nouvelle.

• Alan Turing (1912-1954) a formalisé la notion d'algorithme avec sa machine de Turing, un modèle théorique de ce qu'une machine peut calculer. C'est la base de toute l'informatique moderne.
• Dans les années 1950-1960, les premiers ordinateurs sont apparus, et avec eux, la nécessité de traduire ces algorithmes en instructions compréhensibles par la machine.
• Aujourd'hui, les algorithmes modernes sont omniprésents et de plus en plus complexes : recherche Google, systèmes de recommandation (Netflix, YouTube), intelligence artificielle (reconnaissance faciale, assistants vocaux), trading financier, etc.

De l'Antiquité à l'ère numérique, les algorithmes sont au cœur de la pensée logique et du calcul.

Il est crucial de faire la distinction entre un algorithme et un programme informatique :

• Un algorithme est une idée, une méthode générale, une séquence logique d'étapes pour résoudre un problème. Il est indépendant de tout langage de programmation et de toute machine. On peut le rédiger en langage naturel (français, anglais), en pseudo-code ou avec des organigrammes.
• Un programme informatique est la traduction concrète d'un algorithme dans un langage de programmation spécifique (comme Python, Java, C++, etc.). C'est ce programme qui est ensuite exécuté par une machine (ordinateur, smartphone).

Analogie :

• L'algorithme est la recette de cuisine (l'idée des étapes).
• Le programme est la recette écrite dans un livre de cuisine spécifique avec des unités de mesure précises et un vocabulaire particulier (la mise en œuvre de l'idée).

Un même algorithme peut être implémenté dans différents langages de programmation. Par exemple, l'algorithme pour trier une liste de nombres peut être écrit en Python, puis en Java, puis en C. Le principe reste le même, seule la syntaxe du langage change.

Un algorithme est le "quoi faire", un programme est le "comment le faire" pour une machine. L'ordinateur ne peut exécuter que des programmes, pas des algorithmes bruts.

Face à un problème complexe, la première étape est de le décomposer en problèmes plus petits et plus faciles à gérer. C'est l'approche par étapes ou approche modulaire.

• Problème initial : Organiser le voyage scolaire.
• Décomposition :
  • Choisir la destination.
  • Définir le budget.
  • Réserver le transport.
  • Réserver l'hébergement.
  • Planifier les activités.
  • Obtenir les autorisations parentales.

Chacun de ces sous-problèmes peut être traité séparément, ce qui simplifie grandement la tâche globale. Cette modularité permet de se concentrer sur une petite partie du problème à la fois, et de réutiliser des solutions pour des sous-problèmes similaires.

Décomposer un problème complexe en sous-problèmes plus simples rend la résolution plus abordable et plus efficace.

Pour concevoir un algorithme, il faut pouvoir le représenter de manière claire et précise avant de le coder. Il existe plusieurs façons de le faire :

1. Langage naturel : C'est la manière la plus simple, mais aussi la plus ambiguë. On décrit les étapes en français (ou autre langue).

   • Exemple : "Si la porte est ouverte, la fermer. Sinon, vérifier si elle est verrouillée."
   • Avantage : Facile à comprendre pour un humain.
   • Inconvénient : Manque de précision, peut prêter à interprétation.

2. Pseudo-code : C'est un langage intermédiaire, entre le langage naturel et un langage de programmation. Il utilise des mots-clés courants (SI, ALORS, SINON, TANT QUE, POUR) et une structure logique claire, mais sans se soucier de la syntaxe exacte d'un langage de programmation.

   • Exemple :

     DEBUT
         LIRE "âge"
         SI âge >= 18 ALORS
             AFFICHER "Majeur"
         SINON
             AFFICHER "Mineur"
         FIN SI
     FIN
     

   • Avantage : Plus précis que le langage naturel, facile à traduire en code.
   • Inconvénient : Nécessite une certaine rigueur.

3. Organigrammes (flowcharts) : C'est une représentation graphique des étapes d'un algorithme, utilisant des symboles normalisés pour les différentes actions (début/fin, entrée/sortie, traitement, décision).

   • Avantage : Très visuel, permet de voir la logique d'exécution en un coup d'œil.
   • Inconvénient : Peut devenir lourd pour des algorithmes complexes.

Le choix de la représentation dépend de la complexité de l'algorithme et du public visé. Pour la Seconde, le pseudo-code est souvent privilégié.

Dans un algorithme, nous avons souvent besoin de stocker des informations pour les manipuler. C'est le rôle des variables.

Une variable est un espace de stockage nommé en mémoire qui peut contenir une valeur. Cette valeur peut changer au cours de l'exécution de l'algorithme. Chaque variable a un nom (par exemple age, nomUtilisateur, prixHT) et un type de données. Le type de données indique la nature des informations que la variable peut contenir.

Les types de données les plus courants sont :

• Types numériques :
  • Entiers (Integer) : Nombres sans virgule (ex: 5, -10, 0). Utile pour compter des éléments, des âges.
  • Réels (Float ou Decimal) : Nombres à virgule (ex: 3.14, -0.5, 99.99). Utile pour des mesures, des prix.
• Types textuels :
  • Chaînes de caractères (String) : Séquences de lettres, chiffres ou symboles (ex: "Bonjour", "SNT", "123 Rue de la Paix"). Toujours entre guillemets.
• Types booléens (Boolean) : Ne peuvent prendre que deux valeurs : Vrai (True) ou Faux (False). Utile pour représenter l'état d'une condition (ex: estMajeur, porteEstOuverte).

Exemple de déclaration de variables en pseudo-code :

VARIABLES
    nom : CHAINE DE CARACTERES
    age : ENTIER
    prixTotal : REEL
    estConnecte : BOOLEEN

Les variables permettent de stocker et de manipuler des données, et leur type détermine la nature de ces données.

Une fois les variables définies, les algorithmes effectuent des opérations sur ces variables.

1. Affectation : C'est l'opération la plus fondamentale. Elle consiste à donner une valeur à une variable. On utilise souvent la flèche <- ou le signe = en pseudo-code.

   • maVariable <- 10 (La variable maVariable prend la valeur 10)
   • nom <- "Alice" (La variable nom prend la valeur "Alice")
   • resultat <- a + b (La variable resultat prend la somme des valeurs de a et b)

2. Opérations arithmétiques : Ce sont les calculs mathématiques de base.

   • + : Addition
   • - : Soustraction
   • * : Multiplication
   • / : Division
   • % : Modulo (reste de la division entière)
   • ^ ou ** : Puissance

3. Opérations de comparaison : Elles permettent de comparer deux valeurs et retournent un résultat booléen (Vrai ou Faux).
   • = ou == : Égal à
   • != ou <> : Différent de
   • < : Inférieur à
   • <= : Inférieur ou égal à
   • > : Supérieur à
   • >= : Supérieur ou égal à

4. Opérations logiques : Elles combinent des expressions booléennes pour former des conditions plus complexes.
   • ET (AND) : Vrai si toutes les conditions sont Vraies.
   • OU (OR) : Vrai si au moins une des conditions est Vraie.
   • NON (NOT) : Inverse la valeur booléenne (Vrai devient Faux, Faux devient Vrai).

Ces opérations sont les briques élémentaires pour construire toute la logique d'un algorithme.

La forme la plus simple d'exécution est la séquence d'instructions. Les instructions sont exécutées les unes après les autres, dans l'ordre où elles sont écrites. C'est une exécution linéaire.

DEBUT
    INSTRUCTION 1
    INSTRUCTION 2
    INSTRUCTION 3
FIN

• L'instruction 1 est exécutée.
• Puis l'instruction 2 est exécutée.
• Enfin l'instruction 3 est exécutée.

Chaque instruction est un bloc d'instructions autonome qui réalise une tâche spécifique.

Les séquences définissent l'ordre d'exécution pas à pas des instructions.

Les structures conditionnelles permettent à un algorithme de prendre des décisions et de choisir différentes branches d'exécution en fonction d'une condition.

• Si simple :

  SI condition ALORS
      // Instructions à exécuter si la condition est VRAIE
  FIN SI
  

• Si... Alors... Sinon :

  SI condition ALORS
      // Instructions si la condition est VRAIE
  SINON
      // Instructions si la condition est FAUSSE
  FIN SI
  

On peut aussi avoir des conditions imbriquées (un SI à l'intérieur d'un autre SI) ou multiples (SINON SI).

Les conditions permettent à l'algorithme de s'adapter à différentes situations en exécutant des instructions spécifiques.

Les structures itératives, ou boucles, permettent de répéter un bloc d'instructions plusieurs fois. Elles sont fondamentales pour automatiser des tâches répétitives.

1. Boucle POUR (For) : Utilisée lorsque le nombre de répétitions est connu à l'avance.

   POUR compteur DE debut A fin FAIRE
       // Instructions à répéter
   FIN POUR
   

```
POUR i DE 1 A 10 FAIRE
    AFFICHER i
FIN POUR
```
Cet algorithme affichera les nombres de 1 à 10.

2. Boucle TANT QUE (While) : Utilisée lorsque le nombre de répétitions n'est pas connu à l'avance, mais que la répétition dépend d'une condition. La boucle continue tant que la condition est VRAIE. Il faut s'assurer que la condition finira par devenir FAUSSE pour éviter une boucle infinie. TANT QUE condition VRAIE FAIRE // Instructions à répéter FIN TANT QUE

```
nombreValide <- FAUX
TANT QUE nombreValide = FAUX FAIRE
    LIRE "Entrez un nombre positif" DANS nombre
    SI nombre > 0 ALORS
        nombreValide <- VRAI
    FIN SI
FIN TANT QUE
```
Cette boucle continuera de demander un nombre jusqu'à ce qu'un nombre positif soit entré.

Les boucles sont essentielles pour automatiser les tâches répétitives et traiter des listes de données.

La conception d'un algorithme efficace suit généralement une méthodologie structurée :

1. Analyse du problème :

   • Comprendre précisément ce que l'on attend de l'algorithme.
   • Identifier les entrées (données fournies) et les sorties (résultats attendus).
   • Définir les contraintes et les règles.
   • Exemple : Calculer la moyenne d'une liste de notes. Entrée : une liste de nombres. Sortie : un nombre (la moyenne). Contrainte : les notes sont entre 0 et 20.

2. Conception de l'algorithme :

   • Décomposer le problème en sous-problèmes (voir section 2.1).
   • Déterminer les étapes logiques pour passer des entrées aux sorties.
   • Choisir les structures de contrôle appropriées (séquences, conditions, boucles).
   • Écrire l'algorithme en pseudo-code ou avec un organigramme.

3. Test et validation :

   • Exécuter l'algorithme "à la main" (tracer l'algorithme) avec des jeux de données de test (cas normaux, cas limites, cas d'erreurs).
   • Vérifier si les résultats produits sont corrects.
   • Déboguer et corriger les erreurs (bugs).

4. Optimisation (si nécessaire) :

   • Une fois que l'algorithme fonctionne, on peut chercher à l'améliorer : le rendre plus rapide, utiliser moins de mémoire, le rendre plus lisible.

Cette méthodologie pas à pas assure une approche rigoureuse et efficace pour créer des algorithmes.

Voici quelques exemples classiques pour illustrer les concepts vus précédemment :

1. Calcul de moyenne :

   • Problème : Calculer la moyenne d'une liste de N nombres.
   • Algorithme (pseudo-code) :

     DEBUT
         LIRE N // Nombre total de notes
         somme <- 0
         POUR i DE 1 A N FAIRE
             LIRE note // Lire chaque note
             somme <- somme + note
         FIN POUR
         moyenne <- somme / N
         AFFICHER "La moyenne est : ", moyenne
     FIN
     

2. Recherche du maximum dans une liste :

   • Problème : Trouver la plus grande valeur dans une liste de nombres.
   • Algorithme (pseudo-code) :

     DEBUT
         LIRE listeDeNombres
         maximum <- listeDeNombres[0] // On suppose le premier élément comme maximum initial
         POUR CHAQUE nombre DANS listeDeNombres FAIRE
             SI nombre > maximum ALORS
                 maximum <- nombre
             FIN SI
         FIN POUR
         AFFICHER "Le maximum est : ", maximum
     FIN
     

3. Échange de valeurs :

   • Problème : Inverser les valeurs de deux variables, A et B.
   • Algorithme (pseudo-code) :

     DEBUT
         LIRE A, B
         temp <- A // Stocker A temporairement
         A <- B    // A prend la valeur de B
         B <- temp // B prend l'ancienne valeur de A
         AFFICHER "Nouvelle valeur de A : ", A
         AFFICHER "Nouvelle valeur de B : ", B
     FIN
     

     Sans la variable temporaire (temp), l'une des valeurs serait perdue.

"Tracer un algorithme" signifie simuler son exécution pas à pas, comme le ferait un ordinateur, pour comprendre son comportement et vérifier sa correction. C'est une technique essentielle pour le débogage et la compréhension.

Pour cela, on utilise un tableau de suivi des variables. Chaque colonne représente une variable et chaque ligne une étape de l'exécution.

On voit clairement comment les valeurs de A et B ont été échangées. Le traçage permet de détecter des erreurs logiques et de s'assurer que l'algorithme fait bien ce qu'on attend de lui.

Le traçage est un outil puissant pour comprendre le fonctionnement interne d'un algorithme et valider sa logique.

Tous les algorithmes ne sont pas égaux en termes d'efficacité.

• La complexité d'un algorithme mesure les ressources (temps et mémoire) nécessaires à son exécution en fonction de la taille des données d'entrée.
• Le temps d'exécution est crucial pour les applications en temps réel. Un algorithme inefficace peut prendre des heures, des jours, voire des années pour des données volumineuses.
• Le nombre d'opérations est une mesure de la complexité. Par exemple, pour trier une liste de $N$ éléments, certains algorithmes nécessitent $N^2$ opérations, d'autres $N \log N$. Pour $N=1000$, $N^2 = 1\,000\,000$ tandis que $N \log N \approx 1000 \times 10 = 10\,000$. La différence est énorme !

Il existe des problèmes non résolubles algorithmiquement (par exemple, le problème de l'arrêt : déterminer si un programme va s'arrêter ou boucler à l'infini). D'autres sont résolubles mais en un temps tellement long qu'ils sont considérés comme "non pratiques" (par exemple, casser certains chiffrements complexes sans clé).

L'efficacité d'un algorithme est primordiale, surtout avec l'augmentation constante du volume de données.

Les algorithmes ne sont pas neutres. Ils sont conçus par des humains et apprennent souvent à partir de données créées par des humains.

• Biais algorithmiques : Si les données d'apprentissage sont biaisées (par exemple, représentent majoritairement un certain groupe de personnes), l'algorithme peut reproduire et amplifier ces biais.

  • Exemple : Un algorithme de reconnaissance faciale entraîné principalement sur des visages masculins blancs aura plus de difficultés à reconnaître des femmes ou des personnes de couleur.
  • Exemple : Un algorithme de recrutement qui apprend des CV passés pourrait favoriser certains profils si l'entreprise a historiquement embauché de manière non diversifiée.

• Discrimination : Les biais peuvent mener à de la discrimination (refus de prêt, sélection injuste, etc.) sans que ce soit intentionnel de la part des concepteurs.

• Transparence : Il est souvent difficile de comprendre "pourquoi" un algorithme a pris une certaine décision (phénomène de la "boîte noire"), ce qui pose des problèmes de responsabilité.

• Éthique : Se poser des questions sur l'impact des algorithmes sur la société est essentiel. Comment assurer l'équité, la vie privée, le respect des droits fondamentaux ?

Les algorithmes reflètent les données sur lesquelles ils sont entraînés et les choix de leurs concepteurs. Ils peuvent reproduire et amplifier les inégalités existantes.

Les algorithmes transforment profondément notre société :

• Recommandations personnalisées : Sur les plateformes de streaming (Netflix, Spotify) ou les réseaux sociaux, les algorithmes nous proposent des contenus basés sur nos préférences. Cela peut créer des "bulles de filtre" où nous sommes exposés uniquement à des informations qui confirment nos opinions.
• Intelligence Artificielle (IA) : L'IA est un domaine qui s'appuie massivement sur des algorithmes complexes (apprentissage automatique, réseaux de neurones). Elle est utilisée dans des domaines comme la médecine (diagnostic), les véhicules autonomes, la traduction automatique.
• Vie privée : Les algorithmes collectent et analysent d'énormes quantités de données personnelles. Cela soulève des questions sur la protection de nos informations et l'utilisation qui en est faite.
• Automatisation du travail : De nombreux emplois sont automatisés par des algorithmes et des robots, ce qui a des conséquences sur le marché du travail et la nature des compétences requises.
• Information et désinformation : Les algorithmes des réseaux sociaux peuvent contribuer à la propagation rapide de fausses informations, rendant plus difficile la distinction entre le vrai et le faux.

Comprendre les algorithmes et leurs enjeux est donc fondamental pour être un citoyen éclairé et responsable dans le monde numérique actuel.

Les algorithmes sont des outils puissants qui façonnent notre quotidien et soulèvent des questions majeures sur l'avenir de notre société.