Traitement des données : algorithmique

Un algorithme est une série finie et non ambiguë d'instructions claires et précises, permettant de résoudre un problème donné ou d'effectuer une tâche spécifique. Imagine une recette de cuisine : elle te donne des étapes à suivre pour préparer un plat. Un algorithme, c'est la même chose, mais pour un ordinateur.

Chaque instruction doit être réalisable et le processus doit se terminer en un nombre fini d'étapes.

Key Concepts:

• Définition d'un algorithme : Une suite logique d'étapes pour résoudre un problème.
• Séquence d'instructions : Les étapes sont exécutées dans un ordre précis.
• Résolution de problèmes : Le but ultime de tout algorithme est d'atteindre un objectif ou de trouver une solution.

Exemple : Algorithme pour allumer une lampe.

1. Aller vers la lampe.
2. Chercher l'interrupteur.
3. Si l'interrupteur est en position "éteint", alors basculer l'interrupteur en position "allumé".
4. Vérifier si la lampe est allumée.
5. Si la lampe n'est pas allumée, vérifier l'ampoule.
6. Fin.

Pour communiquer un algorithme, il existe plusieurs méthodes :

• Langage naturel : C'est la façon la plus simple de décrire un algorithme, en utilisant des phrases de tous les jours. C'est utile pour comprendre l'idée générale, mais peut manquer de précision.
  • Avantage : Facile à comprendre pour un humain.
  • Inconvénient : Peut être ambigu, difficile à traduire en code machine.
• Pseudocode : C'est un langage intermédiaire entre le langage naturel et un langage de programmation. Il utilise des structures de contrôle (SI...ALORS, TANT QUE, POUR) et des mots-clés qui ressemblent à ceux des langages de programmation, mais sans respecter une syntaxe stricte. C'est la méthode la plus courante et recommandée pour concevoir des algorithmes.
  • Avantage : Précis, non ambigu, facile à traduire dans n'importe quel langage de programmation.
  • Inconvénient : Nécessite une certaine familiarité avec les structures de programmation.
• Organigrammes (notions) : Ce sont des représentations graphiques d'un algorithme. Chaque étape est représentée par un symbole spécifique (rectangle pour une instruction, losange pour une décision, etc.), et des flèches indiquent l'ordre d'exécution.
  • Avantage : Très visuel, permet de voir le flux logique d'un coup d'œil.
  • Inconvénient : Peut devenir très complexe et difficile à lire pour de grands algorithmes. Nous n'allons pas les utiliser dans ce cours, mais il est bon de savoir qu'ils existent.

Exemple en Pseudocode (allumer une lampe) :

DEBUT Algorithme AllumerLampe
  ALLER_VERS_LAMPE
  TROUVER_INTERRUPTEUR
  SI INTERRUPTEUR_EST_ETEINT ALORS
    BASCULER_INTERRUPTEUR_SUR_ALLUME
  FIN SI
  SI LAMPE_N_EST_PAS_ALLUMEE ALORS
    VERIFIER_AMPOULE
  FIN SI
FIN Algorithme

Pour qu'un algorithme puisse manipuler des informations, il a besoin de variables. Une variable est un espace de stockage nommé en mémoire qui peut contenir une valeur. Pense à une boîte étiquetée : l'étiquette est le nom de la variable, et ce qu'il y a dedans est sa valeur.

Chaque variable a un type de données qui détermine quel genre d'information elle peut stocker (nombre entier, texte, vrai/faux, etc.) et quelles opérations peuvent être effectuées dessus.

Key Concepts:

• Déclaration de variables : C'est l'acte de créer une variable et de lui donner un nom et un type.
• Types entiers : Pour les nombres sans décimales (ex: 5, -10, 0). Souvent appelés int ou entier.
• Types flottants : Pour les nombres avec décimales (ex: 3.14, -0.5, 100.0). Souvent appelés float ou réel.
• Types booléens : Pour représenter une valeur de vérité, soit VRAI (True) soit FAUX (False). Très utilisés pour les conditions.
• Chaînes de caractères : Pour stocker du texte (ex: "Bonjour", "NSI"). Souvent appelés string ou chaîne.
• Affectation de valeurs : C'est l'action de donner une valeur à une variable. On utilise généralement le symbole <- ou = en pseudocode.

