:: wikimiki.org ::

Structure De Données

Structure de données

En informatique, structure de données une structure logique destinée à contenir des données, afin de leur donner une organisation permettant de simplifier leur traitement.

Pourquoi organiser les données?

Pour prendre un exemple de la vie quotidienne, on peut présenter des numéros de téléphone par département, par nom, par profession (comme les Pages jaunes), par numéro téléphonique (comme les annuaires destinés au télémarketing), par rue et/ou une combinaison quelconque de ces classements. À chaque usage correspondra une structure d'annuaire appropriée. En organisant d'une certaines manière les données, ont permet un traitement automatique de ces dernières plus efficace et rapide. Le fait d'utiliser une structure de données approprié à un traitement peut également faire baisser de manière significative la complexité d'une application et ainsi participer à faire baisser le taux d'erreurs.

Types de collections

Collections séquentielles

Une collection séquentielle permet de ranger des objets dans un ordre arbitraire. On parle de collection indexée quand on peut accéder à chaque élément de la collection par un numéro d'orde (l'index). Le choix d'une implémentation particulière dépend d'un certain nombre de compromis, comme l'occupation mémoire ou les performances requises pour diverses opérations de base : itération, ajout d'un élément (au début, à la fin ou encore dans un emplacement quelconque de la collection), indexation, suppression d'un élément, décompte du nombre d'éléments, etc... Il existe deux grands types de collections séquentielles :
- les listes
- les tableaux ou vecteurs Un certain nombre de structures de données sont des restrictions de collections séquentielles, qui n'autorisent qu'un sous ensemble des opérations de base :
- Pile
- File

Files à priorités

Le type abstrait file à priorités est une collection d'éléments indexés par des clés sur lesquels ont peut effectuer deux opérations: l'insertion d'un élément et l'extraction de l'élément de plus grande clé.
- Tas ou tas binaire On peut implémenter une union sur les files à priorité:
- Tas binomial
- Tas de Fibonacci

Tables de symboles ou collections mappées

Ce type de collection nommé dictionnaire ou map permet de ranger des objets en fonction d'une clef dans une table de symboles. La clef doit généralement respecter un certain nombre d'invariants pour être valide (valeur de hachage ou résultats de la comparaison par exemple).
- Table de hachage
- Arbre binaire de recherche ou ABR
- Arbre balancé ou arbre à critère d'équilibre.
- Arbre AVL
- Arbre 2-3-4
- Arbre rouge-noir ou arbre SBB (Symetric Binary Tree)
- Arbre B ou B-Tree

Autres collections

- Buffer tournant
- Graphes

Lien externe

- [http://fastnet.univ-brest.fr/~gire/COURS/ALGO_C/moncours.html Algorithmique et Structure de données] Catégorie:Algorithmique ja:データ構造 ko:자료구조 th:โครงสร้างข้อมูล

Informatique

ko:컴퓨터 과학 ja:情報工学 simple:Computer science th:วิทยาการคอมพิวเตอร์ zh-cn:计算机科学 zh-tw:計算機科學 oc:informatica] Etymologiquement, Le terme informatique désigne l'automatisation du traitement de l'information par une machine (virtuelle ou physique). Dans son acception courante, l'informatique désigne de façon vague l'ensemble des sciences et techniques en rapport de près ou de loin avec l'information et l'ordinateur. Par exemple, l'informatique désigne aussi bien le matériel informatique que la conception et l'administration de la partie immatérielle d'un ordinateur : les logiciels. La traduction anglaise étymologique serait informatics, mais l' usage tant en français qu'en anglais fait qu'une meilleure traduction serait probablement computer science, bien que ce terme fasse peut-être référence de façon plus explicite à ce que l'on pourrait appeler informatique fondamentale ou informatique scientifique. En anglais les termes distincts suivants sont utilisés :
- L'informatique fondamentale (Computer Science), ce qui ressort de l' épistémologie procédurale, soit notamment de l'étude des algorithmes, et donc indirectement des logiciels et des ordinateurs.
- L'ingénierie informatique (Computer Engineering), ce qui ressort de la fabrication et de l'utilisation du matériel informatique.
- L'ingénierie logicielle (Software Engineering), ce qui ressort de la modélisation et du développement des logiciels; ceci comprend le traitement des données (Data Processing), ce qui est du domaine de la mise en pratique des traitements de données.
- L'évolution des techniques et des technologies reliées à l'informatique (Information Technology). Des professions aussi diverses que concepteur, développeur, responsable d'exploitation, ingénieur système, technicien de maintenance, matérielle ou logicielle, chercheur en informatique ou directeur d'un centre de calcul, relèvent du domaine de l'informatique. Néanmoins, le terme informaticien désigne le plus souvent ceux qui conçoivent, déploient et mettent en œuvre des solutions.

Étymologie

