Introduction et organisation du cours vii
1 Notions générales 1
1.1 Qu’est-ce que la programmation? . . . 1
1.1.1 Une première approche intuitive . . . . . . 1
1.1.2 L’ordinateur . . . 1
1.1.3 L’algorithmique . . 2
1.1.4 La compilation ou l’interprétation . . . . . 3
1.1.5 Les différents langages et le choix de C++ . 4
1.2 Pourquoi programmer pour un mathématicien? . . 4
1.2.1 Traiter efficacement des données numériques . . . . . . 5
1.2.2 Étudier un modèle à travers des simulations 5
1.2.3 Ce que ne fait pas la programmation . . . . 5
1.3 Programmer efficacement : quelques conseils . . . . 6
1.3.1 Aborder sereinement un projet de programmation . . . 6
1.3.2 Bonnes pratiques de codage lors d’un travail en équipe 7
1.4 La notion de complexité . 7
2 Structure et compilation d’un programme 9
2.1 Histoire du C++ . . . . . 9
2.2 Quelques références indispensables . . 10
2.3 Exemples de programmes 10
2.3.1 Premier exemple . 10
2.3.2 Un deuxième exemple avec une fonction auxiliaire . . . 11
2.3.3 Un troisième exemple issu des mathématiques . . . . . . 12
2.4 Compilation de fichiers . . 13
2.4.1 Cas d’un fichier unique . . . . 13
2.4.2 Cas de plusieurs fichiers séparés 14
2.4.3 Les directives de précompilation . . . . . . 17
2.4.4 Durée d’exécution d’un programme . . . . . 17
2.4.5 [hors programme] Compilation pour utilisation par d’autres langages
de programmation : l’exemple de swig . . 18
Exercices . . . . . 21
3 La syntaxe du C++ 23
3.1 Les types . . 23
3.1.1 Généralités . . . . 23
3.1.2 Les types simples . 24
3.1.3 Les tableaux statiques . . . . . 29
3.1.4 Les structures . . . 30
3.1.5 Les références . . . 32
3.2 Les tests et les boucles . . 33
3.2.1 Le test if ( ) { } else { } . . . 33
3.2.2 Le test switch . 34
3.2.3 Les boucles . . . . 36
3.3 Les fonctions 37
3.3.1 Description générale . . . . . . 37
3.3.2 Les λ-fonctions à partir du standard C++11 41
Exercices . . . . . 44
4 La bibliothèque standard (STL) 47
4.1 Présentation de la bibliothèque standard . . . . . . 47
4.2 Les entrées-sorties vers le terminal et les fichiers . . 49
4.2.1 Lecture et écriture de données 49
4.2.2 Écriture dans le terminal . . . . 49
4.2.3 Lecture dans le terminal. . . . 49
4.2.4 Lecture et écriture dans un fichier . . . . . . 51
4.3 Les chaînes de caractères string . . 52
4.4 Les conteneurs ordonnés std::vector et std::list . . . . . 53
4.4.1 Les tableaux . . . 53
4.4.2 Les listes . . . . . 56
4.5 Les conteneurs non ordonnés std::map et std::set . . . . . 59
4.5.1 Les ensembles, std::set et std::unordered_set . . 59
4.5.2 Les fonctions à domaine de définition fini et le conteneur map . . . . 60
4.6 Itérateurs et algorithmes sur les conteneurs . . . . 61
4.6.1 Un exemple simple et basique : dénombrer des éléments selon un critère . 61
4.6.2 Les itérateurs . . . 62
4.6.3 Les algorithmes de et . . . . 64
4.6.4 Des extensions des itérateurs bien utiles en pratique . . 66
4.7 L’aléatoire en C++ . . . . 69
4.7.1 L’aléatoire et la programmation 69
4.7.2 Les générateurs de nombres aléatoires en C++ . . . . . 71
Exercices . . . . . 76
5 Programmation orientée objet et classes 81
5.1 Généralités sur les classes 82
5.1.1 Étude d’un exemple préliminaire . . . . . . 82
5.1.2 Vocabulaire et définition d’une classe : champs et méthodes . . . . . 85
5.2 Présentation des différentes méthodes 88
5.2.1 Accesseurs et mutateurs . . . . 88
5.2.2 Constructeurs et destructeurs . 91
5.2.3 Incrémentation et décrémentation . . . . . 93
5.2.4 Méthodes de conversion . . . . 94
5.3 Surcharge d’opérateurs, de fonctions et amitié . . . 95
5.4 Héritage public entre classes . . . . . . 96
5.4.1 Définition et syntaxe . . . . . . 96
5.4.2 Méthodes virtuelles et polymorphisme . . . 100
TABLE DES MATIÈRES v
5.4.3 Méthodes virtuelles pures . . . 101 Exercices . . . . . 103
6 Programmation générique et templates 109
6.1 Introduction à la programmation générique . . . . 109
6.1.1 Présentation de quelques exemples . . . . . 109
6.1.2 Vocabulaire et syntaxe . . . . . 110
6.1.3 Structure du code et compilation . . . . . . 112
6.1.4 Particularités pour les modèles de classe . . 113 6.1.5 Redéfinition d’une instanciation particulière 114
6.2 Quelques exemples issus de différentes bibliothèques . . . . . . 115
6.2.1 La bibliothèque standard et la STL . . . . . 115
6.2.2 Objets mathématiques standards . . . . . . 115
6.2.3 Un exemple d’algèbre linéaire : la bibliothèque Eigen . 116 6.2.4 Les nouveautés des standards récents de C++ et la notion de std : :tuple116
Exercices . . . . . 118
7 Gestion de la mémoire 121
7.1 Notions sur les pointeurs . 121
7.1.1 L’un des atouts du C et du C++ . . . . . . 121
7.1.2 Les adresses en mémoire . . . . 121
7.1.3 Récupérer l’adresse d’une variable et y accéder . . . . . . 122 7.1.4 Les références : un cas particulier de pointeur . . . . . . 124
7.2 Gestion dynamique de la mémoire . . 125
7.2.1 Arithmétique des pointeurs . . . 125
7.2.2 Allocation et désallocation de mémoire . . . 126
7.3 Gestion de la mémoire dans les classes 128
7.3.1 Méthodes supplémentaires à définir . . . . . 128
7.3.2 Opérateur d’affectation . . . . 130
7.4 Les structures de données usuelles . . 131
7.4.1 La problématique de la complexité . . . . . 131
7.4.2 Listes et itérateurs 131
7.4.3 Listes simplement chaînées, piles, arbres, « skip lists », arbres . . . . 135 7.4.4 Les itérateurs des conteneurs de la STL . . 136
7.5 [Hors programme] Une rapide revue des pointeurs intelligents en C++11 . . 137
Exercices . . . . . 139
Conclusion 141
Appendice : Makefile 143
Introduction à Makefile 143
Bibliographie 144
vi TABLE DES MATIÈRES
Introduction et organisation du cours
Ce cours a pour but de vous donner une base solide de programmation en C++ orientée vers les mathématiques appliquées, avec un fort accent mis sur le calcul intensif.
Étant donné le volume horaire restreint, de nombreuses bibliothèques ne seront pas présentées et nous ne pourrons pas aborder en détail le calcul parallèle; en revanche, la structure du cours vise à donner suffisamment de bases sur ces questions pour que l’étudiant intéressé puisse s’y mettre par lui-même à la suite du cours, en M2 ou en stage.
Le côté pratique étant essentiel pour un cours de programmation, le nombre d’étudiants inscrits est limité à 100 étudiants. Il y a 4 groupes de TP et une répartition uniforme des étudiants sur ces 4 groupes est indispensable pour le bon fonctionnement des TP. L’effectif d’un groupe de TP est plafonné à 25. L’inscription dans l’un des 4 groupes est obligatoire et nécessaire pour valider ce module.
Le cours a lieu le lundi de 8h30 à 10h30 et est assuré par D. Simon, l’auteur de ce polycopié. Les TP ont lieu les
lundi, mardi, mercredi et vendredi de 13h45 à 16h45 en salle 16.26.401
et sont assurés par C. Boutillier, D. Giorgi et D. Simon. La salle étant dans un couloir de laboratoire, vous êtes priés d’arriver et d’attendre en silence devant la porte.
Calendrier prévisionnel pour l’année 2019–2020
— premier et deuxième cours : lundi 13 janvier 2019
— premier TP : la semaine du 20 janvier 2019
— premier TP noté : la semaine du 24 février 2019
— deuxième TP noté : la semaine du 20 avril 2019 (juste après les vacances de printemps)
Évaluation. Les séances de TP sur machine sont obligatoires. Elles donnent lieu à deux notes (à travers 2 séances de TP notés en séances 6 et 12 des TP) sur 25. L’examen et le rattrapage sont sur papier et donnent lieu à une note pour 75. Le calcul de la note finale procède selon la formule :
(︂note TP1 sur 25 + note TP2 sur 25)︂
note finale sur 100 = + note examen sur 75
L’évaluation en TP se fait par binôme ou individuellement (si le nombre de machines le permet) : la composition d’un binôme ne peut pas varier d’un TP noté au suivant.
Structure de l’ouvrage. Le chapitre 1 ne traite pas du C++ mais de l’informatique en général. Il vise à donner une culture générale sur les ordinateurs et l’algorithmique et fournit des conseils pour aborder sereinement un projet de programmation.
Le chapitre 2 présente le C++ à travers des exemples de programmes, décrit leur structure générale et permet d’apprendre à les compiler.
Le chapitre 3 présente la syntaxe du C++, i.e. les mots-clefs et symboles à maîtriser pour écrire des programmes élémentaires. La plupart des notions sont classiques en programmation et se retrouvent dans de nombreux autres langages avec des syntaxes légèrement différentes.
Le chapitre 4 présentela bibliothèque standard du C++, qui permett de gérer en pratique de nombreux outils classiques tels les conteneurs, les algorithmes et les nombres pseudoaléatoires.
Le chapitre 5 explique comment créer de nouveaux types en C++ à l’aide de classes et comment exploiter la programmation orientée objet.
Le chapitre 6 décrit la programmation générique en C++ qui permet d’écrire des morceaux de code réutilisables sur des objets de types très différents à l’aide de « templates » (modèles en français) de fonctions et de classes.
Le chapitre 7 décrit une spécificité majeure du C et du C++ : la possibilité de gérer soi-même la mémoire à l’aide des pointeurs pour une plus grande efficacité du code.
Remerciements. Je tiens ici à remercier toutes les personnes qui ont participé à l’élaboration de ce polycopié. En premier lieu, je voudrais remercier Vincent Lemaire qui est à l’origine de ce cours et me l’a transmis et avec qui j’ai enseigné cette matière de nombreuses fois. Mes collègues de TP, Cédric Boutillier, Raphaël Roux, Nicolas Gilliers, Thibaut Lemoine et Daphné Giorgi ont été, au fil du temps et des évolutions de ce cours, d’une aide précieuse pour la relecture et la conception des sujets. Enfin, je voudrais remercier mes autres relecteurs qui ont corrigé de très nombreuses coquilles et mauvaises formulations : il doit malheureusement en rester encore
Chapitre 1 Notions générales d’algorithmique et de programmation
1.1 Qu’est-ce que la programmation?
1.1.1 Une première approche intuitive
Programmer consiste à écrire de manière détaillée une suite d’instructions élémentaires à effectuer pour pouvoir réaliser une tâche donnée. La connaissance de cette suite d’instructions permet ensuite à toute entité dotée de capacités de logique et d’arithmétique — autrement dit capable d’exécuter les instructions élémentaires — d’effectuer la tâche donnée : cette entité peut être un être humain ou un ordinateur.
L’avantage de ce dernier est sa capacité d’effectuer extrêmement rapidement les calculs logiques et arithmétiques; son inconvénient — si cela en est un — est de suivre aveuglément les instructions qui lui ont été fournies et de ne pas mesurer la pertinence du résultat.
Les instructions doivent être écrites dans un langage que comprend l’ordinateur. Comme pour les langues humaines, il existe plusieurs langages mais ils décrivent tous les mêmes calculs mathématiques et logiques. Pour nous, ce langage sera le C++.
1.1.2 L’ordinateur
Pour bien comprendre les langages informatiques, il est nécessaire d’avoir une idée du fonctionnement d’un ordinateur. Nous n’entrerons pas dans les détails qui peuvent atteindre une très grande complexité et dont les informaticiens sont les spécialistes.
Un ordinateur est essentiellement composé :
— de mémoire vive (la RAM) : c’est là que sont écrites les données manipulées par le processeur. Y accéder pour lire ou écrire des données est très rapide. Lorsqu’un programme termine, toutes les données présentes dans la RAM qui dépendent de ce programme sont effacées et perdues. C’est une mémoire rapide mais temporaire.
— de mémoire morte (disque dur, CD, DVD, disquette, clef USB, etc.) : c’est là que sont écrites les données de manière durable, i.e. au-delà de la fin d’un programme. Y accéder est beaucoup plus lent que pour la RAM. Le processeur ne se permet d’y écrire que sur instruction explicite du programmeur.
— de processeurs : ce sont eux qui effectuent les calculs. Ils chargent quelques données, opèrent des opérations logiques et arithmétiques très élémentaires sur celles-ci et donnent le résultat.
— de périphériques, en particulier l’affichage : tout ce qui permet de faire l’interface avec l’être humain ou d’autres machines (par exemple, l’écran, l’imprimante, des capteurs électroniques, une sortie Ethernet, une carte Wifi, etc).
Un langage de programmation comporte donc les types d’instructions suivants :
— des instructions de calcul qui permettent d’ordonner aux processeurs les opérations logiques et arithmétiques à effectuer et d’indiquer sur quelles données les effectuer,
— des instructions d’affectation qui permettent d’indiquer où stocker le résultat dans la RAM pour un usage futur,
— des instructions de lecture et écriture qui permettent d’aller lire des données ou d’écrire des résultats dans la mémoire morte ou de les afficher dans des périphériques, tels l’écran.
L’un des buts de ce cours est de maîtriser ces trois types de commandes dans le langage C++.
Toute mémoire, vive ou morte, est organisée de la manière suivante : c’est une suite ordonnée de valeurs 0 ou 1, appelées bits. Cette organisation unidimensionnelle a deux conséquences majeures.
D’une part, toute donnée un peu plus évoluée que 0 ou 1 doit être codée en termes d’une succession de 0 et 1. Par exemple, un nombre entier sera écrit en base deux; les lettres de l’alphabet seront numérotées et leur numéro sera écrit en base deux. Dans les instructions de lecture et écriture, il faut donc faire attention à dire à l’ordinateur ce qu’il doit lire! Par exemple la suite de bits 01101 peut coder aussi bien un tableau (0,1,1,0,1) de cinq valeurs dans {0,1}, l’entier 0 × 1 + 1 × 2 + 1 × 4 + 0 × 8 + 1 × 16 = 22, ou l’entier 1×1+0×2+1×4+1×8+0×16 = 13 écrit dans l’autre sens. Le codage de l’information a donc une grande importance : c’est à la base de la notion de type que nous étudierons en C++.
D’autre part, le caractère ordonné de la mémoire permet d’accéder à toute séquence écrite dans la mémoire, vive ou morte, très facilement en donnant au processeur le numéro du bit de début et le nombre de bits à lire. Cet adressage de la mémoire est à la base des notions de pointeur et référence essentielles en C++.
1.1.3 L’algorithmique
L’algorithmique est une discipline qui se focalise sur le découpage d’une méthode de traitement d’une tâche donnée en étapes élémentaires préalablement fixées et dont le but est de minimiser le nombre d’étapes élémentaires à utiliser. Cela permet d’avoir un programme qui s’exécute en un temps minimal avec le moins d’opérations possibles.
En particulier, l’algorithmique ne dépend que très peu du langage utilisé; c’est la programmation des étapes élémentaires qui dépend du langage, non le choix du découpage en étapes élémentaires. Pour les questions mathématiques qui vont nous intéresser, la plupart des langages usuels offrent le même panel d’opérations élémentaires.
Il s’agit donc de bien réfléchir à la méthode de résolution d’un problème avant de commencer à écrire des lignes de programmation!
Un exemple extrêmement élémentaire de deux algorithmes qui réalisent la même tâche en des temps très différents est celui du calcul d’une puissance.
Exemple : calcul dea517. Soit a un élément d’un anneau; quel est le nombre minimal de multiplications à utiliser pour calculer a517 ?
Une première réponse naïve consiste à dire 516 : on commence par calculer a2 (une multiplication), puis a3 = a2× a (une autre multiplication), puis a4 = a3× a, etc., puis a517 = a516 × a.
1.1. QU’EST-CE QUE LA PROGRAMMATION?
En fait, on peut en utiliser beaucoup moins! Le nombre optimal ici est de 11 multiplications. Nous commençons par écrire 517 = 512 + 4 + 1 = 29 + 22 + 1. On calcule a2 (une multiplication) puis a4 = a2× a2 (une multiplication), puis a8 = a4× a4 (une multiplication), etc, puis a29 = a28× a28 (une multiplication). Pour calculer a52, nous avons utilisé 9 multiplications. De plus, pendant ce calcul, nous avons déjà calculé a4. Il suffit donc de calculer a517 = a512× a4× a (deux multiplications). Au total, seules 11 multiplications ont été nécessaires!
1.1.4 La compilation ou l’interprétation
Le code d’un programme est la suite de lignes de programmation écrites dans un langage donné (C++ dans ce cours) pour effectuer une tâche donnée. C’est la transcription dans ce langage C++ des algorithmes expliqués dans la section précédente.
À ce stade, nous sommes encore loin de ce qui se passe réellement dans le cœur de l’ordinateur, où les opérations élémentaires « physiques » consistent à transformer des 0 en 1 aux bons endroits. Pour passer de l’un à l’autre, il faut convertir nos lignes de programmation en « instructions machine » : c’est l’étape de compilation ou interprétation du programme (voir en fin de section pour la différence entre les deux notions). C’est un autre programme qui est chargé de cela : le compilateur1 ou l’interpréteur.
Un langage de programmation est ainsi inutile sans compilateur/interpréteurs associé. Pour un même langage, il peut exister différents compilateurs. Selon les processeurs utilisés et le système d’exploitation, les instructions machine peuvent varier : le travail du compilateur est de gérer tout cela. Nous n’entrerons pas dans les détails du fonctionnement du compilateur et des instructions machines dans ce cours.
Le compilateur produit un fichier exécutable qui contient les instructions machine. Il ne reste alors qu’à exécuter ce fichier pour que l’ordinateur effectue réellement les opérations que nous avions prévues dans notre algorithme de départ.
Il est possible que le compilateur détecte des erreurs de syntaxe (parenthèses non fermées, instruction inconnue, tentative d’addition de vecteurs de dimensions différentes, etc.). Dans un tel cas, le compilateur indique la ligne du programme qu’il ne comprend pas et qu’il faut corriger. Il est important de garder en mémoire les deux choses suivantes :
— le compilateur ne prend aucune initiative : c’est donc au programmeur d’ajouter lui-même les parenthèses manquantes, même dans les cas où cela semble trivial. Pour éviter cela, il vaut mieux essayer d’être le plus rigoureux possible dès le début de la rédaction du code.
— le compilateur ne sait pas détecter une erreur de raisonnement : il produira toujours un programme exécutable si la syntaxe est correcte, même si ce programme effectue une toute autre opération que ce vous auriez souhaité. Il est de la responsabilité du programmeur de vérifier que son programme effectue bien la tâche imposée : personne ne peut le faire à part lui.
En résumé, pour un langage compilé – ce qui est le cas de C++ —, les quatre étapes successives de programmation à respecter sont les suivantes : conception de l’algorithme (pas de langage à apprendre, uniquement des mathématiques), écriture du code, compilation du code pour produire le programme exécutable, exécution de ce programme.
Un langage interprété mélange les deux dernières étapes : au lieu de compiler une fois pour toute un code et de l’exécuter ensuite autant de fois que nécessaire, on lance directement l’interpréteur sur le code non-compilé et ce dernier transforme chaque ligne en instruction machine immédiatement exécutée.
1.1.5 Les différents langages et le choix de C++
Il existe une multitude de langages de programmation. L’immense majorité d’entre eux partage les mêmes fonctionnalités élémentaires. Ce qui les différencie est d’une part leur syntaxe, qui peut rendre la même opération agréable ou détestable à écrire, et d’autre part la présence de fonctionnalités spécifiques supplémentaires. Il est important de prendre conscience qu’a priori toute tâche est réalisable par tous les langages usuels. Le choix d’un langage est donc arbitraire.
Parmi les langages usuels, on peut citer Fortran, Pascal (anciens), Java, C, C++, Python (calcul), Perl, Ruby (traitement des chaînes de caractères), Haskell, C# , Caml, etc.
Les critères de choix usuels sont les suivants :
— habitude : en général, apprendre un nouveau langage requiert du temps donc on ne fait cet investissement en temps que sous obligation ou forte incitation; sinon on continue à utiliser un langage que l’on connaît déjà;
— intégration de fonctionnalités à des programmes préexistants ou travail en équipe : en général, on s’adapte à ce qui était déjà là quand on vient d’intégrer l’équipe de développement d’un projet;
— choix d’une syntaxe adaptée aux outils que l’on souhaite utiliser : une même tâche peut prendre une seule ligne dans certains langages contre plusieurs dizaines de lignes dans un autre;
— gestion de la mémoire et choix entre compilation et interprétation : pour de petits programmes, ce critère n’est pas important; pour un gros programme de calcul intensif, l’utilisation d’un langage compilé, qui permet de gérer la mémoire soi-même, rend possible des optimisations à plus grande échelle lors de la transformation des lignes de code en instructions machine.
— ouverture du code et choix d’un langage connu : si le code du programme est public, plus le langage est largement connu, plus les chances augmentent que quelqu’un puisse vous aider.
— existence de bibliothèques qui réalisent déjà ce que l’on souhaite faire.
Le langage C++ est un langage maintenant très classique et figure parmi les plus utilisés, en particulier en finance et en calcul intensif. D’une part, sa syntaxe est assez naturelle et, d’autre part, sa gestion directe de la mémoire permet une bonne vitesse d’exécution.
Le C++ est réputé pour avoir une certaine lourdeur syntaxique, comparativement à Python par exemple : cette lourdeur se révèle être un avantage pour les gros programmes car la rigueur qu’elle impose évite l’accumulation de petites erreurs ou incompatibilités entre programmeurs. De plus, une fois qu’on maîtrise le C++, il est facile de passer à d’autres langages moins lourds et moins rigides : « Qui peut le plus peut le moins »
1.2 Pourquoi programmer pour un mathématicien?
Ce cours s’adresse à des mathématiciens et non à des informaticiens. C’est donc une certaine vision de la programmation qui domine ce cours. En particulier, nous ne traiterons absolument pas les questions d’interfaces (menus déroulant, messages clignotants, représentation graphique, etc), de protocoles TCP pour Internet, de communication par wifi, de hardware, etc.
Ce cours n’a pas pour but non plus de traiter le problème mathématique du contrôle des erreurs commises lors de discrétisation ou d’approximations : nous renvoyons pour cela à des cours de mathématiques.
1.2. POURQUOI PROGRAMMER POUR UN MATHÉMATICIEN?
L’emphase est mise sur l’implémentation de calculs mathématiques en C++, en particulier liés aux probabilités et aux statistiques en lien avec différentes applications.
1.2.1 Traiter efficacement des données numériques
Savoir résoudre formellement un problème est au cœur des mathématiques; malheureusement, appliquer la formule de la solution dans un cas pratique peut parfois être long et pénible. Par exemple, le pivot de Gauss permet de résoudre formellement un système linéaire mais il est très fastidieux de résoudre « à la main » un système de 10 équations à 10 inconnues. Or, dans de nombreux cas pratiques, ce sont des systèmes de taille supérieure à 10000 qu’il faut résoudre. Il devient alors inévitable d’écrire un code qui réalise la méthode du pivot de Gauss.
De nombreux TP ce semestre ont pour but d’écrire les algorithmes et les lignes de code qui permettent de programmer des méthodes mathématiques que vous avez étudiées pendant vos années d’université : méthode de Monte-Carlo pour des estimations d’intégrales, algèbre linéaire, polynômes, chaînes de Markov, etc.
Avec le récent développement du « Big Data », les volumes statistiques à traiter sont énormes et requièrent de gros moyens de calcul programmés efficacement (calcul parallèle, etc) : le langage C++ se révèle bien adapté pour cela.
1.2.2 Étudier un modèle à travers des simulations
De nombreuses situations pratiques issues de la physique, de la biologie ou de l’économie donnent lieu à des modèles mathématiques : équations différentielles, variables aléatoires de loi jointe prescrite, etc. Il est en général plus facile de prouver qu’une formule qu’on a préalablement devinée est vraie (par récurrence par exemple) plutôt que d’établir la formule sans savoir au préalable à quoi elle doit ressembler. Calculer des solutions numériques à un problème donné permet souvent de se faire souvent une bonne première idée de ce à quoi les solutions vont ressembler.
1.2.3 Ce que ne fait pas la programmation
Pour un mathématicien néophyte en programmation, certaines impossibilités peuvent parfois dérouter. Tout d’abord, sauf cas très particulier très récents (cf. le langage Coq par exemple), un programme ne prouve pas qu’un algorithme marche : il se contente de l’exécuter quelle que soit la pertinence du résultat. Si l’algorithme de départ est faux, le programme peut être syntaxiquement correct (i.e. le compilateur ne donne aucun message d’erreur) et le résultat faux. Autrement dit, l’écriture d’un programme vient après la formulation mathématique d’un problème et d’une méthode formelle de résolution.
Dans un tout autre registre, une autre impossibilité est déroutante : l’absence des nombres réels et de tout infini ! En effet, mathématiquement, un nombre réel requiert la connaissance de tous les chiffres de son développement binaire ou décimal. Il faudrait une mémoire infinie pour stocker ne serait-ce qu’un réel; sur une machine réelle, on travaille avec des troncatures des nombres réels à une précision donnée. Cela a pour conséquence majeure l’accumulation des erreurs d’arrondis qui peuvent mener à des résultats aberrants.
Exemple : calcul de la série harmonique. Nous souhaitons calculer les valeurs de Hn /k. Nous savons que cette série diverge comme logn quand n → ∞.
Néanmoins, calculons Hn selon deux méthodes différentes avec des variables de type float (réels avec une précision basse, cf. le chapitre suivant) :
— du grand vers le petit : on commence par 1, puis on ajoute 1/2, puis 1/3, etc, jusqu’à 1/n;
— du petit vers le grand : on commence par 1/n, puis on ajoute 1/(n−1), puis 1/(n−2), etc, jusqu’à 1/2 puis 1;
