Techniques de programmation

Styles de programmation¶

Vocabulaire¶

Effet de bord: Une fonction est à effet de bord lorsqu'elle modifie l'état de la mémoire de l'ordinateur.
Objet non mutable: Lorsque l'on ne peut pas modifier l'état d'un objet après sa création, on dit que celui-ci est non mutable. Par exemple True en Python est un objet non mutable. La plupart des objets sont mutables en Python.

En python, le type tuple est non-mutable, tandis que le type list est mutable.

  ma_liste = [1, 2, 3]
  mon_tuple = (1, 2, 3) # Ne soulève pas d'erreurs
  mon_tuple[0] += 1     # Soulève une erreur lors de son exécution

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[3], line 3
      1 ma_liste = [1, 2, 3]
      2 mon_tuple = (1, 2, 3) # Ne soulève pas d'erreurs
----> 3 mon_tuple[0] += 1     # Soulève une erreur lors de son exécution

TypeError: 'tuple' object does not support item assignment

Une fonction ayant un effet de bord peut avoir un comportement différent alors qu'elle est appelée avec les mêmes arguments.

  ma_liste = [1, 2, 3]
  def f(x):
      """ int -> [int] """
      for i in range(len(ma_liste)):
          ma_liste[i] += x
      return ma_liste
  print(f(1))
  print(f(1))

[2, 3, 4]
[3, 4, 5]

Au contraire, une fonction n'ayant pas d'effet de bord a nécessairement le même comportement lors d'appels successifs.

  ma_liste = (1, 2, 3)
  def g(x):
      """ int -> [int] """
      return [e + x for e in ma_liste]
  print(g(1))
  print(g(1))

[2, 3, 4]
[2, 3, 4]

Dans certains langages de programmation, on dit qu'une fonction est pure lorsqu'elle ne possède pas d'effet de bord, et on dit qu'elle est impure lorsqu'elle possède des effets de bord.

Programmation fonctionnelle¶

Le style de programmation fonctionnel est proche de l'écriture de preuves mathématiques : on décrit un programme à l'aide d'appel de fonctions et on les compose entre elles. On utilise des appels récursifs pour obtenir un comportement similaire à une boucle. Il est caractérisé par :

l'absence d'effets de bord
les objets sont non mutables
les fonctions réalisent des calculs qui renvoient toujours le même résultat

On parle de paradigme fonctionnel.

La fonction suivante ajoute x à tous les éléments de la liste l.

La liste l n'est pas modifiée.

def f_fonc(l, x):
    """ [int], int -> [int] """
    if l == []:
        return []
    else:
        return [l[0] + x] + f_fonc(l[1:], x)
l = [1, 2, 3]
print(f_fonc(l, 1))
print(l)

[2, 3, 4]
[1, 2, 3]

Programmation impérative¶

Le style de programmation impérative est très proche de la manière de fonctionner d’un ordinateur : dans ce style de programmation, on exécute des instructions qui modifient l’état de l’ordinateur. On utilise des boucles pour répéter des instructions. Il est caractérisé par :

la présence d’effets de bord
les objets sont mutables
l’ordinateur exécute des instructions. Le résultat dépend de l'état actuel de l'ordinateur.

On parle de paradigme impératif.

La fonction suivante ajoute x à tous les éléments de la liste l.

La liste l est modifiée.

def f_imp(l, x):
    """ [int], int -> [int] """
    for i, e in enumerate(l):
        l[i] += x
    return l
l = [1, 2, 3]
print(f_imp(l, 1))
print(l)

[2, 3, 4]
[2, 3, 4]

Complexité d'un algorithme¶

Un algorithme est un procédé automatique permettant de résoudre un problème en un nombre fini d'étapes. La complexité en temps d'un algorithme est le nombre d'opérations effectuées en fonction de \(n\), la taille des données du problème.

On s'intéresse au nombre d'opérations effectuées plutôt qu'au temps, car tous les ordinateurs n'effectuent pas le même nombre d'opérations par seconde.

Taille	\(\log_{2}(n)\)	\(n\)	\(n\log_{2}(n)\)	\(n^2\)	\(2^n\)
10	0.003 ms	0.01ms	0.03 ms	0.1 ms	1 ms
100	0.006 ms	0.1 ms	0.6 ms	10 ms	10¹⁴ siècles
1000	0.01 ms	1ms	10 ms	1s
10⁴	0.013 ms	10 ms	0.1 s	100 s
10⁵	0.016 ms	100 ms	1.6 s	3 h
10⁶	0.02 ms	1s	20 s	10 jours

On considère que la plupart des opérations élémentaires s'effectuent en temps constant, à l'exception notable de l'exponentiation qui s'effectuent en un temps proportionnel à la taille de l'exposant.

On rappelle l'implémentation python de l'algorithme du tri par sélection.

