Ce cours d’initiation à l’algorithmique permettra à toute personne de mettre en œuvre les notions de bases de l’algorithmique dans leur programme et permettra aux plus expérimentés de voir et concevoir leurs algorithmes différemment.
II – Chapitre 1 Discours de la Méthode(extraits)
III – Chapitre 2 Quelques définitions et quelque syntaxe
III-C-1 – 2.3.1 Entête de l’algorithme
III-C-2 – 2.3.2 Le corps de l’algorithme
III-C-4 – 2.3.4 Évaluation d’expression
III-C-5 – 2.3.5 Initialisation
III-C-6 – 2.3.6 Modification de valeurs
III-C-7 – 2.3.7 Mise en séquence
III-C-8 – 2.3.8 Branchement conditionnel
III-C-9 – 2.3.9 Autres branchements conditionnels
III-C-11 – 2.3.11 Autres boucles
III-C-12 – 2.3.12 Instruction retourner
III-C-13 – 2.3.13 Appel de fonctions
IV-C – 3.3 Comparaison de problèmes
IV-C-1 – 3.3.1 Augmenter les contraintes en entrée
IV-C-2 – 3.3.2 Diminuer les contraintes en sortie
IV-C-3 – 3.3.3 Décomposition en un ensemble équivalent de sous- problèmes
V – Chapitre 4 Terminaison et complexités
V-C – 4.3 Complexité d’une entrée
V-C-1 – 4.3.1 Complexité d’un booléen
V-C-2 – 4.3.2 Complexité d’un entier
V-C-3 – 4.3.3 Complexité d’une matrice d’entiers
V-D – 4.4 Complexité d’un algorithme
V-D-1 – 4.4.1 Instruction élémentaire
V-D-2 – 4.4.2 Espace utilisée par l’algorithme
V-D-3 – 4.4.3 Complexité en temps dans le pire des cas
V-D-4 – 4.4.4 Complexité en temps en moyenne
V-D-5 – 4.4.5 Complexité en temps dans le meilleur des cas
V-D-6 – 4.4.6 Complexité en espace
V-E – 4.5 Complexité d’un problème
V-E-1 – 4.5.1 Compromis espace-temps
V-F – 4.6 Notations et simplifications
V-F-1 – 4.6.1 À une constante multiplicative près: notation e
V-F-2 – 4.6.2 Des fonctions étalons
V-F-3 – 4.6.3 Simple majoration : notation O
V-F-4 – 4.6.4 Quelques règles d’évaluation de complexité
V-F-5 – 4.6.5 Mise en séquence
V-F-6 – 4.6.6 Branchement conditionnel
V-G – 4.7 Un peu de vocabulaire
V-G-1 – 4.7.1 Un algorithme linéaire
V-G-2 – 4.7.2 Un algorithme exponentiel
V-H – 4.8 Étude du problème de puissance
V-H-1 – 4.8.1 Importance des hypothèses
VI – Chapitre 5 Algorithmes « Diviser Pour régner »
VI-A – 5.1 Un premier exemple : la multiplication de deux entiers
VI-A-1 – 5.1.1 Un premier algorithme
VI-A-2 – 5.1.2 Un second algorithme
VI-A-3 – 5.1.3 Évaluation de la complexité
VI-B – 5.2 Évaluation de la complexité
VI-B-1 – 5.2.1 Définition récursive de la fonction
VI-C – 5.3 Résolution de certaines fonctions N – N définies récursivement
VI-D – 5.4 Un deuxième exemple : la multiplication de deux matrices
VI-D-1 – 5.4.1 Première méthode
VI-D-2 – 5.4.2 Seconde méthode dite de Strassen
VII – Chapitre 6 Programmation Dynamique
VII-A – 6.1 Une solution de programmation dynamique
VII-A-1 – 6.1.1 Autre alternative
VII-A-2 – 6.2 Bien fondé de l’approche dynamique
VIII – Chapitre 7 Algorithme Glouton
VIII-A – 7.1 Un premier exemple : le rendu de monnaie
VIII-B – 7.2 Deuxième exemple : optimisation de la location d’une salle
VIII-B-1 – 7.2.1 Première tentavive
VIII-B-2 – 7.2.2 Deuxième tentavive
VIII-B-3 – 7.2.3 Troisième tentavive concluante
IX – Chapitre 8 Quelques algorithmes de tri
IX-B – 8.2 Une première implémentation
IX-C – 8.3 Une deuxième implémentation à l’aide d’un tas
IX-C-1 – 8.3.1 Définition de haut niveau d’un tas
IX-C-2 – 8.3.2 Implémentation d’un tas
IX-C-3 – 8.3.3 Ajouter un élément dans un tas
IX-C-4 – 8.3.4 Extraire le maximum dans un tas
IX-C-5 – 8.3.5 Implémentation d’un tas-arbre à l’aide d’un tableau
IX-C-6 – 8.3.6 Écriture de l’algorithme
IX-C-7 – 8.3.7 Évaluation de la complexité
IX-D – 8.4 Approche « Diviser pour régner »
IX-D-1 – 8.4.1 Première solution algorithmique de TriRec
IX-D-2 – 8.4.2 Seconde solution algorithmique de TriRec
IX-D-3 – 8.4.3 Différentes variantes liées au choix du pivot
IX-D-4 – 8.4.4 Le choix du premier pivot venu: le tri rapide
IX-D-5 – 8.4.5 Le choix d’un pivot aléatoire
IX-D-6 – 8.4.6 Le choix d’un pivot médian
I – TABLE DES MATIÈRES
Ce cours est dédié aux étudiants de 1ère année de l’Enseirb spécialité informatique. Son intitulé « Initiation à l’algorithmique » est d’un certain point de vue un contresens. Tous les étudiants de l’Enseirb bénéficient d’une solide culture mathématique et ont donc nécessairement de larges connaissances en algorithme. En effet, la quasi totalité des objets mathématiques qu’ils ont rencontré depuis leur plus tendre âge ont été définis de façon calculatoire.
L’objet de ce cours est donc de s’appuyer sur ces connaissances et ce qu’elles recèlent d’intuition pour présenter différentes méthodes générales pour fournir à un problème une ou plusieurs solutions algorithmiques.
Nous insisterons sur la nécessité pour résoudre un problème de le découper en sous-problèmes auxiliaires, de résoudre ainsi le premier problème avant même d’avoir résolu ces problèmes auxiliaires. Cette approche descendante que nous suggère Descartes (Chapitre 1) est présentée dans le Chapitre 3.
Ce principe universel rappelé, nous présenterons des méthodes de résolution de problèmes qui ont pour nom
- l’approche « Diviser pour Régner ».
- la Programmation Dynamique.
- l’approche gloutonne.
Tout au long de ce cous, nous insisterons sur différentes qualités attendues des algorithmes écrits
- la correction naturellement qui assure que l’algorithme répond bien au problème.
- la simplicité d’écriture qui met en valeur notamment les différentes étapes de calcul en fournissant une vision structurée et donc simple de l’algorithme.
- la faible consommation de deux ressources que sont le temps et l’espace. En d’autres termes, nous évaluerons la complexité en temps et en espace de ces algorithmes.
Les deux derniers principes sont très souvent contradictoires. Un algorithme très rapide en temps s’écrit de façon plus complexe. Cette opposition apparaît dans l’écriture récursive dans de très nombreux cas, celle-ci offre une définition très simple mais utilise des ressources en espace non constant, alors qu’une version itérative plus compliquée à définir utilise moins d’espace. Pour cette raison, nous aurons soin pour certains problèmes d’écrire plusieurs solutions algorithmiques, chacune ayant une qualité singulière.
La résolution du problème Tri conclura ce cours en illustrant l’intérêt des méthodes présentées plus haut. Ce cours n’est pas un cours d’algorithmique et structures de données. Il ne contiendra pas notamment les classiques notions de Pile, Liste et File, d’arbres ou de graphes, ni leurs définitions, ni à fortiori leurs implémentations. Les exemples de problèmes concernant auant que faire ce peut des objets simples comme les booléens, les entiers ou des objets déjà très familiers à tous les étudiants comme les tableaux ou matrices.
Nous pouvons conseiller quelques documents
- Ce document accessible à http://www enseirb fr/lapoire/lereAnnee/InitiationAlgorithme/Cours/.
Nous rappelons que ce document est disponible sous forme papier. Il n’est donc pas utile de l’imprimer. Les remarques, corrections éventuelles sont les bienvenues et sont sollicitées à 1apoireenseirb f r.
- « Introduction à l’algorithmique » de Cormen and Co. Collection Dunod. Cet ouvrage est présent à la bibliothèque de l’Enseirb. Il est complet, long( plus de 1000 pages) et couvre l’ensemble des notions vues dans ce cours dans de nombreux autres cours d’Informatique de l’Enseirb. Les chapitres concernés par ce cours sont les chapitres 1, 2, 3, 4, 6, 7, 15, 16 et 28.
II – Chapitre 1 Discours de la Méthode(extraits)
« Au lieu de ce grand nombre de préceptes dont la logique est composée, je crus que j’aurois assez des quatre suivants, pourvu que je prisse une ferme et constante résolution de ne manquer pas une seule fois à les observer.
Le premier était de ne recevoir jamais aucune chose pour vraie que je ne la connusse évidemment être telle; c ‘est-à-dire, d’éviter soigneusement la précipitation et la prévention, et de ne comprendre rien de plus en mes jugements que ce qui se présenterait si clairement et si distinctement à mon esprit, que je n’eusse aucune occasion de le mettre en doute.
Le second, de diviser chacune des difficultés que j’examinerais, en autant de parcelles qu’il se pourrait, et qu’il serait requis pour les mieux résoudre.
Le troisième, de conduire par ordre mes pensées, en commençant par les objets les plus simples et les plus aisés
- connaître, pour monter peu à peu comme par degrés jusque à la connaissance des plus composés, et supposant même de l’ordre entre ceux qui ne se précèdent point naturellement les uns les autres.
Et le dernier, de faire partout des dénombrements si entiers et des revues si générales, que je fusse assuré de ne rien omettre.
Descartes, Discours de la Méthode(1 637)
III – Chapitre 2 Quelques définitions et quelque syntaxe
Dans ce chapitre, nous présentons le pourquoi d’un algorithme sa raison d’être est de résoudre un problème.
Nous présenterons en outre un langage de description algorithmique. Celui-ci est propre à ce cours. Il a été choisi pour des raisons de simplicité et de proximité avec d’autres langages comme le langage C.
III-A – 2.1 Problèmes
La raison d’être d’un algorithme est de résoudre un problème. La plus grande attention doit être portée à la compréhension du problème, faute de quoi l’algorithme n’a aucune chance d’être correct.
Le langage utilisé pour la définition d’un problème est un langage scientifique utilisant pour des raisons de simplicité une langue naturelle (le français par exemple) ou, pour lever toute ambiguiité, un langage logique. La compréhension du problème nécessite la maîtrise de ce langage.
Un problème est une relation binaire liant deux objets. Un exemple de problème est
problème Puissance
Entrée : un réel x#O, un entier n
Sortie : le réel
Cette relation n’est pas nécessairement fonctionnelle. comme par exemple le problème suivant problème FacteurPremier
Entrée : un entier n> 1
Sortie : un facteur propre premier de n si il en existe, O sinon.
III-B – 2.2 Types
Les objets manipulés ici sont typés. Un type est en fait un ensemble d’opérations permettant de manipuler ces objets.
Le type le plus élémentaire est sans contestation possible le type booléen que l’on peut définir à l’aide de cinq opérations
- vrai() qui retourne le booléen vrai.
- faux Q qui retourne le booléen faux.
- A qui associe aux deux booléens vrai le booléen vrai et faux sinon. Cette opération peut se noter et.
- V qui associe aux deux booléens faux le booléen faux et vrai sinon. Cette opération peut se noter ou.
- qui associe à vrai la valeur faux et inversement. Cette opération peut se noter non.
D’autres types seront utilisés, comme le type entier. Les opérations fournies seront, sauf mention contraire, les opérations arithmétiques classiques, addition, multiplication, division euclidienne, etc …. Parfois, nous nous
interrogerons sur la façon optimale d’implémenter ces fonctions auquel cas, nous supposerons par exemple que seule l’addition est fournie et qu’il nous faut redéfinir par exemple la multiplication. Nous fournirons alors une description détaillée de l’opération additive fournie. Sa complexité en temps dépend des hypothèses (voir Section 4.3).
Un autre type est le type tableau. Les opérations sur ce type permettent de
- de construire un tableau. Il faut alors fournir sa longueur, une valeur d’initialiser chacun des éléments et son premier indice (si il n’est pas fourni, on supposera qu’il s’agit de 1). Ainsi constructTab(1O) (100) (1) retourne un tableau de longueur 10 de valeurs toutes égales à 100 et de premier indice 1.
- de calculer sa longueur. La fonction longueur retourne la longueur d’un tableau.
- de calculer ou de modifier la valeur d’un tableau T à un indice j fourni. Nous utiliserons alors l’expression déjà familière T [i].
III-C – 2.3 Algorithme
Un exemple d’algorithme résolvant Puissance est
Comme nous pouvons l’observer sur l’exemple de l’algorithme puissance, un algorithme est un texte composé de deux parties
- une partie entête, appelée aussi prototype. Dans l’exemple fonction puissance( x : réel ; n : entier) : réel.
- le corps de l’algorithme qui fournit sa définition. Dans l’exemple début fin.
III-C-1 – 2.3.1 Entête de l’algorithme
L’entête d’un algorithme fournit 4 informations:
- la première est la nature de l’algorithme, fonction ou procédure; dans l’exemple : fonction. Celle-ci est précisée par le mot-clef fonction ou procédure. Pour des raisons de simplicité, nous utiliserons quasi exclusivement des fonctions qui contrairement aux procédures retournent en fin de calcul un ou plusieurs objets typés. Ainsi, le résultat du calcul effectué devra être retourné (instruction retourner présentée plus bas).
- le second est le nom de l’algorithme; dans l’exemple : puissance. Une grande importance doit être consacré à la définition de ce nom. Plusieurs méthodes existent quant à la définition de ce nom. Une minimale définit
le nom simplement à partir du simple problème à résoudre (exemple : fonction puissance). On peut aussi indiquer dans le nom, la méthode utilisée, voire le type des objets passées en entrée ou en sortie. Ces choix sont primordiaux dans l’écriture de longs programmes nécessitant l’écriture d’un grand nombre de fonctions. Les exemples que nous présenterons sont relativement simples et concis et donc ne nécessitent pas cet effort.
- le troisième est le nom et le type des arguments en entrée; dans l’exemple ( x : réel ; n : entier). Les différents types sont ceux spécifiés par le problème.
- la quatrième est le type (ou les types) de l’objet retourné par la fonction (dans l’exemple réel). Les types retournés sont ceux spécifiés par le problème à résoudre.
En conclusion, excepté le nom de l’algorithme et le nom des arguments en entrée, le prototype est entièrement dépendant de la définition du problème à résoudre et s’écrit donc sans difficulté (si le problème est clairement défini !).
III-C-2 – 2.3.2 Le corps de l’algorithme
Nous allons définir ici une syntaxe permettant d’écrire tout algorithme. Cette syntaxe est propre à ce cours. Elle n’a pas vocation à permettre la compilation ou l’exécution de l’algorithme sur une machine. Son ambition est de fournir selon une syntaxe simple des algorithmes simples et non ambigus qui pourront être traduits, avec un minimum d’effort, dans un langage de programmation comme le Langage C.
III-C-3 – 2.3.3 Variable
La quasi-totalité des problèmes nécessitent pour leur résolution un espace mémoire auxiliaire sur lequel sont exécuter des calculs intermédiaires. Pour gérer de façon simple et lisible cette espace mémoire, on utilise des « variables ».
Ainsi, derrière toute variable, se trouve un espace mémoire dont on peut modifier le contenu. De façon plus abstraite et donc plus formelle, une variable possède plusieurs attributs
1. un identificateur.
Ce nom dont elle ne change pas devra être choisi de façon judicieuse pour rendre l’algorithme compréhensible.
Naturellement, il ne peut pas être choisi parmi les mots clefs début, tantque, etc.
2. un type.
La variable possède à sa création un type dont elle ne peut pas changer. Notons que dans d’autres langages, d’autres choix existent.
3. une valeur.
Dès sa création, la variable possède une valeur de, naturellement, même type. Cette valeur peut naturellement varier d’où le nom de variable.
4. une durée de vie.
Dans un objectif de simplification, une variable existe uniquement au cours d’un appel de fonction et cesse à la fin de cet appel de fonction, donc lors de l’exécution de l’instruction retour.
Exemple 1 Voici un second algorithme qui nous permettra d’illustrer comment créer une variable et comment modifier la valeur d’une variable à l’aide de l’opération d’affectation +
III-C-4 – 2.3.4 Évaluation d’expression
Tout programme contient des expressions typées. Une expression typée est une expression bien formée vérifiant la syntaxe du type considérée.
Par exemple 2.j + 2 est une expression de type entier.
Puisque à tout moment de l’exécution d’un algorithme chaque variable possède une valeur, à tout moment on peut évaluer une expression, c’est à dire lui associer une valeur.
Dans l’exemple précédent, avant exécution de T [i] <-2 + 2 ;, la variable a pour valeur 5, aussi l’évaluation de l’expression 2 . + 2 fournit la valeur 12. Ces expressions peuvent naturellement être construites à partir de fonctions.
Ainsi (exemplelO+20.exemplelO) est une expression de type entier construite à partir de la fonction exemple 1 qui retourne à chaque appel la valeur entière 10.
L’évaluation de (exemplelO+20.exemplelO) fournit la valeur entière 210.
III-C-5 – 2.3.5 Initialisation
Pour créer une variable, il suffit d’utiliser l’opération affectation f- et de préciser à droite de ce symbole sa première valeur.
Ainsi i<-4 crée une variable de nom i, de type entier puisque 4 est de ce type et de valeur 4.
Ainsi r<-4.0 crée une variable de nom r, de type réel puisque 4.0 est de ce type et de valeur 4.0.
Ainsi j<-i crée une variable de nom j, de type entier puisque j est de ce type et de valeur celle de i à savoir 4. Notons que les variables j et j sont distinctes, ainsi la prochaine modification de j n’entrainera pas de modification de j.
En ce qui concerne le type tableau, vous pouvez utiliser un constructeur de tableau. Ainsi, T<-constructTab(10) (100)
- crée une variable T, de nom T, de type tableau et désignant un tableau de taille 10, à éléments tous égaux à 100 et de premier indice 1.
III-C-6 – 2.3.6 Modification de valeurs
Une fois la variable créée. l’utilisation de l’affectation – permet de modifier la valeur de la variable. Dans le programme exemple 1, i<-5 remplace l’ancienne valeur 4 par la valeur 5.
En ce qui concerne les tableaux, seules les modifications élémentaires sont autorisées. Ainsi, T[i]<- j modifie la 5ème case du tableau T de valeur initiale 100 par la valeur de l’expression 2.j+2 à savoir 12.
III-C-7 – 2.3.7 Mise en séquence
La première possibilité pour structurer un ensemble d’instructions est leur mise en séquence.
La syntaxe est
début
<instruction 1>
<instruction 2>
<instruction n>
f in
L’exécution d’une telle séquence est réalisée en exécutant d’abord l’instruction <instruction 1>, puis l’instruction <instruction 2> jusqu’à l’instruction <instruction n>.
III-C-8 – 2.3.8 Branchement conditionnel
Une deuxième possibilité pour structurer un ensemble d’instructions est l’utilisation du branchement conditionnel si alors sinon.
La syntaxe est
si <expression booléenne> alors
<instruction 1>
sinon
<instruction 2>
L’exécution d’une telle instruction consiste à évaluer l’expression <expression booléenne> (qui doit nécessairement être de type booléen!) c’est à dire lui associer ou le booléen vrai ou faux puis ensuite, si l’évaluation fournit vrai exécuter <instruction 1>, et sinon exécuter <instruction 2>.
Exemple 2 La fonction maximum de la figure 2.3 associe comme valeur à la fonction maximum(a,b : entier) : entier
variable maxi la valeur de la variable a si l’expression a>b est vraie ou sinon la valeur de la variable b. Clairement, maxi prend pour valeur le maximum des valeurs de a et b. La fonction maximum permet bien de calculer le maximum des deux paramètres passés en entrée.
III-C-9 – 2.3.9 Autres branchements conditionnels
Notons l’existence d’autres branchements conditionnels. Par exemple, si alors dont la syntaxe
si <expression booléenne> alors
<instruction>
est équivalent à
si <expression booléenne> alors
<instruction 1>
sinon
ne rien faire
III-C-10 – 2.3.10 Boucle
Une troisième possibilité pour structurer un ensemble d’instructions est l’utilisation de la boucle tantque.
La syntaxe est
tantque <expression booléenne> faire
<instruction>
Une définition formelle de cette boucle peut être faite en utilisant le branchement conditionnel si alors l’instruction
tantque <expression booléenne> faire
<instruction>
est équivalente au sous-programme (infini!) suivant
si <expression booléenne> alors
début
<instruction>
si <expression booléenne> alors
début
<instruction>
si <expression booléenne> alors
début
<instruction>
si <expression booléenne> alors
début
<instruction>
ETC
- in f in f in f in
Cette définition peut créer une certaine gêne un sous-programme infini peut être difficile à concevoir. Aussi, nous illustrerons la définition du tantque à l’aide de l’exemple suivant
Exemple 3 L’exécution de
i +- 31.
tantque (i>28)
i+-i-2
<instruction suivante>
consiste à associer à i la valeur 31 puis à évaluer l’expression i>28 qui fournit le booléen vrai (car 31 > 28) et donc à exécuter i<-i-2; la valeur de j est alors 29;
évaluer l’expression i>28 qui fournit le booléen vrai (car 29 > 28 est vrai) et donc à exécuter i<-i-2; la valeur de i est alors 27;
évaluer l’expression i>28 qui fournit le booléen vrai (car 27 > 28 est faux) ; l’instruction tantque est alors finie d’être exécutée; on exécute alors <instruction suivante>
La structure de contrôle tantque est très puissante. Elle permet de mettre en séquence un nombre aussi grand qu’on le souhaite d’une même instruction, voire même d’un nombre infini, comme le montre l’exemple suivant
Exemple 4 L’exécution de
i +- 31.
tantque (i<>28) <> signifie #
i+-i-2
<instruction suivante>
consiste à associer à i la valeur 31 puis à
évaluer l’expression i<>28 qui fournit le booléen vrai (car 31 28 est vrai) et donc à exécuter i<-i-2; la valeur de i est alors 29;
évaluer l’expression i<>28 qui fournit le booléen vrai (car 29 28 est vrai) et donc à exécuter i<-i-2; la valeur de i est alors 27;
évaluer l’expression i<>28 qui fournit le booléen vrai (car 27 28 est vrai) et donc à exécuter i<-i-2; la valeur de i est alors 25;
et ainsi de suite
La boucle ne finira jamais d’être exécutée. Nous entrons dans ce que nous appelons une « boucle infinie ». Le programme dans lequel serait exécutée une telle instruction ne retourne aucune valeur car ne termine pas.
Les programmes que vous devrez écrire devront terminer. La question cruciale de la terminaison sera abordée dans le chapitre suivant.
III-C-11 – 2.3.11 Autres boucles
D’autres boucles existent. Citons en trois (cette liste n’est pas exhaustive et sera enrichie en cours ou en TD)
1. la boucle de syntaxe
faire <expr. entière> fois
<instruction>
Elle est équivalente à
indice +- <expr. entière>
tantque indice > O faire
début
<instruction>
indice +- indice – 1.
-
- in
- la boucle de syntaxe
pour <variable entière> de <expr. entièrel> à <expr. entière2> <instruction>
Elle est équivalente à
<variable entière> +- <expr. entièrel>
tantque (<variable entière> < <expr. entière2>) faire début <instruction>
indice +- indice + j
-
- in
- la boucle de syntaxe faire
<instruction>
jusqu’à.
<expression booléenne>
Elle est équivalente à
début
<instruction>
tantque non(<expression booléenne>) faire
<instruction>
f in
Par leur définition même. ces trois boucles n’augmentent pas la pouvoir expressif du langage algorithmique les boucles tanque suffisent. Quel est donc leur intérêt? Elles permettent d’écrire des algorithmes de compréhension plus simple. Propriété que nous attendons de tous les algorithmes que vous écrirez.
III-C-12 – 2.3.12 Instruction retourner
L’exécution de toute fonction doit se terminer par l’exécution de la fonction retourner ayant pour argument un de type égal au type retourné par la fonction. Lors de l’exécution de l’instruction retourner <expression>, l’expression est évaluée, cette valeur est alors retournée, l’exécution de la fonction est finie.
Ainsi, la fonction
fonction add(n : entier) :entier
retourner n+1.
permet de calculer l’entier qui succède à l’entier.
Certaines syntaxes imposent que toute fonction ne possède qu’une instruction retourner et que celle ci soit à la fin. Pour des raisons de simplicité non de syntaxe mais d’écriture, nous accepterons le contraire, si cela se justifie comme dans l’exemple suivant
Exemple 5 Considérons le problème qui consiste à décider si un entier n est présent dans un tableau d’entiers
problème Recherche
Entrée : un entier a, un tableau d’entier T
Sortie : vrai si il existe 1< i < longueur(T) tel que a=T[i] faux sinon
Une première solution peut être
fonction recherchel(a : entier ; T : tableau d’entiers) : booléen début
res +- faux()
pour i de 1. à longueur(T)
si (a = T[i]) alors
res +- vrai()
retourner res
f in
L’algorithme recherche2 de la Figure 2.4 fournit une seconde solution; elle permet de quitter la boucle dès que l’on a trouvé le bon indice et utilise pour cela une boucle tantque.
Les deux solutions ont chacune un avantage la première est de définition plus simple alors que la seconde est (un peu) plus rapide mais de définition plus complexe. Une solution aussi simple que la première et aussi rapide que la seconde est fourni par l’algorithme recherche3 (Figure 2.5); il utilise retourner à l’intérieur de la boucle tantque
Exercice 1 Ecrire un algorithme solution de Recherche obtenu à partir de recherche2 en remplaçant la boucle tantque par une boucle JusquA. Vous pourrez dans un premier temps réécrire l’algorithme de façon automatique en utilisant la règle de réécriture définissant la boucle JusquA à partir de la boucle tanque. Dans un second temps, vous modifierez l’algorithme ainsi obtenu en le rendant plus simple et plus compréhensible.
III-C-13 – 2.3.13 Appel de fonctions
Nous pouvons bien entendu utiliser une fonction déjà définie pour en définir une seconde. Dans l’exemple de la Figure 2.6, la fonction tata utilise pour sa définition la fonction toto.
Dans l’exemple de la fonction toto, en supposant que le paramètre a prenne pour valeur l’argument 10, l’état des variables aux instants ti, t2 et t3 sera instant tlO variables existantes : a
valeur de a : 10
instant t20 variables existantes : a , b
| valeur de a | : 10 | ||
| valeur de b | : 13 | ||
| instant t30 | variables existantes : a , b , c | ||
| valeur | de a | : | 10 |
| valeur | de b | : | 13 |
Exemple 6 fonction toto(a:entier) :entier
valeur de c : 16
Remarquons dès à présent que la modification de la variable a à l’intérieur de la fonction toto (instruction a <- a + 3 😉 n’a pas entrainé de modification de valeur de la variable a du programme tata: à l’instant t20, la variable a conservé la valeur 10 qu’elle avait à l’instant tlO.
Récursivité
Observons que tout ce qui n’est pas interdit étant autorisé, la définition d’une fonction peut contenir des appels à elle-même. L’exemple trop célèbre du problème Factoriel admet ainsi pour solution
fonction factoriel(a:entier) :entier
début
si a = 1 alors
retourner
sinon
retourner a factoriel (n-1)
end
La compréhension de cet algorithme présente deux difficultés:
1. sa correction.
Cette difficulté en fait n’en est pas une. Sa correction est la conséquence immédiate de la définition mathématique même de a! : a! peut être défini comme étant l’entier égal à 1 si a = 1 et égal à a (a – 1)! sinon.
2. sa complexité(en temps et en espace).
Ce point plus délicat exige de connaître précisément le modèle de calcul, c’est à dire la façon dont sont gérés les différents appels récursifs, au sein de ce que appelons la pile d’appel.
Ces différentes notions seront traités dans de prochains chapitres ainsi que dans d’autres cours dispensés à l’Enseirb.
Lire la conclusion de ce chapitre à ce suj et.
III-C-14 – 2.3.14 Indentation
Afin de gagner en lisibilité, on doit utiliser les sauts de ligne et les espaces blancs de façon à ce que l’écriture de votre programme mette en valeur sa structure intrinsèque. Ainsi, l’algorithme recherche2 écrit correctement plus haut ne peut pas s’écrire ainsi
fonction recherche2(n : entier ; T : tableau d’entiers) : booléen début res +- f aux() ; i +- 1.
tant que (res=faux ET i < longueur(T)) début si (n = T[i])
alors res +- vrai() ; i +- i + j
fin retourner res ; fin
Cette écriture est formellement correcte mais est illisible un compilateur la comprendrait mais pas un humain.
On autorise souvent d’utiliser cette indentation pour masquer les parenthèses (début, fin) en effet, il y a redondance entre un texte bien indenté et ces parenthèses. Ainsi, l’algorithme recherche2 peut s’écrire de la façon décrite par la Figure 2.7.
Utilisez cette tolérance avec précaution. En effet, une erreur d’indentation et votre programme est radicalement différent. Ainsi, le programme recherche4 (Figure 2.8) est totalement différent, faux et d’ailleurs ne termine pas.
Exercice 2 Trouver une instance pour lequel recherche4 ne termine pas. Écrire avec des parenthèses début , fin ce même algorithme recherche4.
III-D – 2.4 Conclusion
Nous avons présenté dans ce chapitre de façon une syntaxe des programmes à écrire. Cette syntaxe est simple.
Vous êtes en mesure de « comprendre » (au sens syntaxique) n’importe quel programme. Malheureusement, contrairement à une langue étrangère où la compréhension d’une syntaxe et d’un dictionnaire caractérise une bonne maîtrise de la langue, cette connaissance là n’est qu’un préambule à votre initiation aux algorithmes.
Nous verrons dans les prochains chapitres quelques méthodes très générales pouvant permettre de trouver la solution algorithmique à un problème donné (Chapitres 3, 5, 6 et 7). Nous verrons aussi comment écrire des algorithmes en respectant les propriétés essentielles d’un bon algorithme
sa lisibilité
Obtenu notamment par de simples règles d’indentation, par des choix de noms de variables et de sous-fonctions, par une bonne décomposition du problème en sous-problèmes auxiliaires.
sa correction
La notion de correction sera définie dans le Chapitre 3. Nous veillerons naturellement à ce que l’ensemble des algorithmes présentés et étudiés soient corrects. Cependant les outils permettant de prouver formellement la correction d’un algorithme seront présentés dans les cours Analyse d’Algorithmes et Structures Arborescentes.
Naturellement ces outils seront partiellement en TD.
sa faible complexité en temps et/ou en espace
Les Chapitres 4,5,6 et 7 aborderont ces notions.
IV – Chapitre 3 Problèmes
Résoudre un problème consiste à écrire un algorithme. Nous dirons qu’un algorithme A résout un problème P si pour toute instance (entrée) x de P, la sortie y retournée par l’algorithme A, lorsque celui-ci termine, est une des sorties spécifiées par le problème P.
L’algorithme présente nécessairement différentes étapes de calcul. Ces étapes peuvent se situer à des niveaux différents. Il est alors important de savoir hiérarchiser ces niveaux.
Ainsi, par exemple, si au cours d’un algorithme il faut calculer le maximum de deux entiers a et b et affecter le résultat à une variable c, il est incongru d’écrire le code
si a < b
- -b sinon c – a
Il faut écrire c <- maximum(a,b), quitte à redéfinir la fonction maximum. On gagne en lisibilité, on évite d’éventuels erreurs, mais surtout on n’encombre pas la définition de l’algorithme général de calculs subalternes.
Ainsi, pour résoudre un problème, on écrit pas une seule fonction, mais de fait une fonction générale qui fait elle-même appel à d’autres fonctions auxiliaires, solutions elles-mêmes d’autres problèmes auxiliaires.
IV-A – 3.1 Un premier exemple
Si l’on souhaite résoudre le problème suivant
problème ÉlémentMax
Entrée : un tableau T d’entiers non vide
Sortie : l’entier maximum des entiers de T
À l’algorithme
fonction élémentMaxl(T:tableau d’entiers) :entier
res +- T[1]
pour i de 2 à longueur(T)
si T[i] > res
res +- T[i]
retourner res
nous préférerons l’algorithme suivant
fonction élémentMax2(T:tableau d’entiers) :entier
res +- T[1]
pour i de 2 à longueur(T)
res +- maximum(res,T[i])
retourner res
Il nous faudra alors préciser le problème résolu par maximum à savoir
problème Maximum
Entrée : deux entiers a et b
Sortie : le maximum de a et b
et éventuellement rappeler la définition d’un algorithme résolvant ce problème. Cette définition a déjà été faite et est donc désormais inutile.
IV-B – 3.2 Un second exemple
Considérons le problème suivant
| problème | FacteurProprePremier | ||
| Entrée | : | un | entier a> 1 |
| Sortie | : | un | facteur propre premier de a si il en existe, O sinon. |
Une première solution consisterait à écrire
fonction facteurProprePremierO(a: entier) : entier
pour i de 1. à a-1. faire
si estDiviseur(i,a) alors
retourner i
retourner O
Cette solution bien que concise est une mauvaise solution. Elle ne met pas en valeur les différents sous-problèmes associés à celui-ci et présente un algorithme très mauvais car très lent nous verrons dans le chapitre que cet algorithme est en fait exponentiel.
Cette solution n’étant pas décomposée à l’aide de fonctions auxiliaires, vous ne savez pas réécrire cet algorithme si ce n’est en le réécrivant totalement :dit autrement, cet algorithme est à prendre ou à jeter entièrement. Nous ne le conserverons donc pas.
Avant de résoudre un problème, il faut comprendre celui-ci.
IV-C – 3.3 Comparaison de problèmes
Dans cette section, nous montrons comment extraire d’un problème des sous- problèmes plus simples.
Ce qui permet d’une part de progresser d’un problème plus simple vers des problèmes plus difficiles et d’autre part de décomposer un problème en un ensemble équivalent de sous-problèmes. Il s’agit d’appliquer humblement les principes second et troisième du Discours de la Méthode (voir Chapitre 1).
Si vous rencontrez des difficultés à résoudre un problème, extrayez-en un plus simple et essayez de le résoudre. Nous dirons qu’un problèmeP est aussi simple d’un point de vue logique qu’un problèmeQ, si tout algorithme solution de Q est une solution de P. Si il est différent, il sera dit plus simple. Si l’on vous demande de résoudre algorithmiquement un problème Q, pensez en en extraire un problème plus simple P.
En effet, la résolution de P est un passage obligé pour la résolution de Q toute solution de Q étant une solution de P, si vous ne savez pas résoudre P, vous ne savez pas résoudre non plus P!
IV-C-1 – 3.3.1 Augmenter les contraintes en entrée
Une façon d’en extraire un plus simple est de limiter les instances. Ainsi, par exemple, le problème FacteurProprePremier induit comme nouveau problème si l’on se réduit aux entiers nombres non premiers
problème FacteurPremierRestreint
Entrée : un entier a> 1 qui n’est pas premier
Sortie : un facteur premier de a
IV-C-2 – 3.3.2 Diminuer les contraintes en sortie
Une seconde façon de simplifier un problème est au lieu de restreindre les entrées, de relâcher les sorties c’est à dire de réduire les contraintes portant sur les sorties.
Ainsi, un problème plus simple car extrait de FacteurPremierRestreint en remplant « facteur propre premier » par « facteur propre » est
problème FacteurPropre
Entrée : un entier a> 1 qui n’est pas premier
Sortie : un facteur propre de a
En outre, un problème plus simple que FacteurProprePremier est obtenu en remplaçant « un facteur propre premier de n » par un entier > 1. On obtient clairement le problème suivant
problème EstComposite
Entrée : un entier a> 1
Sortie : un entier > O si il existe un facteur propre premier de a O sinon.
Ce dernier problème est appelé EstComposite car il est très proche du problème qui décide si un entier est composite
problème EstComposite
Entrée : un entier a> 1
Sortie : vrai si il existe un facteur propre premier de a faux sinon.
Rappelons qu’un entier estpremier si il admet exactement deux diviseurs 1 et lui-même et est composite sinon.
Il est facile d’observer sur cet exemple, que toute solution algorithmique facteurProprePremier de FacteurProprePremier est une solution de chacun des problèmes
- FacteurPremierRestreint
- FacteurPropre
- EstComposite
IV-C-3 – 3.3.3 Décomposition en un ensemble équivalent de sous- problèmes
Dans la section précédente, nous avions montré que les problèmes FacteurPremierRestreint et EstComposite sont plus simples que FacteurProprePremier.
L’algorithme suivant prouve que FacteurProprePremier se décompose exactement en deux premiers problèmes.
fonction facteurProprePremier(a: entier) : entier
si estComposite (a)
retourner facteurPremierRestreint (a)
sinon
retourner O
Observons que si l’on sait résoudre FacteurPropre, on sait résoudre FacteurPremierRestreint à la condition que l’on sache résoudre le problème EstComposite.
fonction facteurPremierRestreint(a:entier) :entier
faire
a +- f acteurPropre(a)
jusqu’à
non(estComposite(a)
retourner a
Conclusion méthodologique
Cet exemple illustre qu’un problème initial FacteurProprePremier peut se décomposer en deux problèmes FacteurPropre et EstComposite. Pour résoudre le premier il est nécessaire et même suffisant de résoudre les deux autres.
En introduction, nous avions indiqué que la solution facteurProprePremierO était une mauvaise solution car très lente il peut utiliser jusqu’à instructions élémentaires.
Est-ce que l’algorithme facteurProprePremier est meilleur? Tout dépend bien entendu des fonctions auxiliaires estComposite et f acteurPropre. De premières solutions immédiates seraient
fonction estComposite(a:entier) :booléen
pour i de 2 à a-1. faire
si estDiviseur(i,a)
retourner faux
retourner vrai
fonction facteurPropre(a:entier) :entier
pour i de 2 à a-1. faire
si estDiviseur(i,a)
retourner i
Ces solutions nécessitent chacune opérations; si elles étaient retenues, entraineraient un nombre d’opérations pour f acteurProprePremier égal à 2
Si l’on interroge la communauté scientifique, nous obtenons deux réponses 1. la première réponse est une bonne nouvelle le problème EstComposite peut être résolu à l’aide d’un algorithme estComposite nécessitant (log(a))’2 opérations élémentaires.
Cet algorithme, découvert récemment, est trop compliqué pour être présenté dans ce cours.
- la deuxième réponse est une mauvaise nouvelle on ne sait pas résoudre facteurPropre avec des algorithmes réellement plus efficaces que facteurPropre.
Sur un exemple, nous avons décomposé un problème FacteurProprePremier en deux problèmes EstComposite et FacteurPropre, nous avons montré que la résolution du premier problème était équivalent à la résolution des deux autres problèmes.
Ayant appris que le deuxième problème pouvait être résolu « rapidement », nous en avons déduit que la difficulté du premier résidait dans la difficulté du troisième.
Cette approche de décomposition doit être privilégiée systématiquement. Elle met en valeur des liens existant avec d’autres problèmes, éventuellement déjà étudiés ou déjà résolus. En outre, elle permet de répartir le travail auprès de différentes équipes.
Chacune ayant pour objectif de résoudre l’un des sous problèmes. dans le temps.
Si à l’avenir, une meilleure solution apparaissait en ce qui concerne FacteurPropre, elle pourrait être introduite immédiatement dans votre algorithme.
V – Chapitre 4 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.
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.
V-A – 4.1 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
- –
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.
V-B – 4.2 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 X
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.
V-C – 4.3 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.
V-C-1 – 4.3.1 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.
V-C-2 – 4.3.2 Complexité d’un entier
Trois hypothèses apparaissent
- 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.
- 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.
- 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.
V-C-3 – 4.3.3 Complexité d’une matrice d’entiers
Quand nous considérerons une matrice d’entiersn 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.
V-D – 4.4 Complexité d’un algorithme
Un algorithme est un objet qui à partir de toute entrée permet d’exécuter des instructions en consommant deux ressources
- du temps. Le temps sera évalué en considérant le nombre d’instructions élémentaires devant être exécutées une instruction est élémentaire si elle peut être exécutée en un temps fixe.
- de l’espace. L’espace est le noinbie d’octets utilisé pal l’exécution de l’algorithme. Il ne tient pas compte de l’espace utilisé par les objets fournis en entrée.
V-D-1 – 4.4.1 Instruction élémentaire
Le caractère élémentaire d’une instruction dépend des hypothèses initiales.
Ainsi, si l’on décide de manipuler des entiers à taille fixe (sur 4 octets par exemple), l’addition d’entiers (ainsi d’ailleurs que toutes les opérations) doit être considérée comme élémentaire.
- l’opposé si l’on considère des entiers pouvant être de grande taille (plusieurs centaines d’octets et davantage), l’addition ne peut pas être considérée comme élémentaire car elle nécessite autant de manipulation de bits qu’il y en a de présent.
V-D-2 – 4.4.2 Espace utilisée par l’algorithme
Dans les algorithmes itératifs, l’espace utilisé peut se résumer à celui nécessaire pour représenter les nouvelles variables utilisées.
fonction factlter(a:entier) :entier
res f- 1.
tantque (a>1) faire
res +- res a
a f- a – 1.
retourner res
Ainsi la complexité en espace de cet algorithme est constant. La complexité en temps est (un multiple de) n
Dans les algorithmes récursifs, il faut considérer en outre l’espace requis pour gérer l’ensemble des appels récursifs. Cette gestion est organisée au travers de ce que l’on appelle unepile d’appel dont la taille est égal au nombre d’appels récursifs. Ainsi, par exemple l’algorithme
fonction factRec(a:entier) :entier
si a = O
retourner 1.
sinon
retourner a factRec(a-1)
nécessite une pile d’appel de hauteurn. En supposant que la multiplication soit élémentaire (en temps constant), la complexité en espace est un multiple de n ainsi que celle en temps.
V-D-3 – 4.4.3 Complexité en temps dans le pire des cas
La complexité en temps dans le pire des cas d’un algorithme est la fonction qui à tout entier n associe le nombre d’instructions élémentaires maximal exécutées par A sur des entrées de complexité n. Ainsi, l’algorithme fonction decalage(a:entier) :entier
si a = O alors retourner O
tant que estPair(a) faire
a-
retourner a
qui consiste à supprimer les bits nuls de poids faible a une complexité en temps (si l’on suppose l’évaluation de élémentaire, ce qui est toujours le cas)
- constante pour tout entier impair.
- égale à log(a) pour toute puissance de 2.
Ainsi, sa complexité en temps dans le pire des cas est log(a).
Quand nous évoquerons la complexité d’un algorithme, nous considèrerons la complexité dans le pire des cas. Cependant il en existe d’autres la complexité en moyenne et celle dans la meilleur des cas.
V-D-4 – 4.4.4 Complexité en temps en moyenne
La définition diffère de celle dans le pire des cas en considérant non le nombre maximal d’instructions élémentaires mais la moyenne du nombre d’instructions élémentaires sur l’ensemble des entrées de taillen.
Calculer en moyenne est un exercice souvent plus délicat que dans le pire des cas. Dans le cas de l’algorithme decalage, cette complexité en moyenne est constante. En mesurant le nombre d’exécutions de a<-a/2, on observe sur les entiers de taille 3 (représenté ci-dessous en binaire)
001 : nbre d’instruction O
010 : nbre d’instruction 1
011 : nbre d’instruction O
100 : nbre d’instruction 2
101 : nbre d’instruction O
110 : nbre d’instruction 1
111 : nbre d’instruction O
Ainsi, le nombre moyens d’exécutions de est sur des entiers de taille 3 égal à 4/7
Exercice 3 Prouver que la complexité en moyenne de decalage est constant.
V-D-5 – 4.4.5 Complexité en temps dans le meilleur des cas
La définition diffère de celle dans le pire des cas en considérant non le nombre maximal d’instructions élémentaires mais le nombre minimal d’instructions élémentaires sur l’ensemble des entrées de taillen.
Dans l’exemple de decalage, le meilleur des cas est naturellement atteint par les entiers impairs. Ainsi, la complexité en temps dans le meilleur des cas de decalage est constante.
V-D-6 – 4.4.6 Complexité en espace
Pour définir la complexité en espace, il suffit de remplacer le terme « nombre d’instructions élémentaires exécutées par A » par « nombre d’octets utilisées lors de l’exécution de A ». A l’image de la complexité en temps, il existe notamment trois complexités en espace
- dans le pire des cas.
- en moyenne
- dans le meilleur des cas.
V-E – 4.5 Complexité d’un problème
Une idée naturelle est d’évaluer la complexité en temps d’un problème ( de même pour l’espace). Puisque un problème admet plusieurs solutions algorithmiques, on peut les comparer sous le critère de leur complexité en temps et considérer la plus faible que nous définissons comme la complexité du problème.
V-E-1 – 4.5.1 Compromis espace-temps
Il n’existe pas parfois de meilleur algorithme.
Nous verrons plus loin, qu’un même problème ayant en entrée des entrées de taillen peut par exemple admettre une solution algorithmique de complexité en temps dans le pire des cas en n2 et une complexité en espace constante.
une solution algorithmique de complexité en temps dans le pire des cas en n et une complexité en espace n.
Ces deux solutions étant incomparables, l’une ne peut être considérée comme meilleure que l’autre.
V-F – 4.6 Notations et simplifications
Le calcul des complexités est « complexe ». Pour les mêmes raisons qu’en ce qui concerne la terminaison, il n’existe pas de méthode générale (ou algorithme) pour calculer la complexité d’un algorithme et encore moins celle d’un problème.
Nous montrerons comment évaluer la fonction complexité d’un algorithme en évaluant non pas précisément cette fonction mais la classe à laquelle elle appartient.
V-F-1 – 4.6.1 À une constante multiplicative près: notation e
Les fonctions complexité que nous considérons dès à présent sont supposées à valeurs entières strictement positives.
Supposons que nous utilisions des entiers manipulés au travers d’additions et de multiplications considérées comme instructions élémentaires.
Supposons que nous ayons deux algorithmes. Le premier sur une entrée de taille n provoque 10 n additions et n multiplications. Le second n additions et 2on multiplications. Le premier a pour complexité en temps n F-* 11on. Le second n -* 3 n.
Lequel est optimal? En fait tout dépend des complexités réelles de l’addition et de la multiplication, c’est à dire du nombre de cycles d’horloges nécessité par le processeur pour additionner et multiplier deux entiers. Deux stratégies s’offrent à nous:
- ou on comptabilise pour chacune des opérations le nombre d’exécutions. On obtient alors tant de comparaisons, tant d’affectations, tant d’additions, tant de multiplications. Cette précision est parfois nécessaire dans l’étude d’algorithmes embarquées ou à temps réel mais est coûteuse.
- ou on considère toutes ces opérations élémentaires comme équivalentes. C’est le choix que nous ferons. En conséquence de quoi, il est absurde de préférernF-*3onànF-* 11on.
En conséquence de quoi, deux fonctions f et g égales à une constante multiplicative près devront être considérées comme équivalentes.
La conséquence de ceci, deux fonctions f et g pour lesquelles il existe des réels 0< et 0< i3 tels que: Vn.f(n) <g(n) <.f(n)
et dont tels que g(n) < f(n) < g(n) devront être considérées comme équivalentes. Conséquence de ce choix, deux simplifications interviennent
À une constante additive près
Soit f : N* -* N* une fonction et k un entier.
La fonction k + f vérifie 1/k+1. k + f < f < k + f. Donc ces deux fonctions seront considérées comme équivalentes.
Comportement asymptotique
Soit f : -* N* une fonction et N un entier. Soit g la fonction qui à tout entier n E [1, N] associe 1 et à tout autre entier associe f(n). Soit M := max[l,N] f(i). Il est facile d’observer que
Vng(n) <f(n) <M g(n)
En d’autres termes, deux fonctions étant égales asymptotiquement doivent être considérées comme équivalentes.
Notation e
Soit f N* -* N* une fonction. Nous noterons C(f) l’ensemble des fonctions g N* -* N* telles qu’il existe un entierN, deux réels et 3 tels que pour tout entier n > N on ait
.f(n) <g(n) <.f(n)
Du fait que f E e(g) induit une relation d’équivalence (Exercice 5). Pour cette raison, la notation f E C(g) est remplacée par la notation f =
Exercice 4 Démontrer pour toutes fonctions f, g N* -* N* et tout réel > O
- e(.f)=e(f)
- C(f+g) = C(max(f,g))
Exercice 5 Démontrer que la relation g E C(f) induit une relation d’équivalence (réflexive, symétrique, transitive), c’est à dire que pour toute fonction f, g et h on a:
- fEe(f).
- f E C(g) entraine g E e(f).
- f E e(g) et g E (h) entraine f E e(h).
V-F-2 – 4.6.2 Des fonctions étalons
Certaines fonctions N* -* N* servent d’étalons et fournissent une hiérarchie simple de cet ensemble indénombrable de classes. Pour des raisons de simplicité, les fonctions sont notées plus simplement ainsi la fonction n -* n2 est notée plus simplement n2. Quelques exemple des fonction
- la fonction 1 dite constante.
- la fonction logarithmique log(n).
- la fonction linéaire n.
- la fonction n logn.
- les fonctions polynomiales n, n2, …, nk avec k fixé.
- des fonctions superpolynomiales comme 2″.
- la fonction exponentielle 2.
- des fonction superexponentielles telles que fl, 22.
Les algorithmes que nous souhaitons faire exécuter sur machine doivent être de complexité en temps et en espace au pire polynomiale et ce selon une petite puissance (<= 4) un algorithme nécessitant 2 opérations élémentaires nécessite dans le cas où n = 10000 (par exemple une petite matrice carrée de taille 100.100) un temps qui se compte en milliard d’années!
Exercice 6 Considérant qu’une opération élémentaire se fasse en 10 seconde (un milliardième de seconde), rappelant qu’une année comporte à peu près 3.1O seconde. Calculer le temps nécessaire à l’exécution d’un algorithme sur une entrée de taille 100, 1000 ou 10000 de complexité
- n,
- n2,
- n6,
- n’00
- 2,
- 22h.
V-F-3 – 4.6.3 Simple majoration : notation O
Considérons la fonction
fonction toto(n : entier): entier
i – n
tantque i > O faire
si testlnconnu(i) alors
retourner i
i +- i-1
retourner i
Supposons que testlncorinu se fasse en temps constant. Que peut-on dire de la complexité en temps (dans le pire des cas) de cet algorithme? Tout dépend du test que réalise testlncorinu. La complexité en temps de toto est, par exemple,
- e(1) si testlnconnu teste la parité.
- e(log(n)) si testlnconnu teste la primalité la proportion de nombres premiers est
- e(n) si testlnconnu teste le fait d’être puissance de 2.
Dans des situations comparables du fait de notre incapacité à évaluer finement la complexité, nous nous contenterons de majorer la fonction complexité. Dans l’exemple de la fonction toto, nous dirons que sa complexité en temps (dans le pire des cas) appartient à la classe 0(n), c’est à dire que sa fonction complexité temps est majorée (à une constante multiplicative près) par la fonction n F-* n.
Ainsi, pour toute fonction f N* -* N* la classe 0(f) est l’ensemble des fonctions g telles qu’il existe un entier N et un réel > O tels que pour tout entier n > N on ait
g(n) <.f(n)
Pour des raisons de simplicité et de similarité avec la notation g = l’appartenance g E0(f) est noté g = 0(f).
A titre d’exercice, quelques petites propriétés
Exercice 7 Démontrer pour toutes fonctions f, g : N* -* N* et tout réel > O
- 0(.f)=0(f).
- 0(f + g) = 0(max(f, g)).
- (f) c 0(f).
Exercice 8 Démontrer pour toutes fonctions f, g: N* -* N*
- f=e(g)e(f)=e(g).
- f=0(g)0(f)C0(g).
- f=0(g)0(f)=0(g).
0 induit une relation d’ordre et non d’équivalence
Observons que si n E 0(n2) (noté n = 0(n2)) , nous avons n2 0(n) (noté n2 0(n)) . La relation induite par 0 n’est pas symétrique, elle est simplement d’ordre
Exercice 9 Démontrer que la relation g E 0(f) induit une relation d’ordre large (réflexive, transitive), c’est à dire que pour toute fonction f, g et h on a
- fE0(f).
- f E 0(g) et g E 0(h) entraine f E 0(h).
V-F-4 – 4.6.4 Quelques règles d’évaluation de complexité
Pour chacun des exercices suivants, et pour chacun des entiers j E [1, 4], nous notons #fi la complexité en temps dans le pire des cas de la fonction fi.
V-F-5 – 4.6.5 Mise en séquence
Exercice 10 Considérer l’algorithme suivant
fonction fl(i : entier ):entier
i +- f2(i)
j +- f3(i)
retourner j + j
Démontrer que
- #fl = O(#f2 + #f3).
- #fl = e(#f2 + #f3).
Exercice 11 Considérer l’algorithme suivant
fonction fl(i : entier ):entier
j +- f2(i)
retourner f 3(i)
Démontrer que
- #fl O(#f2 + #f3) et donc #fl e(#f2 + #f3). Vous considérez des entiers de taille (complexité non constante). Vous choisirez une fonction f2 qui augmente significativement la taille de i par exemple une fonction exponentielle.
- Exprimer selon une notation O la fonction #f 1 en fonction de #f 2, #f 3 et f2. La fonction f2 sera supposée croissante.
V-F-6 – 4.6.6 Branchement conditionnel
Exercice 12 Considérer l’algorithme suivant
fonction fl(n:entier) :entier
si f2(n) alors
retourner f 3(n)
sinon
retourner f 4(n)
Démontrer que
- #fl = O(#f2 + #f3 + #f4).
- #f 1 = e(#f2 + #f 3 + #f4) n’est pas toujours vrai. Fournir un exemple.
V-G – 4.7 Un peu de vocabulaire
Quand on précise la complexité d’un algorithme ou d’un problème, il faut définir en fonction de quelle quantité celle-ci est exprimée. Nous pouvons employer l’expression « tel algorithme est de complexité linéaire ». A défaut de toute précision, ceci signifie linéaire en fonction de la complexité (la taille) de l’entrée X.
V-G-1 – 4.7.1 Un algorithme linéaire
Considérons le problème de la comparaison de deux matrices carrées de même taille
fonction égal(A,B: matrice): booléen
1 +- nbColonnes(A)
pour i de 1. à 1 faire
pour j de 1. à 1 faire
si A[i,j] B[i,j] alors
retourner faux Q
retourner vraiQ;
Cet algorithme est de complexité en temps e(12) quadratique en fonction de 1 mais doit être considéré comme un simple algorithme linéaire (en la taille des entrées  et B égale à n = 12) qui compare bit à bit les représentations machines des objets. La fonction complexité est en fait e(n).
V-G-2 – 4.7.2 Un algorithme exponentiel
Considérons l’algorithme suivant.
fonction factlter(k:entier) :entier
res +- 1.
tantque (k>1) faire
res +- res k
k – k – 1.
retourner res
Supposons que le produit de deux entiers est de complexité constante. Cet algorithme est de complexité en temps
- linéaire en fonction de l’entréek mais doit être considéré comme exponentiel (en la taille de l’entrée k égale à n = log2(k)). La fonction complexité est en fait n -* 2.
Exercice 13 Qualifier chacune des complexité en temps et en espace de l’algorithme d’addition de deux matrices carrées. S’agit t- il de complexité constante? logarithmique? linéaire? quadratique? exponentielle? autre?
Même question pour le produit de deux matrices carrées?
Exercice 14 Considérons l’un des premiers algorithmes que vous exécutiez dans votre jeune âge (l’entier est fourni par l’enseignant la machine c’est vous!) procédure punition(k: entier) pour i de 1. à k faire écrire ( »J’apprendrais mes lecons ») Même question que l’exercice précédent.
V-H – 4.8 Étude du problème de puissance
Considérons le problème de puissance d’un élément x selon une puissance k. Nous supposerons ici que toute multiplication est une instruction élémentaire (complexité en temps et en espace constante).
problème Puissance
Entrée : un élément x, un entier k
Sortie :
Un premier algorithme est
fonction puissancel(x:élément ; k : entier) : élément
res +- 1.
faire k fois
res +- res x
retourner res
Les complexités dans le pire des cas sont
- (k) en temps.
- e(1) en espace.
Un second algorithme est
fonction puissance2(x:élément ; k : entier) : élément
si (k=O) alors
retourner 1.
sinon
retourner x.puissance2(x,k-1)
Les complexités dans le pire des cas sont
- (k) en temps.
- (k) en espace dû à la pile d’appel.
Un troisième algorithme récursif utilisant la propriété x2k = (x2)k est
fonction puissance3(x:élément ; k : entier) : élément
si (k=O) alors
retourner 1.
sinon si estPair(k)
retourner puissance2(xox,k/2)
sinon
retourner xopuissance2(xox, (k-1)/2)
Clairement à chaque appel récursif, l’argument k est divisé par 2, un entier k entraine log(k) appels récursifs successifs. Les complexités dans le pire des cas sont
- (l(k)) en temps.
- e(log(k)) en espace dû à la pile d’appel.
Cet algorithme induit la version itérative suivante
fonction puissance4(x:élément ; k : entier) : élément
1 +- nombreBits(k)
res +- 1.
pour i de 1. à 1 faire
res +- res res
si ièmeBit(k,i)=1. alors
res +- x res
retourner res
Dans cet algorithme. nombreBits (k) retourne le nombre de bits de la représentation binaire de l’entier k ( c’est à dire log(n + 1)1).
Par exemple nombreBits(6) vaut 3 car la représentation binaire de 6 est 110.
ièmeBits(k,i) retourne le ième bit à partir du bit de poids fort. Ainsi, ièmeBits(6,1), ièmeBits(6,2) et ièmeBits(6,3) valent respectivement 1, 1 et O.
Les complexités dans le pire des cas sont
- e(log(k)) en temps.
- e(1) en espace.
Exemple 8 Si l’on souhaite calculer puissance4(1O,6) les instructions successivement exécutées sont
res+-1 ; res=1
res +- res res ; res = 1.
res +- x res ; res = 10
res +- res res ; res 100
res +- x res ; res 1000
res +- res res ; res = 1000000
Nous voyons sur cet exemple comment à partir de deux définitions différentes d’un même objet produire deux algorithmes (algorithmes puissancel et puissance2). Ces deux algorithmes ont pour avantage leur simplicité mais non leur complexité. Ensuite, nous voyons comment à traduire une propriété arithmétique en un algorithme récursif (puissance3) dont la correction est immédiate car liée étroitement à cette même propriété. L’algorithme produit est optimal en temps mais non en espace. En observant comment il organise les calculs, nous pouvons le « derécursiver » et obtenir un algorithme itératif optimal en temps et en espace (algorithme puissance4).
V-H-1 – 4.8.1 Importance des hypothèses
Nous avons démontré dans la section précédente, que le nombre d’exécutions de l’opération multiplication est égal à
- pour puissancel, e(k).
- pour puis sance2, e(k).
- pour puissance3, e(log(k)).
- pour puissance4, e(log(k)).
Hypothèse 1
Dans cette même section, l’étude de la complexité repose sur le fait que
- les éléments sont représentés sur un nombre constant d’octets.
- (et donc) que l’opération de multiplication a une complexité en temps constante.
Cette hypothèse est conforme au cas par exemple de réels représentés sur un nombre d’octets fixes (hypothèses réalistes). Les complexités en temps sont alors
- pour puissancel, e(k).
- pour puis sance2, e(k).
- pour puissance3, e(log(k)).
- pour puissance4, e(log(k)).
La représentation d’un réel x dans le langage C (type float norme IEEE 754) est normalisé sous la forme d’un triplet (cv, 3, ‘y) représenté sur 4 octets vérifiant l’équation
x = 3o 2
où:
- est le signe -1 ou 1 codé sur un bit.
- 3 est la mantisse, une fraction réelle de l’intervalle [1, 2[ codée sur 23 bits.
- ‘y est l’exposant, un entier codé sur 8 bits appartenant à [-126, 127]
Cependant si vous modifiez les hypothèses, si vous supposez que la complexité de la multiplication n’est pas constante mais est par exemple proportionnelle à la taille de l’élément multiplié y (eQtaiiie(y))) vos conclusions différeront.
Hypothèse 2
Ici, nous supposons que
- la complexité en temps de l’addition dépend de la complexité des éléments.
- le produit de deux éléments de même taille conserve cette même taille Cette hypothèse est notamment vérifiée dans le cas du produit de deux matrices carrées (à éléments de taille constante).
Les complexités en temps sont alors
- pour puissancel, e(-taine(x) k).
- pour puissance2, e(taiiie(x) k).
- pour puissance3, e(-taiiie(x) log(k)).
- pour puissance4, e(taille(x) log(k)).
Sous cette nouvelle hypothèse les deux derniers algorithmes sont encore bien meilleurs que les deux premiers.
Hypothèse 3
Ici, nous supposons que
- la complexité en temps de l’addition dépend de la complexité des éléments.
- le produit de deux éléments a pour taille la somme des deux tailles. Cette hypothèse est notamment vérifiée dans le cas du produit de deux entiers à taille variable.
Les complexités en temps sont alors
- pour puissancel, e(tai11e(xk)) = (k taille(x)).
- pour puissance2, e(tai11e(xk)) = (k taille(x)).
- pour puissance3, e(tai11e(xk)) = (k taille(x)).
- pour puissance4, e(tai11e(xk)) = (k taille(x)).
Sous cette dernière hypothèse, les algorithmes ont même complexité en temps!
Exercice 15 Évaluer la complexité en espace des différents algorithmes dans chacune des deux nouvelles hypothèses.
Exercice 16 Expliquer pourquoi dans le cadre de l’étude de la puissance supposer des entiers de taille fixe n’a pas beaucoup d’intérêt et ce contrairement aux réels (de taille fixe eux aussi).
Exercice 17 Qualifier la complexité de chacun des algorithmes dans chacune des hypothèses est-elle constante, linéaire, polynomiale, exponentielle?
VI – Chapitre 5 Algorithmes « Diviser Pour régner »
L’approche « Diviser Pour Régner » (Divide and Conquer) est une méthode qui permet de résoudre un problème en fournissant un algorithme récursif. Cette méthode n’offre naturellement aucune garantie il n’existe pas de méthode (ou algorithme) permettant à partir d’un problème d’obtenir à coup sûr une solution algorithmique.
La structure générale d’un algorithme « Diviser Pour Régner » Â et permettant d’associer à une entrée x une solution s comporte 3 parties
- la décomposition. Celle-ci consiste à décomposer l’entrée x en a nouvelles entrées xl,… ,x.
- a appels récursifs. Ceux-ci consistent à appliquer récursivement la fonction  sur chacune des nouvelles entrées x,. . . , et à retourner les a solutions 5i,
- la recomposition. Celle-ci consiste à recomposer à partir des solutions partielles s, . . , la solution s associée à X.
VI-A – 5.1 Un premier exemple : la multiplication de deux entiers
Supposons que nous manipulions des entiers de très grande taille (plusieurs centaines d’octets) et que nous souhaitions les multiplier. Nous sommes confrontés au problème suivant
Problème Produit
Entrée : a, b : entier
Sortie : aob
Ici, nous considérons comme opérations élémentaires, les seules opérations de lecture d’un bit, de modification d’un bit, d’accès au bit suivant, de suppression du bit de poids faible (division par 2 noté n »1) ou d’insertion d’un nouveau bit de poids faible (multiplication par 2 noté n »1).
VI-A-1 – 5.1.1 Un premier algorithme
Un premier algorithme est le suivant
fonction produit(a,b: entier): entier
res +- O
tantque b O faire
si estPair(b)
res +- addition(res,a)
a +- a » 1.
b – b » 1.
retourner res
Cet algorithme utilisant la fonction addition de complexité linéaire en la taille des entrées a et b, la complexité de produit est quadratique car étant exactement égal à e(taiiie(a) taiiie(b)) = e(n2) avec n taille(a) + taille(b) (on rappelle que la taille d’un entier a est le nombre de bits de se représentation binaire log (a)).
Cstret algorithme est quadratique. Peut-on faire mieux?
Clairement, pour multiplier deux entiers a et b, chaque bit compte la modification d’un seul bit modifie le résultat.
Aussi, doit-on lire chacun des bits de a et chacun des bits de b. En conséquence de quoi, tout algorithme résolvant
Produit est de complexité en temps au moins linéaire.
VI-A-2 – 5.1.2 Un second algorithme
Notons n la taille maximale de a et b. Quitte à incrémenter n, nous pouvons supposer que n est un entier pair. Décomposons a sous la forme a = 2 + a2 a2 est composé des bits de poids faibles de a; a1 est composé des bits de poids forts de a. Décomposons b sous la forme b = b1 2 + b2.
L’égalité évidente
a b = (a1 b1). 2 + (a1 b2 + a2 b1). 2 + a2 b2
entraîne l’égalité
a b = (ai + a2)(bi + b2). 2 + a1 b1o (2 – 2) + a2 b2 (1- 2)
Apparaît dans cette dernière égalité, un algorithme de multiplication d’entiers bine plus efficace que l’algorithme traditionnel. Que nous dit cette égalité, pour multiplier a par b il faut en fait
- décomposer l’entrée (a, b) en trois nouvelles entrées: (ai+a2, b1+b2), (ai, b1) et (a2,b2).
- appliquer récursivement le produit sur chacune de ces entrée. Notons 51, S2 et s3 les produits associés.
- recomposer le résultat final s à l’aide de ces solutions partielles s1, 2 et s3 de la façon suivante
s s1o 2 + 2o – 2 2 + s3- 53o 2
L’algorithme peut s’écrire
fonction produit2(a,b: entier) :entier
n +- taille(a,b)
si n= 1.
si (a=1. ET b=1)
retourner 1.
sinon
retourner O
p +- n » 1. ; p=
(a1,a2) +- décomposition(a,n)
(b1,b2) +- décomposition(b,n)
i +- produit(addition(a1,a2),addition(b1,b2))
s2 +- produit(a1,b1)
s3 +- produit(a2,b2)
res +- s »p ; signifie : res +- s2
res – addition(res, s2″n)
res +- soustraction(res, s2″p)
res +- addition(res, s3)
res +- soustraction(res, s3″p)
retourner res
VI-A-3 – 5.1.3 Évaluation de la complexité
Notons f N -* N* la fonction de complexité en temps. Pour simplifier l’exposé, la taille d’un couple est considéré le maximum des tailles des deux entiers. Observant que pour multiplier deux entiers a et b de taille chacun au max n, il est nécessaire de
- de décomposer ces entiers et produire les trois couples d’entiers. Chacune des opérations (décomposition, taille, addition, décalage, affectation) est de complexité 0(n). La complexité de la décomposition est e(n).
- de réaliser trois appels récursifs sur ces trois couples de taille chacun .
- de recomposer la solution finale à partir des trois solutions partielles. Cette recomposition nécessite 2 additions, 2 soustractions, 4 décalages droits chacune de ces opération est de complexité en temps 0(n). La complexité de la recomposition est e(n).
En clair, la fonction complexité f(n) est défini récursivement par f(1) = 1 et f(n) =n+3f()
Nous verrons comment résoudre un tel système d’équations. Nous pouvons ici le résoudre à la main.
La solution est f(n) = n + 3( + 3( +…)) = n(()° + (i)’ + n.(2(n)) qui est égal à no nmn()/mn(2). Observant que 1 + ln()/ ln(2) est égal à ln(3)/ln(2) = 1n2(3), nous avons f (n) = nmn2(3) n »58
Cet algorithme est donc meilleur que le premier algorithme de complexité e(n2). De nouvelles améliorations « Divide and conquer » sont possibles qui permettent pour tout réel E > O de fournir un algorithme solution de Produit de complexité en temps e(n+c).
D’autre part des techniques utilisant les transformées de Fourier permettent en temps linéaire e(n) de résoudre ce même problème. Ainsi, le produit est de même complexité qu’une addition ou qu’une comparaison.
VI-B – 5.2 Évaluation de la complexité
Évaluer la complexité d’un algorithme se fait en deux temps.
VI-B-1 – 5.2.1 Définition récursive de la fonction
Cette première peut être immédiate. Il est nécessaire de projeter la définition récursive de l’algorithme en une définition récursive de la fonction complexité en temps. Nous pouvons alors obtenir par exemple l’équation
f(n) = f(fl 3) + 6 f(2 1) + 3 n + + 879
Cette équation doit être débarassée des termes marginaux, des constantes multiplicatives n’apparaissant pas dans le terme récursif. Nous obtenons alors pour équation
g(n) = 7 g() + g
Exercice 18 Démontrer que les fonctions f et g vérifiant les deux systèmes d’équation précédent vérifient f = () et donc g = e(f).
VI-C – 5.3 Résolution de certaines fonctions N – N définies récursivement
Il n’existe pas de méthode générale pour résoudre une équation. Les équations que nous proposons de résoudre sont de la forme
g(n) – a g()
Si votre définition récursive n’est pas de cette forme, il faut tenter de s’y ramener par tous les moyens. Souvent, les moyens présentés dans la section précédente suffisent. Parfois, nous avons une inéquation de la forme : f(n) < a f()
- nk. Auquel cas, la conclusion que l’on peut en tirer estf(n) = O(g(n)) avec g solution de l’équation précédente. La solution de l’équation est égale à:
- g(n) = O(nb(a) ln(n)) si a = b’ c.a.d si k = lnb(a).
- g(n) = O(n(a)) si a > bk.
- g(n) = O(nk) si a < bk.
preuve
Soit g la fonction définie par: g(n) = a g() + nk. Pour tout entier n on a:
- g(n) =nk+a.(g()).
- g(n) = nk + a ((n)k + a
- g(n) = nk(1 t ()2 . .. t ()1nb(n)).
L’observation que toute somme de la forme 1 + r + … + r1 définie à partir d’un terme r constant est égale
- àl+l doncàe(l) sir=1.
- à (r’ – 1)/(r – 1) donc à 0(r1) si r> 1.
- à (r’ – 1)/(r – 1) donc à 0(1) si r < 1.
permet de conclure à
- si a = bk, g(n) = O(nl(a) ln(n)) puisque k = lnb(a)
- si a > b’, g(n) = e(nk ()1nb(n)). Observant que ()mflb(fl) est égal à lna(n) a/ (() b ) b ‘ c’est à dire à l(a), on obtient g(n) = O(nl(a)).
- si a < bk, g(n) = e(nk)
Exercice 19 Pour réaliser le produit de deux entiers, une autre équation vérifiée par a b est ab= (a1 .bi).2n +(ai.b2+a2.bi).2 +a2b2
Cette équation fournit un algorithme récursif.
- Écrire cet algorithme en utilisant les fonctions utilisées dans produit2.
- Écrire la définition récursive de la fonction complexité en temps
- Résoudre cette équation et calculer de fait cette fonction complexité.
- Calculer la fonction complexité en espace.
- Comparer ces différentes complexités avec celles des algorithmes solution de Produit.
- Conclure en comparant cet algorithme aux autres solutions.
VI-D – 5.4 Un deuxième exemple : la multiplication de deux matrices
Nous pouvons nous inspirer du produit de deux entiers, pour réaliser le produit de deux matrices carrées
problème ProduitMat
Entrée : deux matrices X Y carrées de même taille
Sortie : le produit matriciel de X et Y
Notons Z la matrice produite. Décomposant chacune des matrices carrées X, Y et Z de même taille supposée paire en des matrices A, A, B, C, D, E, F, G, H, I, J, K, L, de la façon suivante
ABI EF IJI
X=CD Y=GH Z=KL
VI-D-1 – 5.4.1 Première méthode
La première méthode découle des équations évidentes
I = AE + BG
J = AF + BH
K = CE + DG
L = CF + DH
Exercice 20 En vous inspirant de la section traitant du produit de deux entiers:
- Écrire un algorithme résolvant ProduitMat utilisant la méthode décrite plus haut.
- Vérifier que l’équation vérifiée par la fonction complexité en temps est f(n) = 8f() + n où n est taille de la matrice (9 pour une matrice 3 3).
- Vérifier que la solution de cette équation est O(n).
- Calculer la complexité en espace.
- Conclure en comparant cet algorithme avec d’autres solutions a ce même problème.
VI-D-2 – 5.4.2 Seconde méthode dite de Strassen
Reprenant les notations de la section précédentes, la seconde méthode découle des égalités suivantes
- Pi = A(G-H) P5 = (A+D)(E-H)
- P2 = (A+B)H P6 = (B-D) (F+H)
- P3 = (C+D)E P7 = (A-C) (E+G)
- P4 = D(F-E)
- I = P5 + P4 – P2 + P6
- J = Pi + P2
- K = P3 + p4
- L = P5 + Pi – P3 – P7
Exercice 21 1. Vérifier la correction des équations proposées.
- Vérifier la correction des équations proposées.
- En vous inspirant de la section traitant du produit de deux entiers, écrire un algorithme résolvant ProduitMat utilisant la méthode décrite plus haut.
- Vérifier que l’équation vérifiée par la fonction complexité en temps est f(n) = 7. f() + n où n est taille de la matrice (9 pour une matrice 3 3)
- que la solution de cette équation est 0(n » 7) 0(n’403).
- Calculer la complexité en espace.
- Conclure en comparant cet algorithme avec d’autres solutions a ce même problème.
VI-D-3 – 5.4.3 Conclusion
Une solution algorithmique améliore l’algorithme de Strassen (O(n »403) et fournit un algorithme de complexité 0(n1138) (Coppersmith & Winogend). Pour des raisons évidentes, le produit de deux matrices nécessite de lire chacun des éléments de la matrice et nécessite au moins 0(n) opérations. Peut-on à l’image du produit de deux entiers (ou de deux vecteurs) atteindre cette limite 0(n) ou sinon, s’en rapprocher davantage? La question est ouverte.
VII – Chapitre 6 Programmation Dynamique
Considérons l’algorithme suivant
fonction toto(s:séquence d’entiers) :entier
si longueuer(s) = 1 alors
retourner s1
sinon
retourner toto(extractl(s)) + toto(extract2(s))
où extractl et extract2 extraient deux sous-séquences de s.
Notons n la longueur de la séquence s. Supposons pour simplifier que la complexité de extractl et extract2 est 0(1). Dans le cas où extractl(s) et extract2(s) sont systématiquement de longueur < avec b > 1, nous nous trouvons face à un algorithme « Divide and Conquer » de complexité en temps polynomial car solution de g(n) = 1 + 2
- contrario, Supposons par exemple que extractl (s) (resp. extract2 (s) retire un unique élément de s par exemple le premier (resp. le dernier). La fonction complexité en temps vérifie l’équation
g(n) = 1 + 2 g(n – 1)
et est égale à 0(2″) L’algorithme est exponentiel et est impraticable (le traitement d’une séquence de 100 éléments nécessite un siècle et ce même si 1 milliard d’opérations élémentaires sont exécutées par seconde).
L’observation des calculs effectués par toto nous montre que l’appel sur la séquence (1,2,3,4,5,6) entrainel’exécution de toto sur les séquences (1,2,3,4,5) et (2,3,4,5,6). Ce qui provoquera récursivement 4 appels sur les séquences (1,2,3,4), (2,3,4,5), (2,3,4,5) et (3,4,5,6). Nous voyons ici que par deux fois toto est exécuté sur la séquence (2,3,4,5).
Si on détaille le nombre de fois où les appels sont exécutés sur chacune des sous séquences nous obtenons le dessin suivant
1,2,3,4,5,6) :1
(1,2,3,4,5):1 (2,3,4,5,6):1
(1,2,3,4): 1 (2,3,4,5):2 (3,4,5,6):1
(1,2,3):1 (2,3,4):3 (3,4,5):3 (4,5,6):1
(1,2):1 (2,3):4 (3,4):6 (4,5):4 (5,6):1
(1):1 (2):5 (3):1O (4):1O (5):5 (6):1
Il est facile d’observer que le nombre d’appels sur les séquences de longueur 1 est exponentiellement proportionnel à son opposé soit 26 : 2 appels sur les séquences de longueurs 1 ont été exécutés alors que 6 en tout auraient suffit.
L’idée de la programmation dynamique repose sur l’idée de réaliser un compromis espace-temps, c’est à dire d’éviter de répéter les mêmes calculs quitte, pour éviter ces répétitions, à utiliser une mémoire auxiliaire pour se rappeler des calculs effectués.
VII-A – 6.1 Une solution de programmation dynamique
Pour mémoriser les calculs, nous avons besoin de deux informations:
- la première déjàCalc indique pour toute séquence si le calcul de toto a déjà été effectué.
- la seconde valeurs indique pour toute séquence pour laquelle le calcul de toto a été effectué, la valeur de ce calcul.
Supposons que extractl (s) supprime le premier élément de la séquence s alors que extract2(s) supprime le dernier. Ici, toute sous-séquence extraite t d’une séquence initiale s peut être représenté par un couple d’entiers (i, i) formé du rang du premier élément de t relativement à s et du rang du dernier élément de t relativement à s.
L’algorithme devient alors
fonction totoDynamique(s:séquence): entier
n +- longueur(s)
déjàCalc +- matriceCarrée(n,fauxO)
valeurs +- matriceCarrée(n,O)
(déjàCalc,valeurs) +- totoDynamRec(déjàCalc,valeurs,1,l)
retourner valeurs[1][n]
fonction totoDynamRec(déjàCalc,valeurs: matrice,i,j :entiers) matrice X matrice si déjàCalc[i] [j]
retourner (déj àCalc ,valeurs)
sinon
si i=j
x +- ièmeElément(s,i)
sinon
(déjàCalc,valeurs) +- totoDynamRec(déjàCalc,valeurs,i,j-i)
(déjàCalc,valeurs) +- totoDynamRec(déjàCalc,valeurs,i+i,j)
x +- valeurs [i] [j-i] + valeurs [i+i] [j]
déjàCalc[i] [j] + vraiO
valeurs[i][j] +- x
retourner (déj àCalc ,valeurs)
Évaluation de la complexité de totoDynamique
Notons n la longueur de la liste s. La complexité en espace est lié à la taille des deux matrices déjàCalc et valeurs soit 0(n2) et à la taille maximal de la pile d’appel 0(n) soit un total de0(n2).
La complexité en temps est égal à 0(n2). Cette complexité est dûe aux hypothèse faites en introduction qui supposaient les complexités de extracti et extract2 constantes. à la complexité de la construction des deux matrices déjàCalc et valeurs. au fait que l’instruction x<-valeurs [i] [j-i]+valeurs [i+i] [j] est exécutée une unique fois pour tout couple (i, i) avec j <j.
Ainsi, le nombre de fois où la fonction totoDynamiqueaec est appelé est exactement 1 plus deux fois le nombre de couples (i,j) avec 1 <j < <nc’est àdire 1+(n-1)’n 0(n2)=.
En conséquence, nous avons un algorithme quadratique 0(n2) alternative effective à un algorithme toto impraticable car de complexité exponentielle 0(2j.
VII-A-1 – 6.1.1 Autre alternative
Dans l’exemple précédent, nous pouvons abandonner l’écriture récursive et dynamique et obtenir un meilleur algorithme qui organise itérativement le remplissage de la matrice valeurs en prenant des couples (i, j) de façon à faire croître j – i. Cette connaissance nous permet ainsi de faire l’économie et de la matrice déj àCalc et de la pile d’appel induite par tout algorithme récursif. L’algorithme est
fonction totoltératif (s : séquence): entier
1 +- longueur(s)
valeurs +- matriceCarrée(l,O)
pour i de 1 à 1 faire
pour j de 1 à 1 faire
si i=j alors
valeurs[i] [i] = ièmeElément(s,i)
sinon
valeurs [i] [j] + valeurs [i] [j-1] + valeurs [i+1] [j] retourner valeurs [1] [n]
VII-A-2 – 6.2 Bien fondé de l’approche dynamique
L’existence d’un algorithme itératif aussi simple que totoltératif est liée à notre capacité à prédire quelles sont les sous-séquences de s sur lesquelles le calcul doit être effectué (ici toutes les sous-séquences de la forme (si, . . . , s) avec s = (si,. . . , sa)) et dans quel ordre elles doivent être évaluées (ici selon j – i croissant). Le caractère polynomial de totoltératif était possible car l’ensemble de ces sous-séquences était de cardinalité polynomiale ici e(n2).
Parfois cette connaissance est absente et seule une approche dynamique illustrée par totoDynamique est possible. Supposons que extractl et extract2 extraient de toute séquence s des sous- séquences selon des algorithmes complexes. Par exemple
fonction extractl(s:séquence):séquence Y notation s = (s1,.. .,s)
si s1 + 2 < s3 + 3 alors
retourner (s1,s3,. . . ,s)
sinon si s2 s4 alors
retourner (s2,s4,. . . ,s)
sinon si etc
- cause d’une telle complexité, il est possible à priori que toute sous-séquence de s ait une évaluation nécessaire à celle de s. Or le nombre de sous-séquences de s est exponentiel e(2) : par exemple la séquence (1, 2, 3) de longueur 3 admet exactement 7 = 2 – 1 sous-séquences : Q, (1), (2), (3), (1, 2), (1, 3), (2, 3).
Il n’est alors pas possible d’évaluer toutes les sous séquences de s comme l’a réalisé totoltératif. Il nous faut évaluer que les sous-séquences réellement nécessaires, c’est à dire celles rencontrées lors du calcul récursif. L’approche est celle utilisée par totoDynamique à la différence près qu’il faut reconsidérer la définition de déjàCalc et de valeurs. Sans rentrer dans les détails, nous pouvons supposer déjàCalc est un ensemble de séquence dans lequel nous pouvons ajouter toute nouvelle séquence (fonction ajouter) et dans lequel nous pouvons décider de l’appartenance d’une séquence à cet ensemble (fonction appartient).
valeurs est un ensemble de couples (t ,v) formés d’une séquence t et d’un entier y dans lequel nous pouvons extraire pour une séquence donné t la valeur entière associée y dans l’ensemble valeurs (fonction calcValeur).
L’algorithme devient alors
fonction totoDynainique2(s:séquence): entier (déjàCalc,valeurs) +- totoDynainaec2(ensVide() ,ensVide() ,s) retourner calcValeur(valeurs,s)
fonction totoDynamRecG(déjàCalc,valeurs: ensemble,s : séquence) ensemble X ensemble
si appartient(s,déjàCalc)
retourner calcValeur(valeurs,s)
sinon
si longueur(s)=i
x – uniqueElément(s)
sinon
t +- extracti(s)
u +- extract2(s)
(déjàCalc,valeurs) +- totoDynamRec2(déjàCalc,valeurs,t) (déjàCalc,valeurs) +-totoDynamRec2(déjàCalc,valeurs,u)
x +- calcValeur(valeurs,t) + calcValeur(valeurs,u)
déjàCalc +- ajouter(déjàCalc,s)
valeurs +- ajouter(valeurs,(s,x))
retourner (déj àCalc ,valeurs)
La complexité de cet algorithme dépendra naturellement de;
- de la longueur de la séquence initiale s.
- la cardinalité N de l’ensemble des sous-séquences dont l’évaluation est nécessaire à la séquence initiale s.
- de la complexité des opérations calcValeur, appartient, ajouter. Une implémentation très naïve des ensembles déjàCalc et valeurs permet
une complexité des primitives en e (N n), qui offre une complexité générale pour totoDynamique2 égale à C(n N2). Une meilleure implémentation (dans certains cas) offre des complexités pour les primitives égales à C(n) et donc une complexité générale égale à C(n N).
La complexité est principalement lié au nombre N de sous-séquences nécessairement évaluables pour évaluer s. Si ce nombre est polynomial, la programmation dynamique offre un algorithme (de complexité en temps) polynomial. Si ce nombre N est exponentiel, il n’existe, sauf cas singulier, aucune solution algorithmique en temps polynomial qu’elle soit dynamique ou autre.
VIII – Chapitre 7 Algorithme Glouton
L’approche « Divide and Conquer » construit une solution après avoir découper l’entrée initiale en plusieurs sous-entrées et après avoir calculer les solutions partielles à chaque nouvelle sous-entrée. La construction de la solution se fait en fait après avoir parcouru toute l’entrée.
L’approche gloutonne diffère de celle-ci en construisant une partie de la solution de façon définitive.
VIII-A – 7.1 Un premier exemple : le rendu de monnaie
Soit E l’ensemble des monnaies en euro. Le problème de la boulangère est de rendre une valeur S en euro en utilisant un nombre minimal de pièces.
problème RenduDeMonnaie
Entrée : S : entier, E : ensemble d’entiers
Sortie : une séquence d’entiers de E de somme S et de longueur minimale
L’algorithme s’écrit de façon récursive de la façon suivante
fonction renduRec(S:entier ; E: ensemble d’entiers): séquence d’entiers
si S=O
retourner O
sinon
calculer x la plus grande valeur de E inférieure ou égale à S retourner ajouter (x , renduRec (S-x)) ou ainsi de façon itérative
fonction rendulter(S:entier ; E: ensemble d’entiers): séquence d’entiers
solution +- séquenceVide()
tantque S O faire
calculer x la plus grande valeur de E inférieure ou égale à S solution +- ajouter(x,solution) S+-S-x
retourner solution
Cet exemple illustre ce qu’est un algorithme glouton en ébauchant la solution sans prendre connaissance de la totalité de l’entrée : en effet, pour rendre la valeur de 17 centimes, seul le premier chiffre compte (le chiffre 1) et détermine de rendre une pièce de 10 centimes si S vaut {1, 2, 5, 10, 20, 50}.
VIII-A-1 – 7.1.1 Correction
La correction de cet algorithme est lié au choix de l’ensemble E.
Si l’ensemble des pièces européennes avait été {1, 4, 6} l’algorithme aurait été incorrect : il associe à la valeur 8 la séquence (6, 1, 1) qui n’est pas optimale, la solution optimale étant (4, 4).
VIII-A-2 – 7.1.2 Amélioration
Pour des raisons de complexités en temps et en espace, une autre représentation de la séquence solution est préférable. En effet si E est égal à {1, 2, 5, 10}, la solution associée à la valeur 1000000 (resp .10100) est la séquence composée de 10000 (resp. i0) éléments égaux à 10. Cet algorithme est donc nécessairement exponentiel.
Une autre représentation peut se faire dans l’exemple E = {1, 2, 4, 10} par un tableau indicé de 1 à 4 et indiquant le nombre de pièces correspondant. L’algorithme est
fonction rendu(S:entier ; E: tableau d’entiers): tableau d’entiers
solution +- tableau(4)(O)
pour i de 1 à 4 faire
solution[i] +-
S+-S-x
retourner solution
VIII-B – 7.2 Deuxième exemple : optimisation de la location d’une salle
Supposer que vous proposiez une salle à la location et ne pouvant être loué que pour un événement à la fois vous souhaitiez maximiser le nombre d’événements; chaque événemente ayant une date de début de et une date de fin df.
Exemple 9 Dans le cas de trois événements (1, 10), (8, 13), (12, 20), une solution optimale est de retenir les deux événements (1, 10) et (12, 20).
VIII-B-1 – 7.2.1 Première tentavive
Un premier algorithme consiste à retenir en priorité les événements compatibles avec les événements déjà retenus qui sont de durée minimale
fonction reservi(E:ensemble d’événements) : ensemble d’événements reste +- E
solution +- ensembleVide()
tantque vrai() faire
tenter de choisir un événement e de date de durée minimale compatible avec solution
si choix impossible
retourner solution
enlever e à reste
ajouter e à solution
Cet algorithme est incorrect car il associe à l’ensemble des événements {(1, 10), (8, 13), (12, 20)} le singleton {(8, 13)} qui n’est pas optimal.
VIII-B-2 – 7.2.2 Deuxième tentavive
Un second algorithme consiste à retenir en priorité les événements compatibles avec les événements déjà retenus qui ont une date de début minimale
fonction reserv2(E:ensemble d’événements) : ensemble d’événements reste +- E
solution +- ensembleVide()
tantque vrai() faire
tenter de choisir un événement e de date de début minimale compatible avec solution
si choix impossible
retourner solution
enlever e à reste
ajouter e à solution
Cet algorithme est incorrect car il associe à l’ensemble des événements {(1, 100), (2, 2), (3, 3),. . ., (10, 10)} le singleton {(1, 100)} qui n’est pas optimal la solution optimale étant {(2, 2), (3, 3), . . . , (10, 1O)}.
VIII-B-3 – 7.2.3 Troisième tentavive concluante
Un troisième algorithme consiste à retenir en priorité les événements compatibles avec les événements déjà retenus qui ont une date de fin maximale
fonction reserv3(E:ensemble d’événements) : ensemble d’événements reste +- E
solution +- ensembleVide()
tantque vrai() faire
tenter de choisir un événement e de date de début maximale compatible avec reste
si choix impossible
retourner solution
enlever e à reste
ajouter e à solution
On observe que cet algorithme associe à l’ensemble {(1, 10), (8, 13), (12, 20)} la solutionoptimale{(1, 10), (12,20)} et àl’ensemble {(1, 100), (2,2), (3,3),…, (10, 10)} la solution optimale étant {(2, 2), (3, 3),. . ., (10, 10)}.
Cet algorithme est correct, a une complexité en temps linéaire. Ces assertions sont laissés en exercice Exercice 22 Considérons l’algorithme réserv3. Supposons que l’ensemble desn événements soit représenté par deux tableaux d’entiers indicés de 1 àn et indiquant l’un la date de début (tableau dateDeb) et l’autre la date de fin (tableau dateFin).
- Réécrire l’algorithme reserv3 en utilisant et en observant la propriété suivante: un événement e qui n’a pas été retenu dans le contexte d’une solution courante solution ne peut être retenu après; il peut ainsi être supprimé de l’ensemble reste. Pour cela vous devrez Indiquer comment représenter l’ensemble reste. Indiquer comment représenter l’ensemble solution.
- Évaluer la complexité de cette implémentation.
- Prouver par récurrence la correction de l’algorithme reserv3.
VIII-C – 7.3 Conclusion
Un grand nombre d’algorithmes optimaux du point de vue de la complexité en temps sont d’origine gloutonne, en particulier ceux fonctionnant en temps linéaires.
De nombreuses théorisations de cette approche gloutonne existent. La plus générale étant celle utilisant des matroïdes.
IX – Chapitre 8 Quelques algorithmes de tri
Un problème classique en informatique est celui du tri
problème Tri
Entrée : un ensemble d’entiers E
Sortie : une séquence triée composée de chacun des éléments de E
Notons que mous aurions pu supposer que l’ensemble en entrée était une partie d’un univers d’éléments muni d’un ordre total. Ce cas particulier fait aux entiers n’altère pas le caractère général des algorithmes que nous allons considérer.
Nous verrons comment à partir des deux méthodes vues dans les chapitres précédents résoudre un tel problème.
IX-A – 8.1 Approche gloutonne
Une approche gloutonne consiste à construire la séquence finale en en définissant un premier élément : clairement, il suffit d’extraire de l’ensemble E son plus petit élément x et de continuer. On déduit un premier algorithme récursif
fonction triGloutonRecursif(E: ensemble) :séquence
si estVide(E) alors
retourner sequenceVide O
sinon
(e,E) +- extraireMinimum(E)
retourner ajouterEnDebut(e ,triGloutonRecursif(E))
Cet algorithme se traduit immédiatementen l’algorithme itératif suivant
fonction triGloutonltératif(E: ensemble) :séquence
Solution +- séquenceVideO;
tantque E n’est pas vide faire
(e,E) +- extraireMaximum(E)
Solution +- aj outerEnFin (e ,Solution)
retourner Solution
Cet algorithme très générique n’indique pas la façon dont sont représentés les ensembles ou les séquences.
IX-B – 8.2 Une première implémentation
Une première solution consiste à supposer que l’ensemble E est représenté à l’aide d’un tableau indicé de 1 à un indice n. L’ensemble courant sera représenté par ce même tableau et l’indice indDeb indiquant l’indice du premier élément (l’ensemble E étant formé des éléments indicés par les indices de indDeb à n).
Extraire l’élément minimum de E consistant à parcourir l’intervalle [indDeb,nj, calculer l’indice indMin du plus petit élément, échanger les éléments aux indices indDeb et indMin puis incrémenter indDeb. L’algorithme est ainsi:
fonction triGloutoni(T:tableau) :tableau
n – longueur(T)
indDeb – 1
pour indDeb de 1 à n-1 faire
indMin – indDeb
pour i de indDeb+1 à n faire
si T[i] < T[indMin] alors
indMin – i
T – échanger(T,indDeb,indMin)
retourner E
L’algorithme a pour complexité en espace (1) et pour complexité en tempse(n2).
IX-C – 8.3 Une deuxième implémentation à l’aide d’un tas
Ici, nous implémenterons nons pas l’algorithme qui extrait le minimum des éléments restants mais son algorithme dual qui considère les éléments maximums
fonction triGloutonRecursif2(E: ensemble) :séquence
si estVide(E) alors
retourner sequenceVide O
sinon
(e,E) +- extraireMaximum(E)
retourner aj outerEnFin (e, triGloutonRecursif (E))
fonction triGloutonltératif2(E: ensemble) :séquence
Solution +- séquenceVideO;
tantque E n’est pas vide faire
(e,E) +- extraireMaximum(E)
Solution +- ajouterEnFin(e,Solution)
retourner Solution
La complexité de l’algorithme est liée à la complexité de l’extraction du minimum. Si nous choisissons de représenter l’ensemble E par une séquence sous forme de tableau l’extraction est ene(n), la complexité globale est en e(n2).
Une solution très rapide existe qui utilise un tas.
IX-C-1 – 8.3.1 Définition de haut niveau d’un tas
Un tas peut être défini comme un ensemble dans lequel
- on peut extraire le plus grand élément.
- on peut ajouter tout nouvel élément.
Ainsi, le tas est un ensemble dégradé dans lequel on ne peut extraire d’autre élément que le plus grand! Nous verrons que cette restriction permet d’obtenir pour chacune de ces opérations une complexité en espace constante et en temps égale à e(log(n)) où n est la cardinalité de l’ensemble considéré.
IX-C-2 – 8.3.2 Implémentation d’un tas
Pour implémenter un tas, on utilise un arbre binaire c’est à dire un objet qui contrairement à l’objet mathématique unidimensionnelle qu’est la séquence (dessinée sur une ligne) est un objet bidimensionnel (dessinée sur une page).
Un arbre est un ensemble d’éléments qui admettent certains unfils-gauche et/ou un fils-droit.
L’élément qui n’a pas de père est appelé laracine. Un tas est un arbre dans lequel
- l’élément fils-gauche (resp. fils-droit) y d’un élément x vérifie y x.
- tous les niveaux de l’arbre sont remplis excepté éventuellement le niveau le plus bas qui cependant ne doit pas laissé de « trou » dans sa partie gauche (voir exemple ci-dessous).
Exemple 10 Ainsi, l’ensemble {100, 40, 50, 20, 30, 1, 4, 3, 5, 2} peut être représenté par l’arbre suivant
100
- \
50 40
-
- \ /\
20 30 1 4
/\ /
35 2
Cet arbre a pour racine 100. Le fils gauche de 100 est 50, son fils droit est 40 qui a pour fisi gauche 1 et fils droit 4.
IX-C-3 – 8.3.3 Ajouter un élément dans un tas
Pour ajouter un nouvel élément y dans un tas représenté par un arbre, il suffit de le placer au plus bas niveau et le « faire remonter » de façon à respecter la hiérarchie père fils. Cet algorithme est illustré par l’example ci-dessous et sera formellement écrit dans la section suivante.
Exemple 11 Ajouter l’élément 66 dans le tas de l’exemple précédent consiste à le placer au niveau inférieur à droite de l’élément le plus à droite et à le faire remonter itérativement si il supérieur à son père
| 100 | 100 | 100 | |||||||||||
| / \ | / \ | / \ | |||||||||||
| 50 | 40 | 50 | 40 | 66 | 40 | ||||||||
| / | \ | / \ | /\ | / | \ | /\ | /\ | ||||||
| 20 | 30 | 1 | 4 | 20 | 66 | 1 | 4 | 20 | 50 | 1 | 4 | ||
| /\ | /\ | /\ | /\ | /\ | /\ | ||||||||
| 3 5 2 66 | 3 5 2 30 | 3 5 2 30 | |||||||||||
IX-C-4 – 8.3.4 Extraire le maximum dans un tas
Pour extraire le maximum d’un tas représenté par un arbre, il suffit de déplacer à la racine l’élément le plus à droite sur le dernier niveau, puis de faire « descendre » cet élément dans l’arbre de façon à respecter la hiérarchie père fils. Cet algorithme est illustré par l’exemple ci-dessous et sera formellement écrit dans la section suivante.
Exemple 12 Supprimer le maximum dans le tas de l’exemple précédent consiste à déplacer à la racine 30 et à le faire descendre dans l’arbre en échangeant l’élément courant éventuellement avec le maximum de son fils gauche et de son fils droit.
| 30 | 66 | 66 | ||||||||
| / \ | / \ | / | \ | |||||||
| 66 | 40 | 30 | 40 | 50 | 40 | |||||
| / \ /\ | / \ /\ | / \ /\ | ||||||||
| 20 | 50 | 1 4 | 20 | 50 1 | 4 | 20 | 30 | 1 | 4 | |
| /\ / | /\ / | /\ / | ||||||||
| 35 | 2 | 35 | 2 | 35 2 | ||||||
IX-C-5 – 8.3.5 Implémentation d’un tas-arbre à l’aide d’un tableau
Une représentation simple et optimale d’un tas est l’utilisation d’un tableau dans lequel
- la racine est à l’indice 1
- le fils gauche d’un élément à l’indice j a pour indice 2 i.
- le fils droit d’un élément à l’indice j a pour indice 2 i + 1.
Exemple 13 Ainsi, le tableau suivant
- 2 3 4 5 6 7 8 9 10
- 50 40 20 30 1 4 3 5 2
fournit une représentation du tas
100
- \
50 40
- \ /\ 20 30 1 4 /\ / 35 2
On observe que le fils-gauche de l’élément 50 (indice 2) est l’élément 20 (indice 4). On observe que le fils-droit de l’élément 50 (indice 2) est l’élément 30 (indice s).
IX-C-6 – 8.3.6 Écriture de l’algorithme
L’ensemble E sur lequel le tri est effectué est représenté à l’aide d’un tableau. Le tas utilisé dont la cardinalité varie au cours de l’algorithme est en fait constitué par la partie gauche du tableau borné par un indice cardTas. L’algorithme est
fonction triParTas(t:tableau) :tableau
n +- longueur(t)
pour i- 2 à n
t – ajouterTas(t,i)
pour i- n à 2
t +- échanger(t,i,i)
t +- descenteTas(t,i-i)
retourner t
où les deux fonctions auxiliaires résolvent les deux problèmes définis par les Figures 8.1 et 8.2.
IX-C-7 – 8.3.7 Évaluation de la complexité
Comme cela sera établi dans les deux sections suivantes, les deux fonctions auxiliaires ajouterTas et descenteTas ont une complexité en espace en (1) et une complexité en temps dans le pire des cas en e(log(i)). On en déduit que triParTas a une:
- complexité en espace de e(1). L’espace mémoire utilisé est, excepté quelques variables pour gérer des indices, celui du tableau fourni en entrée. Il s’agit donc tri « sur place ».
- complexité en temps dans le pire des cas égale à e(nlog(n)). Du fait de l’égalité e(nlog(n)) = ZiE[lfl] ilog(i).
Pour ces deux raisons, cet algorithme de tri est optimal.
Écriture de ajouterTas
Une solution à Aj outerTas est l’algorithme suivant illustré par l’exemple 11:
fonction ajouterTas(t :tableau,cardTas : indice) :tableau i – cardTas
tantque i>i ET t[i]>t[i/2] faire
t +- échanger(t,i,[i/2])
i +- [i/2]
retourner t
La complexité en espace de cet algorithme est (1) et en temps (dans le pire des cas) en e(log(n)) avec n := cardTas : en effet à chaque passage de boucle j est au moins divisé par deux. Il faut donc au plus log(n) passages de boucles pour que i > 1 soit évalué à faux.
Exercice 23 En reprenant l’exemple du tas de l’Exemple 11, fournir les états différents du tableau représentant ce tas au cours de l’algorithme ajouterTas.
Écriture de descenteTas
Une solution à DescenteTas est l’algorithme défini par la Figure 8.3 et illustré par l’Exemple 12 La complexité en espace de cet algorithme est e(1) et en temps (dans le pire des cas) en e(log(n)) avec n := cardTas : en effet à chaque passage de boucle j est au moins multiplié par deux. Il faut donc au plus log(n) passages de boucles pour que 2 i > cardTas soit vérifié.
Exercice 24 En reprenant l’exemple du tas de l’Exemple 12, fournir les états différents du tableau représentant ce tas au cours de l’algorithme descenteTas.
IX-D – 8.4 Approche « Diviser pour régner »
La méthode « Diviser pour régner » consiste à « décomposer » l’instance en deux (ou plusieurs) nouvelles instances, à appliquer récursivement l’algorithme de tri sur ces deux nouvelles sous-instances et à recomposer à partir des deux résultats partiels le résultat général.
L’algorithme de découpe vient très naturellement : il s’agit de partitionner un ensemble en deux parties. Un algorithme assez générique est alors
fonction tri(E:ensemble) :séquence
(F,G) +- partition(E)
retourner fusionner(tri(F) ,tri(G))
Notons dès à présent les propriétés souhaitées des algorithmes de partition et de fusion. Notons n la cardinalité de l’ensemble E. En supposant que l’on arrive à réaliser les calculs de partition et de fusion en au plus n opérations élémentaires et à partitionner E en deux parties de cardinalité égales, la fonction complexité en temps (dans le pire des cas) f de tri vérifie
f(n) =n+2.f()
La fonction f est donc égale à e(nln(n)).
Le résultat est alors optimal: nous ne connaissons pas d’algorithme de tri de complexité en temps inférieur à O(nln(n)).
Observons dès à présent, l’enjeu de décomposer E en deux parties de cardinalité proche. Si cette contrainte n’est pas respectée, et si l’on autorise de partitionner E en deux parties une ayant 1 élément et l’autre n – 1 éléments. L’équation devient
f(n) <n+f(n-1)
La fonction f est donc égale à 0(n2).
Lors des différents algorithmes étudiés, nous représenterons les ensembles ainsi que les listes à l’aide de tableaux. D’autres algorithmes existent qui utilisent d’autres façons de représenter les ensembles à partir de listes, files ou arbres.
L’algorithme général de tri a pour définition
fonction tri(T:tableau) :tableau
retourner triRec(T, 1, longueur (T))
et utilise une fonction auxiliaire triRec qui résout récursivement le problème suivant problème TriRec
Entrée : un tableau T, deux indices i i j longueur(T)
Sortie : un tableau U contenant les mêmes éléments que T tel que U[i. .j] est trié U[i. .j] contient les mêmes éléments que T[i. .j]
IX-D-1 – 8.4.1 Première solution algorithmique de TriRec
Le premier algorithme est basé sur une façon naturelle de décoomposer un tableau : il suffit de calculer l’indice du milieu (-t) sans déplacer les éléments.
fonction triReci(T : tableau ; i,k : indices) : tableau
si i = k
retourner T
j
T +- triReci(T,i,j-i)
T +- triReci(T,j,k)
T +- fusion(T,i,j,k)
retourner T
La difficulté principale est ici de résoudre le problème
problème Fusion
Entrée : un tableau T, trois indices i < j < k tels que les sous-tableaux T[i. .j-i] et T[j. .k] sont triés.
Sortie : un tableau U contenant les mêmes éléments que T tel que
U[i. .i-i] = T[i. .i-i]
U[i. .k] est trié
U[k+i. .n] = T[k+i. .n]
L’algorithme fusion (Figure 8.4) utilise deux tableaux auxiliaires gauche et droit dans lesquels nous réalisons une copie des sous-tableaux T[i. .j-i] et T [j k]. Ces copies sont réalisées par la fonction copie.
Exercice 25 Écrire un algorithme itératif inspiré de triReci. L’idée étant de fusionner les sous-tableaux de longueur 2, puis ceux de longueur 4, puis ceux de longueur 8. Evaluer la complexité en temps et en espace de celui-ci. Comparer ces complexités à celles de triReci. Conclure.
Évaluation de la complexité
La complexité en temps de fusion est égal à k-i-l-i la longueur du tableau symboliquement passé en argument. Ainsi, l’équation fournissant la complexité en temps de triReci est
g(n) = 2 g() n
La complexité en temps de triReci est ainsi e(n log(n)).
La faiblesse de cet algorithme est l’opération copie qui utilise une mémoire auxiliaire de taille e(n).
IX-D-2 – 8.4.2 Seconde solution algorithmique de TriRec
Le précédent algorithme consistait à
- en temps constant, décomposer un tableau, par simple calcul d’un indice.
- en temps linéaire recomposer un tableau trié à partir des sous-tableaux tries.
Le second algorithme présenté ici consiste à
- en temps linéaire, décomposer le tableau.
- en temps constant recomposer un tableau trié à partir des sous-tableaux triés.
Pour recomposer en temps constant un tableau trié à l’aide de deux sous-tableaux triés, une seule solution est possible : faire en sorte que les éléments du sous- tableau de gauche soient inférieurs ou égaux aux éléments du sous-tableau de droite.
Pour réaliser cela, on choisit dans le tableau initial un élément appelé pivot autour duquel cette décomposition se fera. Ces deux tâches sont dévolues à deux fonctions résolvant les deux problèmes suivants
problème ChoixPivot
Entrée : un tableau T, deux indices 1 i j longueur(T) Sortie : un indice indPivot appartenant à [i,j] problème Distribuer
Entrée : un tableau T, trois indices i,j,indPivot tels que 1 < < indPivot < j longueur(T)
Sortie : un tableau u et un indice k tels que:
u contient les mêmes éléments que t
u[1. .i-1] = t[1. .i-1]
u[j-l-1. .n] = t[j+1. .n]
u[k] = t[indPivot]
VaE[i,k-1] u[a]<u[k]
VaE[k-l-1,j] u[k] u[a]
La Figure 8.5 fournit la définition de l’algorithme récursif.
Une solution algorithmique pour Distribuer
Une solution algorithmique au problème Distribuer est fourni par la Figure 8.6.
Il est facile d’observer que la complexité en temps de distribuer est linéaire en la longueur du tableau T considéré (c’est à dire p := jo – io + 1) soit e(j0 – i0).
IX-D-3 – 8.4.3 Différentes variantes liées au choix du pivot
L’algorithme général triRec2 admet plusieurs variantes qui dépendent de la façon de choisir le pivot. Rappelons que si la complexité en temps du choix du pivot (c’est le cas) n’excède pas celle de distribuer (en e(n) où n est la longueur du tableau symboliquement fourni en entrée) l’inéquation fournissant la complexité en temps dans le pire des cas est
f(n) <n+f(n-1)
Auquel cas, la complexité est majorée par n2. Si l’on souhaite obtenir une complexité faible, il nous faut partitionner l’ensemble en deux parties égales ce qui nous permet d’obtenir pour équation f(n)=n+2.f() et d’obtenir ainsi pour complexitén ln(n).
IX-D-4 – 8.4.4 Le choix du premier pivot venu: le tri rapide
Le problème ChoixPivot admet pour première solution
fonction choixPivoti(T:tableau ; i,j : indices) : indice retourner j
Point faible
Cette solution de complexité en temps e(1) a le désavantage d’offrir une complexité en temps dans le pire des cas pour triRec2 égale à e(n2).
Exercice 26 Pour tout entier n, notons T le tableau trié (1,2,. . . , n).
- Démontrer que pour tout n et tous indices j et j, distribuer(Tn,i,j ,i) retourne le couple (Tn, i).
- En déduire que l’équation définissant le nombre d’instructions élémentaires exécutées sur de tels tableaux est g(n) = 1 + g(n – 1) + n
- En déduire que la complexité (dans le pire des cas) de triRec2 est e(n2).
Exercice 27 Quel est le nombre d’instructions élémentaires exécutées sur un tableau à éléments tous égaux?
Point fort
Le premier point fort est la simplicité de l’algorithme! Le second est que la complexité en temps en moyenne, notée f(n), est e(nlog(n)).
Pour calculer cette moyenne, on restreint l’étude à des tableaux dont les éléments définissent un intervalle de la forme [1, n]. La preuve est l’objet de l’exercice suivant
Exercice 28 1. Démontrer que le nombre de tels tableaux de longueur n est exactement n!.
- Démontrer que l’intégrale de x ln(x) est égale à x2 ln(x) – x2. En déduire que ZiE[ln] pln(p) = e(n2 ln(n)).
- Démontrer que f(n) vérifie l’équation
(f(p)+f(n-p-1))
pE[1,n 1]
Pour cela, utiliser le fait que l’ensemble des tableaux de longueur n se partitionne enn ensembles de mêmes cardinalités, ceux dont le premier élément est 1, deux dont le premier élément est 2 etc.
4. Résoudre cette équation et conclure.
Algorithme dit « tri rapide » : méfiez-vous de son nom!
Cet algorithme a pour nom, l’algorithme de tri rapide. Ce nom est un faux ami : en effet cet algorithme est de complexité en temps dans le pire des cas e(n2), il est donc de ce point de vue bien moins rapide que le tri par tas ou le tri médian.
Cependant, il offre du point de vue de la complexité en moyenne un résultat optimal en e(n log(n)) équivalent à celui du tri par tas ou du tri médian (voir plus loin). Mieux une évaluation fine du nombre d’instructions élémentaires montre qu’il est plus rapide que le tri par tas : sa complexité de la formen log(n) présente une constante multiplicative bien inférieure à celle du tri médian ou du tri par tas. Pour cette raison bien concrète, il est préféré aux deux autres tris. Il est en fait possible de fournir une variante améliorée du tri rapide. C’est l’objet du point suivant.
IX-D-5 – 8.4.5 Le choix d’un pivot aléatoire
Nous pouvons améliorer l’algorithme suivant en choisissant pour indice un indice pris aléatoirement dans l’intervalle [i,j]
fonction choixPivot2(T:tableau ; i,j : indices) : indice retourner aléatoire(i,j)
La complexité en temps dans le pire des cas est conservée : il s’agit de e(n2). La complexité en moyenne est conservée : il s’agit dee(nln(n)). L’avantage est qu’ici pour tout tableau fourni en entrée (à valeurs deux à deux distinctes) l’espérance du nombre d’instructions este(nln(n)). Ainsi, pour tout tableau, la malchance d’avoir un traitement en e(n2) instructions est faible.
Ce algorithmes aléatoires n’étant pas étudiés dans ce cours, nous ne ne retiendrons que cette idée : quand nous avons à choisir entre plusieurs options équivalentes, une bonne stratégie algorithmique est le choix aléatoire.
IX-D-6 – 8.4.6 Le choix d’un pivot médian
Soit E un ensemble à n éléments, nous appelons médian le ième plus petit élément avec j := [j.
Nous avons vu précédemment, que l’on obtient une complexité en temps dans le pire des cas en n log(n) en partitionnant l’ensembleE initial en deux parties de cardinalité proche (cette condition est en fait non seulement suffisante mais aussi nécessaire voir Exercice 30). En d’autres termes il faut choisir pour pivot le médian de l’ensemble E.
Le calcul du médian est réalisé en résolvant le problème plus général suivant problème Sélection
Entrée : un ensemble E, un entier iE [1,card(E)]
Sortie : le ième plus petit élément de E
En supposant que E représenté à l’aide d’un tableau T de longueur n, le calcul du i-ième plus petit élément de T se fait de la façon suivante
- en considérant comme bloc chacun des sous-tableaux de longueur 5 associés aux intervalles d’indice [1, 5], [6, 10], [11, 16] etc, on trie chacun des blocs.
- en considérant chacun des médians des sous blocs (aux indices 3, 8, 13 etc), on calcule le médian x (et son indice mdx) de ces médians en utilisant de façon récursive sélection.
- on exécute distribuer en prenant pour pivot ce médian. On obtient ainsi un tableau T partitionné autour du médian des médians x à l’indice noté k, avec aux indices de 1 à k – 1 des valeurs < x et aux indices de k + 1 à n des valeurs x.
- si j = k on retourne x, sinon si j < k on calcule récursivement sélection sur l’entrée (T[i k,-i] , i) sinon on calcule récursivement sélection sur l’entrée (T[ki-i,n] ,i-k).
Exercice 29
- Démontrer que k appartient à l’intervalle [, ].
- Démontrer que la fonction complexité en temps f de sélection vérifie l’inéquation f(n) <n + f() + f()
- Résoudre cette inéquation en démontrant que e(nln(n)) en est solution.
- Quelle serait la complexité de l’algorithme, si au lieu de considérer des blocs de 5, nous avions considérer des blocs de longueur
5. Écrire l’algorithme.
Exercice 30 Dans l’algorithme triRec2, supposons qu’il existe un réel fixé O < a <=1/2 tel que l’entier [k-i]/j-i+1 appartienne à l’intervalle [a, 1 – a]
- Que vaut a quand le pivot choisi est le médian?
- Écrire l’équation vérifiée par la fonction complexité en fonction de a?
- Résoudre cette équation.
- Que pensez-vous de l’intérêt d’un tel algorithme lorsque a=1/10, a=1/10^10 , a=1/10^10^10