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)
Input In [66], in <cell 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

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)\).