def ins_trie(l, e):
  """ Liste, int -> Liste
  l est triée par ordre croissant """
  if est_vide(l):
    return ajoute(l, e)
  else:
    if e < tete(l):
      return ajoute(l, e)
    else:
      a = ins_trie(queue(l),e)
      return ajoute(a, tete(l))

def tri_insertion(l):
  """ Liste -> Liste
  Trie la liste l à l'aide de l'algorithme du tri par insertion """
  if est_vide(l):
    return l
  else:
    rst = tri_insertion(queue(l))
    return ins_trie(rst, tete(l))

On suppose que les fonctions est_vide, ajoute, tete et queue s'exécutent en temps constant. La complexité de la fonction ins_trie est alors dans le pire des cas linéaire en la taille de la liste. La complexité de la fonction tri_insertion est dans le pire des cas quadratique en la taille de la liste.

On rappelle l'implémentation python du tri fusion.

def tri_fusion(l):
    """ Liste -> Liste
    Trie la liste l (tri fusion) """
    if est_vide(l) or est_singleton(l):
        return l
    else:
        l1, l2 = diviser(l)
        l1 = tri_fusion(l1)
        l2 = tri_fusion(l2)
        return fusionner(l1, l2)

On suppose que les opérations est_vide et est_singleton s'effectuent en temps constant, que les opérations fusionner et diviser ont une complexité linéaire. Pour une liste l de taille \(n\), on note \(c_n\) est le nombre d'opérations élémentaires effectuées par tri_fusion(l). On a :

\[\begin{cases} c_0 = c_1 = 0 \\ c_n = 2c_{n/2} + 2n \end{cases} \]

Lorsque \(n = 2^k\) on a : \(c_{n} = 2 n\log_2(n)\).

On dit que la complexité de la fonction tri_fusion est quasilinéaire.

On fait la moyenne du temps d'execution des deux algorithmes. n est la taille de la liste à trier.

Dresser l'arbre d'appel de l'instruction tri_fusion(l) lorsque l est la liste \((8, 1, 7, 3, 1, 6, 4, 5)\).

Optimisation¶

Le code récursif naïf permettant de calculer le \(n\)-ième terme de la suite de Fibonacci a une complexité exponentielle, il est inutilisable dans la pratique.

def fibo(n):
    """ int -> int
    Renvoie le n-ième terme de la suite de Fibonacci """
    if n <= 1:
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

Mémoïsation¶

La technique dite de mémoïsation permet d'éviter de répéter des calculs déjà effectués plusieurs fois. On décrit le fonctionnement d'une fonction récursive fibomem qui utilise pour cela une variable supplémentaire memo de type dictionnaire, qui va jouer le rôle de "mémoire" partagée entre les appels récursifs :

les clés de memo correspondront aux valeurs de n pour lesquelles on a déjà calculé \(F_n\) ;
la valeur associée à n dans memo est \(F_{n}\).

À chaque appel récursif fibomem(n, memo) :

si n est une clé de memo : cela veut dire que le calcul a déjà été effectué. Il suffit donc de renvoyer memo[n].
sinon : on effectue le calcul de \(F_n\) en mémoïsant les résultats intermédiaires. On met à jour memo avec la valeur de \(F_n\) et on renvoie \(F_n\).

def fibomem(n, memo):
    """ int -> int
    Renvoie le terme d'indice n de la suite de Fibonacci
    Met à jour le dictionnaire memo """
    if n in memo: 
        return memo[n]
    if n <= 1:
        memo[n] = n
        return memo[n]
    else:
        memo[n] = fibomem(n - 1, memo) + fibomem(n - 2, memo)
        return memo[n]

Programmation dynamique¶

L’approche dite "par programmation dynamique" repose elle-aussi sur l’utilisation d’une structure de donnée auxiliaire afin de mémoriser les résultats intermédaires.

Définir les sous problèmes. Pour \(i\in \mathbb{N}\) et \(i \leq n\) calculer \(F_i\).
Identifier la relation de récurrence entre les sous-problèmes.

\[ F_{i} = \begin{cases} 0 &\textrm{si } i = 0 \\ 1 &\textrm{si } i = 1 \\ F_{i - 1} + F_{i - 2} &\textrm{sinon} \\ \end{cases} \]
En déduire un algorithme qui résolve les sous-problèmes. On initialise un tableau tab de taille \((n + 2)\). La taille d'indice \(i\) contient \(F_i\). On renseigne les cases d'indice \(0\) et \(1\) du tableau, que l'on parcourt en remplissant successivement les cases à l'aide de la relation de récurrence.
Résoudre le problème général. On renvoit tab[n]

def fibodyn(n):
    """ int -> int
    Calcule le terme d'indice n de la suite de Fibonacci """
    tab = [None]*(n + 2) 
    tab[0], tab[1] = 0, 1
    for i in range(2, n + 1):
        tab[i] = tab[i - 1] + tab[i - 2]
    return tab[n]

Notions de calculabilité et décidabilité¶