Exemple :

// Déclaration et affectation
nombre_entier <- 10        // nombre_entier est de type entier, sa valeur est 10
prix_unitaire <- 19.99     // prix_unitaire est de type flottant, sa valeur est 19.99
est_actif <- VRAI          // est_actif est de type booléen, sa valeur est VRAI
message <- "Salut le monde" // message est de type chaîne de caractères

// L'affectation peut changer la valeur d'une variable
nombre_entier <- nombre_entier + 5 // nombre_entier vaut maintenant 15

Le type d'une variable détermine les opérations possibles. On ne peut pas multiplier une chaîne de caractères par un entier, par exemple.

Les opérateurs sont des symboles qui nous permettent d'effectuer des opérations sur des valeurs ou des variables. Une expression est une combinaison de valeurs, de variables et d'opérateurs qui produit une nouvelle valeur.

Key Concepts:

• Opérateurs arithmétiques : Pour les calculs mathématiques.
  • + (addition)
  • - (soustraction)
  • * (multiplication)
  • / (division)
  • % (modulo - reste de la division entière)
  • ^ ou ** (puissance)
• Opérateurs de comparaison : Pour comparer des valeurs. Ils retournent toujours un booléen (VRAI ou FAUX).
  • = ou == (est égal à)
  • != ou <> (est différent de)
  • < (est strictement inférieur à)
  • <= (est inférieur ou égal à)
  • > (est strictement supérieur à)
  • >= (est supérieur ou égal à)
• Opérateurs logiques : Pour combiner des expressions booléennes.
  • ET (AND) : VRAI si les deux conditions sont VRAIES.
  • OU (OR) : VRAI si au moins une des conditions est VRAIE.
  • NON (NOT) : Inverse la valeur de vérité (NON VRAI devient FAUX, NON FAUX devient VRAI).

Exemples :

// Opérateurs arithmétiques
resultat <- 10 + 5 * 2 // résultat vaut 20 (multiplication prioritaire)
reste <- 17 % 3       // reste vaut 2

// Opérateurs de comparaison
est_majeur <- age >= 18 // est_majeur est VRAI si age est 18 ou plus
sont_egaux <- "pomme" <mark> "poire" // sont_egaux est FAUX

// Opérateurs logiques
condition_complexe <- (age > 18 ET permis_valide </mark> VRAI) OU (parent_present <mark> VRAI)
// condition_complexe est VRAI si (majeur ET permis) OU parent présent

La priorité des opérateurs est importante== (comme en maths : multiplication avant addition).

Une structure séquentielle est la forme la plus simple d'exécution. Les instructions sont exécutées les unes après les autres, dans l'ordre où elles sont écrites. C'est le comportement par défaut d'un algorithme.

Key Concepts:

• Exécution pas à pas : Chaque instruction est traitée l'une après l'autre.
• Ordre des instructions : L'ordre est crucial ; changer l'ordre peut changer le résultat.
• Blocs d'instructions : Un ensemble d'instructions exécutées séquentiellement.

Exemple :

DEBUT Algorithme CalculSimple
  nombre1 <- 5
  nombre2 <- 10
  somme <- nombre1 + nombre2 // exécuté après l'affectation de nombre1 et nombre2
  AFFICHER "La somme est : " + somme
FIN Algorithme

Si nous inversions les lignes somme <- nombre1 + nombre2 et nombre1 <- 5, l'algorithme tenterait d'additionner une variable nombre1 non encore définie, ce qui provoquerait une erreur. L'ordre est primordial.

Les structures conditionnelles permettent à un algorithme de prendre des décisions et d'exécuter différentes instructions en fonction de si une condition est vraie ou fausse. C'est ce qui rend les algorithmes "intelligents".

