Cours

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 [290], 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]

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 insere_trie(l, x):
    """ Liste, int -> Liste """
    if est_vide(l):
        return ajoute(l, x)
    else:
        if x < tete(l):
            return ajoute(l, x)
        else:
            rst = queue(l)
            pre  = tete(l)
            rst_x = insere_trie(rst, x)
            lst = ajoute(rst_x, pre)
            return lst

def tri_sel(l):
    """ Liste -> Liste """
    if est_vide(l):
        return l
    else:
        pre = tete(l)
        rst = queue(l)
        rst_t = tri_sel(rst)
        lst_t = insere_trie(rst_t, pre)
        return lst_t

La complexité de la fonction tri_sel est, dans le pire des cas, quadratique en le nombre \(n\) d'éléments qui composent l.

Démonstration.

Lol

Programmation dynamique¶

à partir de l'arbre d'appel de fibonnacci
nombre de chemins
rendu de monnaie (tp)
problème du sac à dos