Les travaux de Church et de Turing dans les années 40 visent à définir la notion de calculabilité. On en retiendra la définition suivante : une fonction \(f\) à un paramètre est dite calculable s'il existe un algorithme qui étant donné une valeur \(x\) renvoit en un nombre fini d'étapes le nombre \(f(x)\). Lorsqu'un langage de programmation permet de calculer \(f(x)\) pour toute fonction calculable et pour toute valeur de \(x\), on dit que celui-ci est Turing-complet. Tous les langages de programmation sont Turing-complet. Autrement dit, tous les algorithmes peuvent être écrits dans n'importe quel langage de programmation.

On appelle problème de décision toute question dont la réponse est oui ou non. Par exemple, 159357 est-il premier est un problème de décision. Quel est le 45ème nombre premier n'est pas un problème de décision. On dit qu'un problème de décision est décidable s'il existe une fonction calculable \(f\) renvoyant True lorsque la réponse au problème est oui, et False sinon. Dans ce cas on appelle la fonction \(f\) un décideur. On dit qu'un problème est indécidable s'il n'est pas décidable.

Le problème de l'arrêt¶

Un bug courant dans l'écriture de programmes est de rencontrer une boucle qui ne termine pas, et de bloquer ainsi l'utilisation de l'ordinateur. Ce comportement peut aussi être utilisé à des fins malveillantes par des virus pour saturer la mémoire de l'ordinateur et le rendre inutilisable. On aimerait donc détecter via l'étude du code source du programme si celui-ci va engendrer ou non ce genre de problème.

Le problème de l'arrêt est le suivant : "Peut-on détecter les programmes qui ne terminent pas ?". On va montrer qu'un tel problème est indécidable. Supposons par l'absurde qu'il existe un décideur decideur_arret pour le problème de l'arrêt. Cette fonction prend en entrée un nom de fichier renvoit True si ce fichier correspond à un programme python qui termine, et False si le programme ne termine pas. On écrit alors le programme suivant :

if decideur_arret("impossible.py") == True:
    while True:
        pass
else:
    pass

Quel est alors le comportement du programme impossible.py lorsqu'il est exécuté par python ? Il est possible qu'il puisse terminer. Dans ce cas, decideur_arret("impossible") renvoit True donc c'est la boucle qui ne termine pas qui est exécutée. C'est impossible. Cela veut donc dire qu'il ne termine pas. Mais alors decideur_arret("impossible.py") renvoit False c'est donc l'instruction pass qui est exécutée, et le programme termine. On en déduit donc qu'il ne peut pas exister de décideur pour le problème de l'arrêt. Celui-ci est donc indécidable.

Problème de l'égalité et réduction¶

Il est fréquent que l'on demande aux élèves d'écrire des fonctions python, dont on ne sait pas trop si elles répondent correctement au problème posé. Le professeur, lorsqu'il prépare ses questions, écrit des fonctions python que l'on suppose répondant correctement à la question. On pourrait se demander s'il est possible d'automatiser la tâche de vérification des réponses des élèves : étant donné une fonction f fournie par un élève, une fonction g fournie par le professeur, peut-on dire si f(e) == g(e) pour toute entrée e ?

On appelle ce problème le problème de l'égalité : "Peut-on décider si deux programmes sont équivalents". Par équivalents on veut dire que lorsque les programmes terminent ils terminent en renvoyant le même résultat, et si l'un des deux programmes ne termine pas l'autre programme ne termine pas non plus. Un décideur decideur_egalite de ce problème est donc un programme qui renvoit True si le texte des deux programmes donnés en entrée correspondent à des programmes équivalents, False sinon.

On va montrer que ce problème est indécidable en se ramenant au problème de l'arrêt. Supposons par l'absurde qu'il existe un décideur decideur_egalite au problème de l'égalité. La fonction decideur_egalite renvoie True si et seulement si les programmes stockés dans les fichiers fichier1 et fichier2 sont équivalents. On écrit alors le code suivant :

def infini():
    while True:
        pass

def decideur(programme):
    if decideur_egalite("infini.py", programme) == True:
        return False
    else:
        return True   

Quel est le comportement de la fonction decideur ? Étant donné le nom de fichier d'un programme quelconque :

si celui-ci ne termine pas, alors il est équivalent au programme "infini.py" et donc l'instruction decideur_egalite("infini.py", programme) renvoie True. La fonction decideur renvoit dans ce cas False.
Si celui-ci termine, alors decideur(programme) renvoit True.

On a donc construit une fonction python qui renvoie True si et seulement si le programme contenu dans le fichier programme termine : il s'agit d'un décideur pour le problème de l'arrêt ! Or on sait que cela est impossible, cela veut donc dire que la fonction decideur_egalite ne peut exister. Le problème de l'égalité est donc indécidable.

Remarque. On a utilisé ici une technique de réduction : on a montré qu'un problème est indécidable en utilisant le fait que sa décidabilité entraîne nécessairement la décidabilité d'un problème que l'on sait indécidable.