Diaporama n°4¶

Algorithmique - Notions fondamentales¶

I. Généralités¶

Définition¶

Un algorithme est une "démarche systématique" qu'un novice est censé suivre pour résoudre un problème.

Analogies :

  • "recette de cuisine" pour faire une île flottante
  • "mode d'emploi" pour installer une box internet
  • "notice de montage" pour monter un meuble en kit

Exemple : pour savoir si un nombre entier est divisible par 3, il suffit de regarder si la somme de ses chiffres est divisible par 3

Exemple : pour sortir d'un labyrinthe parfait (sans ilot), il suffit d'avancer en laissant sa main sur le mur droit

NB : Le novice n'a pas besoin de comprendre pourquoi l'algorithme fonctionne, pour constater qu'il donne le bon résultat

Programme ou algorithme ?¶

Un programme informatique est la traduction / mise en oeuvre / implémentation (anglicisme) d'un algorithme dans un langage de programmation

NB : c'est le programmeur qui fait la traduction, afin que la "démarche systématique" soit réalisée par la machine

NB : le programmeur n'a pas besoin lui non plus de comprendre pourquoi l'algorithme fonctionne

NB : Erreur de programmation (bug d'implémentation) != Erreur de conception (algorithme "incorrect")

Cours¶

I - Généralités¶

II - Terminaison¶

Exemple 1 : variant de boucle (while)¶

In [ ]:
# calcule le quotient de la division entière de a (a entier, a>=0) par (b entier, b>0)
# entrée : a,b    # sortie : q
q = 0
tant que (a >= b):
    a = a - b 
    q += 1
renvoyer q

III - Correction¶

Exemple 2 : invariants¶

indiquer les invariants pour prouver la correction de l'algorithme suivant

In [ ]:
def max3(a,b,c):
    """ renvoie la plus grande valeur des trois """
    if (a > b):
        if (a > c):
            return a
        else :     
            return c
    else :
        if (b > c):
            return b
        else :      
            return c

Exemple 3 : invariants¶

indiquer les invariants pour prouver la correction de l'algorithme suivant

In [3]:
def max3bis(a,b,c):
    """ renvoie la plus grande valeur des trois """
    m = a
    if (b > m):
        m = b
    # ????
    if (c > m):
        m = c
    # ????
    return m

Exemple 4 : invariant de boucle¶

In [ ]:
# détermine la plus petite valeur de la liste L, supposée non vide
# entrée : L     sortie : mini

mini = L[0]
pour i allant de 1 à len(L)-1:
    si (L[i] < mini):
        mini = L[i]
renvoyer mini

que peut-on affirmer pour la variable mini ?

In [ ]:
# détermine la plus petite valeur de la liste L, supposée non vide
# entrée : L     sortie : mini

mini = L[0]
pour i allant de 1 à len(L)-1:
    si (L[i] < mini):
        mini = L[i]
    # invariant : mini est le minimum de { L[0], L[1] ... L[i] }
renvoyer mini

A la fin du tour de boucle i, mini est le minimum de { L[0], L[1] ... L[i] }

In [ ]:
# détermine la plus petite valeur de la liste L, supposée non vide
# entrée : L     sortie : mini

mini = L[0]
# invariant : mini est le minimum de { L[0] }
pour i allant de 1 à len(L)-1:
    si (L[i] < mini):
        mini = L[i]
    # invariant : mini est le minimum de { L[0], L[1] ... L[i] }
# invariant : mini est le minimum de { L[0], L[1] ... L[len(L)-1] }, donc de L
renvoyer mini

Après le boucle dernier tour de boucle, mini est le minimum de { L[0], L[1] ... L[len(L)-1] }, donc de L

CQFD

IV. Complexité¶

A suivre ...¶