Le terme informatique a été créé en mars 1962 par Philippe Dreyfus à partir des mots «information» et «automatique». Il donna ce nom à l'entreprise qu'il venait de fonder, la Société d'Informatique Appliquée, sans breveter le mot informatique. En France, l'usage officiel du mot a été consacré par Charles de Gaulle qui, en Conseil des ministres, a tranché entre «informatique» et «ordinatique», et le mot fut choisi par l'Académie française en 1967 pour désigner cette nouvelle discipline. En juillet 1968, le ministre fédéral de la Recherche scientifique d'Allemagne, Gerhard Stoltenberg, prononça le mot informatik lors d'un discours officiel au sujet de la nécessité d'enseigner cette nouvelle discipline dans les universités de son pays, et c'est ce mot qui servit aussitôt à nommer certains cours dans les universités allemandes. Le mot informatica fit alors son apparition en Italie et en Espagne, de même quinformatics au Royaume-Uni. Pendant le même mois de mars 1962 Walter F. Bauer inaugura la société américaine Informatics Inc., qui elle breveta son nom et poursuivit toutes les universités qui utilisèrent ce nom pour décrire la nouvelle discipline, les forçant à se rabattre sur computer science, bien que les diplômés qu'elles formaient étaient pour la plupart des praticiens de l'informatique plutôt que des scientifiques au sens propre. L'Association for Computing Machinery, la plus grande association d'informaticiens au monde, approcha même Informatics Inc. afin de pouvoir utiliser le mot informatics pour remplacer l'expression computer machinery, mais l'entreprise déclina l'offre. La société Informatics Inc. cessa ses activités en 1985, achetée par Sterling Software.
Histoire
Voir l'article détaillé : Histoire de l'informatique
Les origines
Depuis des millénaires, l'Homme a créé et utilisé des outils l'aidant à calculer (abaque, boulier, etc.). Les premières machines mécaniques apparaissent entre le XVIIe et le . La première machine à calculer mécanique réalisant les quatre opérations aurait été celle de Wilhelm Schickard au , mise au point notamment pour aider Kepler à établir les tables rudolphines d'astronomie. En 1642, Blaise Pascal réalisa également une machine à calculer mécanique qui fut pour sa part commercialisée et dont neuf exemplaires existent dans des musées comme celui des Arts et métiers et dans des collections privées (IBM). La découverte tardive du mécanisme d'Antikhitère montre que les Grecs de l'Antiquité eux-mêmes avaient commencé à réaliser des mécanismes de calcul en dépit de leur réputation de mépris général pour la technique (démentie d'ailleurs par les travaux d'Archimède). Cependant, il faudra attendre la définition du concept de programmation (illustrée en premier par Joseph Marie Jacquard avec ses métiers à tisser à cartes perforées, suivi de Boole et Ada Lovelace pour ce qui est d'une théorie de la programmation des opérations mathématiques) pour disposer d'une base permettant d'enchaîner des opérations élémentaires de manière automatique.
L'informatique moderne
L'ère des ordinateurs modernes commença avec les développements de l'électronique pendant la Seconde Guerre mondiale, ouvrant la porte à la réalisation concrète de machines opérationnelles. Au même moment, le mathématicien Alan Turing théorise le premier ce qu'est un ordinateur, avec son concept de machine universelle de Turing. L'informatique est donc un domaine fraichement développé, même s'il trouve ses origines dans l'antiquité (avec la cryptographie) ou dans la machine à calculer de Blaise Pascal, au . Ce n'est qu'à la fin de la Seconde Guerre mondiale qu'elle a été reconnue comme une discipline à part entière et a développé des méthodes, puis une méthodologie qui lui étaient propres. Son image a été quelque temps surfaite : parce que les premiers à programmer des ordinateurs avaient été des ingénieurs rompus à la technique des équations différentielles (les premiers ordinateurs, scientifiques, étaient beaucoup utilisés à cette fin), des programmeurs sans formation particulière, parfois d'ailleurs issus de la mécanographie, cherchaient volontiers à bénéficier eux aussi de ce label de rocket scientist afin de justifier des salaires rendus confortables par :
- le prix élevé des ordinateurs de l'époque (se chiffrant en ce qui serait des dizaines de millions d'euros aujourd'hui compte-tenu de l'inflation, il reléguait au second plan les considérations de parcimonie sur les salaires) ;
- l'aspect présenté comme peu accessible de leur discipline et un mythe de difficulté mathématique entretenu autour. En fait, les premiers ordinateurs ne se programmaient pas de façon très différente de celle des calculatrices programmables utilisées aujourd'hui dans les lycées et collèges, et maîtrisées par des élèves de quatorze ans mais le domaine était nouveau et l'algorithmique nécéssite un certain degré de concentration associé, peut-être à tort, à la réflexion pure. L'émergence d'un aspect réellement scientifique dans la programmation elle-même (et non dans les seules applications scientifiques que l'on programme) ne se manifeste qu'avec la série The Art of Computer Programming de Donald Knuth, professeur à l'Université de Stanford, à la fin des années 1960, travail monumental encore inachevé en 2004. Les travaux d'Edsger Dijkstra, Niklaus Wirth et Christopher Strachey procèdent d'une approche également très systématique et elle aussi quantifiée. On demandait à Donald Knuth dans les années 1980 s'il valait mieux selon lui rattacher l'informatique (computer science) au génie électrique — ce qui est souvent le cas dans les universités américaines — ou à un département de mathématiques. Il répondit : «Je la classerais volontiers entre la plomberie et le dépannage automobile» pour souligner le côté encore artisanal de cette jeune science. Toutefois, la forte scientificité des trois premiers volumes de son encyclopédie suggère qu'il s'agit là plutôt d'une boutade de sa part. Au demeurant, la maîtrise de langages comme Haskell ou même APL demande un niveau d'abstraction tout de même plus proche de celui des mathématiques que des deux disciplines citées. La miniaturisation des composants et la réduction des coûts de production, associées à un besoin de plus en plus pressant de traitement des informations de toutes sortes (scientifiques, financières, commerciales...) a entraîné une diffusion de l'informatique dans toutes les couches de l'économie comme de la vie de tous les jours.
Approche fonctionnelle
Comme énoncé ci-dessus, l'informatique est le traitement automatisé de données par un appareil électronique : l'ordinateur ; les germanophones parlent de elektronisch Daten Verarbeitung / EDV (« traitement électronique de données »), les anglophones dinformation technology / IT (« technologies de l'information »), c'est-à-dire :
- données ou informations : in fine, l'ordinateur manipule des nombres (d'où le terme anglais computer, littéralement « calculateur »), mais ces nombres peuvent représenter divers types d'informations :
- des... nombres bien évidemment, dans le cas de calculs scientifiques (flottants) ou comptables (décimal, ou binaire entier)... ;
- un texte, des lettres (caractères), que l'on peut mettre en forme avec un traitement de texte, imprimer, envoyer par courrier électronique... ;
- du dessin vectoriel (CAO, logiciels d'illustration, et de typographie) ;
- des images statiques (photographies) ou animées (vidéo), des hologrammes ;
- des sons, enregistrés (technique du direct to disk) ou bien fabriqués par l'ordinateur (synthétiseur), que ce soient des bruitages, de la musique (cf. musique et informatique) ou de la parole ; :la conversion de ces informations en suite de nombres pose le problème du format des données, du codage et des formats normalisés (par exemple, représentations des nombres entiers ou à virgule flottante, format ASCII, Unicode, TeX ou RTF et polices PostScript ou TrueType pour les textes, formats bitmap, TIFF, JPEG, PNG, etc. pour les images fixes, formats QuickTime, MPEG pour les vidéos, interface MIDI pour la musique...).
- automatisé : l'utilisateur n'intervient pas, ou peu, dans le traitement des données ; le traitement est défini dans un programme qui se déroule tout seul, l'utilisateur se contente de fournir des paramètres de traitement ; le programme automatique se déroule selon un algorithme, l'établissement de ce programme est le domaine de la programmation.
- traitement : ces données sont :
- créées :
- nombres : acquisition automatique de données d'une expérience avec un ordinateur ;
- texte : taper un texte au clavier ;
- images : dessins réalisés à la souris ou sur une tablette graphique, synthèse d'image (pour présenter un projet – objet fictif en cours de conception –, imagerie médicale, dessin artistique – infographie –, film d'animation ou pixilation) ou numérisation d'une image existante (scanner, appareil photographique numérique) ou d'images animées (caméra numérique, webcam) ;
- sons enregistrés (microphone) ou recréés à partir d'une partition virtuelle (synthétiseur) ou d'un texte (synthèse vocale).
- analysées :
- nombres : l'analyse des nombres relève du domaine concerné (mathématiques, physique, économie...) ;
- texte : rechercher les occurrences de mots dans un texte pour en tirer des statistiques, aide à la correction orthographique et/ou grammaticale, et, plus généralement, traitement automatique des langues (TAL) ;
- images : on peut vouloir identifier un objet (reconnaissance de forme, reconnaissance des caractères ou OCR), ou bien déterminer la surface couverte par une couleur (par exemple pour quantifier une surface recouverte) ;
- sons : analyse spectrale, reconnaissance vocale.
- modifiées :
- nombres : calculs ;
- texte : modification d'un texte existant, traduction automatique dans une autre langue (ou langage de programmation) ;
- images : modification du contraste, de la luminosité, des couleurs, effets spéciaux ;
- sons : application d'effets (réverbération, distorsion, ajustement de la hauteur) ; ::comme il existe, selon les programmes et les besoins, une grande variété de codages possibles pour représenter chaque type d'information, beaucoup de traitements consistent à convertir les données d'un format vers un autre...
- archivées puis restituées :
- les moyens et techniques d'archivage varient en fonction de la durée de conservation souhaitée et des quantités de données en jeu : mémoires électroniques, bandes magnétiques, disques magnétiques ou optiques ;
- les moyens de restitution dépendent de la nature des données : écrans ou imprimantes pour le texte et les images, haut-parleurs ou instruments MIDI pour les sons...

Approche organisationnelle

