Aller au contenu

Algorithmes de référence

1. Recherche par balayage⚓︎

Explication : L'algorithme parcourt les éléments du tableau un par un pour trouver une valeur donnée (val). Si la valeur est trouvée, son indice est renvoyé. Sinon, une valeur indicative, -1, est renvoyée.

Langage algorithmique : 

Algorithme RechercheParBalayage(tab, val)
    Pour i allant de 0 à longueur(tab) - 1 faire
        Si tab[i] = val alors
            Renvoyer i
        Fin Si
    Fin Pour
    Renvoyer -1
Fin Algorithme

Traduction Python : 

def recherche_par_balayage(tab, val):
    """
    Recherche par balayage dans un tableau pour une valeur spécifique.

    :param tab: liste des nombres dans laquelle effectuer la recherche.
    :param val: valeur à rechercher dans le tableau.
    :return: indice de la valeur si trouvée, sinon -1.
    """
    for i in range(len(tab)):
        if tab[i] == val:
            return i
    return -1

Complexité :

  • Temps : O(n), où n est la taille du tableau. Chaque élément est comparé une fois, dans le pire des cas.
  • Espace : O(1), aucune structure additionnelle n’est utilisée.

Correction :

  1. Adéquation : L'algorithme vérifie chaque élément et renvoie l'indice dès qu'un élément correspondant à val est trouvé.
  2. Complétude : Si val n’est pas présent dans tab, l'algorithme finit toutes les itérations et renvoie -1. Aucune valeur n'est ignorée.

Terminaison :

  • La boucle "Pour" parcourt les indices de 0 à n-1. Elle s’arrête dès que i dépasse n-1 ou lorsqu'une correspondance est trouvée.
  • L'algorithme garantit la terminaison après au plus n itérations.

2. Recherche du minimum⚓︎

Explication : L'algorithme trouve l'élément le plus petit dans le tableau en comparant successivement chaque élément à la valeur courante du minimum.

Langage algorithmique : 

Algorithme RechercheDuMinimum(tab)
    min <- tab[0]
    Pour i allant de 1 à longueur(tab) - 1 faire
        Si tab[i] < min alors
            min <- tab[i]
        Fin Si
    Fin Pour
    Renvoyer min
Fin Algorithme

Traduction Python : 

def recherche_du_minimum(tab):
    """
    Trouve le minimum dans un tableau.

    :param tab: liste des nombres.
    :return: plus petite valeur dans le tableau.
    """
    min_val = tab[0]
    for i in range(1, len(tab)):
        if tab[i] < min_val:
            min_val = tab[i]
    return min_val

Complexité :

  • Temps : O(n), car chaque élément est comparé une fois au minimum courant.
  • Espace : O(1), une seule variable supplémentaire est utilisée.

Correction :

  1. Adéquation : L'algorithme compare chaque élément à min. À la fin, min contient la plus petite valeur.
  2. Complétude : Aucun élément n’est ignoré, et tous sont pris en compte.

Terminaison :

  • La boucle "Pour" s’exécute un nombre fini d’itérations (n-1) et termine après avoir parcouru tout le tableau.

3. Recherche du maximum⚓︎

Explication : L'algorithme identifie l'élément ayant la plus grande valeur en comparant chaque élément au maximum courant.

Langage algorithmique : 

Algorithme RechercheDuMaximum(tab)
    max <- tab[0]
    Pour i allant de 1 à longueur(tab) - 1 faire
        Si tab[i] > max alors
            max <- tab[i]
        Fin Si
    Fin Pour
    Renvoyer max
Fin Algorithme

Traduction Python : 

def recherche_du_maximum(tab):
    """
    Trouve le maximum dans un tableau.

    :param tab: liste des nombres.
    :return: plus grande valeur dans le tableau.
    """
    max_val = tab[0]
    for i in range(1, len(tab)):
        if tab[i] > max_val:
            max_val = tab[i]
    return max_val

Complexité :

  • Temps : O(n), car chaque élément est comparé une fois au maximum courant.
  • Espace : O(1).

