Informatique au lycée Faustin Fleret

Il est nécessaire de pouvoir s'assurer qu'un algorithme effectue bien ce qui est attendu (la correction), qu'il finit bien par s'arréter (la terminaison) et qu'il effectue son travail dans un délai raisonnable (la compléxité).
Nous allons découvrir comment démontrer qu’une boucle while se termine avec le variant de boucle, puis nous allons prouver qu’un algorithme est correct avec l’invariant de boucle.

Problème de terminaison : le variant de boucle

Le problème de la terminaison est un problème important en informatique lorsqu'on parle de boucles. Ce problème se pose lorsque l'on écrit une boucle qui peut potentiellement ne jamais se terminer, c'est-à-dire qu'elle continuera à tourner indéfiniment sans jamais s'arrêter.

Pour éviter cela, on utilise une technique appelée "variant de boucle". Un variant de boucle est une expression numérique qui doit être modifiée à chaque itération de la boucle et qui doit garantir que la boucle finira par se terminer.

• Exemple 1 : boucle for en Python avec un variant :

  Copier le code

  for i in range(n):
      # instructions de la boucle
  

  Dans cet exemple, le variant de boucle est la variable i, qqui est incrémentée à chaque itération de la boucle. Comme i commence à 0 et que la boucle continue tant que i < n, le variant de boucle atteindra finalement la valeur "n" et la boucle se terminera.

• Exemple 2 : boucle while en Python avec un variant :

  Copier le code

  i = 0
  while i < n:
      # instructions de la boucle
      i += 1
  

  Dans cet exemple, le variant de boucle est la variable i, qui augmente de 1 à chaque itération de la boucle. Comme i commence à 1 et que la boucle continue tant que i < n, le variant de boucle atteindra finalement la valeur "n" et la boucle se terminera.

Il est important de choisir un variant de boucle qui garantit que la boucle se terminera. Si le variant de boucle ne décroît pas à chaque itération, ou s'il ne décroît pas suffisamment rapidement, la boucle pourrait ne jamais se terminer.

En résumé, le variant de boucle est une technique importante pour garantir que les boucles se terminent correctement. Il est important de bien choisir un variant de boucle qui garantit la terminaison de la boucle.

Algorithme division(a, b)
Entrée : a et b sont deux entiers positifs non nuls avec a > b.
Sortie : un tuple (q,r) constitué de deux entiers q et r tels que a = bq + r et r < b.
q ← 0
r ← a
tant que r > b faire
	q ← q + 1
	r ← r - b
retourner (q,r)

Problème de correction : l'invariant de boucle

En programmation, l'une des tâches les plus importantes est de s'assurer que le code fonctionne correctement. Pour cela, on utilise souvent des boucles pour parcourir une liste ou effectuer une opération un certain nombre de fois. Cependant, il peut arriver que la boucle ne s'exécute pas comme prévu, entraînant des erreurs dans le programme.

C'est là que l'invariant de boucle entre en jeu. Un invariant de boucle est une condition qui doit être vraie à chaque itération de la boucle, garantissant ainsi que le programme fonctionne correctement. En d'autres termes, si l'invariant est vrai avant l'itération de la boucle, il sera également vrai après l'itération.

Voici un exemple d'utilisation de l'invariant de boucle : Supposons que nous voulions calculer la somme des n premiers entiers. Nous pouvons utiliser une boucle pour itérer à travers chaque nombre et ajouter le résultat à la somme totale. Cependant, si la boucle n'est pas correctement écrite, elle peut entraîner des erreurs dans le calcul de la somme.

Voici un exemple de code en Python pour calculer la somme des n premiers entiers :

def somme_des_entiers(n):
	 """Renvoie la somme des entiers jusqu'à n."""
    somme = 0  # invariant 
    for i in range(1, n+1):
        somme += i
        # invariant: contient la somme partielle des i premiers entiers
        assert somme == i*(i+1)//2, "Invariant de boucle rompu !"
    return somme

Dans ce code, l'invariant de boucle est que la variable somme contient la somme des i premiers entiers positifs avant chaque itération de la boucle.

• Avant la boucle, somme est initialisé à 0, ce qui est bien la somme des 0 premiers entiers positifs.
• À chaque itération, nous mettons à jour la somme partielle pour inclure le nombre suivant et vérifions que l'invariant est toujours vrai. Si l'invariant est faux à une itération, cela signifie qu'il y a une erreur dans la boucle et nous devons corriger le code..

Après la boucle, somme contient la somme des n premiers entiers positifs, comme requis.

