Enseignement d'introduction à la programmation pour les SIG

L'objectif de ce cours est d'introduire des notions avancées d'algorithmique. Ce cours est assez peu applicatif mais j'espère qu'il ne sera pas moins intéressant pour autant. Les notions qui sont introduites dans ce cours sont des outils importants pour aborder la programmation de manière plus solide par la suite, en ayant un peu de recul sur vos programmes.

Les exemples seront données et pratiqués en Python, et certains exemples seront directement traités au sein de QGis. Pour les exemples de QGis, je vous laisse reprendre la fiche du dernier TP qui illustrait l'utilisation de Python au sein de QGis et pendant laquelle vous aviez travaillé sur deux couches vectorielles (arrêts de bus de la STAR et supports de vélos STAR de Rennes). Pour les exemples qui ne traitent pas directement de données vectorielles, vous pourrez les traiter dans QGis, mais il serait préférable de le faire dans Spyder. La version de Python que j'utilise est une version 3.

Dans la suite, vous pouvez copier/coller le contenu des codes dans vos programmes pour les tester, les changer et voir leur comportement.

CM1 -- Recherche et tri dans des structures de données linéaires

Dans ce cours, nous nous intéresseront à deux tâches très usuelles en programmation informatique: la recherche d'un élément dans un ensemble de valeurs et le tri de valeurs. Ce sont des outils fondamentaux qui ont été étudiés depuis l'origine de l'algorithmique. Ils permettent d'introduire les notions de base de ce cours.

Motivation

À titre d'exemple, je reprends les algorithmes sur lesquels vous aviez travaillé lors du premier cours (avec la couche des arrêts de bus) :