Correction :

  1. Adéquation : Le maximum est correctement mis à jour à chaque comparaison.
  2. Complétude : Tous les éléments sont pris en compte pour garantir que la vraie valeur maximale est trouvée.

Terminaison :

  • Comme pour le minimum, la boucle parcourt un nombre fini d'éléments et garantit que l'algorithme s'arrête.

4. Calcul de la somme⚓︎

Explication : L'algorithme calcule la somme de tous les éléments du tableau en les additionnant un par un.

Langage algorithmique : 

Algorithme CalculDeLaSomme(tab)
    somme <- 0
    Pour i allant de 0 à longueur(tab) - 1 faire
        somme <- somme + tab[i]
    Fin Pour
    Renvoyer somme
Fin Algorithme

Traduction Python : 

def calcul_de_la_somme(tab):
    """
    Calcule la somme des éléments dans un tableau.

    :param tab: liste des nombres.
    :return: somme des éléments du tableau.
    """
    somme = 0
    for i in range(len(tab)):
        somme += tab[i]
    return somme

Complexité :

  • Temps : O(n), car chaque élément est ajouté une fois.
  • Espace : O(1).

Correction :

  1. Adéquation : La somme cumulée est correctement calculée grâce à une addition élément par élément.
  2. Complétude : Tous les éléments sont pris en compte dans l'addition.

Terminaison :

  • L’itération sur une liste finie garantit que l'algorithme se termine après un nombre limité d'opérations.

5. Calcul de la moyenne⚓︎

Explication : Cet algorithme calcule d'abord la somme de tous les éléments du tableau, puis divise cette somme par le nombre d'éléments pour obtenir la moyenne.

Langage algorithmique : 

Algorithme CalculDeLaMoyenne(tab)
    somme <- 0
    Pour i allant de 0 à longueur(tab) - 1 faire
        somme <- somme + tab[i]
    Fin Pour
    moyenne <- somme / longueur(tab)
    Renvoyer moyenne
Fin Algorithme

Traduction Python : 

def calcul_de_la_moyenne(tab):
    """
    Calcule la moyenne des éléments dans un tableau.

    :param tab: liste des nombres.
    :return: moyenne des éléments du tableau.
    """
    somme = 0
    for i in range(len(tab)):
        somme += tab[i]
    return somme / len(tab)

Complexité :

  • Temps : O(n), car chaque élément est parcouru une fois pour calculer la somme.
  • Espace : O(1), car seules deux variables supplémentaires sont utilisées (somme et moyenne).

Correction :

  1. Adéquation : La somme est correctement calculée à l’aide de l’algorithme prouvé correct plus tôt, et la division par la taille du tableau donne une moyenne exacte.
  2. Complétude : Tous les éléments du tableau sont pris en compte dans la somme, garantissant que la moyenne inclut toutes les données.

Preuve de terminaison :

  • La boucle "Pour" parcourt un nombre fini d'éléments (de 0 à n-1) et s'arrête après n itérations.
  • La division et le retour final sont des opérations simples exécutées une fois après la boucle, garantissant que l'algorithme se termine toujours.

6. Recherche dichotomique⚓︎

Explication : Cet algorithme est conçu pour rechercher une valeur spécifique dans un tableau trié. Il réduit la zone de recherche en deux à chaque étape, en comparant la valeur cible avec le milieu de l’intervalle.

Langage algorithmique : 

Algorithme RechercheDichotomique(tab, val)
    debut <- 0
    fin <- longueur(tab) - 1
    Tant que debut ≤ fin faire
        milieu <- (debut + fin) // 2
        Si tab[milieu] = val alors
            Renvoyer milieu
        Sinon si tab[milieu] < val alors
            debut <- milieu + 1
        Sinon
            fin <- milieu - 1
        Fin Si
    Fin Tant que
    Renvoyer -1
Fin Algorithme

Traduction Python : 

def recherche_dichotomique(tab, val):
    """
    Recherche dichotomique dans un tableau trié.

    :param tab: liste triée des nombres.
    :param val: valeur à rechercher dans le tableau.
    :return: indice de la valeur si trouvée, sinon -1.
    """
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == val:
            return milieu
        elif tab[milieu] < val:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