L'informatique pour l'organisation est un élément d'un système de traitement d'information (les entrées peuvent être des formulaires papier par exemple) et d'automatisation. Depuis Henry Ford, l'automatisation des tâches ayant été identifiée comme un avantage concurrentiel, la question est : que peut-on automatiser ? Autant il est relativement facile d'automatiser des tâches manuelles, autant il est difficile d'automatiser le travail intellectuel et parfois créatif. L'approche de l'informatique dans une organisation commence donc par l'élucidation des processus, c'est-à-dire modéliser le métier. Après validation, la MOA (Maîtrise d'Ouvrage) fournit les spécifications fonctionnelles de (l'ouvrage) qui vont servir de référence dans la conception pour la MOE (Maîtrise d'œuvre). Cette conception sera alors effectuée dans le respect d'un Cycle de développement qui définit les rôles et responsabilités de chaque acteur. Ainsi, les échanges entre MOA et MOE ne se résument pas à la maîtrise des chantiers (tenue des délais et des coûts, et validation des livrables), la MOA et la MOE sont garantes (éventuellement responsables sur un plan juridique) de la cohérence des systèmes d'information, et de l'adéquation des solutions informatiques avec les problèmes utilisateurs finaux initialement constatés.

Matériel

Article détaillé : Matériel informatique On utilise également le terme anglais hardware (littéralement « quincaillerie ») pour désigner le matériel informatique. Il s'agit de tous les composants que l'on peut trouver dans : 1. Les ordinateurs et leurs périphériques : un ordinateur est un ensemble de circuits électroniques permettant de manipuler des données sous forme binaire, représentées par des variations de signal électrique. Il existe différents types d'ordinateurs : ordinateur 5150 datant de 1981, Système d'exploitation IBM-DOS 2.0]]
- Les micro-ordinateurs. De bureau ou portables. Ils sont composés d'une unité centrale : un boîtier contenant la carte mère, l'alimentation, des unités de stockage. On y ajoute une console : un écran et un clavier. Divers périphériques peuvent leur être ajoutés, une souris, une imprimante, un scanner..ect; scanner
- Les stations de travail. Des micro-ordinateurs particulièrement puissants et chers, utilisés uniquement pour des besoins professionnels pointus (conception assistée par ordinateur). Ce terme était particulièrement en vogue dans les années 1980-1990. Depuis les années 2000, il n'est guère possible de concevoir une station de travail plus puissante qu'un micro-ordinateur haut de gamme ;
- Les mainframes. Une armoire abrite l'unité centrale et l'alimentation, une ou plusieurs autres les périphériques de stockage (disque dur, sauvegarde) tandis que les moyens de communication et réseau (routeur, hubs, modem) sont dans la même pièce, mais dans des racks séparés. Une console d'administration (écran, clavier, imprimante) est généralement située dans ce même local ; administration]
- Les PDA (Personal Digital Assistant, encore appelés organiseurs). Ce sont des ordinateurs de poche proposant des fonctionnalités liées à l'organisation personnelle (agenda, calendrier, carnet d'adresse, etc.). Ils peuvent être reliés à Internet par différents moyens (réseau Wifi, Bluetooth, etc.).
- Et bien d'autres appareils. Dans le domaine de l'informatique embarquée : téléphone, électroménager, automobile, armements militaires, etc. Les cartes à puces, ou l'informatique industrielle.

Logiciel

Le logiciel désigne la partie à première vue immatérielle de l'informatique, l'organisation et le traitement de l'information : les programmes. On s'est en effet vite rendu compte que des machines techniquement très avancées pour leur époque, comme la Bull Gamma 60, restaient invendables tant qu'on n'avait pas de programmes à livrer pour les rendre immédiatement opérationnelles. IBM lança entre 1968 et 1973 une sorte d'ancêtre du logiciel libre avec son ordinateur 1130, politique qui assura à celui-ci par effet boule de neige un succès immédiat et planétaire, mais les conclusions d'un procès antitrust lui interdirent de distribuer bénévolement du logiciel. Le monde des mainframes classe les logiciels en catégories suivantes :
- systèmes d'exploitation ;
- bases de données, comme DB2, Ingres ou Oracle ;
- programmes de communication, comme NCP ou RSCS ;
- moniteurs de télétraitement ;
- systèmes transactionnels, comme CICS ;
- systèmes de temps partagé, utilisés pour le calcul ou le développement ;
- compilateurs traduisant les langages en instructions machine et appels système ;
- tout le reste entrait en une catégorie nommée Logiciels applicatifs. Plus simplement on distingue généralement trois types de logiciels (par ordre de proximité du matériel) :
- le firmware
- le système d'exploitation
- les logiciels et applications utilisateur (en anglais software) On classe aussi les logiciels en libre et propriétaire, bien que les deux soient parfois panachés à des degrés divers. Certains ont une fonction bureautique ou multimédia comme par exemple les jeux vidéo. Certains logiciels ont acquis des noms connus de tous. Le noyau du système d'exploitation crée le lien entre le matériel et le logiciel. Un logiciel, quand il est fourni sous sa forme binaire, serait utilisable uniquement avec un système d'exploitation donné (car il en utilise les services), et ne fonctionnerait que sur un matériel spécifique (car il en utilise le code d'instructions). Une conception plus récente, depuis le milieu de années 1980, consiste à distribuer les logiciels tous binaires confondus, et à les munir d'un système de licences par jetons ou tokens permettant l'usage de N copies simultanées du logiciel sur le réseau, tous matériels confondus. Cette approche est majoritaire dans le monde UNIX. À l'initiative de Richard Stallman et du GNU, à partir de 1985, une mouvance de programmeurs refuse cette logique propriétaire et ceux-ci se muent en concepteurs inventifs pour se lancer dans le développement d'outils et de bibliothèques système libres compatibles avec le système UNIX. C'est pourtant le projet indépendant Linux, initié par Linus Torvalds, basé sur les travaux et les outils du GNU, qui aboutira dans la création d'un système d'exploitation complet et libre. Une bonne partie des logiciels actuels fonctionnent dans un environnement graphique pour interagir avec l'utilisateur. La diversité des systèmes informatiques a fait apparaître une technique visant à combiner le meilleur de chacun de ces univers : l'émulateur. Il s'agit d'un logiciel permettant de simuler le comportement d'un autre système dans celui que l'on utilise,
- soit pour qu'une machine semble être une autre (voir IBM 1130),
- soit pour simuler le comportement d'un système d'exploitation (par exemple DOS ou Windows sous Linux). Le terme anglais est software, à l'origine un jeu de mot entre hardware (« quincaillerie », pour désigner le matériel) et l'opposition soft/hard (mou/dur), opposition entre le matériel (le dur) et l'immatériel (le mou). Les traductions françaises matériel et logiciel rendent parfaitement cette opposition et cette complémentarité. Le logiciel réalise normalement une fonction attendue de ses utilisateurs. Néanmoins, des effets secondaires (parfois nommés par contresens de traduction effets de bord) existent. Parfois même, certains logiciels sont destinés à nuire, comme les virus informatiques, nommés en anglais, par analogie avec software : malware (qu'on pourrait traduire par le néologisme nuisiciel, ou logiciel malveillant).

La création des logiciels

