Remerciez-le!

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

Algorithmique, programmation Lionel GUEZ∗ guez@lmd.ens.fr Bureau E324 20 avril

Algorithmique, programmation Lionel GUEZ∗ guez@lmd.ens.fr Bureau E324 20 avril 2020 École normale supérieure – L3 sciences de la planète Table des matières 1 Introduction 1 2 Concepts 3 3 Langage d’algorithme 6 3.1 Variables et types . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Les instructions simples . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Les instructions composées . . . . . . . . . . . . . . . . . . . . . 9 3.5.1 La séquence . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5.2 L’alternative . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.5.3 L’itération . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Conseils de présentation 12 5 Idéaux 14 6 Procédures 14 6.1 Choix entre sous-algorithme et fonction pure . . . . . . . . . . . 19 7 Conception descendante 20 1 Introduction Ce cours présente des concepts communs aux divers langages de program- mation utilisés en calcul scientiﬁque et des conseils généraux de programmation. Par ailleurs, le cours introduit l’écriture d’algorithmes pour préparer l’écri- ture d’un programme. L’algorithme est une suite ﬁnie, séquentielle, de règles que l’on applique à un nombre ﬁni de données, pour résoudre un problème. ∗Emprunts nombreux au cours de Philippe FACON, Institut d’informatique d’entreprise, 1988. 1 L’algorithme se place à un niveau logique, plus ou moins précis, repoussant les problèmes ou les détails techniques du langage de programmation. Voici un exemple : l’algorithme d’Euclide, qui permet de trouver le plus grand commun diviseur de deux nombres entiers. Exemple : algorithme d’Euclide a et b 2 entiers naturels non nuls et a > b calculer le reste r de la division de a par b oui non PGCD = b a prend la valeur de b b prend la valeur de r r = 0 ? L’algorithme peut être spéciﬁé comme ci-dessus à l’aide de symboles gra- phiques ou sous forme purement textuelle. Voici par exemple le même algorithme d’Euclide sous forme purement textuelle. Ce cours : langage textuel de description d’algorithme (“pseudo- code”) entrer (a, b) {a et b 2 entiers naturels non nuls et a > b} r = reste de la division de a par b tant que r ̸= 0 faire a = b b = r r = reste de la division de a par b ﬁn tant que écrire (b) On trouve aussi l’appellation pseudo-code pour ce langage textuel de des- cription d’algorithme. Idéalement, on apprécierait que l’algorithme soit indépendant du langage de programmation visé : un même algorithme pourrait être “traduit” en divers langages de programmation. En pratique, en écrivant un algorithme, on a en ligne de mire un langage de programmation particulier. Notamment parce que l’on doit réﬂéchir pour l’algorithme aux structures de données qui vont être manipulées, et que les structures de données disponibles dépendent du langage de programmation. 2 2 Concepts de base des langages de program- mation impératifs Les langages de programmation classiquement utilisés en calcul scientiﬁque (par exemple Fortran, C++, Python) sont dits “impératifs”. Dans un tel lan- gage, un programme est une suite d’instructions, dans un ordre bien déﬁni, qui modiﬁent “l’état de la mémoire”. La mémoire est essentiellement un ensemble de “variables”, qui contiennent des valeurs, en général des nombres ou du texte. On peut imaginer les variables comme des cases portant des noms. Le programme lit ou modiﬁe les valeurs contenues dans ces cases. Lorsqu’un programme impé- ratif est exécuté, la mémoire passe donc par une suite ﬁnie d’états. Cf. ﬁgures (1) et (2). un état de la mémoire texte du programme variables du programme program exe1_1 implicit none integer, parameter:: n = 3 logical mask(n,n) integer id(n,n) integer, dimension(n):: diagon = 1 integer i, j character(len=12) fmt mask = reshape((/ ((i == j, j = 1, n), i = 1, n) /), (/ n, n /)) id = unpack(diagon, mask, 0) write(unit=fmt,fmt='(a,i3,a)') '(', n, '(i1,1X))' print *, 'id :' do i = 1, n write (unit=*,fmt) id(i,:) end do end program exe1_1 pointeur d’instruction courante 3.5 2 “a” vrai Figure 1 – État de la mémoire. Déﬁnitions — Type d’une variable : type de la valeur qu’elle contient. Exemples : nombre entier, ou texte. Le type détermine les opérations possibles sur la variable. Exemple : + - × / pour les entiers. — Constante littérale : une valeur, écrite littéralement. Exemple : 2,718 282. — Constante symbolique : un nom donné à une valeur littérale. Exemple : e pour la base des logarithmes népériens. Non modiﬁable par le programme. — Expression : combinaison d’opérations appliquées à des variables ou des constantes. — Procédure : suite d’instructions à laquelle on donne un nom. Typage statique, déclarations. Dans certains langages de programmation, le type d’une variable donnée est ﬁxé à l’écriture du programme. On dit que le typage est statique dans ce langage de programmation. Par exemple, les lan- gages Fortran, C et C++ sont à typage statique. Le type d’une variable est alors ﬁxé dans une ligne particulière du programme qu’on appelle une ligne de “dé- claration”. En plus des déclarations de types des variables, on peut aussi trouver des déclarations qui déﬁnissent de nouveaux types (ne pas confondre la déﬁni- tion d’un nouveau type et la déclaration d’une nouvelle variable avec un type 3 program exe1_1 implicit none integer, parameter:: n = 3 logical mask(n,n) integer id(n,n) integer, dimension(n):: diagon = 1 integer i, j character(len=12) fmt mask = reshape((/ ((i == j, j = 1, n), i = 1, n) /), (/ n, n /)) id = unpack(diagon, mask, 0) write(unit=fmt,fmt='(a,i3,a)') '(', n, '(i1,1X))' print *, 'id :' do i = 1, n write (unit=*,fmt) id(i,:) end do end program exe1_1 3.5 2 “a” vrai instruction instruction exécution du programme program exe1_1 implicit none integer, parameter:: n = 3 logical mask(n,n) integer id(n,n) integer, dimension(n):: diagon = 1 integer i, j character(len=12) fmt mask = reshape((/ ((i == j, j = 1, n), i = 1, n) /), (/ n, n /)) id = unpack(diagon, mask, 0) write(unit=fmt,fmt='(a,i3,a)') '(', n, '(i1,1X))' print *, 'id :' do i = 1, n write (unit=*,fmt) id(i,:) end do end program exe1_1 0. 2 “a” vrai program exe1_1 implicit none integer, parameter:: n = 3 logical mask(n,n) integer id(n,n) integer, dimension(n):: diagon = 1 integer i, j character(len=12) fmt mask = reshape((/ ((i == j, j = 1, n), i = 1, n) /), (/ n, n /)) id = unpack(diagon, mask, 0) write(unit=fmt,fmt='(a,i3,a)') '(', n, '(i1,1X))' print *, 'id :' do i = 1, n write (unit=*,fmt) id(i,:) end do end program exe1_1 0. 2 “a” faux Figure 2 – Exécution d’un programme. La mémoire de la machine passe par une suite ﬁnie d’états. 4 pré-existant) et des déclarations de constantes symboliques. Les lignes de décla- rations ne modiﬁent pas l’état de la mémoire, elles déﬁnissent ou caractérisent des objets que le programme manipule. Typage dynamique Dans d’autres langages de programmation, une variable de nom donné peut voir son type changer en cours d’exécution. Le type de la variable est déterminé par la valeur aﬀectée à cette variable. On dit que le typage est dynamique dans ce langage de programmation. Le langage Python par exemple est à typage dynamique. Types entier et réel. Les langages de programmation scientiﬁque permettent d’utiliser des valeurs de type entier ou de type réel (entre autres types). La dis- tinction entre entiers et réels n’est pas la même en informatique qu’en mathéma- tiques. Mathématiquement, si un nombre est entier, il est aussi réel, tandis que, informatiquement, une valeur est ou bien entière ou bien réelle. Chaque langage oﬀre donc une possibilité de distinguer une valeur entière d’une valeur réelle. Par exemple, dans les langages scientiﬁques classiques, les écritures 2 et 2. (avec un point) distinguent la valeur 2 considérée comme entière ou réelle. En outre, pour les langages à typage statique, la déclaration d’une variable distingue le type en- tier et le type réel. Une valeur entière n’est pas traitée comme une valeur réelle. La diﬀérence est dans le “codage” de uploads/Ingenierie_Lourd/ 0727-algorithmique-programmation 1 .pdf