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.
RécursivitéLa récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle.
Course-of-values recursionIn computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence . The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are primitive recursive.
Diviser pour régner (informatique)thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion En informatique, diviser pour régner (du latin , divide and conquer en anglais) est une technique algorithmique consistant à : Diviser : découper un problème initial en sous-problèmes ; Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ; Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Dynamic loadingDynamic loading is a mechanism by which a computer program can, at run time, load a library (or other ) into memory, retrieve the addresses of functions and variables contained in the library, execute those functions or access those variables, and unload the library from memory. It is one of the 3 mechanisms by which a computer program can use some other software; the other two are static linking and dynamic linking.
Dynamic linkerIn computing, a dynamic linker is the part of an operating system that loads and links the shared libraries needed by an executable when it is executed (at "run time"), by copying the content of libraries from persistent storage to RAM, filling jump tables and relocating pointers. The specific operating system and executable format determine how the dynamic linker functions and how it is implemented.
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.
Algorithmic paradigmAn algorithmic paradigm or algorithm design paradigm is a generic model or framework which underlies the design of a class of algorithms. An algorithmic paradigm is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program. Backtracking Branch and bound Brute-force search Divide and conquer Dynamic programming Greedy algorithm Recursion Prune and search Kernelization Iterative compression Sweep line algorithms Rotating calipers Randomized i
Récursion mutuelleEt mathématiques et en informatique, la récursion mutuelle est une récursion où deux (ou plus) fonctions mathématiques ou programmatiques sont définies l'une en termes de l'autre. En informatique, cependant, on utilise plus souvent le terme "récursivité croisée". Par exemple, deux fonctions A(x) and B(x) définies comme suit : La récursion mutuelle est très commune dans le style de programmation fonctionnelle et est souvent utilisée pour la programmation en LISP, Scheme, ML et celle de langages similaires.
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.
Langage de programmation dynamiqueCet article traite d'une classe des langages de programmation. Pour la méthode consistant en la réduction du temps d'exécution d'un algorithme, voir programmation dynamique On utilise le terme langage de programmation dynamique en informatique pour décrire une classe de langages de haut niveau qui exécutent au moment de l'exécution des actions que d'autres langages ne peuvent exécuter que durant la compilation.
Type systemIn computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type (for example, integer, floating point, string) to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer program, such as variables, expressions, functions, or modules. A type system dictates the operations that can be performed on a term. For variables, the type system determines the allowed values of that term.
Problème du sac à dosEn algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.
Hilbert schemeIn algebraic geometry, a branch of mathematics, a Hilbert scheme is a scheme that is the parameter space for the closed subschemes of some projective space (or a more general projective scheme), refining the Chow variety. The Hilbert scheme is a disjoint union of projective subschemes corresponding to Hilbert polynomials. The basic theory of Hilbert schemes was developed by . Hironaka's example shows that non-projective varieties need not have Hilbert schemes.
Schéma noethérienEn géométrie algébrique, les schémas noethériens sont aux schémas ce que les anneaux noethériens sont aux anneaux commutatifs. Ce sont les schémas qui possèdent un certain nombre de propriétés de finitude. De nombreux résultats fondamentaux en géométrie algébrique sont montrés dans le cadre des schémas noethériens. Il est généralement considéré comme raisonnable de travailler dans la catégorie des schémas noethériens. Un schéma affine Spec A est noethérien si A est un anneau noethérien.
Problème de décisionEn informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.
Règle du produitEn analyse mathématique, la règle du produit, aussi appelée règle de Leibniz, est une formule utilisée afin de trouver les dérivées de produits de fonctions. Sous sa forme la plus simple, elle s'énonce ainsi : En notation de Leibniz, cette formule s'écrit : Une application importante de la règle du produit est la méthode d'intégration par parties. Soit la fonction définie par : Pour trouver sa dérivée avec la règle du produit, on pose et . Les fonctions , et sont partout dérivables car polynomiales.
Quotient ruleIn calculus, the quotient rule is a method of finding the derivative of a function that is the ratio of two differentiable functions. Let , where both f and g are differentiable and The quotient rule states that the derivative of h(x) is It is provable in many ways by using other derivative rules. Given , let , then using the quotient rule: The quotient rule can be used to find the derivative of as follows: Reciprocal rule The reciprocal rule is a special case of the quotient rule in which the numerator .
Algorithme de Cocke-Younger-KasamiEn informatique théorique et en théorie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles, publié par Itiroo Sakai en 1961. Il permet de déterminer si un mot est engendré par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nommé d'après les trois personnes qui l'ont redécouvert indépendamment, J. Cocke, dont l'article n'a jamais été publié, D. H. Younger et T. Kasami qui a publié un rapport interne aux US-AirForce.
Problème du voyageur de commercevignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.