Ce code est typiquement un code de recherche : l'objectif de cet algorithme est de retrouver tous les arrêts qui ont un abri. Ce type d'opération est très régulièrement fait, et l'objectif va être de comprendre en détails, les différentes manières qu'on peut avoir de réaliser cette opération (et c'est passionnant !! Si si !!).
Bon, en fait, ce qui va m'intéresser par la suite, c'est surtout les performances de ces différents algorithmes et, en particulier, les performances en temps de calcul (on aurait pu s'intéresser aussi à l'espace mémoire nécessaire pour faire fonctionner ces algorithmes). Nous allons donc reprendre l'exemple ci-dessous et ajouter quelques lignes pour calculer le temps nécessaire pour faire la recherche sur la couche de données :

Et, je vais maintenant vous proposer un autre code pour faire la même manipulation ... ce code utilise la notion de filtre que vous trouvez pour faire des sélections d'attributs dans QGis. Cette même notion se retrouve également en Python.

Executez ces deux codes et comparez les temps d'exécution !. Un objectif de ce cours va donc d'être en mesure d'expliquer ce comportement.

Retour à un contexte plus simple que les couches vectorielles

Dans cette partie, vous pourrez revenir dans Spyder pour tester les codes.

On commence par la recherche d'un élément dans une liste de valeurs (entiers). Plus précisément, il s'agit ici de savoir .

Ce code est composé de deux fonctions : une fonction pour la génération aléatoire d'un vecteur d'entiers et une fonction qui effectue la recherche d'un élément dans un vecteur.
Le programme principal illustre l'utilisation de ces deux fonctions.
On pourra noter qu'un soin particulier est donné à la documentation de ces fonctions !! Ces codes doivent vous servir d'exemple pour vos futurs programmes Python.

La fonction def recherche(vec, elem) détermine si un élément est présent ou non elem est présent ou non dans le vecteurvec. La fonction retourne un booléen. Dans le cas d'introduction, la tâche était légèrement différente, il s'agissait d'identifier la liste de tous les éléments du vecteur qui correspondaient à la valeur recherchée.

def recherche(vec, elem):
    """Fonction de recherche des occurrences de l'élément elem dans le vecteur vec
    
    :param vec: vecteur
    :param elem: élément à rechercher
    :type vec: list of int
    :type elem: int
    :return: retourne une liste de positions où se trouve l'élément recherché (liste vide si il n'est pas présent)
    :rtype: [int]
    """
    sel=[]
    for pos in range(len(vec)):
        if vec[pos]==elem:
            sel.append(pos)
    return sel
?>

Notion de preuve de programme

Comment peut-on être sûr que le programme réalise bien la tâche qui a été demandée (et dans tous les cas) ? La notion de preuve de programme correspond à l'idée de utiliser des raisonnements sur le programme qui vont prouver que celui-ci réalise bien la tâche escontée. Pour cela, le principe consiste d'une part à définir une notion d'état du programme et, d'autre part, à identifier dans le programme des points de passage pour lesquels on s'intéressera à l'état du programme. On définira alors ce qu'on appelle des assertions qui vont spécifier cet état : ces assertions sont des éléments qui vont permettrent de construire la preuve de notre programme.
Dans le cas du programme précédent, on va s'intéresser aux détails de la fonction de recherche. On se trouve en présence d'un algorithme qui réalise une boucle. Quatre points sont alors intéressants à regarder (cf ci-dessous) :

L'état avant la boucle
L'état en début d'une itération
L'état en fin d'une itération
L'état après la boucle

On complémente cela avec l'autre cas intéressant provenant de l'utilisation du if :

L'état lorsque le test est validé

On peut également noter que les positions 4 et 5 sont intéressantes à regarder dans la mesure où elles correspondent aux états possibles de sortie de la fonction (juste avant des return): si on est en mesure de définior précisément l'état du programme au moment où on passe à ces points, alors on saura exactement ce que calcule la fonction.


def recherche(vec, elem):
    # point (1)
    for i in range(len(vec)):
        # point (2)
        if vec[i]==elem:
            # point (5)
            return (True,i)
        # point (3)
    # point (4)
    return (False,0)

On va commencer par définir ce que sera l'état du programme. C'est clairement une étape importante, puisque c'est là dessus qu'on va raisonner par la suite La notion d'état correspond à un instant donné de l'exécution du programme. Pour la recherche, nous allons avoir besoin de savoir:

est-ce qu'on a déjà trouvé l'élément dans le tableau (oui/non)
où on en est de la lecture du tableau (position)

À partir de là, nous allons pouvoir écrire des assertions, c'est-à-dire des phrases qui peuvent être évaluées à vrai ou faux. La particularité des assertions ci-dessous est qu'elles sont vraies À CHAQUE FOIS que l'exécution du programme passe par le point correspondant

Rien particulier à noter

- on est à la i-eme case, i<=len(vec)
- l'élément n'a pas encore été trouvé dans les (i-1) premières cases

- l'élément n'a pas encore été trouvé dans les i premières cases

- l'élément n'a pas été trouvé dans le tableau

- l'element elem est dans la i-eme case du tableau

Donc, maintenant, je vais donner des exemples de raisonnement qui peuvent être menées sur ces assertions pour établir une preuve du bon fonctionnement de mon programme. La première chose qu'il faut faire, c'est de prouver que ces assertions sont belles et bien correctes (c'est-à-dire que dans tous les cas elles soient vraies).

Commençons par le plus simple, l'assertion (5) est assez triviale dans la mesure où d'après la ligne précédente, on ne peut atteindre ce point du programme que si effectivement, il y a elem à la position i du tableau. On peut rajouter que dans ce cas, comme on sort de la fonction, la solution renvoyée par la fonction est correcte !
Ensuite, on peut aussi assez facilement traiter le cas du point (4). Il s'agit d'un point de sortie d'une boucle. Il faut donc s'intérroger sur les conditions de sortie de cette boucle et l'état qui précédait cette sortie. Dans le cas de ce programme, la seule manière de sortir normalement de la boucle est d'atteindre la fin de la lecture du tableau, soit i=len(vec). C'est la seule manière parce que c'est une boucle for et qu'il n'y a pas de break. L'état de sortie en la position (4) est alors celui du point (3), avec i=len(vec). Avec l'assertion de (3), on en déduit trivialement que "l'élément n'a pas encore été trouvé dans les len(vec) premières cases". Comme le tableau est de taille len(vec), on en déduit que l'élément n'a pas été trouvé dans le tableau. De la même manière que précédemment, on s'assure ainsi que ce second point de sortie donne effectivement le bon résultat.
on passe maintenant à l'assertion du point (2). Dans ce cas de début de boucle, il faut considérer deux cas: le cas initial (la première fois où on passe en (2) et on arrive donc de la position (1)) et le cas de la boucle pour lequel on revient du point (3). Dans le cas du début de boucle, on a i=1 et pas encore trouvé l'élément recherché (on commence juste!). Tout roule ! Dans le cas où on revient du point (3), on est sûr que "on est à la i-eme case, i<=len(vec)" grâce à la boucle for dont les bornes assurent la validité de cette assertion. Ensuite, comme dans l'itération précédente on avait en (3) "l'element elem est dans la i-eme case du tableau", en ayant incrémenté i on a donc bien "l'element elem est dans la (i-1)-eme case du tableau" !!
Finalement, il reste l'assertion du point (3).
- on sait d'après (2) que "l'element elem est dans la (i-1)-eme case du tableau"
- il faut donc simplement montrer que, si on passe en (3), c'est bien le cas également pour la case i! Et de fait, si ce n'est pas le cas (raisonnement par l'absurde) on serait passé en (5) et comme il y a un return, on serait sorti de la fonction et ne serions jamais passés en (3). Donc, l'élement n'est pas dans la case i.
ceci permet donc de conclure que toutes mes assertions sont correctes !

Il faut donc maintenant savoir ce qu'il en est de la fonction ... pour cela, il faut se référer aux spécifications de celle-ci, qui donnent, du point de vu fonctionnel, ce qu'est sensé réaliser la fonction. Nous avons alors deux choses à vérifier pour dire que le programme fonctionne :

la correction: est-ce que le programme a bon lorsqu'il donne un résultat ?
Donc, cela, on a vu que pour les points (4) et (5) les sorties correspondaient bien aux attentes à chaque fois. On en déduit donc que le programme est correct.
la complétude: est-ce que le programme trouvera toujours la solution lorsqu'elle existe ?
Ensuite, on sait que le programme passe systématiquement sur toutes les cases du tableau pour les tester ... on peut donc en conclure que le programme est complet.

Notion de complexité (au pire cas)

Nous allons dans cette partie effectuer nos premiers calculs de complexité. Nous ne traiteront ici que le cas des algorithmes itératifs. Avant de commencer, rappelons notre hypothèse de base : toutes les opérations élémentaires sont à égalité de côut. Cela permet donc d'affirmer que le temps d'exécution est proportionnel au nombre de ces opérations élémentaires.

Algorithmes sans structures de contrôle

Si un algorithme n'en comporte pas, pour évaluer sa complexité il suffit juste de dénombrer le nombre d'opérations successives qu'il possède. La fonction suivante convertit un nombre de secondes en heures, minutes, secondes :

def conversion(n):
    h = n // 3600
    m = (n - 3600*h) // 60
    s = n % 60
    return h,m,s

On peut dénombrer cinq opérations arithmétiques et trois affectations. On a donc $T(n)=8$ .

Le cas des structures conditionnelles

En présence d'une structure conditionnelle, il faut commencer par dénombrer le nombre de conditions du test.

On décompte ensuite le nombre d'opérations élémentaires de chacune des alternatives, et l'on prend le maximum de ce décompte afin d'obtenir la complexité dans le pire des cas.

La fonction suivante calcule $(-1)^n$ sans effectuer de produit mais en utilisant un test avec une alternative :

def puissanceMoinsUn(n):
   if n%2==0:
      res = 1
   else:
      res = -1
   return res

Le test de la conditionnelle comporte une opération arithmétique et une comparaison. Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes alternatives est de un.

On a donc $T(n)=3$ .

Le cas des structures itératives

Il y a deux possibilités lors du traitement d'une structure itérative. Si chaque itération comporte le même nombre d'opérations élémentaires, pour évaluer la complexité il suffit de multiplier le nombre d'itérations par le nombre d'opérations de chacune d'elles. Si chaque itération ne possède pas le même nombre d'opérations, il faudra alors distinguer ces itérations, c'est-à-dire évaluer la complexité de chacune d'elle puis en faire la somme.

Le nombre d'opérations élémentaires d'une itération inclut bien sûr l'évaluation des tests d'entrée de boucle.

Cette fonction utilise une structure for pour calculer la somme des $n$ premiers entiers :

def sommeEntiers(n):
    somme = 0
    for i in range(n+1):
        somme += i
    return somme

Ici chaque itération a le même nombre d'opérations, à savoir cinq : deux affections (i et somme), deux additions (i et somme) et une comparaison. On a d'autre part une affectation, lors de l'initialisation de la variable somme. Ainsi $T(n)=5n+1$ .

Voici, une autre méthode pour calculer cette somme est d'utiliser une formule explicite.

def sommeEntiersBis(n):
   return n*(n+1)//2

Cet algorithme ne comporte pas de structures de contrôle, il est juste constitué de trois opérations arithmétiques.On a donc $T(n)=3$ .

Les deux algorithmes précédents nous offrent un premier exemple de comparaison d'efficacité puisqu'ils répondent tous deux à la même tâche. La conclusion est ici évidente, il vaut mieux utiliser le second.

Premiers exemples un peu plus élaborés

On va dans cette sous-partie se pencher sur des situations un peu plus délicates avec le calcul de la complexité des algorithmes de recherche séquentielle (cf précédemment).

Ici la complexité sera fonction de la longueur de la liste, que nous noterons $n$ . Dans le pire des cas l'élément recherché n'appartient pas à la liste, et il a fallu la parcourir en entier pour arriver à cette conclusion, c'est-à-dire effectuer $n$ itérations. De plus, chaque itération comporte le même nombre d'opérations élémentaires, à savoir une affectation, une addition et deux comparaisons.

On a donc $T(n)=4n$ .

Notation grand O

On introduit tout d'abord une notation. On dit qu'une fonction $f$ est un grand $O$ d'une fonction $g$ ssi $∃c>0, ∃n0>0 tel que ∀n>n0, f(n)<c×g(n)$ , on note alors $f(n)=O(g(n))$ .

Cela signifie qu'à partir d'un certain rang la fonction $f$ est majorée, à une constante multiplicative près, par la fonction $g$ . Il s'agit donc d'une situation de domination de la fonction $f$ par la fonction $g$ .

Cette notation permet d'avoir de comparer des temps de calcul en se passant du calcul de tous les détails du nombre d'instruction. Voici en pratiques quelques relations grand O

Si $T(n)=4$ alors $T(n)=O(1)$ .
Si $T(n)=3n+2$ alors $T(n)=O(n)$ .
Si $T(n)=2n²+3$ alors $T(n)=O(n²)$ .

Les complexités algorithmiques que nous allons calculer vont dorénavant être exprimées comme des grand $O$ de fonctions de références. Cela va nous permettre de les classer.
Des algorithmes appartenant à une même classe seront alors considérés comme de complexité équivalente. Cela signifiera que l'on considèrera qu'ils ont la même efficacité.
Le tableau suivant récapitule les complexités de référence :

$Ο$	Type de complexité
$Ο(1)$	constant
$Ο(log(n))$	logarithmique
$Ο(n)$	linéaire
$Ο(n×log(n))$	quasi-linéaire
$Ο(n²)$	quadratique
$Ο(n^3)$	cubique
$Ο(2^n)$	exponentiel
$Ο(n!)$	factoriel

Recherche séquentielle: cas pratique d'évaluation des temps d'exécution (légèrement différent de la complexité)

Dans cette section, l'objectif est d'évaluer les temps réels de traitement. Les complexités au pire cas sont parfois trompeuses par rapport à la réalité, notamment parce que les vraies données sont parfois plus simples que.
Le code ci-dessous illustre comment calculer le temps d'exécuter moyen de recherche.

Exercice

Modifier le programme pour calculer des temps moyens de recherche pour des tailles de listes allant de 100000 jusqu'à 500000 (de 50000 en 50000).
Vous pourrez aussi dessiner un graphique pour illustrer le comportement de l'algorithme en adaptant le code ci-dessous :
```
import matplotlib.pyplot as plt #outil pour faire des graphiques

x=[] #tableau pour contenir des valeurs
for i in range(1,100):
    val=cos(i)
    x.append( val ) #ajout d'un élément à la liste x

plt.plot(x,'b') # le 'b' signifie un affichage en bleu
```
plus de détails et d'exemples de matplotlib ici: https://matplotlib.org/.
Les temps suivent ils la relation linéaire espérée? Comment expliquer ce comportement?
Modifier la génération aléatoire des valeurs de la liste
```
int(random.randint(vecsize/10,1000))
```

Recherche séquentielle: cas pratique d'évaluation sur les données des arrêts de bus

L'exemple ci-dessous évalue le temps moyen de la recherche. Le cas de l'abri simple était peut être un cas particulier, il est alors plus pertinent de calculer le temps moyen obtenu sur toute les valeurs possibles de l'attributs mobilier (et on aurait aussi pu changer d'attribut).

import time

layer = iface.activeLayer()

mobiliers = set()
layer.setSubsetString("")
for f in layer.getFeatures():
    mobiliers.add(f['mobilier'])

mobiliers = list(mobiliers)

start_time = time.time()

for m in mobiliers:
    selected_fid = []
    for f in layer.getFeatures():
        if f['mobilier']==m:
            selected_fid.append(f.id())
    print(len(selected_fid))
    
elapsed =  (time.time()- start_time) / len(mobiliers)
print( "{0:.4}".format(elapsed) )

Exercice

Modifier le code de sorte à évaluer le temps moyen de recherche avec l'utilisation des filtres.

Recherche dichotomique

Retour sur la recherche séquentielle! La recherche se fait donc en temps linéaire. Mais est-ce possible de faire mieux ?

La plupart des bons algorithmes fonctionnent grâce à une méthode astucieuse pour organiser les données. Par exemple, on sait très bien, intuitivement, que pour retrouver une carte dans un jeu, il est très utile que le jeu soit trié.

On part donc de l'idée que le tableau est trié

Ce qui est intéressant de remarquer ici, c'est que l'algorithme est théoriquement avec un coût au pire cas qui est le même que précédemment. Il est alors intéressant de comparer en pratique.

Mais on va donc aller vers un autre type d'algorithme, qui va fonctionner sur des tableaux triés, mais dont le cout théorique au pire cas va être meilleur.

Version itérative

Dans l'algorithme ci-dessous, appellé recherche dichotomique,

On vous fournit également le code de comparaison des deux méthodes (recherche séquentielle et recherche dichotomique :

preuve de programme: identifier les points d'arrêt qui semblent importants dans le programme, puis essayer de définir des assertions et de les prouver
évaluation de la complexité algorithmique (difficile!):
- commencer par considérer la taille des tableaux qui est traitée à chaque tour de boucle
- essayer d'identifier une fonction mathématique qui permettra d'exprimer le nombre de tour de boucle maximum qui sera effectué par le programme en fonction de la taille du tableau $n$ .
- sachant que tout le reste des opérations peut être considéré comme un O(1), en déduire la complexité de l'algorithme

On donne ci-dessous un graphique obtenu pour comparer l'évolution des temps de calcul (en recherche logarithmique) entre la recherche séquentielle (en rouge), la recherche dichotomique (en bleu) et la recherche séquentielle sur tableau trié (en vert).

Complexité

Pour chacun des codes ci-dessous, indiquer la complexité algorithmique en fonction de $n$ et $m$ . On pourra noter que ces fonctions ne font rien de particulier !

def fonction1(n,m):
    a = 0
    for i in range(n):
        a = a + 1
    for j in range(m):
        a = a + 1
    return (a)

def fonction2(n,m):
    a = 0
    for i in range(n):
        a = a + 1
        for j in range(m):
            a = a + 1
    return (a)

def fonction3(n,m):
    a = 0
    for i in range(n):
        a = a + 1
        for j in range(i):
            a = a + 1
    return (a)

Complexité (2)

Pour chacun des codes ci-dessous, indiquer la complexité algorithmique en fonction de $n$ et $m$ . On pourra noter que ces fonctions ne font rien de particulier !. On note également T un tableau de taille $n$ .

def fonction1(n,m):
    b = 0
    for i in range(n):
        for j in range(m):
            for k in range(n):
                b = b + 1
    return (b)

def fonction2(n,m):
    if n > m:
        for i in range(n):
            a = a + 1
    else:
        a = n * m
    return (a)

def fonction3(n,m,T):
    a = 0
    i = n
    while i > 0:
        a = a + T[i]
        i = i - 1
    return (a)

def fonction4(n,T,e):
    a = 0
    while i < n:
        if e == T[i]:
            a = a + 1
        i = i + 1
    return (a)

Qu'est ce que fait ce dernier algorithme ?

Version récursive

Le but de cette section est d'introduire la notion de récursivité. L'algorithme précédent de recherche dichotomique est un exemple de logique de programme qui fonctionne très bien pour l'écriture de programme sous forme de récursion.

Notion de récursivité

L'idée de la récursion est similaire à celui que vous avez rencontré pour la définition des suites numériques (ie des termes $u(n), ∀ n ∈ N$ ). Vous pouvez définir les termes d'une suite de deux manières:

de manière "iterative": $∀ n ∈ N, u(n)= g(n)$
de manière récursive: $∀ n ∈ N, u(n+1)= f(u(n))$

Un exemple classique de défintion récursive d'une fonction est la factorielle. On a $∀ n ∈ N, n!= (n-1)! x n$ . Le programme qui découle de cette formule est :

def fact(n):
    return n*fact(n-1)

Dans ce cas, la fonction fact fait appel "récursivement" à la fonction fact (mais avec un paramètre différent) ... qui elle même va faire appel ... etc.
Quand est-ce que cela se termine ?? Bonne question !! En l'état une erreur se produit ... parce que la récursion est infinie ! Il faut donc définir des "cas terminaux" qui vont faire s'arrêter la récursion (et remonter!). On peut se souvenir que lors d'un raisonnement par récurrence ou bien pour la définition d'une suite récursive, il faut également donner des cas de départ différent du cas de récursion. Le cas terminal pour la factorielle est celui de $0!=1$ . On a donc une fonction plutôt sous la forme:

def fact(n):
    if n==0:
        # cas terminal
        return 1
    else:
        # cas recursif
        return n*fact(n-1)
    return ret

Pour tester le fonctionnement de votre fonction, on vous propose l'utiliser la fonction suivante qui "trace" les différents appels récursifs

def fact(n):
    print("enter fact({})".format(n))
    if n==0:
        ret=1
    else:
        ret=n*fact(n-1)
    print("exit fact({})".format(n))
    return ret
    
fact(4)

L'affichage attendu est:

enter fact(4)
enter fact(3)
enter fact(2)
enter fact(1)
enter fact(0)
exit fact(0)
exit fact(1)
exit fact(2)
exit fact(3)
exit fact(4)

Les outils d'algorithmique précédents peuvent être utilisé pour prouver les programme et évaluer la complexité. Ces outils sont alors alors utilsés avec des raisonnements par récurrence ou bien avec des outils sur les suites/séries récurrentes.

Exemple de calcul de la complexité de la fonction factorielle: on a $T(k)=O(1)+T(k-1)$ pour $k>0$ et $T(0)=O(1)$ . On peut en déduire que $T(k)$ est une suite récursive : suite arithmétique de raison $1$ . On en déduit que $T(n)=O(n)$ .

La version itérative de la factorielle serait:

def fact(n):
    ret=1
    for i in range(1:n):
        ret *= i
    return ret

Le palindrome récursif

Exemple d'algorithme récursif sur un tableau

def palindrome_rec( T ):
    """
    Fonction de palindrome recursif
    """
    print("palindrome " + str(T))
    if len(T)==2:
        return T[0]==T[1]
    elif len(T)==1:
        return True
    else:
        if T[0]==T[-1]:
            return palindrome_rec( T[1:-1] )
        else:
            return False

T=[34,45,56,45,34]

if palindrome_rec(T):
    print("ok")

T=[34,45,56,56,45,34]

if palindrome_rec(T):
    print("ok")

Attentions aux "recopies cachées"!! Le code ci-desous va être plus efficace en Python parce que le tableau T ne sera pas dupliqué à chaque appel de fonction.

def palindrome_rec( T, d =0, f = -1 ):
    """
    Fonction de palindrome recursif
    """
    if f==-1:
        f = len(T)-1
    print("palindrome " + str(d) +"-" + str(f))
    if d==f-1:
        return T[d]==T[f]
    elif d==f:
        return True
    else:
        if T[d]==T[f]:
            return palindrome_rec( T, d+1, f-1 )
        else:
            return False

La recherche dichotomique

Donc, l'objectif est de faire la recherche dichotomique à l'aide d'un algorithme récursif! La récursivité utilise une stratégie de "diviser pour régner": en résolvant une multitude de sous-problèmes, on arrive à un programme globalement plus efficace.
Et bien soit, voyons à quoi cela ressemble :

À regarder

preuve du programme (attention: la spécification des fonctions est très importante). Prouver le bon fonctionnement d'un algorithme récursif nécessite de vérifier deux propriétés : premièrement l'algorithme se termine et deuxièmement si l'algorithme se termine, il fait bien ce qu'on attend de lui (correction/complétude). Dans le cas des algorithmes récursifs, ces méthodes sont spécifiques.
calcul de la complexité

Exercice: écriture de fonctions récursives

Algorithme d'Euclide

L'algorithme d'Euclide calcule le PGCD de deux nombres $a$ , $b$ ainsi:

PGCD(a, 0) = a
PGCD(a, b) = PGCD(b, a % b) si b != 0

Puissance de 2 récursive

L'objectif de cet exercice est d'écrire un algorithme récursif pour le calcul de $2^n$ .

On note $p(n)=2^n$ . Écrire une relation de récurrence entre $p(n)$ et $p(n-1)$ .
Écrire un algorithme récursif qui implemente la fonction p(n)
Tester votre fonction en calculant $p(3)$

Suite de Fibonacci

La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Elle commence généralement par les termes 0 et 1 (parfois 1 et 1) et ses premiers termes sont : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.

On note $F(n)$ la n-eme valeur de la suite de Fibonacci. Écrire une relation de récurrence entre $F(n)$ , $F(n-1)$ et $F(n-2)$ .
Écrire un algorithme récursif qui implemente la fonction fibo(n)
Tester votre fonction. Que vaut $F(8)$ ?
Ajouter un affichage dans votre fonction récursive à l'image de l'exemple de la factorielle pour analyser la "pile d'appels"

Calcul de $x^n$ (exponentiation)

On se place dans la situation où on ne sait pas calculer la puissance d'un nombre $x$ par un entier $n$ . On doit donc écrire une nouvelle fonction qui va permettre de la calculer à partir des opérations de bases (notamment la multiplication).

La première proposition est donc l'algorithme naïf

Fonction puissance(x,n):
    p = 1
    POUR i = 1..n FAIRE
        p *= x
    RETOURNE(p)

Evaluer la complexité algorithmique de cet algorithme.
On propose maintenant un second algorithme récursif suivant.

Fonction puissance(x,n):
    SI n est pair ALORS
        p = puissance( x, n/2 )
        RETOURNER( p*p )
    SINON
        p = puissance( x, (n-1)/2 )
        RETOURNER( p*p*x )

La tâche de tri

Étant donné un tableau de valeurs entières (contenant potentiellement des répétitions), la tâche de tri d'un tableau consiste à construire un (nouveau) tableau dans lequel les valeurs sont triées en ordre croissant.
Dans la suite de cette section, on présente différentes méthodes de tri d'un tableau.

Tri par insertion

L'idée est de trier progressivement le tableau : supposant que t[0:k] est déjà trié, j'insère t[k] à sa place parmi les valeurs de t[0:k] (en décalant les plus grandes valeurs d'un cran vers la droite si nécessaire) de sorte que t[0:k+1] se retrouve trié. Le principe de modularité pourrait nous conduire à écrire une fonction qui détermine la place de t[k], puis une deuxième fonction qui se charge de l'insertion. On obtient un code plus compact en décalant les valeurs au fur et à mesure de la recherche de la place de t[k] (sans oublier de mémoriser la valeur de t[k], qui risque d'être écrasée très vite !). Plus précisément, pour $k$ allant de $1$ à $n - 1$ :

je stocke la valeur de t[k] dans une variable temp et j'initialise j à la valeur k
tant que j>0 et temp < t[j-1] (j'ai une valeur supérieure à temp à gauche de t[j]), je décale t [j-1] d'un cran vers la droite et je décrémente j
à la sortie de la boucle j'installe temp à sa place.

La fonction de tri peut ainsi s'écrire en Python :

def tri_ins(t):
    for k in range(1,len(t)):
        temp=t[k]
        j=k
        while j>0 and temp<t[j-1]:
            t[j]=t[j-1]
            j-=1
        t[j]=temp
        return t

Elements de preuve:

pour la boucle while, la valeur de j diminue strictement à chaque passage, il y aura donc au maximum k itérations ; terminaison naturelle pour la boucle for ;
preuve par récurrence de l'invariant de boucle : "après l'exécution de la boucle for pour la valeur k les valeurs t[0],...,t[k] sont les valeurs initiales rangées par ordre croissant"

Complexité au pire: $n(n-1)/2$

Tri par insertion récursif

L'idée de l'algorithme se prête bien à une vision récursive, en écrivant une procédure tri_ins(t,j) qui trie (récursivement) la tranche t[:j] :

si j = len(t), il n'y a rien à faire
sinon j'insère t[j] dans la tranche t[:j-1] (qui à ce stade est triée, cf. l'hypothèse de récurrence dans la preuve) puis je lance l'appel récursif tri_ins(t,j+1).

Pour la modularité, j'écris une procédure récursive qui insère t[j] dans la tranche t[:j-1] supposée triée.

def insere(t,j):
    if j>0 and t[j]<t[j-1]:
        t[j-1],t[j]=t[j],t[j-1]
        insere(t,j-1)

def tri_ins(t,j=1):
    if j<len(t):
        insere(t,j)
        tri_ins(t,j+1)

Tri par fusion

L'idée récursive est naturelle :

s'il y a au plus une valeur, le tableau est trié ;
s'il y a au moins deux valeurs, couper le tableau en deux, trier (récursivement) les deux sous-tableaux obtenus, puis fusionner les résultats : la fusion consiste à rassembler dans un seul tableau trié les valeurs contenues dans les deux tableaux triés fournis en paramètre (en respectant bien sûr les répétitions éventuelles : la longueur du résultat de la fusion est la somme des longueurs des deux tableaux initiaux).

D'où le programme Python, en supposant programmée ladite fusion

def tri_fusion(t):
    if len(t)<2:
        return t
    else:
        m=len(t)//2
        t_gauche=tri_fusion(t[:m])
        t_droite=tri_fusion(t[m:])
        return fusion(t_gauche,t_droite)

La terminaison est justifiée par la décroissance stricte de $n$ à chaque appel récursif, la correction par récurrence forte sur $n$ .
Noter que la profondeur maximale des appels récursifs est de l'ordre de $log2(n)$ , ce qui permettra de trier de grands tableaux, même avec Python ...

La fusion se prête très bien également à une programmation récursive, avec les avantages et inconvénients habituels : élégante et facile à justifier, mais gourmande en mémoire.
Voici une vision récursive de l'algorithme de fusion de deux tableaux triés t1 et t2 :

si l'un des deux tableaux est vide, renvoyer l'autre ;
sinon renvoyer le tableau formé par la plus petite des deux valeurs t1[0] et t2[0], suivie de la fusion de t1 et t2, l'un des deux ayant été privé de sa première valeur déjà placée !

D'où ce programme Python:

def fusion(t1,t2):
    if t1==[]:
        return t2
    elif t2==[]:
        return t1
    elif t1[0]<t2[0]:
        return [t1[0]]+fusion(t1[1:],t2)
    else:
        return [t2[0]]+fusion(t1,t2[1:])

D'une manière itérative, la fusion peut se faire de la sorte

def fusion(t1,t2):
    """
    :param t1 et t2: t1 et t2 sont deux tableaux triés
    """
    i1=0
    i2=0
    t=[]
    #tant qu'il y a des valeurs dnas les deux tableaux, on prend 
    while i1!=len(t1) and i2!=len(t2):
        if t1[i1]>=t2[i2]:
            t.append( t2[i2] )
            i2+=1
        else:
            t.append( t1[i1] )
            i1+=1
    #on vide le dernier tableau
    while i1!=len(t1):
        t.append( t1[i1] )
        i1+=1
    while i2!=len(t2):
        t.append( t2[i2] )
        i2+=1

Si on regarde la première fonction tri_fusion et qu'on note $T(n)$ la complexité au pire cas de celui-ci pour un tableau de taille $n$ , on peut déterminer sa complexité de manière récursive en disant que cet algorithme nécessite le temps pour faire le tri de deux tableaux de taille $n/2$ (soit $2*T(n/2)$ ) et le temps de la fusion des deux tableaux (temps qui est linéaire avec la taille des sous tableaux, soit $O(n)$ ). On peut donc écrire que $T(n)=2*T(n/2)+n$ avec $T(1)=1$ . Si on a ainsi une suite dont on cherche une expression explicite. Si on suppose que les tableaux ont des tailles qui sont des puissances de 2, on a $n=p^2$ . On peut ainsi reformuler: $T(n)=2*T(n/2)+n$ en $T(2^p)=2*T(2^(p-1))+2^p$ et donc, en divisant, $T(2^p)/2^p=T(2^(p-1))/2^(p-1)+1$ . Si on note $U(p)=T(2^p)/2^p$ , on revient à écrire $U(p)=U(p-1)+1$ dont on sait écrire la forme explicite (suite arithmétique): $U(p)=1+p$ . On a ainsi que $T(2^p)=1+p.2^p~p.2^p$ , et en fonction de $n$ : $T(n)=n.log2(n)$ .

Complexité au pire est donc en $O(n.log(n))$ .

Tri rapide -- Quicksort

L'idée consiste à partitionner d'abord le tableau t à trier autour d'un pivot : on choisit l'une des valeurs du tableau (ledit pivot), par exemple t[0] et l'on construit deux tableaux avec les t[i] pour i > 0 (où l'on peut retrouver le pivot si sa valeur figure pour plusieurs indices...) :

le premier t1 avec les valeurs correspondant aux indices i tels que t[i] < pivot
le second t2 avec les valeurs correspondant aux indices i tels que t[i] ≥ pivot

Il n'y a plus qu'à trier (récursivement !) t1 et t2 et à renvoyer les valeurs triées de t1, suivies de la valeur du pivot et des valeurs triées de t2 ! On obtient ainsi les valeurs de t triées (preuve immédiate par récurrence forte).

def quicksort(t):
    if t == []:
        return []
    else:
        pivot = t[0]
        t1 = []
        t2 = []
        for x in t[1:]:
            if x<pivot:
                t1.append(x)
            else:
                t2.append(x)
        return quicksort(t1)+[pivot]+quicksort(t2)

Du point de vue de la complexité, on peut noter que -- contrairement à la situation du tri par fusion -- t1 et t2 peuvent être de tailles déséquilibrées, ce qui fait que la complexité de ce tri peut-être quadratique dans le pire des cas. Mais sa complexité en moyenne est en $n log(n)$ et sa mise en oeuvre s'avère très rapide, d'où son nom !

Tri par sélection

Le principe du tri par sélection est le suivant :

rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ;
continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

En pseudo-code, l'algorithme s'écrit ainsi :

  procédure tri_selection(tableau t, entier n)
      pour i de 1 à n - 1
          min = i
          pour j de i + 1 à n
              si t[j] < t[min], alors min = j
          fin pour
          si min != i, alors échanger t[i] et t[min]
      fin pour
  fin procédure

Faites la preuve de cet algorithme
Déterminer la complexité au pire cas. Cet algorithme vous semble-t-il efficace ?
Implémenter l'algorithme en Python et tester le

CM2 -- Arbres

CM1: Recherche et tris

CM2: les arbres