Key Concepts:

• Test de condition : Une expression booléenne est évaluée.
• Exécution alternative : Si la condition est VRAIE, un bloc d'instructions est exécuté ; sinon, un autre bloc (optionnel) peut être exécuté.
• Conditions imbriquées : Il est possible de placer des structures conditionnelles à l'intérieur d'autres structures conditionnelles.

Syntaxe générale en pseudocode :

SI condition ALORS
  // Instructions à exécuter si la condition est VRAIE
SINON
  // Instructions à exécuter si la condition est FAUSSE (cette partie est optionnelle)
FIN SI

Exemple : Vérifier si un nombre est positif.

DEBUT Algorithme VerifierPositif
  nombre <- LIRE("Entrez un nombre : ")
  SI nombre > 0 ALORS
    AFFICHER "Le nombre est positif."
  SINON SI nombre < 0 ALORS // On peut ajouter des "SINON SI" pour plusieurs conditions
    AFFICHER "Le nombre est négatif."
  SINON
    AFFICHER "Le nombre est zéro."
  FIN SI
FIN Algorithme

Les conditions permettent à l'algorithme de s'adapter aux différentes situations.

Les structures itératives, aussi appelées boucles, permettent de répéter un bloc d'instructions plusieurs fois. C'est essentiel pour automatiser des tâches répétitives.

Key Concepts:

• Répétition d'instructions : Un ensemble d'instructions est exécuté un certain nombre de fois.
• Condition d'arrêt : Pour éviter une boucle infinie, il doit y avoir une condition qui, une fois remplie, termine la boucle.
• Itération sur des séquences : Parcourir tous les éléments d'une liste, d'une chaîne de caractères, etc.

Boucle TANT QUE (WHILE)

La boucle TANT QUE répète un bloc d'instructions tant qu'une condition donnée reste VRAIE. La condition est testée avant chaque exécution du bloc.

Syntaxe :

TANT QUE condition EST VRAIE FAIRE
  // Instructions à répéter
FIN TANT QUE

Exemple : Compter de 1 à 5.

DEBUT Algorithme Compter
  compteur <- 1
  TANT QUE compteur <= 5 FAIRE
    AFFICHER compteur
    compteur <- compteur + 1 // C'est l'instruction qui fait évoluer la condition
  FIN TANT QUE
FIN Algorithme

Sans l'incrémentation du compteur, la boucle ne s'arrêterait jamais !

Boucle POUR (FOR)

La boucle POUR est utilisée lorsque l'on sait à l'avance combien de fois on veut répéter une action, ou lorsque l'on veut parcourir une collection d'éléments. Elle est souvent plus compacte pour ces cas.

