Recherche maximum

• Le diaporama du cours

Résumé du cours

Algorithme de recherche du maximum

L’algorithme de recherche du maximum dans un tableau consiste à:

• Initialiser une variable pour stocker le maximum provisoire
• Parcourir séquentiellement le tableau en comparant chaque élément au maximum provisoire
  • Mettre à jour le maximum provisoire si un élément plus grand est trouvé
• Renvoyer le maximum final après avoir parcouru tout le tableau

Implémentation en Python

Plusieurs implémentations sont présentées, notamment:

def maximum(tab: list) -> int:
    maxi_prov = 0
    for val in tab:
        if val > maxi_prov:
            maxi_prov = val
    return maxi_prov

Concepts clés abordés

• Coût algorithmique: Le coût de la recherche du maximum est linéaire, dépendant de la taille du tableau.
• Terminaison: La notion de variant de boucle est introduite pour prouver qu’un algorithme se termine.
• Correction: Vérifier qu’un programme réalise effectivement ce qui était prévu.