Un projet informatique s'inscrit dans un cycle de développement qui définit les grandes étapes de la réalisation (planification), de la manière dont on passe d'une étape à l'autre (modèle incrémental, en V, en spirale, etc.). Pour les petits projets (ou les petites équipes de développement), cette réflexion est souvent négligée (on se répartit les modules et chacun développe dans son coin). Ceci est une cause fréquente d'erreurs (bogues) et de non-conformité (le produit final n'est pas conforme aux attentes de l'utilisateur). Mais même les énormes projets, avec beaucoup de moyens, sont victimes de cette négligence ; ainsi, l'échec du premier vol d'Ariane 5 fut dû à un problème de logiciel, etc. Un projet peut alors intégrer une approche de la qualité et de la sûreté de fonctionnement des systèmes informatiques afin de contrôler autant que possible le produit final. Un projet comprend les étapes suivantes :
- l'établissement d'un cahier des charges qui définit les spécifications auxquelles devra répondre le logiciel ;
- la définition de l'environnement d'exécution (architecture informatique) :
- type(s) d'ordinateur sur lequel le logiciel doit fonctionner (station de calcul, ordinateur de bureau, ordinateur portable, assistant personnel, téléphone portable, guichet automatique de banque, ordinateur embarqué dans un véhicule ;
- type et version du(des) système(s) d'exploitation sous-jacent ;
- périphériques nécessaires à l'enregistrement des données et à la restitution des résultats (capacité de stockage, mémoire vive, possibilités graphiques...) ;
- nature des connexions réseau entre les composants (niveau de confidentialité et de fiabilité, performances, protocoles de communication...) ;
- la conception de l'application et de ses constituants, et notamment de l'interactivité entre les modules développés : structure des données partagées, traitement des erreurs générées par un autre module... : c'est le domaine du génie logiciel ;
- la mise en place d'une stratégie de développement :
- répartition des tâches entre les développeurs ou les équipes de développement, qui vont assurer le codage et les tests ;
- le plan de test du logiciel, pour s'assurer qu'il remplit bien la mission pour laquelle il a été écrit, dans toutes les conditions d'utilisation qu'il pourra normalement rencontrer, mais aussi dans des cas limites. Après chacune de ces phases, on peut avoir une étape de recette, où le client va valider les choix et les propositions du maître d'œuvre. La phase de programmation consiste à décrire le comportement du logiciel à l'aide d'un langage de programmation. Un compilateur sert alors à transformer ce code écrit dans un langage informatique compréhensible par un humain en un code compréhensible par la machine, le résultat est un exécutable. On peut également, pour certains langages de programmation, utiliser un interpréteur qui exécute un code au fur et à mesure de sa lecture, sans nécessairement créer d'exécutable. Enfin, un intermédiaire consiste à compiler le code écrit vers du bytecode. Il s'agit également d'un format binaire, compréhensible seulement par une machine, mais il est destiné à être exécuté sur une machine virtuelle, un programme qui émule les principales composantes d'une machine réelle. Le principal avantage par rapport au code machine est une portabilité théoriquement accrue (il « suffit » d'implanter la machine virtuelle pour une architecture donnée pour que tous les programmes en bytecode puissent y être exécutés), portabilité qui a fait, après sa lenteur, la réputation de Java. Il convient de noter que ces trois modes d'exécution ne sont nullement incompatibles. Par exemple, OCaml dispose à la fois d'un interpréteur, d'un compilateur vers du bytecode, et d'un compilateur vers du code natif pour une grande variété de processeurs. Une fois écrit (et compilé si nécessaire), le code devient un logiciel. Pour des projets de grande amplitude, nécessitant la collaboration de beaucoup de programmeurs, voire de plusieurs équipes, on a souvent recours à une méthodologie commune (par exemple MERISE) pour la conception et à un atelier de génie logiciel (AGL) pour la réalisation. Au cours de la programmation et avant la livraison du produit final, le programme est testé afin de vérifier qu'il fonctionne bien (y compris dans des cas d'utilisation en mode dégradé) et qu'il est conforme aux attentes de l'utilisateur final. Les tests intermédiaires permettent de s'assurer que chaque module de code réalise correctement une fonction : ce sont les tests unitaires. Les tests finals qui vérifient le bon enchaînement des modules et des traitements sont des tests d'intégration. Pour certaines applications demandant un haut niveau de sûreté de fonctionnement, les tests sont précédés d'une étape de vérification, où des logiciels spécialisés effectuent (généralement sur le code source, mais parfois aussi sur le code compilé) un certain nombre d'analyses pour vérifier partiellement le bon fonctionnement du programme. Il n'est toutefois pas possible (et des théorèmes mathématiques montrent pourquoi), de garantir la parfaite correction de tout logiciel par ce moyen et la phase de test reste donc nécessaire. Elle se complète aussi, lorsqu'il s'agit d'une évolution d'une application existante, de nombreux tests automatisés de non-régression. Statistiques : la création d'un logiciel est une tâche ardue ; environ 31 % des projets informatiques sont abandonnés avant d'être terminés, plus de 50 % des projets coûtent le double du coût initialement estimé et seulement 15 % des projets finissent dans les temps et selon le budget défini. Les besoins de seule maintenance de l'existant peuvent prendre jusqu'à 50 % des effectifs d'une équipe chargée d'un logiciel (or, c'est là une fonction pénible, ingrate, peu valorisante et qui rebute et démotive les bons programmeurs).

Traitement de l'information

L'information, pour être traitée, doit être :
- représentée par un codage :
- on utilise un système de numération binaire, où l'élément unitaire informationnel est le bit (contraction de l'anglais binary digit : chiffre binaire). Les bits sont généralement regroupés par huit, pour constituer des octets (ou bytes). Un octet peut être représenté par la séquence des bits qui le constituent (par exemple : 00101110) ou par une paire de valeurs hexadécimales (pour le même exemple : 2E), plus compact. Le choix du binaire ne résulte pas de la mystique, mais tout simplement d'utiliser de simples circuits de commutation, qui ont de très larges tolérances et par conséquent de faibles coûts ;
- on représente la structuration de l'information pour permettre des échanges entre composants logiciels et entre composants matériels. Pour cela, on définit des langages et des formalismes de représentation.
- stockée dans des systèmes permanents (mémoires dites de masse) ou non (mémoires dites volatiles).

Échanges de données : protocoles et normes

Les protocoles définissent une manière de procéder, notamment pour codifier la façon dont deux entités communiquent (modules ou couches logicielles, périphériques, etc.). On parle notamment de protocole de communication lorsqu'on veut définir des mécanismes de contrôle sur la manière dont l'échange d'information est réalisé. Un protocole peut ainsi définir :
- un langage de description d'instructions et de données graphiques (exemple : AGP) ;
- un standard de commandes et de flux d'information pour une mémoire de masse (exemples : SCSI, FireWire, IDE, Serial ATA) ;
- des échanges entre le processeur et des cartes d'extension (exemples : PCI, PCI Express, ISA) ;
- des modalités de transfert d'information entre périphériques (exemple : USB) ou sur un réseau TCP/IP, Internet, ATM, X.25) ;
- des commandes entre un client et un serveur (exemples : POP3, IMAP, HTTP, FTP …) ;
- des échanges de données informatisés spécifiques (exemples : EDI, EAI, X.400, X.500). Certains protocoles sont définis par des normes pour permettre l'interopérabilité des matériels ou de logiciels les mettant en œuvre. D'autres normes définissent, toujours dans le domaine de l'échanges de données :
- des langages de représentation d'information sans pour autant définir la manière dont cette information peut être échangée (exemples : ASN.1, XML) ;
- des architectures de réseaux (exemples : Modèle OSI, Wifi, Ethernet, Token-Ring).

Stockage des données

En matière de stockage d'information, on distingue le dispositif permettant de l'enregistrer physiquement (périphériques et composants) de la manière dont on structure et représente l'information pour faciliter son traitement.

Mémoire de masse

