Terminaison et complexités

À un même problème, différentes solutions algorithmiques peuvent être proposées. Nous avons vu dans le chapitre précédent l’existence d’algorithmes qui ne terminent pas, c’est à dire qui sur certaines entrées peuvent ne jamais retourner de résultat car entrant dans des boucles infinies. La première qualité attendue d’un algorithme est bien sûr sa terminaison.
Initiation à l’algorithmique par Denis Lapoire
Un second critère permet de les comparer et ainsi d’en distinguer de meilleures que d’autres. Ce critère est la faible utilisation de deux ressources
• le temps • l’espace.

Terminaison

L’une des qualités attendus d’un programme est qu’il termine, c’est à dire qu’il n’admette aucune instance pour laquelle l’exécution rentre dans une boucle infinie.
On touche ici à l’un des problèmes difficiles en informatique. Par exemple, la communauté scientifique n’a pas réussi à prouver que l’algorithme suivant
fonction syracuse(a:entier) : mot tantque a<>1. faire si a est pair alors a – sinon a retourner  »fini »
terminait sur chaque entrée n. Nous avons bien-sûr exécuté l’algorithme sur un grand nombre d’entiers et observé que le calcul terminait chaque fois.
Mais nous n’avons aucune certitude en ce qui concerne tous les entiers.
Cet exemple traduit le fait que nous n’avons pas de méthode pour décider si un algorithme termine. Pire, nous avons prouvé qu’il n’existe pas de méthode universelle pour décider si un algorithme termine. En clair, le problème de la terminaison

Terminaison

Entrée : un algorithme A Sortie : le booléen indiquant si A termine ou non
est un problème indécidable, c’est à dire incalculable on prouve qu’il n’existe aucun algorithme le résolvant.
Exemple 7 Il existe d’autres exemples de problèmes indécidables. L’un des plus célèbres est le dixième problème de Hilbert, qui s’interrogeait en 1900 sur l’existence d’un algorithme décidant l’existence d’une racine entière pour une équation polynomiale à coefficients entiers. Nous savons aujourd’hui qu’il n’en existe pas ce problème est indécidable.
Ne prenez pas prétexte de l’indécidabilité de la terminaison, pour produire des algorithmes ne terminant pas. Avec un minimum de méthodologie, il est possible lorsque vous écrivez un algorithme de vous assurer de façon formelle qu’il termine.

Complexité

Nous l’avons déjà dit, un grand nombre de problèmes fournissent dans la définition mathématique des objets mentionnés une solution algorithmique.
problème Puissance Entrée : un réel x, un entier a Sortie : le réel Xa
Si on utilise la définition de vue en troisième ou en quatrième, à savoir x multiplié par lui même n fois, on obtient l’algorithme suivant
fonction puissancel(x:réel ; a : entier) : réel res +- 1. faire a fois res +- res x retourner res
Si vous préférez la relation récursive apprise en seconde Xa est égal à 1 si a vaut O et x x°’ sinon. Vous en déduisez l’algorithme suivant
fonction puissance2(x:réel ; a : entier) : réel si (a0) alors res +- 1. sinon res +- xopuissance2(x,a-1) retourner res
Ces deux algorithmes sont tous deux corrects mais ne sont pas équivalents, le second utilisant davantage de ressources espace que le premier. Les deux ressources que nous considérerons ici sont le temps et l’espace.

Complexité d’une entrée

Avant de définir ce qu’est la complexité d’un algorithme, il nous faut définir la complexité d’une entrée (instance) manipulée par cet algorithme.
Définition 1 La complexité (ou taille) d’une entrée est le nombre d’octets nécessaires à sa représentation.
Comme nous le verrons par la suite, la complexité d’un objet (entrée, algorithme ou problème) est définie à une constante multiplicative près.
Complexité d’un booléen
Ainsi, par exemple, un booléen nécessite pour sa représentation un octet (en fait un bit suffit). Nous dirons qu’il est de complexité ou taille constante.
Complexité d’une matrice de booléen
Une matrice n lignes, m colonnes de booléens est de complexité n m.
Complexité d’un entier
Trois hypothèses apparaissent
1 La première façon de représenter un entier est de lui allouer un nombre d’octets fixe. Ce choix réalisé dans le langage de programmation C (un octet pour le type char, 4 octets pour le type int) a une limite il ne permet de représenter que des entiers en nombre fini. Un entier positif représenté sur 4 octets peut prendre au plus 248 valeurs possibles les entiers sur 4 octets décrivent l’intervalle [0, 232 – 1]. Sous cette hypothèse, la complexité d’un entier est constante. 2 La seconde façon de représenter un entier n est de lui allouer autant d’octets que nécessite sa représentation, à savoir log2 (n + 1)1 (que nous noterons log(ri)). Cette représentation est nécessaire quand les entiers utilisés peuvent prendre des valeurs réellement très grandes c’est le cas d’applications cryptologiques qui manipulent des entiers représentés sur des centaines de bits.
Initiation à l’algorithmique par Denis Lapoire
3 Pour des raisons pédagogiques et de simplicité, nous supposerons souvent un type entier pouvant prendre n’importe quelle grande valeur et dotée d’opérations comme l’addition se réalisant en temps constant. Ce choix est un choix pédagogique mais n’admet aucune implémentation machine concrète.
Complexité d’une matrice d’entiers
Quand nous considérerons une matrice d’entiers n lignes m colonnes, nous supposerons que ceux-ci sont de taille constante. Ainsi, la complexité de la matrice est considérée égale à n m.