Remerciez-le!

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

CNAM Montpellier Année universitaire : 2006-07 Cycle : A Unité d’Enseignement :

CNAM Montpellier Année universitaire : 2006-07 Cycle : A Unité d’Enseignement : Algorithmique – Programmation (NFA001, NFA002, NFA005) Nature : cours Algorithmes et programmes en C++ Support de cours novembre 2006 Enseignant : REITZ Philippe Adresse : LIRMM 161, rue Ada 34392 Montpellier cedex 5 Mél : reitz@lirmm.fr Tél : +33 662 32 20 50 Algorithmique et programmation en C++ Introduction 1 1. INTRODUCTION L'objectif de ce cours est de s’initier à la construction de programmes informatiques. Une telle construction s’effectue en deux phases : • définition abstraite du programme : implique en particulier l’écriture d’algorithmes, dans un langage pas nécessairement compréhensible par un ordinateur ; nous parlerons de langage de spécification (ou de définition) d’algorithmes. • définition concrète du programme : écriture d’un texte traduisant les algorithmes précédents en un langage compréhensible par l’ordinateur ; nous parlerons alors de langage de programmation. 1.1. UNE INTERPRETATION DE LA POSITION DU CNAM L’une des ambitions du CNAM Paris pour cette unité de valeur Algorithmique – Programmation du cycle A est d’user d’un langage qui permette à la fois de spécifier et de programmer des algorithmes. Des langages fonctionnels comme CAML répondent en partie à cette ambition : des règles d’écriture (syntaxe) réduites au minimum, une grande puissance d’expression (peu de lignes suffisent en général pour décrire des algorithmes, même compliqués), et la spécification obtenue est immédiatement opérationnelle. L’approche fonctionnelle souffre toutefois de deux défauts : • elle considère un programme comme une composition de fonctions, et met donc le concept de fonction au cœur du système de pensée. Tout individu désireux de s’approprier cette approche doit donc être familier de ce concept. • les langages de programmation fonctionnelle sont très peu exploités dans le monde professionnel, plus friand d’autres approches de la programmation, en particulier la programmation par objets, très prisée ces temps-ci. Le pari du CNAM Paris est que l’investissement par les auditeurs du CNAM dans un langage comme CAML leur donnera de bonnes bases de programmation, et qu’ils ne seront pas tentés par les mauvaises habitudes observées chez des programmeurs chevronnés, qui ralentissent le temps de développement des programmes ; ces mauvaises habitudes se traduisent en effet par un très grand nombre d’erreurs, coûteuses à corriger. Afin de donner un verni moins académique à cette approche de la programmation, le CNAM Paris fait suivre cet apprentissage de la programmation fonctionnelle par une approche plus classique, la programmation impérative. Cette dernière comble le second défaut (elle est très utilisée dans le monde professionnel), mais perd dans la pureté de la description du programme : de nombreuses considérations techniques (choix de réalisation) viennent interférer dans l’écriture des algorithmes, et il devient difficile de séparer ce qui relève de l’algorithmique de ce qui relève de choix techniques. Algorithmique et programmation en C++ Introduction 2 Le langage impératif préconisé par le CNAM Paris est ADA, reconnu par toute la communauté (professionnelle et académique) comme un langage rigoureux et puissant. L’un de ses concurrents est le langage C++. Ces deux langages ont pour intérêt de mixer deux approches de la programmation : une approche impérative et une approche objet. Cette dernière pénètre aujourd’hui en profondeur tous les secteurs du monde professionnel (le monde académique a été séduit depuis longtemps…), mais son apport reste presque nul quand aux aspects algorithmiques. Pour résumer, une approche objet d’un programme conduit à le penser en terme d’objets qui interagissent pour résoudre un problème donné. Autrement dit, c’est sur l’aspect décomposition d’un problème qu’elle focalise l’attention. Toutefois, à un moment donné, il faut bien résoudre un sous problème, et donc décrire un algorithme. Une critique souvent formulée par les auditeurs ayant assisté à ce cours à Montpellier (CAML puis ADA) est que la première partie en CAML est perçue comme inutile : pourquoi écrire un algorithme en CAML pour le traduire ensuite en ADA ? Autant écrire directement le programme en ADA, puisque si problème de conception il y a, ce problème apparaîtra dans les deux versions. Après diverses évolutions, nous avons choisi à Montpellier d’adopter C++ comme langage de programmation. Il sera aussi le langage de spécification pour des algorithmes décrits dans une forme impérative. Nous adopterons un langage ad hoc pour décrire des algorithmes récursifs. Clairement, le langage C++ n’atteint pas la pureté de description des algorithmes, comme peuvent le faire des langages comme CAML. Dans cette unité de valeur, seuls les aspects impératifs de C++ sont étudiés. Très peu d’éléments seront donnés sur ses aspects orientés objets, afin que les auditeurs qui le souhaitent puissent se référer aux ouvrages de référence du CNAM Paris sans être trop dépaysés. Les premiers programmes décrits dans ce support de cours ne sont pas opérationnels en l’état ; il leur manque un enrobage qui ne sera présenté que plus tard, durant les Travaux Pratiques (directives d’inclusion pour le pré-processeur, et fonction main pour les blocs). 1.2. GENERALITES Un algorithme est un plan d'actions, décrit selon un certain langage. Autrement dit, c’est une description d'une méthode à mettre en œuvre pour résoudre un problème. Exemple : une recette de cuisine est un algorithme : en suivant scrupuleusement ses instructions, la recette vous garantit l'obtention d'un bon petit plat ! Résoudre un problème c'est, partant de son énoncé initial, transformer cet énoncé en une suite d'énoncés. Si cette suite se termine, le dernier énoncé produit s'interprète comme la solution. Chaque transformation d'un énoncé en son successeur résulte de l'application d'une opération élémentaire de résolution. Un algorithme spécifie justement dans quel ordre doivent être appliquées ces opérations élémentaires pour obtenir la solution à un problème donné, quand elle existe. Algorithmique et programmation en C++ Introduction 3 La notion d'énoncé est attachée à celle de langage ; intuitivement, un énoncé est une phrase ou séquence de phrases exprimée dans un langage, par exemple la langue française. Cette langue s’appuie d’abord sur des caractères (lettres de l’alphabet, chiffres, signes de ponctuations), lesquels s’assemblent pour former des mots, lesquels forment des phrases, puis des textes. La notion de langage a été formalisée plus mathématiquement par N. Chomsky : un langage est un ensemble de mots, chaque mot étant une séquence de symboles. L’ensemble des symboles admissibles est appelé l’alphabet du langage. La syntaxe d'un langage est l'ensemble des règles qui permettent de construire des mots corrects ; cette syntaxe est décrite sous forme d’une grammaire. La sémantique d'un langage consiste à préciser comment ces mots, lorsqu'ils sont correctement formés, doivent être interprétés (quel est leur sens, i.e. leur sémantique). En général, interpréter un mot, c'est effectuer une suite d'actions qui traduit le sens qui lui a été attribué. Exemple : le langage qui permet de construire des expressions arithmétiques possède une syntaxe du type : • un chiffre est l'un des caractères 0, 1, …, 9 • un nombre est une succession de chiffres, éventuellement précédée du caractère + ou - • un nombre est une expression arithmétique • si a et b sont deux expressions, alors (-a), a+b, a-b, … sont des expressions • etc. Voici des exemples de constructions correctes (i.e. chacune forme un mot du langage) : -125+(34-87) (2)+(4+(4)) Les mots suivants ne font pas partie du langage des expressions arithmétiques : (34 : parenthèse fermante manquante 89a+3 : les lettres ne sont pas autorisées La sémantique de ce langage précise comment calculer la valeur d'une expression : • la valeur d'une expression composée d'un nombre est ce nombre • la valeur d'une expression de la forme a+b est le résultat de l'addition de la valeur de l'expression a avec la valeur de l'expression b. • etc. Réécrit en termes d'instructions exécutables dans un langage de programmation (c'est à dire codé), l'algorithme devient programme, autrement dit un énoncé compréhensible par la machine. Algorithmique et programmation en C++ Notions de variable et de type 4 2. NOTIONS DE VARIABLE ET DE TYPE Un programme qui s'exécute dans un ordinateur est un processus qui transforme le contenu de la mémoire. Chaque opération élémentaire ne modifie que quelques (i.e. un nombre fini de) cases mémoire à la fois. Cette façon d’observer un programme est trop primitive, car trop proche de la réalité des machines, c’est à dire à un niveau de détail beaucoup trop fin (c’était le point de vue adopté aux débuts de l’informatique, jusque dans les années 60). Une vision plus abstraite, développée ci-après, consiste à considérer qu'un programme manipule des ensembles structurés de variables dont les valeurs évoluent, appelés environnements. 2.1. VARIABLE Une variable se caractérise par son nom, sa valeur et son type. En pratique, une variable correspond à une zone de la mémoire centrale, i.e. un ensemble contigu de cases mémoire. Ainsi le nom d'une variable est une abstraction de celle d'adresse de la première case de la zone mémoire qui lui correspond. En revanche, la valeur d'une variable est une abstraction de la notion de contenu de cette même zone. La règle permettant d’interpréter le contenu effectif des cases mémoire associées comme une valeur est définie par le type. Exemple : indiquer qu'une variable de nom X et de type uploads/s3/ cours-cpp.pdf