Arbre binaireEn informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.
Trie (informatique)thumb|250px|Un trie pour les clés "A", "to", "tea", "ten", "ted", "i", "in", et "inn". En informatique, un ou une trie (prononcé ou ) ou arbre préfixe, est une structure de données ayant la forme d'un arbre enraciné. Il est utilisé pour stocker une table associative où les clés sont généralement des chaînes de caractères. Contrairement à un arbre binaire de recherche, aucun nœud dans le trie ne stocke la chaîne à laquelle il est associé. C'est la position du nœud dans l'arbre qui détermine la chaîne correspondante.
Algorithme de rechercheEn informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.
Arbre binaire de rechercheEn informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
Recherche dichotomiqueLa recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.
Tableau (structure de données)En informatique, un tableau est une structure de données représentant une séquence finie d'éléments auxquels on peut accéder efficacement par leur position, ou indice, dans la séquence. C'est un type de conteneur que l'on retrouve dans un grand nombre de langages de programmation. Dans les langages à typage statique (comme C, Java et OCaml), tous les éléments d’un tableau doivent être du même type. Certains langages à typage dynamique (tels APL et Python) permettent des tableaux hétérogènes.
Arbre splayUn arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.
Ensemble (informatique)En informatique, un ensemble ou set est un type abstrait qui peut stocker certaines valeurs, sans ordre particulier, et sans répétition. Il s'agit d'une mise en œuvre informatique de la notion mathématique d'ensemble fini. Un ensemble stocke des valeurs, sans ordre défini, et ne contient pas de données en double (la tentative d'insertion d'une donnée déjà présente est sans effet). Contrairement à la plupart des autres types de collections les ensembles sont plus utilisés pour tester l'appartenance d'une valeur à cet ensemble que pour en extraire des données.
Self-balancing binary search treeIn computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".
Tableau associatifEn informatique, un tableau associatif (aussi appelé dictionnaire ou table d'association) est un type de données associant à un ensemble de clefs, un ensemble correspondant de valeurs. Chaque clef est associée à une seule valeur (au plus) : un tableau associatif correspond donc à une application de domaine fini en mathématiques. Du point de vue du programmeur, le tableau associatif peut être vu comme une généralisation du tableau : alors que le tableau traditionnel associe des entiers consécutifs à des valeurs, le tableau associatif associe des clefs d'un type arbitraire à des valeurs d'un autre type.
Matrice JudyEn informatique, une matrice Judy est une structure de données mettant en œuvre un type de tableau associatif offrant de hautes performances et une faible utilisation de la mémoire. Contrairement à la plupart des autres bases de données clé-valeur, les matrices Judy n'utilisent pas de hachage, exploitent la compression sur leurs clés (qui peuvent être des entiers ou des chaînes de caractères) et peuvent représenter efficacement des données éparses, c'est-à-dire qu'ils peuvent avoir de grandes plages d'indices non attribués sans augmenter considérablement l'utilisation de la mémoire ou le temps de traitement.
Adressage mémoireL’adressage mémoire est, en électronique et en informatique, la façon dont se fait l'accès aux données conservées en mémoire. Une adresse mémoire est un nombre entier naturel (rarement une autre sorte d'identifiant) qui désigne une zone particulière de la mémoire, ou juste le début d'une zone. Le plus souvent, une donnée peut être lue ou écrite. La mémoire peut être temporaire (mémoire vive) pour le travail ou au contraire durable (mémoire non volatile) pour le stockage.
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Memory pagingIn computer operating systems, memory paging (or swapping on some Unix-like systems) is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. Paging is an important part of virtual memory implementations in modern operating systems, using secondary storage to let programs exceed the size of available physical memory.
Table de hachageUne table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.
Gestion de la mémoireLa gestion de la mémoire est une forme de gestion des ressources appliquée à la mémoire de l'ordinateur. L'exigence essentielle de la gestion de la mémoire est de fournir des moyens d'allouer dynamiquement des portions de mémoire aux programmes à leur demande, et de les libérer pour réutilisation lorsqu'elles ne sont plus nécessaires. Ceci est essentiel pour tout système informatique avancé où plus d'un processus peuvent être en cours à tout moment. Catégorie:Architecture informatique Catégorie:Pages avec
Algorithme de triUn algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique.
Fonction d'ordre supérieurEn mathématiques et en informatique, les fonctions d'ordre supérieur sont des fonctions qui ont au moins une des propriétés suivantes : elles prennent une ou plusieurs fonctions en entrée ; elles renvoient une fonction. En mathématiques, on les appelle des opérateurs ou des fonctionnelles. L'opérateur de dérivation en calcul infinitésimal est un exemple classique, car elle associe une fonction (la dérivée) à une autre fonction (la fonction que l'on dérive). Dans le lambda-calcul non typé, toutes les fonctions sont d'ordre supérieur.
Mémoire virtuellethumb|Schéma de principe de la mémoire virtuelle. En informatique, le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il repose sur l'utilisation de traduction à la volée des adresses (virtuelles) vues du logiciel, en adresses physiques de mémoire vive. La mémoire virtuelle permet : d'utiliser de la mémoire de masse comme extension de la mémoire vive ; d'augmenter le taux de multiprogrammation ; de mettre en place des mécanismes de protection de la mémoire ; de partager la mémoire entre processus.
First-class functionIn computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures. Some programming language theorists require support for anonymous functions (function literals) as well.
