Modèle de cohérenceEn Informatique, les modèles de cohérence sont utilisés dans les systèmes répartis comme les systèmes de mémoire partagée distribuée (DSM) ou les magasins de données distribuées (tels que les système de fichiers, les bases de données, les systèmes de réplication optimiste ou la mise en cache web). On dit que le système supporte un modèle donné si les opérations sur la mémoire suivent des règles spécifiques.
Structure de donnéesEn informatique, une structure de données est une manière d'organiser les données pour les traiter plus facilement. Une structure de données est une mise en œuvre concrète d'un type abstrait. 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.
Structure de données persistanteEn informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu'elle est modifiée ; une telle structure est immuable, car ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures. Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture. La structure est dite totalement persistante si chacune de ses versions peut être lue ou modifiée.
Mise en œuvreLa mise en œuvre est le fait de mettre en place un projet. En ingénierie et plus particulièrement en informatique, la mise en œuvre désigne la création d’un produit fini à partir d’un document de conception, d’un document de spécification, voire directement depuis une version originelle ou un cahier des charges. L’utilisation de l’anglicisme « implémentation », de l'anglais to implement, est courante (et acceptée).
Problème NP-completEn théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
DonnéeUne donnée est ce qui est connu et qui sert de point de départ à un raisonnement ayant pour objet la détermination d'une solution à un problème en relation avec cette donnée. Cela peut être une description élémentaire qui vise à objectiver une réalité, le résultat d'une comparaison entre deux événements du même ordre (mesure) soit en d'autres termes une observation ou une mesure. La donnée brute est dépourvue de tout raisonnement, supposition, constatation, probabilité.
Réduction polynomialeUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .
Purely functional data structureIn computer science, a purely functional data structure is a data structure that can be directly implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable. This restriction ensures the data structure possesses the advantages of immutable objects: (full) persistency, quick copy of objects, and thread safety. Efficient purely functional data structures may require the use of lazy evaluation and memoization.
Test (informatique)vignette|Une programmeuse écrivant du code Java avec JUnit. En informatique, un test désigne une procédure de vérification partielle d'un système. Son objectif principal est d'identifier un nombre maximal de comportements problématiques du logiciel. Il permet ainsi, dès lors que les problèmes identifiés seront corrigés, d'en augmenter la qualité. D'une manière plus générale, le test désigne toutes les activités qui consistent à rechercher des informations quant à la qualité du système afin de permettre la prise de décisions.
Calcul distribuéUn calcul distribué, ou réparti ou encore partagé, est un calcul ou un traitement réparti sur plusieurs microprocesseurs et plus généralement sur plusieurs unités centrales informatiques, et on parle alors d'architecture distribuée ou de système distribué. Le calcul distribué est souvent réalisé sur des clusters de calcul spécialisés, mais peut aussi être réalisé sur des stations informatiques individuelles à plusieurs cœurs. La distribution d'un calcul est un domaine de recherche des sciences mathématiques et informatiques.
Temps de calcul pseudo-polynomialEn informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée). Considérons le problème du test de primalité. On peut vérifier qu'un entier naturel donné n est premier en testant qu'il n'est divisible par aucun des entiers . Cela exige divisions, de sorte que le temps pris par cet algorithme naïf est linéaire en la valeur n .
Type (informatique)vignette|Présentation des principaux types de données. En programmation informatique, un type de donnée, ou simplement un type, définit la nature des valeurs que peut prendre une donnée, ainsi que les opérateurs qui peuvent lui être appliqués. La plupart des langages de programmation de haut niveau offrent des types de base correspondant aux données qui peuvent être traitées directement — à savoir : sans conversion ou formatage préalable — par le processeur.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
Hiérarchie polynomialeEn théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Test de régressionUn test de régression, ou test de non-régression, est un test ayant pour but de détecter les régressions introduites dans un logiciel après un changement effectué dans celui-ci. Une régression est un défaut qui se produit après une modification d'un logiciel lorsque des fonctionnalités existantes ne sont plus réalisées aussi bien qu'avant.
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Automate finithumb|upright=2|Fig. 1 : Une hiérarchie d'automates. Un automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine ou FSM) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie.
Test unitaireEn programmation informatique, le test unitaire (ou « T.U. », ou « U.T. » en anglais) est une procédure permettant de vérifier le bon fonctionnement d'une partie précise d'un logiciel ou d'une portion d'un programme (appelée « unité » ou « module »). Dans les applications non critiques, l'écriture des tests unitaires a longtemps été considérée comme une tâche secondaire. Cependant, les méthodes Extreme programming (XP) ou Test Driven Development (TDD) ont remis les tests unitaires, appelés « tests du programmeur », au centre de l'activité de programmation.
Test de validationUn test de validation est un type de test informatique qui permet de vérifier si toutes les exigences client, décrites dans le document de spécification du logiciel, sont respectées. Les tests de validation se décomposent généralement en plusieurs phases : Validation fonctionnelle : les tests fonctionnels assurent que les différents modules ou composants implémentent correctement les exigences client. Ces tests peuvent être de type valide, invalide, inopportuns, etc.
Vérification formelleIn the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. Formal verification can be helpful in proving the correctness of systems such as: cryptographic protocols, combinational circuits, digital circuits with internal memory, and software expressed as source code.
