Remerciez-le!

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

PROGRAMMATION ET STRUCTURES DE DONNÉES RAKOTOARISOA Tahiana Mai 2011 Je dédie c

PROGRAMMATION ET STRUCTURES DE DONNÉES RAKOTOARISOA Tahiana Mai 2011 Je dédie ce livre à la mémoire de mon arrière–grand–père Nicolas Chantereau dit « le bourru » petit paysan sans propriété dans un obscur hameau du Limousin homme sans diplôme ni reconnaissance officielle de son savoir et connu pourtant dans tout le canton pour le savoir–faire universel qu’il manifestait au service de tous. (Michel GAUTHIER – ADA, Un apprentissage) 2 SOMMAIRE SOMMAIRE................................................3 INTRODUCTION.......................................5 1ÈRE PARTIE. STRUCTURE D’UN ORDINATEUR 7 A. ARCHITECTURE PHYSIQUE...........7 1. Numération...........................................7 2. Booléen.................................................8 3. Entier naturel.........................................9 4. Entier relatif..........................................9 5. Réel.....................................................10 6. Caractère.............................................11 7. Opérateur et/ou....................................12 8. Ordinateur câblé..................................13 9. Ordinateur programmé........................14 10. Instruction.........................................15 11. Programme........................................16 12. Répertoire..........................................18 B. ARCHITECTURE LOGIQUE...........23 1. Programme principal [Main program]23 2. Booléen en C [Boolean]......................29 3. Entier naturel en C [Natural integer]. .31 4. Entier relatif en C [Integer].................33 5. Réel en C [Real]..................................36 6. Caractère en C [Character]..................39 7. Adresse [Pointer]................................40 8. Article [Record]..................................41 9. Variant.................................................43 10. Énumération......................................44 11. Structures de contrôle.......................44 12. Fonction [Function]..........................46 13. Programme en C...............................49 14. Classe................................................50 2ÈME PARTIE. STRUCTURES DE DONNÉES 53 A. STRUCTURES LINÉAIRES..............53 1. Tableau [Array]...................................53 2. Liste chaînée [Linked list]..................56 3. Liste contiguë......................................58 4. Texte [String]......................................59 5. Programme principal paramétré..........62 6. Fichier [File].......................................64 7. Liste triée [Sorted list]........................68 8. Liste bidirectionnelle..........................69 9. Pile [Stack]..........................................70 10. File [Queue]......................................71 3 11. File contiguë......................................72 12. Anneau [Ring]...................................73 B. STRUCTURES NON–LINÉAIRES...74 1. Arbre [Tree]........................................74 2. Arbre binaire [Binary tree]..................77 3. Récursion............................................78 4. Arbre binaire équilibré........................80 5. Tri rapide [Quick sort]........................82 6. Tas contigu [Heap]..............................83 7. Alternant–successeur..........................85 8. Dictionnaire.........................................86 9. Arbre basique......................................87 10. Table [Map]......................................88 11. Graphe [Graph].................................89 12. Graphe étiqueté [Labelled graph].....92 13. Processeur.........................................95 14. Hypercube.........................................98 15. Prédicat [Predicate]...........................98 16. Clause..............................................100 3ÈME PARTIE. PROBLÈMES............103 A. SIMPLES............................................105 1. Tas dynamique..................................105 2. Tas économique................................105 3. Union d’intervalles............................106 4. Transect.............................................107 5. Permutation par échange de voisins..108 6. Permutation par échange de distance minimum 109 7. Coloriage d’une carte........................110 8. Gardiens d’un musée.........................112 B. DIFFICILES.......................................113 1. Flot maximum...................................113 2. Multiprocesseur.................................116 3. Centre d’un graphe............................116 4. Points d’articulation..........................117 5. Triangulation de Delaunay................119 6. Arbre 2D équilibré............................120 7. Tracé d’un graphe planaire...............124 8. Voyageur de commerce....................125 9. Personnels.........................................126 CONCLUSION.......................................127 BIBLIOGRAPHIE....................................128 4 INTRODUCTION Entendre ou lire sans réfléchir est une occupation vaine, réfléchir sans livre ni maître est dangereux (CONFUCIUS – Analectes, 2 : 15) Ce petit ouvrage est un résumé des structures de données les plus connues en informatique. Destiné aux programmeurs, il pourrait être aussi utile à tous ceux qui doivent utiliser un ordinateur ou un logiciel quelconque puisque nous sommes convaincus qu’il faut d’abord connaître ce que c’est un arbre avant de manipuler des répertoires. La première partie pourrait être extrêmement rebutante mais nous n’avons pas trouvé d’autres moyens d’introduire l’informatique qu’en partant d’un domaine connu, totem ou tabou, qu’est la mathématique. Mais que le lecteur se rassure : il n’a besoin que du niveau des classes Terminales, à cause des logarithmes. Le câblage interne d’un ordinateur n’est utile qu’à ceux qui se sont demandé un (beau) jour, mais comment diable tout cela fonctionne–t–il ? En bref, cette partie ne doit pas être « apprise par cœur » comme l’atteste d’ailleurs l’absence du moindre exercice. Ce qui n’est pas le cas de la deuxième partie qui contient tout le bagage qu’un programmeur doit absolument avoir avant d’écrire un programme clair (« structuré » selon le vocable à la mode) et efficace. Ces structures de données sont abordées en premier cycle universitaire tandis que le parallélisme et la programmation déclarative sont enseignés en maîtrise. Tous les exercices doivent être traités pour que le lecteur puisse bien comprendre le pourquoi et le comment de telle ou telle instruction. C’est en forgeant que l’on devient forgeron, dit–on… et il semble difficile d’aborder la dernière partie sans ces exercices de « musculation ». En effet, la troisième partie contient des problèmes sur lesquels nous nous sommes cassé la tête pendant des mois, voire des années. Nous n’avons même pas trouvé la clé de certaines d’entre eux, comme la triangulation de Delaunay, ou le voyageur de commerce. Et encore, la majorité contienne des affirmations sans aucune démonstration, et conduisant à des programmes faux. Les solutions de tous les exercices n’ont pas été incluses dans cet ouvrage puisqu’un simple coup d’œil permettra au lecteur de trouver la « clé » de l’algorithme. Dans cet ouvrage, nous utilisons le langage C++, plus exactement le compilateur de Borland C++ version 5.02 sous Windows XP Professionnel. De temps en temps, nous utilisons également le compilateur de Microsoft Visual C++ 6.0, dont les messages d’erreurs et l’affichage des variables locales sont plus clairs. Mieux encore, C++Builder 5.0 indique dans le programme source où l’erreur a été provoquée et permet également le développement rapide d’application avec fenêtres (RAD – Rapid Application Developpement). Il existe des compilateurs C++ pour MS–DOS, Windows 16 ou 32 bits, Unix, OS/2 et suivant les normes ANSI C (American National Standards Institute) ou ANSI C++. Certains programmes n’existent pas pour certains compilateurs et nous les signalons toujours, ainsi que les fichiers d’en–tête (extension .h) dans lesquels ces programmes ont été écrits. Nous nous efforçons d’écrire des programmes compilables avec n’importe quel compilateur, et même avec un autre langage, sauf si nous ne pouvons pas faire autrement. Ce langage est presque complet (pointeur, type paramétré, polymorphisme, programme en argument d’un autre programme, programmation parallèle) sauf en ce qui concerne la programmation déclarative pour laquelle 5 nous utilisons le langage Prolog, plus exactement le SWI–Prolog version 5.6.6. téléchargeable gratuitement sur www.swi–prolog.org. Parfois, surtout dans la 3è partie, nous utilisons également le langage Ada, plus précisément le compilateur GNAT GPL Edition 2005 produit par AdaCore et téléchargeable gratuitement sur libre2.adacore.com. Dans la présentation de la syntaxe de ces langages (leur grammaire), nous utilisons les conventions suivantes – les textes qui doivent être écrits tels quels (terminaux) sont en courier new gras 0 – les noms qui doivent être remplacés par la définition correspondante sont en courier new normal cDec – la barre verticale | dénote le choix cDec = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 – la virgule , dénote la concaténation cWchar_t = L,cChar – les éléments entre crochets [ et ] sont obligatoires cChar = ',[nonApost,\'],' – les éléments entre parenthèses ( et ) sont facultatifs cNat = cDec,(cNat) – les éléments précédés d’un étoile * peuvent être répétés 0, 1 ou plusieurs fois cNat = cDec,*(cDec) Dans le texte proprement dit, nous utilisons les polices suivants – le corps de texte est en Times New Roman normal – les nouveaux termes et les mises en garde sont en Times New Roman gras. – les programmes et les noms de variables sont en Courier New normal noir. – les commentaires dans les programmes sont en Courier New normal gris. – les textes affichés par l’ordinateur sont en Courier New gras noir. Dans la présentation des programmes et fonctions prédéfinis, nous n’indiquons pas les noms des paramètres pour être plus concis (comme dans les messages d’erreurs). Les opérateurs sont aussi placés avant ou entre les paramètres sans le mot–clé operator. Si une fonction ne doit pas retourner un résultat, alors nous la présentons comme étant un programme void ( bool = bool ) ; au lieu de int operator = ( bool a, bool b ) ; Certaines fonctions, comme l’affectation ci–dessus, ne sont pas définies formellement ainsi. C++ est une amélioration du langage C où de telles définitions étaient encore interdites. De même, les types prédéfinis comme bool ne sont pas vraiment des classes (il n’y a pas de classe en C) class bool ; 6 1ère PARTIE. STRUCTURE D’UN ORDINATEUR A. ARCHITECTURE PHYSIQUE 1. Numération Le problème de la numération est celui de l’écriture de tous les nombres avec un ensemble fini de symboles appelés chiffres 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,… Le nombre x noté unun-1...u1u0,u-1u-2... qui est une suite de chiffres, représente un polynôme en a, a étant la base de numération x = un an + un-1 an-1 + ... u1 a + u0 + u-1 a-1 + u-2 a-2 + ... Par exemple, dans le système décimal (base 10) 42,785 = 4*101 + 2*100 + 7*10-1 + 8*10-2 + 5*10-3 = 4*10 + 2*1 + 7*0,1 + 8*0,01 + 5*0,001 = 40 + 2 + 0,7 + 0,08 + 0,005 Le nombre 43,1255 écrit en base 5 est égal à 43,1255 = 4*51 + 3*50 + 1*5-1 + 2*5-2 + 5*5-3 = 4*5 + 3*1 + 1*0,2 + 2*0,04 + 5*0,008 = 20 + 3 + 0,2 + 0,08 + 0,04 = 23,32 Le nombre 453,7 est écrit en base en 10. Pour l’écrire en base 7, calculons le nombre x tel que 7x ≤ 453,7 < 7x+1 : x est la partie entière du logarithme base 7 de 453,7 log7 453,7 = (log 453,7 / log 7) ≈ 3,143 Þ x = 3 Divisons alors 453,7 par 73, puis le reste de cette division par 72, etc. 453,7 ÷ 73 = 1 reste uploads/Ingenierie_Lourd/ 2003-liste-chainee.pdf