:Fichier de cartes perforées :Bande magnétique :Disque amovible magnétique (Disquette) :Disque magnéto-optique :Disque dur (disque magnétique embarquant le mécanisme, l'électronique et les têtes de lecture) :Disque optique amovible (CD-ROM, CD-R, CD-RW mais aussi DVD-ROM, DVD-R, DVD-RW, DVD+R, DVD+R DL, DVD+RW, DVD-RAM, GD-ROM, HD-DVD, Blu-ray) :Mémoire électronique non volatile (Mémoire flash, clé USB)

Mémoire volatile

:RAM

Organisation des données en vue du stockage

:Formats (extensions) de fichiers :Système de fichiers :Base de données :Annuaire

Approches scientifiques

:L'informatique n'est pas plus la science de l'ordinateur que l'astronomie n'est celle du télescope. :: -- Edsger Dijkstra

En dehors des aspects industriels et technologiques décrits jusqu'ici, l'informatique est une discipline scientifique à part entière. :Algorithmique :Algèbre de Boole :Calculabilité :Géométrie algorithmique :Lambda-calcul :Logique :Model checking :Théorie de l'information :Théorie des graphes :Théorie de la complexité :Théorie de la calculabilité :Théorie des automates finis

Applications

:Bio-informatique :Calcul parallèle :Cryptographie :Exploration de données (data mining) :Informatique grand système (mainframe) :Informatique de gestion :Informatique industrielle :Informatique décisionnelle :Imagerie Informatique :Intelligence artificielle :Interface homme-machine :Micro-informatique :Traitement du signal :Hypermédias :Informatique musicale

Annexes

- Informathèque
- Abréviations en informatique
- Dictionnaire informatique
- Informatique alternative
- Liste des articles d'informatique
- Personnes célèbres en informatique
- Revues informatiques sur papier
- Sécurité informatique
- Sites d'informations sur internet
- Terminologie de la distribution informatique
- Réseaux de neurones
- Musique et informatique
- Ordinateur quantique
- Hello_world
- Visual Information Exploration
-

Liste

En informatique, une liste est une structure de données permettant de regrouper des données de manière à pouvoir y accéder librement (contrairement aux files et aux piles, dont l'accès se fait respectivement en mode FIFO et LIFO). On utilise dans ce but un index qu'on peut placer sur un élément particulier de la liste.

Principe

Le principe de la liste est que chaque élément à stocker possède des pointeurs vers les éléments qui lui sont logiquement adjacents dans la liste. De ce fait, l'usage d'une liste est préconisé lorsque les insertions / suppressions d'éléments en tout point sont relativement plus fréquents que les accès simples, pour des raisons de rapidité de traitement. En effet, une insertion ou suppression se fait en temps constant car ne demande au maximum que deux accès en écriture. En revanche, l'accès à un élément aléatoirement positionné demande le parcours de chacun des éléments qui séparent l'index de l'élément choisi, il est donc préférable d'accéder aux éléments séquentiellement. Une liste possède également une référence statique vers le premier élément (la tête de liste) qui permet de retrouver tous les autres.

Types de listes

Il existe plusieurs types de listes, caractérisés principalement par deux attributs.

Chaînage

Liste simplement chaînée

pointeur Comme on le voit sur ce schéma, deux éléments composent un élément de la liste chaînée :
- la valeur associé à l'élément
- un pointeur vers l'élément suivant Avec seulement un pointeur vers l'élément suivant, l'accès se fait uniquement vers l'avant.

Liste doublement chaînée

La différence avec une liste simplement chaînée est que cette fois-ci, un pointeur vers l'élément précédent est ajouté. Ainsi, l'accès peut se faire indifféremment vers l'avant ou vers l'arrière.

Cycle

Liste non cyclique

Le dernier élément ne possède pas de référence vers le premier élément de la liste.

Liste cyclique (ou circulaire)

Le dernier élément possède une référence vers le premier élément (si la liste est doublement chaînée, le premier élément possède aussi une référence vers le dernier).

Primitives

On définit un certain nombre de primitives, qui sont des fonctions de test, d'accès en lecture ou en écriture dont la liste permet une exécution efficace. Il n'existe pas de normalisation pour les primitives de manipulation de liste. Leurs noms sont donc indiqués de manière informelle. Voici la liste des plus couramment utilisées :
- « Placement sur le premier élément » : place l'index sur le premier élément de la liste.
- « Placement sur le dernier élément » : place l'index sur le dernier élément de la liste.
- « Placement sur l'élément suivant » : place l'index sur l'élément qui suit l'élément courant si c'est possible.
- « Placement sur l'élément précédent » : place l'index sur l'élément qui précède l'élément courant si c'est possible.
- « Liste est-elle vide ? » : Retourne vrai si la liste est vide, faux sinon.
- « L'élément courant est-il le premier ? » : Retourne vrai si l'élément courant est le premier élément de la liste, faux sinon.
- « L'élément courant est-il le dernier ? » : Retourne vrai si l'élément courant est le dernier élément de la liste, faux sinon.
- « Nombre d'élément » : renvoie le nombre d'éléments dans la liste.
- « Ajouter en queue » : ajoute un élément après le dernier élément de la liste (efficace seulement pour une liste doublement chaînée).
- « Ajouter en tête » : ajoute un élément avant le premier élément de la liste.
- « Insertion » : insère un élément avant l'élément courant.
- « Remplacement » : Remplace l'élément courant.
- « Suppression » : Supprime l'élément courant.

Implémentation

Dans des langages impératifs comme le C, l'implémentation des listes utilise l'une des méthodes suivantes :
- Implémentation par contiguité : Les éléments se trouvent dans l'ordre dans une structure de données de plus bas niveau, comme un tableau, par exemple.
- Implémentation par chaînage : Les éléments contiennent les informations (des pointeurs, en C), permettant de retrouver l'élément suivant (chaînage simple) ou les éléments précédent et suivant (chaînage double). Exemple d'implementation dans le langage Pascal (liste d'entiers) :

type liste=^jonction;
     jonction=record
        contenu:longint;
        suivant:liste
     end;

Exemple d'implémentation du type liste d'entiers doublement chaînée dans le langage C :

struct liste
;

Voir aussi

- Liste des listes sur Wikipédia. Catégorie:Structure de données ja:線形リスト ko:연결 리스트

Tableau (informatique)

En informatique, un tableau est une structure de données de base. C'est un ensemble d'éléments (des variables ou autres entités contenant des données), auquel on a accès à travers un numéro d'index (ou indice). Dans les langages classiques, tous les éléments d'un tableau doivent être du même type. Dans les langages de plus haut niveau (comme Python, APL, etc...), cette restriction n'existe plus.

Tableau à une dimension

APL Avec un tableau à une dimension (aussi appelé un vecteur), un numéro d'index donne accès à un seul élément. L'image de droite est une représentation graphique d'une telle structure de données, composé de 7 éléments. En langage C par exemple, on accède au premier élément d'un tableau nommé tab de la manière suivante : tab[0]; En prenant le tableau en exemple, cette instruction retournera 45. Il est à noter que la numérotation de l'index commence à 0.

Tableau à deux dimensions (ou plus)

langage C La création d'un tableau à deux dimensions (aussi appelé matrice) permet l'accès à plus d'une valeur à partir d'un indice. Autrement dit, un numéro d'index pointe sur un autre tableau. L'image de droite représente une telle structure de données. Comme on le voit, le premier tableau est composé de pointeurs vers un tableau. L'accès à un élément se fait donc à travers deux indices. En langage C, l'accès au troisième élément du quatrième tableau ce fait de la manière suivante : tab[3][2]; Cette instruction retournera 58. Il n'y a pas de limite au nombre de dimension (mis à part leur utilité). Ainsi, l'accès un élément dans un tableau à 3 dimensions se fait à l'aide de 3 trois indices (un pour chaque tableau).

Tableau trié

Un Tableau trié est un tableau dont les éléments sont ordonné selon une relation d'ordre total.

Tableaux connus

Tableau périodique des éléments ou Table de Mendeleïev
Tableau de bord d'une voiture Autres sens sur le wiktionnaire: tableau Catégorie:Algèbre linéaire Catégorie:Structure de données ja:配列

Pile (informatique)

En informatique, une pile (stack en anglais) est une structure de données basée sur le principe LIFO (Last In, First Out), ce qui veut dire que les derniers éléments ajoutés à la pile seront les premiers à être récupérés. Le fonctionnement est celui d'une pile d'assiettes : on ajoute des assiettes sur la pile, et on les récupère dans l'ordre inverse, en commençant par la dernière ajoutée.

Pile d'appel

La pile d'appel (souvent appelée « la pile » tout court, parfois « pile système ») est, sur la plupart des architectures de microprocesseurs, une pile particulière dans laquelle sont poussées tout ou partie des paramètres d'appel des procédures ou fonctions, ainsi que l'adresse de retour. Par ailleurs, on y crée un espace pour des variables locales. La pile est ainsi formée de cadres de piles (stack frames) comprenant pour chaque procédure en cours d'appel imbriqué ses paramètres, ses variables locales et son point de retour. La pile système sert à sauver le contexte (valeur des registres, point de retour...) lors des exceptions et des interruptions.

Primitives

Voici les primitives communément utilisées pour manipuler des piles. Il n'existe pas de normalisation pour les primitives de manipulation de pile. Leurs noms sont donc indiqués de manière informelle.
- « Empiler » : ajoute un élément sur la pile.
- « Dépiler » : enlève un élément de la pile et le renvoie.
- « La pile est-elle vide ? » : renvoie vrai si la pile est vide, faux sinon.
- « Nombre d'éléments de la pile » : renvoie le nombre d'éléments dans la pile.

Architecture basée sur la pile

Certains processeurs n'utilisent pas de registre générique, mais uniquement la pile. Par exemple, les calculatrices Hewlett-Packard, les processeur Focus, ou les machines Burroughs de la gamme B 5000

Voir aussi

- File Catégorie: Structure de données ja:スタック ko:스택 (자료구조)

Tas

Catégorie:Algorithmique Catégorie:Structure de données Catégorie:Structure de données

Définition

En informatique, un tas (ou plus précisément un tas binaire) est une structure de données répondant aux conditions suivantes :
- C'est un arbre binaire complet
- Il est ordonné en tas On dit qu'un arbre est ordonné en tas lorsque la propriété suivante est vérifiée : les noeuds sont ordonnés par leurs clés respectives, et : Pour tous A et B noeuds de l'arbre tels que B soit un fils de A clé(A) ≥ clé(B) Cette propriété implique que la plus grande clé soit située à la racine du tas. Ils sont ainsi très utilisés pour implémenter les files à priorités car ils permettent des insertions en temps logarithmique et un accès direct au plus grand élément. L'efficacité des opérations effectuée sur des tas est très importante dans de nombreux algorithmes sur les graphes. Le fait qu'un tas soit un arbre binaire complet permet de le représenter d'une manière intuitive par un tableau unidimensionnel.
- Tableau indicé à partir de 0 : le père d'un noeud en position i a pour position

\lfloor (i-1)/2 \rfloor

, et donc les enfants d'un noeud en position i sont situés à 2i+1 et 2i+2.
- Tableau indicé à partir de 1 : le père d'un noeud en position i a pour position

\lfloor i/2 \rfloor

, et donc les enfants d'un noeud en position i sont situés à 2i et 2i+1. Les tas sont en outre utilisés dans l'algorithme de tri par tas.

Remarques

- Les multiples définitions existantes pour « arbre complet » peuvent porter à confusion. Ici, il est important que les noeuds de l'arbre puissent être stockés de façon contiguë dans un tableau. Donc, tous les étages, de la racine jusqu'à l'avant-dernier, doivent obligatoirement être remplis. De plus, les feuilles de la dernière ligne doivent être "calées à gauche". En revanche, un tas pouvant avoir un nombre quelconque d'éléments, il n'est pas obligatoire que la dernière ligne soit complètement remplie.
- La notion de plus grande clé est équivalente à la notion de plus petite clé, seule diffère la relation d'ordre total utilisée. Les algorithmes restent donc les mêmes si l'on veut accéder directement au plus petit élément et non au plus grand. On peut même, dans la plupart des langages de programmation modernes, programmer de façon à passer la relation d'ordre désirée en paramètre des algorithmes de construction et de manipulation de tas.
Attention : un tas est organisé selon une seule relation d'ordre à la fois. Il faut donc décider dès sa construction si l'on veut accèder ensuite au plus grand élément, ou au plus petit, et selon quel attribut de l'objet stocké dans l'étiquette de chaque noeud. Les manipulations suivantes de ce tas devront obligatoirement se faire par rapport à la même relation d'ordre.

Contre-exemples

Les deux contre-exemples suivants ont pour relation d'ordre:

valeur(pere) \ge valeur(fils)

Primitives

A détailler!
Les Tas supportent les opérations suivantes:
- Construire-Tas
- Ajouter-Elément
- Consulter-Sommet
- Retirer-Elément
- Tamiser
- Tri-Par-Tas Selon les implémentations, les primitives Ajouter-Elément et Retirer-Element invalident la propriété de Tas, ou bien appellent la procédure Tamiser pour le réorganiser.
Souvent Retirer-Element n'est appelée que pour retirer le sommet.

Tas binomial

En informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement. Ainsi, il supporte les opérations suivantes, toutes en O(ln n):
- Insérer un nouvel élément au tas
- Trouver l'élément de plus petite clé
- Effacer du tas l'élément de plus petite clé
- Diminuer la clé d'un élément donné
- Effacer un élément donné du tas
- Fusionner deux tas en un seul Le tas binomial est donc une implémentation du type abstrait tas fusionnable, ie une file à priorités permettant des opérations de fusion.

Notion d'arbre binomial

Un tas binomial est en fait un ensemble d'arbres binomiaux (à comparer avec un tas binaire, qui correspond à un unique arbre binaire). Un arbre binomial est défini récursivement comme suit:
- L'arbre binomial d'ordre 0 est un simple noeud
- L'arbre binomial d'ordre k possède une racine de degré k et ses fils sont racines d'arbre binomiaux d'ordre k-1, k-2, ..., 2, 1, 0 (dans cet ordre) Un arbre binomial d'ordre k peut aussi être construit à partir de deux arbre d'ordre k-1 en faisant de l'un des deux le fils le plus à gauche de la racine de l'autre. Un arbre binomial d'ordre k possède 2^k noeuds, et a pour taille k. Des variantes d'arbres binomiaux sont aussi utilisées pour construire les tas de Fibonacci.

Structure des tas binomiaux

Un tas binomial est implémenté en tant qu'ensemble de tas binomiaux satisfaisant aux propriétés des tas binomiaux:
- Chaque arbre binomial du tas possède une structure ordonnée en tas: la clé de chaque noeud est supérieure ou égale à celle de son parent.
- Pour tout j entier naturel, il existe au plus un tas binomial d'ordre j. La première propriété nous indique que la racine de chaque arbre binomial possède la plus petite clé de l'arbre. La seconde propriété implique qu'un tas binomial contenant n éléments consiste en au plus ln n + 1 arbres binomiaux.. En fait, le nombre et les ordres de ces arbres est déterminé de manière unique par le nombre n d'éléments: chaque tas binomial correspond au bit 1 dans l'écriture binaire du nombre n. Par exemple, 13 correspond à 1101 en binaire,

2^3 + 2^2 + 2^0

, et donc le tas binomial à 13 éléments consistera en 3 arbres binomiaux d'ordres respectifs 3, 2 et 0 (cf. figure ci-dessous) Les racines des arbre binomiaux sont stockés dans une liste indicée par l'ordre des l'arbre. Exemple de tas binomial
Exemple de tas binomial contenant des éléments de clés 1, 2, ..., 13. Le tas consiste en 3 arbres binomiaux d'ordre 0, 2, and 3.

Implémentation des opérations

L'opération de fusion de deux tas est sans doute la plus intéressante et est réutilisée dans la plupart des autres opérations. Les listes de racines des deux tas sont parcourues simultanément, de même que pour le tri fusion. Si seul un des deux tas contient un arbre d'ordre j, celui-ci est ajouté au tas fusionné. Si les deux tas contiennent un arbre d'ordre j, les deux arbres sont fusionnés en un arbre d'ordre j+1 en respectant la structure de tas (la plus grande des deux racines devient fille de la plus petite). Notez que l'on peut avoir besoin de fusionner cet arbre avec un arbre d'ordre j+1 présent dans un des deux tas initiaux. Durant l'algorithme, nous examinons au plus 3 arbres de chaque ordre (deux provenant des deux tas que nous fusionnons et un formé à partir de deux arbres plus petits). Or l'ordre maximal d'un arbre est ln n et donc la complexité de la fusion est en O(ln n). Pour insérer un nouvel élément dans un tas on crée simplement un nouveau tas contenant uniquement cet élément que nous fusionnons ensuite avec le tas initial, et ce en O(ln n). Pour trouver le plus petit élément du tas, nous avons seulement besoin de trouver le minimum parmi les racines des arbre binomiaux (au nombre maximal de ln n) , ce qui ce fait une fois de plus en O(ln n). Pour supprimer le plus petit élément du tas, on trouve tout d'abord cet élément pour l'enlever de son arbre binomial : on obtient alors une liste de ses sous-arbres, que l'on transforme en un autre tas binomial, ensuite fusionné au tas précédent. Quand nous diminuons la clé d'un élément, elle peut devenir plus petite que celle de son père, violant l'ordre en tas de l'arbre. Dans ce cas, nous échangeons l'élément avec son père, voire avec son grand père, et ainsi de suite jusqu'à ce que l'arbre soit de nouveau ordonné en tas. Chaque arbre binomial ayant pour taille maximale ln n, l'opération est en O(ln n). Enfin pour supprimer un élément, on lui donne pour clé moins l'infini (plus petite que toute les autres clés...) puis on supprime le plus petit élément du tas, c'est à dire lui-même.

Bibliographie

- Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8
- Vuillemin, J. (1978). [http://portal.acm.org/citation.cfm?id=359478 A data structure for manipulating priority queues.] Communications of the ACM 21, 309-314.

Liens externes"

- [http://www.cs.yorku.ca/~aaw/Sotirios/BinomialHeap.html une simulation Java d'un tas binomial] Catégorie: structure de données

Table de symboles

Le type abstrait table de symboles correspond à une structure de données constituée d'éléments associés à une clé. On peut alors effectuer deux opérations: l'insertion d'un nouvel élément avec sa clé, et la recherche d'un élément dans la table à partir d'une clé. Les tables de symboles sont utilisées très souvent au niveau matériel avec l'implémentation de systèmes de fichiers (souvent à l'aide d'arbres B) et au niveau logiciel dans les compilateurs durant l'analyse lexicale à l'aide de tables de hachage. Catégorie:structure de données

Arbre binaire de recherche

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire où chaque noeud possède une clé telle que chaque noeud du sous-arbre gauche aie une clé inférieure ou égale à celle du noeud considéré, et que chaque noeud du sous-arbre droit possède une clé supérieure ou égale à celle-ci (selon l'implémentation de l'arbre binaire de recherche, on pourra interdire des clés de valeur égale ou non). Les noeuds que l'on ajoute deviennent des feuilles de l'arbre.

Opérations

Recherche

La recherche dans un arbre binaire d'un noeud ayant une clé particulière est un procédé récursif. On commence par examiner la racine. Si sa clé est la clé recherchée, l'algorithme termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre gauche, sur lequel on effectue alors récursivement la recherche. De même si la clé de la racine est strictement supérieure à la clé recherchée la recherche continue sur le sous-arbre droit. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun noeud. On peut la comparer avec la recherche par dichotomie qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre des liens. Cette opération requiert un temps en O(ln n) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chainée.

Insertion

L'insertion d'un noeud commence par une recherche: on cherche la clé du noeud à insérer, et lorsque l'on arrive à une feuille, on ajoute le noeud comme fils de la feuille en comparant sa clé à celle de la feuille: si elle est inférieure, le nouveau noeud sera à gauche, sinon il sera à droite. La complexité est évidemment la même que pour la recherche: O(ln n) dans le cas moyen et O(n) dans le cas critique.

Suppression

Plusieurs cas sont à considérer, une fois que le noeud à supprimer a été trouvé à partir de sa clé:
- Suppression d'une feuille:: Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
- Suppression d'un noeud avec un enfant: Il faut l'enlever de l'arbre en le remplaçant par son fils.
- Suppression d'un noeud avec deux enfants: Supposons que le noeud à supprimer soit appelé N. On l'échange alors par son successeur le plus proche (le noeud le plus à gauche du sous-arbre droit) ou son plus proche prédecesseur (le noeud le plus à droite du sous-arbre gauche) ce qui permet de garder une structure d'arbre binaire de recherche, puis on supprime N qui est alors une feuille ou un noeud avec un seul fils, ce qui nous ramène au cas précédent. Deleting a node with two children from a binary search tree Pour une implémentation efficace, il est déconseillé d'utiliser uniquement le sucesseur ou le prédecesseur, car ceci contribue à déséquilibrer l'arbre Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille: le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut n dans le pire des cas d'où une complexité maximale en O(n).

Parcours ordonné

On peut facilement récupérer les éléments d'un arbre binaire de recherche dans l'ordre de leurs clés en parcourant récursivement le sous-arbre gauche, puis en ajoutant la racine, puis en parcourant récursivement le sous-arbre droit. On peut évidemment le faire dans l'ordre inverse en commençant par le sous-arbre droit. Le parcours de l'arbre se fait en O(n), puisqu'il doit passer par chaque noeud.

Tri

On peut dès lors implémenter un algorithme de tri simple mais peu efficace, en insérant toutes les clés que l'on veut trier dans un nouvelle arbre binaire de recherche, puis en parcourant de manière ordonnée cet arbre comme ci-dessus. Le pire temps d'exécution est O(n²), obtenu lorsque les clés sont déjà ordonnées: on obtient alors une liste chaînée. Par exemple, si on donne dans cet ordre les clés 1,2,3,4,5 on obtient l'arbre (Vide, 1, (Vide, 2, (Vide, 3, (Vide, 4, (Vide, 5))))). Il y a dont nombreuses façons d'éviter ce problème, la plus commune étant l'arbre balancé. On peut alors arriver à un pire des cas en O(n ln n).

Types d'arbres binaires de recherche

Il existe de nombreux types d'arbres binaires de recherche. Les arbres AVL et les arbres rouge-noir sont deux types d'arbres balancés. Un arbre splay est un arbre binaire de recherche qui rapproche automatiquement de la racine les éléments utilisés fréquemment. Dans un treap, chaque noeud possède aussi une priorité supérieure à chacun de ses fils.

Liens externes

- [http://cslibrary.stanford.edu/110/ Une introduction aux arbres binaires de recherche] Catégorie: structure de données ja:2分探索木

Arbre balancé

Catégorie:Algorithmique Catégorie:Structure de données En informatique, un arbre balancé, aussi appelé arbre à critère d'équilibre, est un arbre qui possède un critère d'équilibre par rapport, par exemple, au nombre de nœuds de ses fils et dont les arbres fils sont eux-mêmes balancés. Le but est d'éviter de construire des arbres dégénérés (arbres peignes), par exemple lors de constructions automatisées d'arbres par un programme. Cela peut être très avantageux lorsqu'on réutilise l'arbre ainsi construit. Ainsi, utiliser un arbre balancé permet d'avoir un temps de recherche dans le pire des cas logarithmique par rapport au nombre de nœuds et non linéaire, comme c'est parfois le cas pour des arbres dégénérés.

Arbres binaires de recherche bien balancés

Les arbres binaires de recherche présentent un cas de dégénérescence les rendant peu utiles dans beaucoup de cas. Une amélioration consiste à ajouter à leurs spécifications un critère d'équilibre imposant des restrictions sur le sous-arbre droit (SAD) et gauche (SAG).

Arbre binaire à critère d'équilibre total

Avec ce type d'arbre, le nombre de nœuds dans le SAD et le SAG doivent différer au plus de un. Cette approche est très rarement utile, une insertion pouvant demander la réorganisation de l'arbre entier. Insertion et suppression en O(N), recherche en O(log₂ N).

Arbre binaire à critère d'équilibre partiel

Dans un arbre AVL, la hauteur du SAG et du SAD diffèrent au plus de un. Le nombre de réorganisations maximum est de O(log N), c'est-à-dire la hauteur de l'arbre. L'insertion, la recherche et la suppression sont en O(log N).

Arbre rouge-noir

Arbre SBB ou arbre rouge-noir ou red-black tree : un arbre balancé où la profondeur maximum de l'arbre en 2
- log₂(N + 1).

Arbre 2-3-4

Un arbre 2-3-4 est un 2-4 arbre B ou arbre B d'ordre 2, c'est un dire un arbre comportant uniquement des 2-noeuds, 3-noeuds et 4-noeuds (un N-noeud étant un noeud possédant N-1 clés et N fils), et dont les clés bornent les clés dans les sous arbres (on se reportera à l'article arbre B pour une définition précise). En tant qu'arbre B, on peut l'utiliser pour implémenter le type abstrait table de symboles. Les opérations de recherche, d'insertion et de suppression sont en O(ln n). Cependant l'aspect le plus intéressant des arbres 2-3-4 est leur isométrie avec les arbres rouge-noir, ie pour chaque arbre 2-3-4 il existe un et un seul arbre rouge-noir correspondant. On peut alors trouver un équivalent aux 2-noeuds, 3-noeuds, 4-noeuds sous forme d'arbre rouge-noir, l'avantage principal étant que les arbres rouge-noir sont des arbres binaires balancés, donc plus simples à implémenter et plus rapides. Catégorie:Structure de données

Arbre B

Les arbres B (B-trees ou B-arbres) sont des arbres balancés qui sont principalement utilisés dans l'implémentation de bases de données et de systèmes de fichiers. Ils gardent les données sous forme triée et permettent une insertion et une suppression en temps d'exécution amorti logarithmique. Le principe général est de permettre aux noeuds de posséder plus d'une clé, ce qui minimise la taille de l'arbre et réduit le nombre opérations d'équilibrage. De plus les B-arbres grandissent à partir de la racine contrairement aux arbres binaires de recherche qui poussent à partir des feuilles. Le créateur des arbres B, Rudolf Bayer, n'a pas expliqué la signification du "B". L'explication la plus fréquente est que le B signifie "balancé", cependant il pourrait aussi signifier "Bayer" ou "Boeing", car il travaillait alors pour Boeing Scientific Research Labs.

Structure d'arbre B

Soient L et U deux entiers naturels non nuls tels que L <= U. On définit alors un L-U arbre B de la manière suivante: chaque noeud sauf la racine contient un minimum de L-1 clés (ou éléments), un maximum de U-1 clés, et possède un maximum de U fils. Pour chaque noeud interne (qui n'est pas une feuille), le nombre de fils est toujours le nombre de clés plus un: si n est le nombre de fils, on parle alors de n-noeud: un L-U arbre ne contient que des n-noeuds avec L <= n <= U. Souvent, on prend U=t et L=2
- t, et on appelle t le degré minimal de l'arbre B. De plus la construction des arbres B implique qu'un arbre B est toujours équilibré. Chaque clé d'un noeud interne est en fait une borne qui divise les sous-arbres de ce noeud. Par exemple si un noeud a 3 fils (racines de trois sous-arbres), alors il a 2 clés notées c1 et c2 qui délimitent les clés de chaque sous-arbre: chaque clé du sous-arbre gauche sera inférieure à c1, toutes les clés du sous-arbre du milieu seront comprises entre c1 et c2, et enfin toutes les clés du sous-arbre droit seront supérieures à c2

Opérations

Recherche

La recherche est effectuée de la même manière dans un arbre binaire de recherche. En partant de la racine, on parcourt récursivement l'arbre, en choisissant pour chaque noeud le sous-arbre fils dont les clés seront comprises entre les mêmes bornes que celles de la clé recherchée.

Insertion

L'insertion nécessite tout d'abord de chercher la feuille où la nouvelle clé devrait être insérée, et l'insérer. La suite se déroule récursivement, selon le fait qu'un nœud ait trop de clés ou pas: s'il possède un nombre acceptable de clés, on ne fait rien, sinon on le transforme en deux nœuds, chacun possédant un minimum de clés, et on fait « remonter » la clé du milieu : on l'insère dans le nœud père. Le nœud père peut alors posséder trop de fils: le procédé continue donc jusqu'à ce que l'on atteigne la racine : si celle-ci doit être divisée on fait « remonter » la clé du milieu dans une nouvelle racine, qui aura alors pour fils les deux nœuds crées à partir de l'ancienne racine de la même manière que précédemment. Pour que l'opération soit possible, on remarque qu'il faut que U >= 2L sinon les nouveaux nœuds n'auront pas assez de clés.

Suppression

On doit d'abord chercher la clé à supprimer, et la supprimer du noeud qui la contient.
- Si le noeud est interne, on procède similairement aux arbres binaires de recherche en recherchant la clé la plus à gauche dans le sous-arbre droit de la clé à supprimer ou la plus à droite dans le sous-arbre gauche: celle-ci appartient à une feuille et on peut la permuter avec la clé à supprimer, que l'on supprime ensuite: comme elle appartient à une feuille, on se ramène au cas suivant:
- Si ce noeud est une feuille, soit il possède encore suffisamment de clés et l'algorithme termine, soit il a moins de L-1 clés et alors:
- soit un de ses frères à droite ou à gauche possède suffisamment de clés pour pouvoir en "passer" une à la feuille en question: dans ce cas cette clé remplace la clé qui sépare les deux sous-arbres dans l'arbre père, qui va elle même dans la feuille en question
- soit aucun de ses frères n'a suffisamment de clés: dans ce cas, le père fait passer une de ses clés dans un des deux (ou le seul) frères pour permettre à la feuille de fusionner avec celui-ci. Ceci peut cependant amener le père a ne pas avoir suffisamment de clés: on réitère alors l'algorithme: si le noeud a un frère avec suffisamment de clés, la clé la plus proche va être échangée avec la clé père, puis la clé père et ses nouveaux descendants sont ramenés dans le noeud qui a besoin d'une clé. Sinon on effectue une fusion à l'aide d'une clé du père et ainsi de suite. Si l'on arrive à la racine et qu'elle possède moins de L éléments, on fusionne ses deux fils pour donner une nouvelle racine.

Remarques

- La plupart du temps, on a U=2L: on parle alors d'arbre B d'ordre L.
- Les arbres 2-3-4 sont l'implémentation la plus utilisée des arbres B: se sont en fait des 2-4 arbres B ou arbres B d'ordre 2.

Références

- Rudolf Bayer, Binary B-Trees for Virtual Memory, ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219-235.
- Rudolf Bayer et McCreight, E. M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1, 173-189, 1972.

Lien externe

- [http://slady.net/java/bt/ Un applet Java permettant de construire visuellement des arbres B] Catégorie:Structure de données ja:B木

Catégorie:Algorithmique

Catégorie:Développement logiciel catégorie:Informatique théorique L'algorithmique est la science des algorithmes. Elle vise à étudier les opérations nécessaires à la réalisation d'un calcul. Cette catégorie réunit tous les articles autour de ce thème. Les algorithmes, fruits de l'algorithmique, sont rangés dans la catégorie algorithme. En savoir plus sur l'algorithmique