Programmation et Algorithmique

10% de réduction sur vos envois d'emailing --> CLIQUEZ ICI

Retour à l'accueil, cliquez ici

Voir également : 

AADL_Edge_07.pdf.htm 18-Oct-2011 17:34 66K MATHEMATIQUESFINANCI ..> 29-Sep-2011 14:28 12K STATISTIQUEDESCRIPTI ..> 08-Oct-2011 11:48 15K approxautosemblabler ..> 29-Sep -2011 14:52 3.1k baseslogrecurrences.htm 29-Sep-2011 14:57 21K calculfinanciervaleu ..> 29-Sep-2011 14:31 100K elementsmathfi.htm 29-Sep-2011 14:40 15K financementetemprunt ..> 29 - Sep-2011 14:39 10K infocontextuelleweb.htm 29-Sep-2011 15:02 81K informationpersonnal ..> 29-Sep-2011 15:04 156K interrogationflexibl ..> 29-Sep-2011 15:09 13K martingalepourlafina ..> 08 -Oct-2011 11:48 47K mathematiquefinancie ..> 29-Sep-2011 17:54 45K mathfiPGM110.htm 29-Sep-2011 14:44 10K mathphysiquestatisti ..> 29-Sep-2011 14:55 22K methodestatistiquege ..> 18-Oct-2011 17:05 116K metiersmathematiques ..> 29-Sep-2011 14:51 114K probabilitesimulatio ..> 08-Oct-2011 11:48 96K rechercheinfobibliot ..> 29-Sep-2011 15:12 30K securiteinformatique. .> 29-Sep-2011 15:00 20K statistiqueelementai ..> 08-Oct-2011 11:48 101K 

STATISTIQUEDESCRIPTI ..> 08-Oct-2011 11:34 15K martingalepourlafina ..> 08-Oct-2011 11:38 47K probabilitesimulatio ..> 08-Oct-2011 11:47 96K statistiqueelementai ..> 08-Oct- 2011 11:26 101K 