Syntaxe (pour un nombre fixe d'itérations) :

POUR variable DE debut À fin FAIRE
  // Instructions à répéter
FIN POUR

Exemple : Afficher les nombres de 1 à 5.

DEBUT Algorithme CompterAvecPour
  POUR i DE 1 À 5 FAIRE
    AFFICHER i
  FIN POUR
FIN Algorithme

Exemple (pour parcourir une séquence) :

DEBUT Algorithme ParcourirListe
  liste_fruits <- ["pomme", "banane", "orange"]
  POUR chaque fruit DANS liste_fruits FAIRE
    AFFICHER "J'aime la " + fruit
  FIN POUR
FIN Algorithme

Les boucles POUR sont idéales pour les itérations déterminées.

Les fonctions (et procédures) sont des blocs de code autonomes qui effectuent une tâche spécifique. Elles permettent de diviser un grand problème en sous-problèmes plus petits et plus faciles à gérer, c'est ce qu'on appelle la modularité.

Key Concepts:

• Décomposition de problèmes : Diviser un problème complexe en tâches plus simples.
• Éviter la répétition : Au lieu de réécrire le même code plusieurs fois, on le met dans une fonction et on l'appelle quand on en a besoin. C'est le principe DRY (Don't Repeat Yourself).
• Lisibilité du code : Un code bien structuré avec des fonctions est plus facile à lire, comprendre et maintenir.

Exemple sans fonction :

// Calcul de la surface d'un rectangle 1
longueur1 <- 10
largeur1 <- 5
surface1 <- longueur1 * largeur1
AFFICHER "Surface 1 : " + surface1

// Calcul de la surface d'un rectangle 2
longueur2 <- 8
largeur2 <- 3
surface2 <- longueur2 * largeur2
AFFICHER "Surface 2 : " + surface2

Exemple avec fonction :

FONCTION calculer_surface_rectangle(longueur, largeur) :
  surface <- longueur * largeur
  RETOURNER surface
FIN FONCTION

// Utilisation de la fonction
surface1 <- calculer_surface_rectangle(10, 5)
AFFICHER "Surface 1 : " + surface1

surface2 <- calculer_surface_rectangle(8, 3)
AFFICHER "Surface 2 : " + surface2

On voit clairement que le code est plus concis et plus clair avec la fonction. La réutilisation du code est un gain de temps et réduit les erreurs.

• Définition : C'est le moment où l'on écrit le code de la fonction, en spécifiant son nom, les informations qu'elle attend (ses paramètres) et ce qu'elle fait.
• Appel : C'est le moment où l'on utilise la fonction dans l'algorithme principal ou dans une autre fonction. On lui passe les valeurs nécessaires (les arguments).

Key Concepts:

• Paramètres d'entrée : Les informations que la fonction reçoit pour travailler. Elles sont définies lors de la création de la fonction.
• Valeur de retour : Le résultat que la fonction renvoie après avoir effectué sa tâche. Une fonction peut retourner une seule valeur, aucune valeur (on parle alors souvent de procédure ou de fonction void), ou parfois plusieurs (via des structures de données).
• Signature de fonction : C'est l'ensemble composé du nom de la fonction et de la liste de ses paramètres (avec leurs types). Elle décrit comment utiliser la fonction.

Syntaxe générale en pseudocode :

// Définition de la fonction
FONCTION NOM_DE_LA_FONCTION(parametre1, parametre2) :
  // Corps de la fonction
  // Instructions utilisant parametre1 et parametre2
  resultat <- ...
  RETOURNER resultat // Optionnel, si la fonction doit renvoyer une valeur
FIN FONCTION

// Appel de la fonction
ma_variable <- NOM_DE_LA_FONCTION(argument1, argument2)

La portée (ou "scope") d'une variable détermine où dans le programme cette variable peut être accédée et utilisée.

Key Concepts:

• Variables locales : Déclarées à l'intérieur d'une fonction. Elles n'existent et ne sont accessibles qu'à l'intérieur de cette fonction. Une fois la fonction terminée, ces variables sont détruites.
• Variables globales : Déclarées en dehors de toute fonction (souvent au début de l'algorithme). Elles sont accessibles depuis n'importe où dans l'algorithme, y compris depuis les fonctions.
• Effets de bord : Lorsqu'une fonction modifie une variable globale. Cela peut rendre le code plus difficile à déboguer et à comprendre, car la fonction a un impact au-delà de sa propre exécution. Il est généralement préférable d'éviter les effets de bord et de privilégier le passage de paramètres et les valeurs de retour.

Exemple :

// Variable globale
message_global <- "Je suis global"

FONCTION ma_fonction():
  // Variable locale
  message_local <- "Je suis local"
  AFFICHER message_local
  AFFICHER message_global // Accès à la variable globale possible

  // Exemple d'effet de bord (à éviter si possible)
  message_global <- "J'ai été modifié par la fonction"
FIN FONCTION

DEBUT Algorithme Principal
  AFFICHER message_global // Affiche "Je suis global"
  ma_fonction()
  AFFICHER message_global // Affiche "J'ai été modifié par la fonction"
  // AFFICHER message_local // ERREUR : message_local n'existe pas ici
FIN Algorithme

Les variables locales favorisent l'indépendance des fonctions.

Un tableau (ou liste dans de nombreux langages comme Python) est une collection ordonnée d'éléments. Chaque élément est identifié par un indice (ou index), qui est sa position dans le tableau. Les indices commencent généralement à 0.

Key Concepts:

• Collection d'éléments : Un ensemble de valeurs regroupées sous un seul nom.
• Indexation : Chaque élément a une position numérique unique pour y accéder.
• Parcours de tableaux : Parcourir tous les éléments du tableau, généralement avec une boucle.

Exemple :

// Déclaration et initialisation d'un tableau
nombres <- [10, 20, 30, 40, 50] // Un tableau de 5 entiers

// Accès aux éléments
premier_element <- nombres[0]  // premier_element vaut 10
troisieme_element <- nombres[2] // troisieme_element vaut 30

// Modification d'un élément
nombres[1] <- 25 // Le tableau devient [10, 25, 30, 40, 50]

// Longueur du tableau
taille <- LONGUEUR(nombres) // taille vaut 5

Parcours d'un tableau avec une boucle POUR :

POUR i DE 0 À taille - 1 FAIRE // De l'indice 0 à l'indice taille-1
  AFFICHER "Élément à l'indice " + i + " : " + nombres[i]
FIN POUR

Les tableaux permettent de stocker plusieurs données de même type sous un même nom.

Les tableaux sont très polyvalents et permettent diverses opérations :

Key Concepts:

• Ajout/suppression d'éléments : Modifier la taille du tableau en y ajoutant ou en retirant des éléments.
  • AJOUTER(tableau, valeur) : ajoute valeur à la fin du tableau.
  • SUPPRIMER_PAR_INDICE(tableau, index) : supprime l'élément à la position index.
• Recherche d'éléments : Trouver si un élément est présent dans le tableau et, si oui, à quelle position.
• Tri (notions simples) : Réorganiser les éléments du tableau dans un ordre spécifique (croissant, décroissant). Nous verrons des algorithmes de tri plus tard.

Exemple :

fruits <- ["pomme", "banane", "orange"]

// Ajout
AJOUTER(fruits, "kiwi") // fruits est maintenant ["pomme", "banane", "orange", "kiwi"]

// Suppression
SUPPRIMER_PAR_INDICE(fruits, 1) // Supprime "banane". fruits est maintenant ["pomme", "orange", "kiwi"]

// Recherche (simple)
element_trouve <- FAUX
POUR chaque fruit DANS fruits FAIRE
  SI fruit == "orange" ALORS
    element_trouve <- VRAI
    SORTIR_BOUCLE // On a trouvé, pas besoin de continuer
  FIN SI
FIN POUR
SI element_trouve ALORS
  AFFICHER "L'orange est dans la liste."
SINON
  AFFICHER "L'orange n'est PAS dans la liste."
FIN SI

Une chaîne de caractères est une séquence ordonnée de caractères (lettres, chiffres, symboles). En algorithmique, elles sont souvent traitées comme des tableaux de caractères.

Key Concepts:

• Séquence de caractères : Chaque caractère a une position (un indice).
• Opérations de base :
  • Concaténation : Joindre deux chaînes ensemble (opérateur +).
  • Longueur : Obtenir le nombre de caractères dans la chaîne.
• Accès aux caractères : Accéder à un caractère spécifique par son indice.

Exemple :

chaine1 <- "Bonjour"
chaine2 <- " le monde"

// Concaténation
chaine_complete <- chaine1 + chaine2 // chaine_complete vaut "Bonjour le monde"

// Longueur
longueur_chaine <- LONGUEUR(chaine_complete) // longueur_chaine vaut 14

// Accès aux caractères
premier_char <- chaine1[0] // premier_char vaut 'B'
cinquieme_char <- chaine1[4] // cinquieme_char vaut 'o'

Les chaînes sont immuables dans beaucoup de langages, ce qui signifie qu'une fois créée, on ne peut pas modifier un caractère existant ; toute modification crée une nouvelle chaîne.

Les algorithmes de recherche permettent de trouver un élément spécifique dans une collection de données.

Key Concepts:

• Recherche séquentielle : Parcourt la collection élément par élément jusqu'à trouver l'élément recherché ou atteindre la fin de la collection. Simple à implémenter, mais peu efficace pour de grandes collections.
• Recherche dichotomique (sur tableau trié) : Ne fonctionne que sur une collection triée. Elle divise la collection en deux à chaque étape, éliminant la moitié où l'élément ne peut pas se trouver. Beaucoup plus rapide que la recherche séquentielle pour les grandes collections.
• Complexité (notions intuitives) : Indique à quel point un algorithme est "efficace" en fonction de la taille des données. Nous approfondirons cela plus tard.

Recherche séquentielle (ou linéaire)

FONCTION recherche_sequentielle(tableau, element_recherche):
  POUR i DE 0 À LONGUEUR(tableau) - 1 FAIRE
    SI tableau[i] == element_recherche ALORS
      RETOURNER i // Renvoie l'indice de l'élément trouvé
    FIN SI
  FIN POUR
  RETOURNER -1 // L'élément n'a pas été trouvé
FIN FONCTION

// Utilisation
ma_liste <- [12, 45, 6, 89, 7, 23]
indice <- recherche_sequentielle(ma_liste, 7) // indice vaut 4
indice_non_trouve <- recherche_sequentielle(ma_liste, 99) // indice_non_trouve vaut -1

Cette recherche est simple, mais si la liste a $N$ éléments, dans le pire des cas (élément en dernière position ou non présent), il faut $N$ comparaisons.

Recherche dichotomique

Conditions : Le tableau doit être trié.

FONCTION recherche_dichotomique(tableau_trie, element_recherche):
  debut <- 0
  fin <- LONGUEUR(tableau_trie) - 1

  TANT QUE debut <= fin FAIRE
    milieu <- (debut + fin) DIV 2 // Division entière
    SI tableau_trie[milieu] <mark> element_recherche ALORS
      RETOURNER milieu // Élément trouvé
    SINON SI tableau_trie[milieu] < element_recherche ALORS
      debut <- milieu + 1 // L'élément est dans la moitié droite
    SINON
      fin <- milieu - 1 // L'élément est dans la moitié gauche
    FIN SI
  FIN TANT QUE
  RETOURNER -1 // L'élément n'a pas été trouvé
FIN FONCTION

// Utilisation
liste_triee <- [6, 7, 12, 23, 45, 89]
indice <- recherche_dichotomique(liste_triee, 23) // indice vaut 3
indice_non_trouve <- recherche_dichotomique(liste_triee, 50) // indice_non_trouve vaut -1

La recherche dichotomique est beaucoup plus rapide : elle divise le problème par deux à chaque étape. Pour $N$ éléments, elle ne nécessite qu'environ $\log_2(N)$ comparaisons. C'est un exemple clé de l'importance d'avoir des données bien organisées.==

Les algorithmes de tri réorganisent les éléments d'une collection dans un ordre spécifique (numérique, alphabétique, etc.).

Key Concepts:

• Tri par sélection : Trouve le plus petit (ou plus grand) élément restant et le place à sa position correcte.
• Tri par insertion : Construit la liste triée un élément à la fois, en insérant chaque nouvel élément à sa place correcte dans la partie déjà triée.
• Comparaison de performances : Évaluer l'efficacité des différents algorithmes de tri (nous verrons cela avec la complexité).

Tri par sélection

FONCTION tri_par_selection(tableau):
  n <- LONGUEUR(tableau)
  POUR i DE 0 À n - 2 FAIRE // On parcourt jusqu'à l'avant-dernier élément
    indice_min <- i
    POUR j DE i + 1 À n - 1 FAIRE // On cherche le minimum dans le reste du tableau
      SI tableau[j] < tableau[indice_min] ALORS
        indice_min <- j
      FIN SI
    FIN POUR
    // Échanger l'élément courant avec le plus petit trouvé
    temp <- tableau[i]
    tableau[i] <- tableau[indice_min]
    tableau[indice_min] <- temp
  FIN POUR
  RETOURNER tableau
FIN FONCTION

// Utilisation
liste_desordonnee <- [64, 25, 12, 22, 11]
liste_triee <- tri_par_selection(liste_desordonnee) // liste_triee vaut [11, 12, 22, 25, 64]

Le tri par sélection fait $N$ passes, et à chaque passe, il parcourt une partie du tableau. Sa complexité est en $N^2$.

Tri par insertion

FONCTION tri_par_insertion(tableau):
  n <- LONGUEUR(tableau)
  POUR i DE 1 À n - 1 FAIRE // On commence par le deuxième élément
    cle <- tableau[i] // L'élément à insérer
    j <- i - 1
    // Déplacer les éléments plus grands que 'cle' vers la droite
    TANT QUE j >= 0 ET tableau[j] > cle FAIRE
      tableau[j + 1] <- tableau[j]
      j <- j - 1
    FIN TANT QUE
    tableau[j + 1] <- cle // Insérer 'cle' à sa place
  FIN POUR
  RETOURNER tableau
FIN FONCTION

// Utilisation
liste_desordonnee <- [64, 25, 12, 22, 11]
liste_triee <- tri_par_insertion(liste_desordonnee) // liste_triee vaut [11, 12, 22, 25, 64]

Le tri par insertion est aussi en $N^2$ dans le pire des cas, mais il est plus efficace sur des tableaux presque triés. Le choix du bon algorithme de tri dépend des caractéristiques des données.

Les chaînes de caractères sont omniprésentes. Voici quelques opérations courantes.

Key Concepts:

• Comptage d'occurrences : Trouver combien de fois un certain caractère ou une sous-chaîne apparaît dans une chaîne.
• Extraction de sous-chaînes : Obtenir une partie d'une chaîne.
• Remplacement de caractères : Changer un caractère ou une sous-chaîne par un autre.

Exemple :

phrase <- "Bonjour le monde, le monde est beau."

// Comptage d'occurrences d'un caractère
compte_e <- 0
POUR chaque char DANS phrase FAIRE
  SI char == 'e' ALORS
    compte_e <- compte_e + 1
  FIN SI
FIN POUR
AFFICHER "Le caractère 'e' apparaît " + compte_e + " fois." // Affiche 4

// Extraction de sous-chaînes (début, longueur)
mot_monde <- EXTRAIRE_SOUS_CHAINE(phrase, 12, 5) // Commence à l'indice 12, 5 caractères => "monde"
AFFICHER "Mot extrait : " + mot_monde

// Remplacement (souvent une fonction native des langages)
nouvelle_phrase <- REMPLACER(phrase, "monde", "univers") // "Bonjour l'univers, l'univers est beau."
AFFICHER "Nouvelle phrase : " + nouvelle_phrase

Ces opérations sont fondamentales pour le traitement de texte, l'analyse de données textuelles et bien d'autres applications.

Comment évaluer si un algorithme est "bon" ?

Key Concepts:

• Temps d'exécution : Combien de temps l'algorithme prend-il pour s'exécuter ? C'est souvent ce qui nous intéresse le plus.
• Espace mémoire : Combien de mémoire l'algorithme utilise-t-il ? Important pour les systèmes avec des ressources limitées.
• Dépendance de la taille des données : Comment le temps et l'espace varient-ils en fonction de la taille des données d'entrée (souvent notée $N$) ? C'est le point le plus important.

Mesurer le temps réel d'exécution n'est pas idéal car cela dépend de l'ordinateur, du langage, etc. On préfère une mesure abstraite : le nombre d'opérations élémentaires.

La complexité algorithmique nous permet de prédire comment la performance d'un algorithme va évoluer lorsque la taille des données d'entrée augmente. On utilise la notation Grand O ($O()$) pour exprimer cet ordre de grandeur.

Key Concepts:

• Meilleur cas : La situation la plus favorable où l'algorithme s'exécute le plus rapidement possible.
• Pire cas : La situation la plus défavorable où l'algorithme s'exécute le plus lentement possible. C'est souvent celui qu'on étudie car il garantit une limite supérieure de performance.
• Cas moyen : La performance attendue en moyenne. Plus difficile à calculer.
• Ordre de grandeur (O(n), O(n²), O(log n)) :
  • $O(1)$ (complexité constante) : Le temps d'exécution est constant, quelle que soit la taille des données. Ex: Accéder à un élément d'un tableau par son indice.
  • $O(\log n)$ (complexité logarithmique) : Le temps d'exécution augmente très lentement avec la taille des données. Typique des algorithmes qui divisent le problème en deux à chaque étape (comme la recherche dichotomique).
  • $O(n)$ (complexité linéaire) : Le temps d'exécution est directement proportionnel à la taille des données. Ex: Recherche séquentielle, parcours d'un tableau.
  • $O(n \log n)$ (complexité linéaire-logarithmique) : Plus rapide que $O(n^2)$, mais plus lent que $O(n)$. Bon pour les algorithmes de tri efficaces (comme le tri fusion ou le tri rapide).
  • $O(n^2)$ (complexité quadratique) : Le temps d'exécution augmente avec le carré de la taille des données. Ex: Tri par sélection, tri par insertion. À éviter pour les grandes quantités de données.
  • $O(2^n)$ (complexité exponentielle) : Le temps d'exécution croît de façon extrêmement rapide. À éviter absolument pour des $N$ même petits.
• Comparaison d'algorithmes : La notation Grand O nous permet de comparer l'efficacité de différents algorithmes pour un même problème, indépendamment de la machine. Un algorithme en $O(N)$ sera toujours plus rapide qu'un algorithme en $O(N^2)$ pour de grandes valeurs de $N$.

Graphique simplifié de la croissance des complexités :

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

L'objectif est de trouver l'algorithme le plus efficace, c'est-à-dire celui dont la complexité est la plus faible.

Reprenons certains des algorithmes vus précédemment et analysons leur complexité.

Key Concepts:

• Complexité de la recherche séquentielle :
  • Meilleur cas : $O(1)$ (l'élément est le premier).
  • Pire cas : $O(N)$ (l'élément est le dernier ou n'existe pas).
  • Cas moyen : $O(N)$.
  • Conclusion : Pour $N$ éléments, il faut en moyenne $N/2$ comparaisons.
• Complexité de la recherche dichotomique :
  • Meilleur cas : $O(1)$ (l'élément est au milieu).
  • Pire cas : $O(\log N)$.
  • Cas moyen : $O(\log N)$.
  • Conclusion : Pour $N$ éléments, le nombre de comparaisons est proportionnel au logarithme de $N$. C'est beaucoup plus rapide pour de grands $N$. Par exemple, pour 1 million d'éléments ($N \approx 10^6$), $\log_2(10^6) \approx 20$. C'est 20 comparaisons contre 500 000 en moyenne pour la recherche séquentielle !
• Complexité des tris simples (Tri par sélection, Tri par insertion) :
  • Pire cas : $O(N^2)$.
  • Conclusion : Ces algorithmes sont acceptables pour de petits tableaux, mais deviennent très lents lorsque $N$ augmente. Pour $N = 1000$ éléments, cela représente $1000^2 = 1 000 000$ opérations. Pour $N = 100 000$, c'est $10^{10}$ opérations, ce qui est trop long.

Comprendre la complexité permet de choisir le bon outil pour le bon problème. Un algorithme élégant mais inefficace peut être pire qu'un algorithme simple mais adapté à la taille des données.