Problème de temps : la complexité d'un algorithme

Le calcul de la complexité d’un algorithme permet de mesurer sa performance. Il existe deux types de complexité :

• complexité spatiale : permet de quantifier l’utilisation de la mémoire
• complexité temporelle : permet de quantifier la vitesse d’exécution

Il est important de connaître la complexité d'un algorithme car elle peut aider à déterminer le temps nécessaire pour exécuter l'algorithme sur des entrées de différentes tailles. Cela peut être particulièrement utile lorsque l'on travaille avec des ensembles de données volumineux, car certains algorithmes peuvent prendre beaucoup plus de temps que d'autres pour traiter de grandes quantités de données.

Réaliser un calcul de complexité en temps revient à compter le nombre d’opérations élémentaires (affectation, calcul arithmétique ou logique, comparaison…) effectuées par l’algorithme.

Par soucis de simplicité, on fera l’hypothèse que toutes les opérations élémentaires sont à égalité de coût, soit 1 « unité » de temps.

Exemple : toto = toto + 1 ---> 1 addition + 1 affectation = 2 unité

La complexité en temps d’un algorithme sera exprimé par une fonction, notée T (pour Time).

On calculera le plus souvent la complexité dans le pire des cas, car elle est la plus pertinente.

Pour comparer des algorithmes, il n’est pas nécessaire d’utiliser la fonction T mais seulement l’ordre de grandeur, noté O(« grand O »).

Exemples d'ordre de grandeur :

• T(n) = 7 => O(1)
• T(n) = 12n + 5 => O(n)
• T(n) = 4n^2 + 2n+6 => O(n^2)
• T(n) = 2 + (n-1) x 5 => O(n)

Les différentes classes de compléxité

Pour se fixer les idées, voici un tableau qui donne le temps approximatif d’exécution en fonction de la taille des données. Nous partirons du principe qu’une instruction élémentaire prend 1 µs (10−6 secondes).

Exemples pour le calcul de la compléxité :

Exemple 1 : Calcul de la somme des n premiers carrés (Boucle for)

def somme_carres(n):
    somme = 0
    for i in range(1, n+1):
        somme += i**2
    return somme

La boucle for s'exécute n fois, donc la complexité de cet algorithme est O(n), car le temps nécessaire pour exécuter l'algorithme est proportionnel à la taille de l'entrée n.

Exemple 2 : Recherche du maximum d'une liste :

def max_liste(liste):
    maximum = liste[0]
    for element in liste:
        if element > maximum:
            maximum = element
    return maximum

La boucle for s'exécute n fois (où n est la taille de la liste), donc la complexité de cet algorithme est O(n), car le temps nécessaire pour exécuter l'algorithme est proportionnel à la taille de l'entrée n (la taille de la liste).

Exemple 3 : Calcul du produit de deux matrices (Boucles for imbriquées):

def produit_matrices(A, B):
    n = len(A)
    m = len(B[0])
    C = [[0]*m for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(B)):
                C[i][j] += A[i][k] * B[k][j]
    return C

La première boucle for s'exécute n fois, la deuxième boucle for s'exécute m fois, et la troisième boucle for s'exécute len(B) fois. Par conséquent, la complexité de cet algorithme est O(n*m*len(B)), car le temps nécessaire pour exécuter l'algorithme dépend de la taille des deux matrices A et B.

def fonction_mystere(tab):
    mystere = tab[0]  #tab est un tableau de réels de taille n
    i = 0
    while i < len(tab) : # ligne 3
        if tab[i] > mystere : # ligne 4
            mystere = tab[i]
        i = i + 1
    return mystere

def somme_de_n(n):
    somme = 0
    i = 1
    while i <= n:
        somme += i
        i += 1
    return somme

def recherche_element(liste, element):
    for i in range(len(liste)):
        if liste[i] == element:
            return True
    return False

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

def on_est_jamais_trop_prudent(tab):
	"""
	Paramametre :
	tab : un tableau d'entier de type list
	Renvoie :
	nombre : entier de type int
	"""
	nombre = L[0]
	n = len(L)
	for i in range(n):
		if nombre < L[i]:
			nombre = L[i]
	for j in range(n):
		if nombre < L[j]:
			nombre = L[j]
	return nombre

def mystere_1(n):
	x = 0
	for i in range(n):
		for j in range(n):
			x += 1
	return x

def mystere_2(n):
	x, i = 0, n
	while i > 1:
		for j in range(i):
			x += 1
			i //= 2
	return x