Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

3 Algorithmique élémentaire Dans ce chapitre, nous introduisons les concepts él

3 Algorithmique élémentaire Dans ce chapitre, nous introduisons les concepts élémentaires de l’algorithmique. Nous voyons tout d’abord les structures élémentaires à partir desquelles sont construits tous les algorithmes écrits dans un langage impératif. Ces structures ont déjà été introduites au cours du chapitre 1 dans le cadre de Py- thon. Nous donnons ensuite quelques algorithmes simples intervenant très souvent comme brique d’une construction plus imposante. Ces petits algorithmes sont à bien maîtriser : il faut être capable de les implémenter rapidement lorsque le besoin se fait sentir, éventuellement en les adaptant à la situation. I Qu’est-ce qu’un algorithme I.1 Déﬁnition Le mot Algorithme vient du nom du mathématicien arabe Al Khwarizmi, auteur au IXe siècle d’un ou- vrage faisant la synthèse de la résolution des équations du second degré, suivant le signe des coeﬃcients (aﬁn d’éviter l’usage du signe moins). L’ouvrage en question, proposant des méthodes de résolution par manipulations algébriques (réduction à des formes connues) a donné son nom à l’algèbre. Les méthodes exposées peuvent s’apparenter à des algorithmes : on y expose, par disjonction de cas (structure condi- tionnelle) des façons systématiques de résoudre un certain problème, ne laissant ainsi rien au hasard. Il s’agit bien d’un algorithme de résolution. Déﬁnition 3.1.1 (Algorithme) Un algorithme est une succession d’instructions élémentaires, faciles à faire et non ambiguës, détermi- nées de façon unique par les données initiales, et fournissant la réponse à un problème posé. Le développement de l’informatique a marqué l’essor de l’algorithmique, mais cette discipline n’est pas l’apanage de l’informatique. La notion d’algorithme est liée mathématiquement à la possibilité de réso- lution systématique d’un problème, donc à la notion de méthode de calcul. On trouve dans le domaine purement mathématique de nombreux algorithmes : • tous les algorithmes de calcul des opérations élémentaires (addition posée, multiplication posée...) • l’algorithme de la division euclidenne par diﬀérences successives • l’algorithme d’Euclide du calcul du pgcd • l’algorithme de résolution des équations de degré 2 • l’algorithme du pivot de Gauss pour résoudre les systèmes d’équations linéaires, et répondre à d’autres questions d’algèbre linéaire. • l’algorithme de Hörner pour l’évaluation d’un polynôme • etc. Les questions qu’on peut se poser sont alors les suivantes : 46 CHAPITRE 3. ALGORITHMIQUE ÉLÉMENTAIRE 1. Quelles sont les structures élémentaires à partir desquelles sont construits les algorithmes. 2. L’algorithme s’arrête-t-il ? (problème de la terminaison) 3. L’algorithme renvoie-t-il le résultat attendu ? (problème de la correction) 4. Combien de temps dure l’exécution de l’algorithme, notamment lorsqu’on le lance sur de grandes données ? (problème de la complexité). Nous nous intéressons dans ce chapitre à la première question, les 3 autres faisant l’objet d’un chapitre ultérieur (analyse des algorithmes) I.2 Le langage L’étude algorithmique formelle nécessite de se dégager de toute contrainte idiomatique relevant des spé- ciﬁcités de tel ou tel langage. Pour cela, nous utiliserons un pseudo-code, indépendant de toute implé- mentation. Les traductions ultérieures dans un langage de programmation spéciﬁque se font alors sans diﬃculté, sachant que certains langages oﬀrent parfois certaines possibilités supplémentaires (qui sont essentiellement du confort, mais n’ajoutent rien à la description formelle des algorithmes, comme par exemple le fait de pouvoir construire une boucle for sur un objet itérable queconque en Python). Nous décrirons systématiquement un algorithme en : 1. lui donnant un nom ; 2. déﬁnissant les données initiales (variables d’entrée, préciser leur type) ; 3. déﬁnissant la sortie (variables de résultat, préciser leur type) ; 4. donnant le bloc d’instructions déﬁnissant l’algorithme. La structure générale est donc la suivante : Algorithme 3.1 : Nom ou description de l’algorithme Entrée : a,b,... : type Sortie : c,d,... : type instructions ; renvoyer (c, d,...) La dernière ligne, permet de déﬁnir le ou les résultats. I.3 Les structures élémentaires Un algorithme repose sur certains types d’instructions élémentaires. Une instruction est une phrase du langage de programmation indiquant à l’ordinateur une ou plusieurs actions à eﬀectuer, induisant un changement d’état de l’ordinateur (c’est-à-dire une modiﬁcation de la mémoire). Les diﬀérentes structures élémentaires à partir desquelles sont contruits les algorithmes en programmation impérative sont, en plus de l’évaluation d’expressions, de l’utilisation de fonctions antérieures, et de l’aﬀectation (notée x ←valeur) : 1. La séquence : Il s’agit d’un regroupement d’instructions élémentaires, qui seront exécutées successivement. Il s’agit de la notion de bloc en informatique, délimité suivant les langages par des balises de début et ﬁn (begin, end), ou tout simplement par l’indentation, comme en Python. L’intérêt de la séquence est de pouvoir considérer plusieurs instructions comme une seule, et de pouvoir inclure cette succession dans des structures plus complexes (structures conditionnelles, répétitives...) Nous écrirons un bloc de la façon décrite dans l’algorithme 3.2. La plupart du temps, un bloc permettra de délimiter la portée d’une structure composée. Dans ce cas, le mot bloc sera remplacé par le mot clé de la structure correspondante, par exemple début pour et fin pour. I Qu’est-ce qu’un algorithme 47 Algorithme 3.2 : Bloc début bloc instructions ﬁn bloc 2. La structure conditionnelle simple : C’est la structure permettant d’eﬀectuer des disjonctions de cas. Elle permet de distinguer plusieurs cas si ces cas nécessitent des modes opératoires diﬀérents. Cela permet également de traiter les cas particuliers. La structure basique est un branchement à deux issues : si condition alors instructions sinon instructions La condition peut être n’importe quel booléen, par exemple le résultat d’un test, ou le contenu d’une variable de type booléen. De plus, la clause alternative (else) est le plus souvent facultative (algorithmes 3.3 et 3.4). Algorithme 3.3 : Structure conditionnelle simple sans clause alternative Entrée : classe : entier Sortie : ∅ si classe = 4 alors Afficher(’Bestial!’) ﬁn si Algorithme 3.4 : Structure conditionnelle simple avec clause alternative Entrée : classe : entier Sortie : ∅ si classe = MPSI4 alors Afficher(’Bestial!’) sinon Afficher(’Khrass’) ﬁn si Certains langages autorisent le branchement multiple, soit via une autre instruction (par exemple case of en Pascal), soit comme surcouche de l’instruction basique. Nous utiliserons cette possi- bilité en pseudo-code (algorithme 3.5). Algorithme 3.5 : Structure conditionnelle multiple Entrée : classe : entier Sortie : ∅ si classe = MPSI4 alors Afficher(’Bestial!’) sinon si classe = PCSI2 alors Afficher(’Skiii!’) sinon Afficher(’Khrass’) ﬁn si Évidemment, d’un point de vue de la complétion du langage, cette possibilité n’apporte rien de neuf, puisqu’elle est équivalente à un emboîtement de structures conditionnelles (algorithme 3.6). 48 CHAPITRE 3. ALGORITHMIQUE ÉLÉMENTAIRE Algorithme 3.6 : Version équivalente Entrée : classe : entier Sortie : ∅ si classe = MPSI4 alors Afficher(’Bestial!’) sinon si classe = PCSI2 alors Afficher(’Skiii!’) sinon Afficher(’Khrass’) ﬁn si ﬁn si 3. Les boucles Une boucle est une succession d’instructions, répétée un certain nombre de fois. Le nombre de passages dans la boucle peut être déterminé à l’avance, ou peut dépendre d’une condition vériﬁée en cours d’exécution. Cela permet de distinguer plusieurs types de boucles : (a) Boucles conditionnelles, avec condition de continuation. On passe dans la boucle tant qu’une certaine condition est réalisée. Le test de la condition est réalisé avant le passage dans la boucle. On utilise pour cela une boucle while ou tant que en français. L’algorithme 3.7 en est un exemple. Algorithme 3.7 : Que fait cet algorithme ? Entrée : ε (marge d’erreur) : réel Sortie : ∅ u ←1 ; tant que u > ε faire u ←sin(u) ﬁn tant que Ici, on calcule les termes d’une suite déﬁnie par la récurrence un+1 = sin(un). On peut montrer facilement que cette suite tend vers 0. On répète l’itération de la suite (donc le calcul des termes successifs) tant que les valeurs restent supérieures à ε. Comme dans l’exemple ci-dessus, une boucle while s’utilise le plus souvent lorsqu’on ne connaît pas à l’avance le nombre de passages dans la boucle. Souvent d’ailleurs, c’est le nombre de passages dans la boucle qui nous intéresse (aﬁn, dans l’exemple ci-dessus, d’estimer la vitesse de convergence de la suite). Dans ce cas, il faut rajouter un compteur de passages dans la boucle, c’est-à-dire une variable qui s’incrémente à chaque passage dans la boucle. C’est ce que nous avons fait dans l’algorithme 3.8. La valeur ﬁnale de i nous dit maintenant jusqu’à quel rang de la suite il faut aller pour obtenir la première valeur inférieure à ε (et par décroissance, facile à montrer, toutes les suivantes vériﬁeront la même inégalité). (b) Boucles conditionnelles, avec condition d’arrêt Il s’agit essentiellement de la même chose, mais exprimé de façon légèrement diﬀérente. Ici, on répète la série d’instructions jusqu’à la réalisation d’une certaine condition. Il s’agit de la boucle repeat... until..., ou répéter... jusqu’à ce que..., en français. L’algorithme précédent peut se réécrire de la façon suivante, de façon quasi-équivalente, à l’aide d’une boucle repeat... until... (algorithme 3.9). La diﬀérence essentielle avec une boucle while est que, contrairement à une boucle while, I Qu’est-ce qu’un algorithme 49 Algorithme 3.8 : Calcul de i tel que ui ⩽ε Entrée : ε (marge d’erreur) : réel Sortie : i : entier u ←1 ; i ←0 ; tant que u > ε faire u ←sin(u) uploads/Ingenierie_Lourd/ algorithmique-elementaire.pdf