Programmation et Algorithmique Ecole Polytechnique Jean Berstel et Jean-Eric  PinAvant-propos Ce polycopie est utilise pour le cours INF 421 intitule Les bases de la programmation et de l'algorithmique. Ce cours fait suite au cours INF 311 Introduction a l'informatique et precede le cours INF 431 intitule Fondements de l'informatique. Ce polycopie reprend et developpe les chapitres 10 et 11 du polycopie de Robert Cori, Jean-Jacques Levy et Francois Morain Les bases de la programmation et de l'algorithmique. Il fait egalement suite au polycopie de Francois Morain Les bases de l'informatique et de la programmation. Pour qu'il n'y ait pas confusion avec ce dernier polycopie, nous avons intitule le n^otre plus simplement Programmation et algorithmique. Comme le lecteur pourra le constater, nous avons suivi pour l'essentiel le canevas des cha- pitres 10 et 11 du polycopie de Robert Cori, Jean-Jacques Levy et Francois Morain, en incluant des applications et des developpements sur certaines variantes. Nous avons aussi insiste, au debut, sur le concept de reference, notion qui se retrouve d'ailleurs, sous le terme de pointeur, dans d'autres langages de programmation. Le theme principal du cours est, du c^ote de la programmation, la conception et la mise en uvre de nouveaux types. Le langage Java le permet de deux facons, par la creation de tableaux, et par la denition de classes. Quant a l'algorithmique, c'est la description et l'emploi de structures de donnees dynamiques qui sont au centre de ce cours. Nous traitons en detail les listes et les arbres. Leur usage dans la representation de sequences et d'ensembles ordonnes est particulierement developpe. Les applications concernent la gestion des partitions (< union- nd > en anglais), la compression de textes, les tetrarbres (< quadtrees >) et des problemes geometriques qui ne sont pas tous decrits dans cette premiere version du polycopie. Les structures plus elaborees, comme les graphes, seront etudiees dans le cours 431. Nous tenons a remercier en tout premier lieu Robert Cori, Jean-Jacques Levy et Francois Morain qui nous ont autorise a reprendre a notre compte certains elements de leurs polycopies. Nous remercions aussi nos collegues de l'Ecole  Polytechnique, et plus particulierement Philippe Chassignet, Emmanuel Coquery, Fabrice Le Fessant, Laurent Mauborgne, Eric  Schost, Alexandre Sedoglavic et Nicolas Sendrier qui ont largement contribue a l'elaboration et a la mise au point de ce cours. Enn nous sommes particulierement reconnaissants a Catherine Bensoussan et au service de reprographie de l'Ecole  Polytechnique pour leur travail exemplaire. Les auteurs peuvent ^etre contactes par courrier electronique aux adresses suivantes : berstel@univ-mlv.fr Jean-Eric.Pin@liafa.jussieu.fr On peut aussi consulter les pages Web des auteurs : http : //www-igm.univ-mlv.fr/~berstel http : //liafa.jussieu.fr/~jep 3Table des matieres I Complements de programmation 9 1 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1 Types et references . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 References d'objets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Methodes et variables statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Variables statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Methodes statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Methodes et variables nal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4 La classe String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 II Structures sequentielles 25 1 Listes cha^nees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.2 Fonctions simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.3 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Copie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.4 Une application : les polyn^omes . . . . . . . . . . . . . . . . . . . . . . . . 36 2 Listes circulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Parcours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 Variations sur les listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4 Hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.1 Adressage direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Tables de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 Resolution des collisions par cha^nage . . . . . . . . . . . . . . . . . . . . . 49 4.4 Adressage ouvert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 Choix des fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . . . . 52 56 TABLE DES MATIERES  IIIPiles et les 55 1 Piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.1 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2 Les exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.1 Syntaxe des exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.2 Levee d'exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3 Capture des exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3 Une application : l'evaluation d'expressions arithmetiques . . . . . . . . . . . . . . 64 4 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.1 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Implantation par tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Implantation par listes cha^nees . . . . . . . . . . . . . . . . . . . . . . . . 69 Choix de l'implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 IV Arbres 73 1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 1.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 1.2 Arbres libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 1.3 Arbres enracines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 1.4 Arbres ordonnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2 Union-Find, ou gestion des partitions . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.1 Une solution du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.2 Applications de l'algorithme Union-Find . . . . . . . . . . . . . . . . . . . 79 3 Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.1 Compter les arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.2 Arbres binaires et mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Ordres sur les mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Codage des arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3 Parcours d'arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.4 Une borne inferieure pour les tris par comparaisons . . . . . . . . . . . . . 83 4 Files de priorite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.1 Tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.2 Implantation d'un tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3 Arbres de selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5 Codage de Human . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.1 Compression des donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.2 Algorithme de Human . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Codes prexes et arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Construction de l'arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Choix de la representation des donnees . . . . . . . . . . . . . . . . . . . . 94 Implantation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.3 Algorithme de Human adaptatif . . . . . . . . . . . . . . . . . . . . . . . 97 V Arbres binaires 101 1 Implantation des arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 1.1 Implantation des arbres ordonnes par arbres binaires . . . . . . . . . . . . 104 2 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 2.1 Recherche d'une cle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 2.2 Insertion d'une cle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107TABLE DES MATIERES  7 2.3 Suppression d'une cle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 2.4 Hauteur moyenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3 Arbres equilibres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3.1 Arbres AVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 Implantation des rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Insertion et suppression dans un arbre AVL . . . . . . . . . . . . . . . . . 115 Implantation : la classe Avl . . . . . . . . . . . . . . . . . . . . . . . . . . 116 3.2 B-arbres et arbres a-b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Arbres a-b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Insertion dans un arbre a-b . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Suppression dans un arbre a-b . . . . . . . . . . . . . . . . . . . . . . . . . 120 VI Applications 123 1 Recherche dans un nuage de points . . . . . . . . . . . . . . . . . . . . . . . . . . 123 1.1 Construction de l'arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 1.2 Recherche de points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 2 Tetrarbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 3 Le probleme des N corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 3.1 Donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.2 Vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.3 Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.4 Arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.5 Calcul des forces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.6 Univers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Bibliographie 136 Index 137Chapitre I Complements de programmation Ce premier chapitre nous permettra de preciser certains points cruciaux de la programmation en Java. Une premiere section est consacree a l'etude detaillee des references, ou adresses. La seconde section fait le point sur les methodes et les variables statiques. Nous terminons par quelques rappels sur les methodes et les variables declares nal. 1 References L'utilisation des adresses se retrouve dans divers langages de programmation (Pascal, C, C++, Java, etc.) et peut para^tre un peu deroutante au debut. Elle devient limpide des que l'on en a assimile les principes de base et c'est la raison pour laquelle nous y consacrons cette section. 1.1 Types et references En Java, les donnees d'un programme se repartissent en deux categories selon leur type : les types primitifs et les autres. Les types primitifs comprennent les types d'entiers (byte, short, int, long), les types des reels ( oat, double), le type des caracteres (char) et le type des booleens (boolean). Les autres types sont les types de tableaux ou d'objets. Par exemple, String est un type d'objets, et int[] est le type d'un tableau d'entiers. La construction de tableaux et la denition de nouvelles classes sont les deux moyens de creer de nouveaux types a partir de types donnes. Ainsi, une denition comme class Personne { String nom; int age; } denit un nouveau type d'objets. Ces deux mecanismes s'embo^tent. Ainsi, class Annuaire { Personne[] liste; } denit un type d'objets ayant pour membres un tableau d'objets de type Personne. La manipulation des donnees dans un programme Java depend de leur type. La reference d'une donnee est l'adresse memoire ou est logee la donnee. La nature precise de l'adresse (entier, maniere de numeroter, etc) nous interesse peu. Une reference est de plus typee par le type de la donnee. 910 CHAPITRE I. COMPLEMENTS  DE PROGRAMMATION Regle. Les donnees de type primitif sont manipulees par valeur, les donnees des autres types sont manipulees par reference. Ainsi, le contenu d'une variable de type int est un entier, le contenu d'une variable de type char est un caractere, et plus generalement le contenu d'une variable de type primitif est une valeur de ce type. En revanche, le contenu d'une variable de type non primitif est l'adresse d'une donnee de ce type. La manipulation de references est bien plus limitee que la manipulation de types de base : on peut seulement les comparer (par == et !=) et les aecter. L'aectation est une aectation de references, et il n'y a donc pas de copie des donnees referencees ! On peut illustrer ce phenomene par un exemple concret. Si un ami vous annonce son demenagement et vous donne ses nouvelles coordonnees, une simple modication dans votre carnet d'adresses vous permettra de continuer a lui ecrire ou a lui telephoner. Bien entendu, cette modication n'a pas eu pour eet le demenagement ou le changement de la ligne telephonique de votre ami. C'est la m^eme chose en Java. Lorsqu'on modie une reference, cela n'entra^ne pas le deplacement physique des donnees, qu'il faudra donc realiser independamment si on le souhaite. Voici un premier exemple. public static void main(String[] args) { byte[] t = {5, 2, 6}; System.out.println("Tableau " + t) ; } Le resultat est > Tableau [B@f12c4e La deuxieme cha^ne s'interprete comme suit : les deux premiers caracteres representent le type d'un tableau d'octets (le crochet ouvrant [ signie < tableau > et B signie < octet')', le symbole '@' signie < adresse >, la n est l'adresse en hexadecimal. Remarque. (Cette remarque peut ^etre ignoree en premiere lecture) Lors d'une impression, la methode println cherche une representation des donnees sous la forme d'une cha^ne de caracteres. Celle-ci est fournie par la methode toString qui est denie pour tout objet. Par defaut, cette methode retourne une cha^ne de caracteres formee du nom de la classe, de '@' et de l'ecriture hexadecimale du code de hachage de l'objet. Par defaut, le code de hachage d'un objet est obtenu en hachant l'adresse de l'objet. Dans notre exemple, f12c4e est l'ecriture hexadecimale du code de hachage de l'adresse du tableau t. Frequemment, une classe redenit la methode toString. Par exemple, la classe String denit cette methode pour qu'elle retourne la cha^ne de caracteres contenue dans la donnee. Ainsi, la cha^ne "Tableau " est eectivement achee telle quelle. Une gure bien choisie aide beaucoup a la comprehension du comportement des references. Pour ce faire, la valeur associee a une variable n est dessinee dans une bo^te etiquetee par n. Dans la gure 1.1, on represente une variable entiere n dont la valeur est 2. Quand la valeur d'une variable est une reference, c'est-a-dire l'adresse d'une donnee, la valeur numerique de cette adresse est remplacee par une eche dirigee vers l'emplacement de la donnee. n 2 Fig. 1.1 { Une variable n contenant la valeur 2. Dans la gure 1.2, on represente une variable de tableau d'octets t. La valeur de cette variable est le debut de la zone memoire reservee au tableau d'octets.1. REF ERENCES  11 t @f12c4e @f12c4e 5 2 6 (a) t 5 2 6 (b) Fig. 1.2 { Une variable t contenant l'adresse d'un tableau de trois octets : (a) situation eective, (b) description symbolique. Quand une variable vaut null, cette valeur est indiquee par une petite croix, comme dans la gure 1.3. t Fig. 1.3 { Une variable t contenant la valeur null. Comme nous l'avons dit, les operations sur les adresses sont restreintes. Voici un exemple d'aectation. public static void main(String[] args) { byte[] t = {5, 2, 6}; byte[] s; s = t; System.out.println("Tableau " + t + " " + s) ; } Le resultat est > Tableau [B@f12c4e [B@f12c4e Avant l'aectation s = t, la valeur de s est indenie. Apres l'aectation, les variables designent le m^eme emplacement dans la memoire (voir gure 1.4). t 5 2 6 s (a) t 5 2 6 s (b) Fig. 1.4 { (a) avant aectation ; (b) apres aectation. En eet, l'instruction d'aectation s = t copie le contenu de t dans s comme toute aectation, et le contenu est l'adresse du tableau. Continuons notre exploration. En toute logique, puisque apres l'aectation s = t, les variables s et t designent le m^eme emplacement memoire, toute modication peut ^etre faite indistinctement via s ou t. En particulier, une modication via s se repere aussi via t. Le programme public static void main(String[] args)