Complexité :

  • Temps : O(log(n)), car l’algorithme divise par deux la zone de recherche à chaque itération.
  • Espace : O(1), car un nombre constant de variables est utilisé.

Correction :

  1. Adéquation : La recherche garantit que, si val est présente dans le tableau, elle sera atteinte en ajustant correctement les bornes (debut, fin) en fonction des comparaisons.
  2. Complétude : Si val n’est pas trouvée, l’intervalle de recherche devient vide, et l’algorithme renvoie -1.

Preuve de terminaison :

  • À chaque itération, l’intervalle [debut, fin] diminue strictement en taille, passant de n à 0, garantissant que la boucle s'arrête.
  • La condition debut > fin finit par être satisfaite, assurant que l’algorithme se termine.

7. Tri par insertion⚓︎

Explication : Cet algorithme insère chaque élément du tableau dans sa position correcte dans la partie triée, de gauche à droite.

Langage algorithmique : 

Algorithme TriParInsertion(tab)
    Pour i allant de 1 à longueur(tab) - 1 faire
        cle <- tab[i]
        j <- i - 1
        Tant que j ≥ 0 et tab[j] > cle faire
            tab[j + 1] <- tab[j]
            j <- j - 1
        Fin Tant que
        tab[j + 1] <- cle
    Fin Pour
Fin Algorithme

Traduction Python : 

def tri_par_insertion(tab):
    """
    Trie un tableau en utilisant le tri par insertion.

    :param tab: liste des nombres.
    :return: tableau trié.
    """
    for i in range(1, len(tab)):
        cle = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1
        tab[j + 1] = cle
    return tab

Complexité :

  • Temps :
  • Meilleur cas : O(n), lorsque le tableau est déjà trié.
  • Pire cas : O(n²), lorsque le tableau est inversé.
  • Espace : O(1), car seules des variables locales sont utilisées.

Correction :

  1. Adéquation : Chaque élément est correctement inséré dans la partie triée, assurant que la sous-liste tab[0..i] est triée après chaque étape.
  2. Complétude : Tous les éléments du tableau sont pris en compte et insérés dans la partie triée.

Preuve de terminaison :

  • La boucle externe s'exécute un nombre fini d'itérations (n-1) de 1 à n.
  • La boucle interne diminue strictement grâce à j -= 1, garantissant qu'elle finit également.

8. Tri par sélection⚓︎

Explication : Cet algorithme trouve le plus petit élément dans la partie non triée du tableau et l’échange avec la première position de cette partie. Ce processus est répété pour chaque position.

Langage algorithmique : 

Algorithme TriParSelection(tab)
    Pour i allant de 0 à longueur(tab) - 1 faire
        min_ind <- i
        Pour j allant de i + 1 à longueur(tab) - 1 faire
            Si tab[j] < tab[min_ind] alors
                min_ind <- j
            Fin Si
        Fin Pour
        échanger tab[i] et tab[min_ind]
    Fin Pour
Fin Algorithme

Traduction Python : 

def tri_par_selection(tab):
    """
    Trie un tableau en utilisant le tri par sélection.

    :param tab: liste des nombres.
    :return: tableau trié.
    """
    for i in range(len(tab)):
        min_ind = i
        for j in range(i + 1, len(tab)):
            if tab[j] < tab[min_ind]:
                min_ind = j
        tab[i], tab[min_ind] = tab[min_ind], tab[i]
    return tab

Complexité :

  • Temps : O(n²), car chaque élément nécessite de parcourir le reste du tableau.
  • Espace : O(1).

Correction :

  1. Adéquation : Le plus petit élément est correctement placé à chaque itération, assurant que la sous-liste triée est correcte.
  2. Complétude : Tous les éléments sont comparés et déplacés, garantissant que le tableau entier est trié.

Preuve de terminaison :

  • Les boucles externes et internes parcourent un nombre fini d’éléments et réduisent strictement la taille de la partie non triée, assurant ainsi la terminaison.