Vérification de modèlesthumb|308x308px|Principe du model checking. En informatique, la vérification de modèles, ou model checking en anglais, est le problème suivant : vérifier si le modèle d'un système (souvent informatique ou électronique) satisfait une propriété. Par exemple, on souhaite vérifier qu'un programme ne se bloque pas, qu'une variable n'est jamais nulle, etc. Généralement, la propriété est écrite dans un langage, souvent en logique temporelle. La vérification est généralement faite de manière automatique.
Pointeur (programmation)En programmation informatique, un pointeur est un objet qui contient l'adresse mémoire d'une donnée ou d'une fonction. C'est l'outil fondamental de l'adressage dit « indirect ». La notion de pointeur reflète l'utilisation différente que l'on peut faire d'un entier naturel, à savoir indiquer une adresse mémoire. Cette utilisation est très différente d'une utilisation arithmétique, d'où la création de registres de processeurs spécifiques (les registres d'adresse) et d'un type de donnée spécifique dans les langages de programmations.
Type récursifEn programmation informatique et théorie des types, un type récursif est un type de données dont la définition fait appel au type lui‐même, de façon récursive. Cela permet entre autres des structures de données qui contiennent des sous‐structures du même type. Cette notion s'applique naturellement dans l'étude des listes et des arbres. Type algébrique de données Les types algébriques sont de loin la forme la plus courante de types récursifs. Un exemple classique est le type liste.
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.
Algorithme récursifUn algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème. L'approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même.
Abstraction (philosophie)L’abstraction est l'opération mentale, de l'esprit par laquelle les propriétés générales, universelles et nécessaires d'un objet sont distinguées de ses propriétés particulières et contingentes. Par cette opération, notre pensée prend une distance par rapport à l'expérience sensible et forme l'ensemble de nos idées qui seront consignées dans le langage. L'opération d'abstraction permet de distinguer entre l'abstrait et le concret. Ceux-ci forment une opposition conceptuelle fondamentale en philosophie.
Null pointerIn computing, a null pointer or null reference is a value saved for indicating that the pointer or reference does not refer to a valid object. Programs routinely use null pointers to represent conditions such as the end of a list of unknown length or the failure to perform some action; this use of null pointers can be compared to nullable types and to the Nothing value in an option type. A null pointer should not be confused with an uninitialized pointer: a null pointer is guaranteed to compare unequal to any pointer that points to a valid object.
Type algébrique de donnéesUn type algébrique est une forme de type de données composite, qui combine les fonctionnalités des types produits (n‐uplets ou enregistrements) et des types sommes (union disjointe). Combinée à la récursivité, elle permet d’exprimer les données structurées telles que les listes et les arbres. Le type produit de deux types A et B est l’analogue en théorie des types du produit cartésien ensembliste et est noté A × B. C’est le type des couples dont la première composante est de type A et la seconde de type B.
Hypostatic abstractionHypostatic abstraction in mathematical logic, also known as hypostasis or subjectal abstraction, is a formal operation that transforms a predicate into a relation; for example "Honey is sweet" is transformed into "Honey has sweetness". The relation is created between the original subject and a new term that represents the property expressed by the original predicate. Hypostasis changes a propositional formula of the form X is Y to another one of the form X has the property of being Y or X has Y-ness.
Programmation orientée objetLa programmation orientée objet (POO), ou programmation par objet, est un paradigme de programmation informatique. Elle consiste en la définition et l'interaction de briques logicielles appelées objets ; un objet représente un concept, une idée ou toute entité du monde physique, comme une voiture, une personne ou encore une page d'un livre. Il possède une structure interne et un comportement, et il sait interagir avec ses pairs.
Tagged pointerIn computer science, a tagged pointer is a pointer (concretely a memory address) with additional data associated with it, such as an indirection bit or reference count. This additional data is often "folded" into the pointer, meaning stored inline in the data representing the address, taking advantage of certain properties of memory addressing. The name comes from "tagged architecture" systems, which reserved bits at the hardware level to indicate the significance of each word; the additional data is called a "tag" or "tags", though strictly speaking "tag" refers to data specifying a type, not other data; however, the usage "tagged pointer" is ubiquitous.
Logique ternaireLa logique ternaire, ou logique 3 états, est une branche du calcul des propositions qui étend l'algèbre de Boole, en considérant, en plus des états VRAI et FAUX, l'état INCONNU. Dans la logique ternaire de Stephen Cole Kleene, les tables de vérité des fonctions de base sont les suivantes : D'une certaine manière, ces propriétés correspondent à l'intuition : par exemple, si on ignore si A est vrai ou faux, son inverse est tout aussi incertain. Les autres fonctions logiques se déduisent de par leur définition, la distributivité continuant à s'appliquer.
Tas binaireEn informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une car elle permet de retirer l’élément de priorité maximale (resp. minimale) d'un ensemble ou d’insérer un élément dans l'ensemble en temps logarithmique tout en conservant la structure du tas binaire. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes : C'est un arbre binaire complet : tous les niveaux sauf le dernier doivent être totalement remplis et si le dernier ne l'est pas totalement, alors il doit être rempli de gauche à droite.
Pointeur intelligentEn informatique, un pointeur intelligent (en anglais smart pointer) est un type abstrait de données qui simule le comportement d'un pointeur en y adjoignant des fonctionnalités telles que la libération automatique de la mémoire allouée ou la vérification des bornes. La gestion manuelle de la mémoire dans les langages utilisant les pointeurs est une source courante de bugs, en particulier de fuites de mémoire ou de plantages.
Software verificationSoftware verification is a discipline of software engineering, programming languages, and theory of computation whose goal is to assure that software satisfies the expected requirements. A broad definition of verification makes it related to software testing. In that case, there are two fundamental approaches to verification: Dynamic verification, also known as experimentation, dynamic testing or, simply testing. - This is good for finding faults (software bugs).
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Tas de FibonacciEn informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe.
Generalized algebraic data typeIn functional programming, a generalized algebraic data type (GADT, also first-class phantom type, guarded recursive datatype, or equality-qualified type) is a generalization of parametric algebraic data types. In a GADT, the product constructors (called data constructors in Haskell) can provide an explicit instantiation of the ADT as the type instantiation of their return value. This allows defining functions with a more advanced type behaviour.
Programmation fonctionnelleLa programmation fonctionnelle est un paradigme de programmation de type déclaratif qui considère le calcul en tant qu'évaluation de fonctions mathématiques. Comme le changement d'état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état.
Théorie spectrale des graphesEn mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .
