Remerciez-le!

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

I.U.T. de Marne-La-Vallée Introduction à l'informatique et programmation en lan

I.U.T. de Marne-La-Vallée Introduction à l'informatique et programmation en langage C (DUT Génie Thermique et Energie) Jean Fruitet Jean.Fruitet@univ-mlv.fr 1999 Introduction à la programmation Jean Fruitet - IUT de Marne La Vallée - 2 I.U.T. de Marne-La-Vallée Introduction à l'informatique et programmation en langage C (DUT Génie Thermique et Energie) Jean Fruitet Jean.Fruitet@univ-mlv.fr Avertissement 3 Caractérisation d’un problème informatique 3 Introduction à l’informatique 5 Le codage binaire 7 Notion d’algorithme et de machine à accès direct 14 Langage C 19 Processus itératifs 43 Fonctions et sous-programmes 44 Notion de complexité 48 Des données aux structures de données : tableaux, calcul matriciel 50 Calcul numérique : fonctions numériques, résolution d'équation, intégration 61 Structures de données : ensembles, listes, piles, files, hachage, arbres, graphes 76 Algorithmes de tri 112 Bibliographie 123 Table des matiéres 122 Introduction à la programmation Jean Fruitet - IUT de Marne La Vallée - 3 Avertissement Ce cours s’adresse aux étudiants de première année de DUT de Génie Thermique et Energie (GTE). Il leur est présenté en quelques dizaines d’heures —une trentaine— les rudiments de la programmation numérique et des notions d’algorithmique. Ces étudiants n'étant pas destinés à une carriére d’informaticien professionnel, je n’aborde pas l’algorithmique dans tous ses raffinements. En particulier les notions pourtant fondamentales de preuve de programme et d’analyse de complexité ne sont pas évoquées. Ce cours est divisé en quatre parties : - notion d'informatique et de codage ; - structure d'un ordinateur : la machine à accès direct (MAD / RAM) ; - langage de programmation : le langage C ; - algorithmique numérique et structures de données. Après quelques notions de théorie de l'information et de codage (codage binaire, représentation des entiers et des flottants) j'introduis la programmation de fonctions numériques sur ordinateur PC sous MS-DOS puis l'utilisation de quelques structures de données fondamentales (tableaux, piles, files, arbres, graphes) et les principaux algorithmes de tri. Ce cours ne fait donc aucune place à la technologie des ordinateurs, leur architecture, système d'exploitation et de fichiers. Il n'est pas non plus question d'apprentissage de logiciels bureautiques (traitement de texte ou de tableur). Ce n'est pas que ces connaissances ne soient pas nécessaires aux techniciens, mais je laisse à d'autres enseignants le soin d'y contribuer. S’agissant de la syntaxe d’un langage de programmation, j’introduis le langage RAM, pour passer rapidement au langage C. J'insiste beaucoup dans ce cours sur la nécessité d'une programmation structurée descendante. Cette démarche est recommandée depuis des lustres par tous les spécialistes. Malheureusement l'expérience montre que livré à lui-même le programmeur moyen se permet des libertés qui rendent rapidement ses programmes illisibles et inutilisables. Mais ce ne sera pas faute d'avoir été prévenu... Caractérisation d’un problème informatique L'art de programmer, c'est l'art de faire résoudre des problèmes par des machines. Il s’agit bien d’un art, au sens de l’artisan, qui passe par une longue période d’apprentissage et d’imitation. Dans cet exercice certains individus ont des dispositions naturelles ; pour les autres un apprentissage rigoureux fournit les rudiments d’une méthode. Le reste est affaire de travail et d’investissement personnels. Un ordinateur est dénué d’intelligence ; il ne peut donc résoudre que les problèmes pour lesquels existe une méthode de résolution algorithmique, c’est-à-dire une recette déterministe. De plus, même si la recette existe en théorie pour résoudre tel problème, encore faut-il que l’énoncé du problème — l’espace des paramètres— et l’ensemble des solutions soient de dimension finie, en raison de la limitation en taille de la mémoire des machines. Enfin, condition ultime, la mise en oeuvre d’un algorithme doit avoir une durée finie. Un problème dont la solution nécessite de disposer d’un temps infini n’est pas considéré comme résoluble par ordinateur. Ces trivialités vont donc limiter nos ambitions de programmeur à une classe de problèmes assez restreinte, d’autant que ne nous disposons pas de puissantes machines de calcul. Introduction à la programmation Jean Fruitet - IUT de Marne La Vallée - 4 2.1. Le traitement de l’information L’informatique est la science du traitement de l’information. Une information est un élément de connaissance susceptible d’être codé, transmis et traité de manière automatique. Le codage numérique en nombres binaires étant adapté à la conception de machines électroniques, une partie essentielle du cours d’informatique porte sur la représentation des nombres et la logique (algèbre de Boole) binaires. Je considèrerai comme acquises les notions d’opération élémentaire (addition, soustraction, multiplication et division réelle et euclidienne) sur les ensembles de nombres naturels, relatifs, rationnels, réels et complexes, qui ne seront pas redéfinies, non plus que les opérations ensemblistes union, intersection, complémentation, ni les notions de relation binaire, relation d’équivalence et relation d’ordre partiel ou total. Concernant les notions de constante numérique, de variable, d’instruction d’affectation, de test, de boucle, qui sont au centre des techniques de programmation, elles seront redéfinies ou précisées selon les besoins. 2.2. Quelques exemples de problèmes L’ordinateur fonctionne en binaire, mais il peut résoudre des problèmes autres que numériques. Et bien que le calculateur électronique soit l’instrument privilégié de l’ingénieur, ce n’est pas en programmant des problèmes numériques qu’on apprend le plus efficacement à programmer. Pourtant il est de tradition dans les sections techniques et scientifiques de commencer par des exercices numériques : - Résoudre une équation du second degré à coefficients réels dans le corps de nombres complexes. - Programmer la division euclidienne de deux entiers en n’employant que des soustractions. - Trouver le plus grand diviseur commun de deux nombres naturels (PGDC). - Enumérer les n premiers nombres premiers. - Tester la conjecture polonaise. - Calculer le nième élément de la suite de Fibonacci. - Calculer le minimum, le maximum, la moyenne et l’écart-type d’une distribution numérique. - Calculer les zéros d’un polynome, tracer graphiquement le graphe d'une fonction numÉrique - inverser une matrice. D’autres problèmes qui ne sont pas strictement numériques sont pourtant tout aussi instructifs pour l’art de la programmation. Ils seront soit traités soit évoqués : - Trouver un mot dans un dictionnaire. - Construire un arbre hiérarchique - Ordonner une liste de mots. - Fusionner deux listes de mots déjà ordonnés. - Enumérer les parcours d’un graphe et trouver le plus court chemin entre deux sommets. - Filtrer une image, etc. Démarche Partant d’un problème élémentaire nous montrerons comment le reformuler en des termes susceptibles d’être traités par un ordinateur idéal. Puis nous coderons ces algorithmes en langage C. Nous encourageons le lecteur à implanter ses propres solutions, à les modifier, éventuellement les améliorer ou à les réutiliser pour d’autres applications. Introduction à la programmation Jean Fruitet - IUT de Marne La Vallée - 5 Tous les exemples fournis en C ont été testés sur compilateur Turbo C sur PC et Think C sur Macintosh. Je remercie par avance celles et ceux qui voudront bien me transmettre remarques et suggestions. Introduction à l’informatique L'Informatique est la science du traitement automatique de l'information. La notion d'information est assez générale. Pour l'informatique elle prend un sens particulier : Une information est un élément ou un système de connaissance pouvant être transmis au moyen d'un support et d'un codage approprié et pouvant être compris. Par exemple des hiéroglyphes (codage) sur un papyrus égyptien (support) constituent une information sur la société égyptienne antique dés qu'on a été en mesure de les lire et d'en comprendre le sens (Champollion au XIXéme siècle). Une information est une fonction du temps, puisque le contenu d'un message est sujet à changer au cours du temps. L'information "La mer est 'calme' dans le Golfe de Gascogne" est particulièrement périssable... Quand le vent se léve et que la houle se forme, la mer devient 'agitée'. L'état de la mer est une information qui peut prendre des valeurs différentes, au cours du temps. Langage La plupart des informations que les Humains échangent sont supportées par un langage, c'est-à- dire des groupes de sons (les mots), qu'il faut assembler "d'une certaine manière" (grammaire) pour que les phrases aient un sens... Avec l'invention de l'écriture, ces mots ont eu une transcription (recodage) sous forme de symboles graphiques (des formes) dessinés ou imprimés. Le concept de mot est fondamental en informatique, de même que celui de langage. Un langage est un ensemble de mots construits avec les lettres choisies dans un alphabet. Les mots sont assemblés en phrases selon des régles de grammaire précises qui définissent la syntaxe du langage. Le sens attaché à ces phrases, c'est-à-dire leur signification, constitue la sémantique. L'essentiel de ce cours va consister à expliquer comment sont commandées les machines que nous nommons ordinateurs, capables d'exécuter des tâches complexes de traitement de l'information. Traitement de l'information Le traitement de l'information consiste en une suite d'opérations transformant une représentation de cette information en une autre représentation plus facile à manipuler ou à interpréter. Exemples : "3*2" remplacé par "6" "Mille neuf cent quatre vingt treize" est remplacé par "1993" "La somme des carrés des côtés de l'angle droit d'un triangle rectangle est égale au carré de l'hypoténuse" est remplacé par "Théoréme de Pythagore" "Championne olympique 1992 et 1996 du 400 mètres féminin" est remplacé par "Marie-José Pérec". Dans une uploads/Science et Technologie/ language-c.pdf