Remerciez-le!

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

J. Barré,P. Le certen,Y. Le Tertre, L. Morin, L. Ungaro Licence Sciences et Tec

J. Barré,P. Le certen,Y. Le Tertre, L. Morin, L. Ungaro Licence Sciences et Technologies Module API Approche impérative. Mise en œuvre en Java Juin 2007 Version 4 118 Copyright © J. Barré,P. Le certen,Y. Le Tertre, L. Morin, L. Ungaro - Ifsic - Université de Rennes 1 La reproduction non autorisée d'une œuvre protégée constitue un délit. LICENCE SCIENCES ET TECHNIQUES MÉTHODES ET OUTILS ALGORITHMIQUES APPROCHE IMPÉRATIVE (MODULE API) Version 4 - juin 2007 Jacques Barré, Pascale Le Certen, Lucien Ungaro Module A.P.I. Algorithmique Programmation Impérative Université de Rennes 1 1 CHAPITRE 1 Introduction 5 1.1 Algorithmes, langages de programmation, programmes 5 1.1.1 Langages de programmation 6 1.1.2 Algorithmes en langages déclaratifs 6 1.1.3 Algorithmes en langages impératifs 8 1.2 Rigueur, syntaxe et sémantique 9 1.3 Résolution d’un problème 10 1.3.1 Phase d’analyse et phase de programmation 10 1.3.2 Méthodes d’analyse 10 1.3.3 Qualités d’un programme 11 1.4 Exemple introductif 11 1.4.1 Analyse 12 1.4.2 Rédaction du programme 12 1.4.3 Compilation - exécution 14 CHAPITRE 2 Introduction aux types de données 19 2.1 Notion de type 19 2.2 Intérêt des types 20 2.2.1 Cohérence des données 20 2.2.2 Nécessité technologique de représenter correctement l’information 20 2.2.3 Intérêt technologique de déterminer les besoins en mémoire 21 2.3 Panorama des diverses catégories de types 21 2.4 Utilisations des types 22 2.4.1 Déclarations 22 2.4.2 Exemples d’opérations sur des données de types primitifs 23 2.5 Description des types scalaires 24 2.5.1 Types primitifs scalaires 24 2.5.2 Types énumérés 27 CHAPITRE 3 Déclarations, fonctions, expressions, instructions 35 3.1 Structure de programmes simples 35 3.2 Déclarations de données 36 3.2.1 Les diverses sortes de données 36 3.2.2 Intérêt des déclarations de constantes 37 3.3 Déﬁnitions de fonctions 39 3.4 Commentaires de spéciﬁcation d’une fonction 41 3.5 Instructions et expressions 42 3.5.1 Séquences d’instructions 42 3.5.2 Instructions d’afﬁchage à l’écran 43 3.5.3 Expression de concaténation de chaînes de caractères 44 3.5.4 Instruction de retour de fonction 44 3.5.5 Expressions 45 3.5.6 Appel de procédure - Appel de fonction 47 3.5.7 Variables et instruction d’affectation 49 3.5.8 Instructions de lecture du clavier 50 2 Module A.P.I Algorithmique Programmation Impérative Université de Rennes 1 CHAPITRE 4 Nommage, portées d’identiﬁcation, durées de vie, modularité 57 4.1 Nommage 57 4.2 Portées d’identiﬁcation 58 4.3 Durées de vie 59 4.4 Identiﬁcation temporaire - blocs d’instructions 60 4.5 Modularité 62 4.5.1 Découpage en classes 62 4.5.2 Paquetages 63 CHAPITRE 5 Instructions conditionnelles 69 5.1 Forme générale de l’instruction conditionnelle 69 5.2 Imbrication de conditionnelles 72 5.3 Aiguillage 74 CHAPITRE 6 Récursivité et itération 81 6.1 Exprimer la répétition 81 6.1.1 Méthode récursive 81 6.1.2 Méthode itérative 82 6.2 Récursivité 83 6.2.1 Exemples de déﬁnitions récursives de fonctions 83 6.3 Terminaison d’un algorithme récursif 84 6.4 Généralités sur l’Itération 85 6.4.1 Forme générale d’une itération 85 6.4.2 Premier exemple de calcul itératif : racine carrée 86 6.4.3 Itération sur une composition de plusieurs variables 86 6.4.4 Trace d’exécution d’une itération 88 6.4.5 Petits ennuis dus à l’absence d’affectation multiple 89 6.5 Notions d’invariant de boucle et de fonction de terminaison 90 6.5.1 Construction d’une itération 90 6.5.2 Invariant de boucle 92 6.5.3 Fonction de terminaison et notion de complexité 94 6.5.4 Autre exemple d’invariant de boucle et de fonction de terminaison 95 6.6 Itérations sur des entrées de données 95 6.7 Boucle pour faire n fois 97 6.8 Boucles à résultat polymorphe 100 CHAPITRE 7 Type énuméré, type structure, notion de référence 115 7.1 Type énuméré 115 7.2 Type structure 117 7.2.1 Déﬁnition d’un type structure 117 7.2.2 Création de structure - désignation par référence 119 7.2.3 Sélection de champ 121 7.2.4 Comparaison des références - comparaison des valeurs 122 7.2.5 Références en paramètre et en résultat 123 7.2.6 Exemple récapitulatif 123 Module A.P.I. Algorithmique Programmation Impérative Université de Rennes 1 3 CHAPITRE 8 Chaînes de caractères 133 8.1 Type chaîne de caractères 133 8.2 Quelques opérations disponibles sur les chaînes de caractères 135 8.3 Exemple de manipulations de chaînes de caractères 137 CHAPITRE 9 Tableaux 143 9.1 Intérêt des tableaux 143 9.2 Création et nommage des tableaux en Java 144 9.3 Accès aux éléments de tableau 145 9.4 Conséquences de la désignation par référence 146 9.5 Déclarations de tableaux initialisés 147 9.6 Exemples d’utilisation de tableaux 149 9.7 Raisonnement sur les tableaux - notion de tranche 150 9.8 Tableaux à plusieurs dimensions 154 CHAPITRE 10 Objets de type classe - abstraction 173 10.1 Approche “variable de type structure” - approche “objet” 173 10.1.1Approche “variable structurée” 173 10.1.2Approche objet 175 10.1.3Citation explicite de l’instance courante : t h i s 1 7 6 10.1.4Encapsulation - notion d’abstraction 177 10.2 Exemple récapitulatif 180 10.3 Retour sur les composants statiques et non statiques 181 10.4 Commentaires de spéciﬁcation pour une classe modèle d’objets 183 CHAPITRE 11 Structures de données : listes 191 11.1 Notion de structure de données 191 11.2 Spéciﬁcation du type liste 192 11.3 Exemples d’utilisation d’une liste 195 11.4 Mise en œuvre des listes 197 11.4.1Représentation des éléments d’une liste 197 11.4.2Parcours de listes 201 11.5 Précisions sur les classes internes 206 CHAPITRE 12 Utilisation des ﬁchiers 211 12.1 Fichiers séquentiels de texte 211 12.2 Utilisation de ﬁchiers textes en Java 212 12.2.1Lecture de ﬁchiers textes 212 12.2.2Écriture de ﬁchiers textes 214 CHAPITRE 13 Structures de données : ensembles 217 13.1 Spéciﬁcation du type ensemble 217 13.2 Exemples d’utilisation d’ensembles 219 13.3 Mise en œuvre des ensembles 219 4 Module A.P.I Algorithmique Programmation Impérative Université de Rennes 1 CHAPITRE 14 Structures de données : arbres 237 14.1 Spéciﬁcation de la classe A r b r e B i n a i r e 2 3 8 14.2 Exemples simples d’utilisation de la classe A r b r e B i n a i r e 2 3 9 14.3 Mise en œuvre de la classe A r b r e B i n a i r e 2 4 0 14.4 Autre exemple d’utilisation de A r b r e B i n a i r e 2 4 4 14.5 Spéciﬁcation de la classe A r b r e 2 4 5 14.6 Exemple d’utilisation de la classe A r b r e 2 4 6 14.7 Mise en œuvre de la classe A r b r e 2 4 9 CHAPITRE 15 Représentation des informations dans les ordinateurs 253 15.1 Nombres et représentations de nombres 253 15.1.1Notion de représentation 253 15.1.2Numérations positionnelles 253 15.1.3Chiffres binaires : bit 255 15.2 Mémoire 256 15.3 Représentations usuelles des types simples 256 15.3.1Représentation des caractères : ASCII et UNICODE 257 15.3.2Représentation des entiers positifs : binaire 258 15.3.3Représentation des entiers relatifs : complément à 2 259 15.3.4Représentation des nombres réels 262 15.4 Représentation des types composites : structures, objets, tableaux 265 15.4.1Représentation des structures et des objets de type classe 265 15.4.2Représentation des tableaux 266 15.5 Opérations sur les réels - erreurs 267 15.5.1Addition - soustraction 267 15.5.2Multiplication - Division 267 15.5.3Erreurs dans les calculs sur les réels 267 15.5.4Erreurs lors des additions et des soustractions 268 ANNEXE 1 Installations 271 Installation de Java 271 Test de l’installation de java 271 Ajout de paquetages 272 Installation d’Eclipse 273 Ouverture d’un projet Eclipse 273 Création d’une classe 274 Exécution 275 ANNEXE 2 Paquetages pour les exercices 277 Entrées-sorties clavier et fichiers textes 277 Listes 281 Ensembles 286 Introduction Module A.P.I. Algorithmique Programmation Impérative Université de Rennes 1 5 CHAPITRE 1 Introduction 1.1 Algorithmes, langages de programmation, programmes • Un algorithme est la description des opérations qui permettent d’accomplir une tâche. Cette tâche peut être un calcul, une transformation d’information, voire un procédé de fabrication. L’usage d’algorithmes est en fait assez répandu. Un modèle de tricot, une recette de cuisine... sont des algorithmes. Un algorithme doit être une description précise, mais pas nécessairement exprimé dans un langage prédéﬁni. Tous les moyens d’expression sont acceptables : langue naturelle, agrémentée de mathématiques, de croquis... • Un langage de programmation est un langage rigoureux, compréhensible par une machine, qui permet d’exprimer sans aucune ambiguïté des algorithmes. • Un programme est un algorithme exprimé dans un langage de programmation. Objectif du cours “algorithmique et programmation impérative” Le but de ce cours est l’apprentissage des bases de l’algorithmique. L’algorithmique est la science des méthodes automatiques de calcul. Le terme “calcul” doit être compris au sens large, à savoir la manipulation d’informations de toutes sortes. Ce module s’intéresse aux algorithmes de style “impératif”, c’est-à-dire construits à l’aide d’instructions qui agissent sur des données. Les instructions sont enchaînées au moyens de structures de contrôle usuelles : conditionnelle, itération et appel de fonction. Dans la première partie de ce cours, les types des données manipulées sont limités aux types primitifs simples (nombres entiers, nombres réels, caractères, booléens), aux structures, aux chaînes de caractères et aux tableaux. Les outils plus sophistiqués permettant l’invention de types de données abstraits seront étudiés dans une deuxième partie. L’algorithmique est non seulement une science, mais aussi une technique. Le but de ce cours est de réaliser effectivement des programmes. Pour cela il faut connaître un langage de pro- grammation. uploads/Litterature/ java-l2.pdf