Démonstration (logique et mathématiques)vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.
Fonction récursiveEn informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives).
Suite de Fibonaccivignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Notée , elle est définie par , et pour . Les termes de cette suite sont appelés nombres de Fibonacci et forment la : vignette|Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.
Récurrence transfinieEn mathématiques, on parle de récurrence transfinie ou de récursion transfinie pour deux principes reliés mais distincts. Les définitions par récursion transfinie — permettent de construire des objets infinis, et généralisent les définitions de suite par récurrence sur l'ensemble N des entiers naturels en considérant des familles indexées par un ordinal infini quelconque, au lieu de se borner au plus petit d'entre eux qu'est N, appelé ω en tant que nombre ordinal.
Fonction récursive primitiveEn théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion primitive (ou bornée) et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. Elles ont été initialement analysées par la mathématicienne Rózsa Péter. On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des -uplets d'entiers naturels, et à valeurs dans .
Induction structurelleEn mathématiques et davantage en informatique, la définition récursive ou induction structurelle est un procédé de définition conjointe d'un type (classe ou ensemble) et d'objets (éléments) qui le compose au moyen de règles de construction (constructeurs) qui agencent ou structurent ces objets. L'on peut ainsi définir des nombres, des listes, des arbres, des relations, et plus généralement, toute structure mathématique (langage, système, ...). En permettant par le même principe de définir un prédicat total i.
FactorielleEn mathématiques, la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Cette opération est notée avec un point d'exclamation, n!, ce qui se lit soit « factorielle de n », soit « factorielle n », soit « n factorielle ». Cette notation a été introduite en 1808 par Christian Kramp. Par exemple, la factorielle 10 exprime le nombre de combinaisons possibles de placement des 10 convives autour d'une table (on dit la permutation des convives).
Généralisations de la suite de FibonacciEn mathématiques, la suite de Fibonacci est définie par récurrence par : pour tout entier . Autrement dit, les deux valeurs de départ 0 et 1 étant données, chaque nombre est la somme des deux précédents. La suite de Fibonacci peut être généralisée de nombreuses façons ; par exemple, en partant d'autres nombres que 0 et 1, en ajoutant plus de deux termes pour générer le suivant, ou en ajoutant des objets autres que des nombres. À l'aide de la relation , on peut étendre la suite de Fibonacci à des indices entiers négatifs.
Codage de FibonacciLe codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs. Le code de Fibonacci produit est un code préfixe et universel. Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur.
Polynôme de FibonacciEn mathématiques les polynômes de Fibonacci, nommés ainsi en l'honneur du mathématicien italien Leonardo Fibonacci, sont une suite de polynômes généralisant les nombres de Fibonacci, définis d'une manière telle que soit égal au n-ième nombre de la suite de Fibonacci. Les polynômes de Lucas généralisent de même les nombres de Lucas. Les polynômes de Fibonacci sont définis par une relation de récurrence linéaire. est un polynôme de degré n-1.
Computable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.
Fonction gammaEn mathématiques, la fonction gamma (notée par Γ la lettre grecque majuscule gamma de l'alphabet grec) est une fonction utilisée communément, qui prolonge de la fonction factorielle à l'ensemble des nombres complexes. En ce sens, il s'agit une fonction complexe. Elle est considérée également comme une fonction spéciale. La fonction gamma est défini pour tous les nombres complexes, à l'exception des entiers négatifs. On a pour tout entier strictement positif, où est la factorielle de , c'est-à-dire le produit des entiers entre 1 et : .
Double factorialIn mathematics, the double factorial of a number n, denoted by n!!, is the product of all the positive integers up to n that have the same parity (odd or even) as n. That is, Restated, this says that for even n, the double factorial is while for odd n it is For example, 9!! = 9 × 7 × 5 × 3 × 1 = 945. The zero double factorial 0!! = 1 as an empty product. The sequence of double factorials for even n = 0, 2, 4, 6, 8,... starts as The sequence of double factorials for odd n = 1, 3, 5, 7, 9,...
Mot de FibonacciEn mathématiques et plus précisément en combinatoire des mots, un mot de Fibonacci est une suite particulière de symboles pris dans un alphabet quelconque de deux lettres. Les mots de Fibonacci sont à l'opération de concaténation ce que les nombres de Fibonacci sont à l'addition. Le mot de Fibonacci infini est l'exemple paradigmatique de mot sturmien. Le nom « mot de Fibonacci » réfère aussi parfois aux éléments d'un langage formel composé des mots sur un alphabet de deux lettres et et ne contenant pas deux consécutifs.
Fonction d'AckermannDans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la forme qu'en a proposée la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(m, n).
Proof by contradictionIn logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved.
Falling and rising factorialsIn mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, rising sequential product, or upper factorial) is defined as The value of each is taken to be 1 (an empty product) when These symbols are collectively called factorial powers. The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation (x)_n , where n is a non-negative integer.
Computer-assisted proofA computer-assisted proof is a mathematical proof that has been at least partially generated by computer. Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a computer program to perform lengthy computations, and to provide a proof that the result of these computations implies the given theorem. In 1976, the four color theorem was the first major theorem to be verified using a computer program.
Induction (logique)L'induction est historiquement le nom utilisé pour signifier un genre de raisonnement qui se propose de chercher des lois générales à partir de l'observation de faits particuliers, sur une base probabiliste. Remarque : Bien qu'associée dans le titre de cet article à la logique, la présentation qui suit correspond surtout à la notion bayésienne, utilisée consciemment ou non, de l'induction.
Démonstration constructiveUne première vision d'une démonstration constructive est celle d'une démonstration mathématique qui respecte les contraintes des mathématiques intuitionnistes, c'est-à-dire qui ne fait pas appel à l'infini, ni au principe du tiers exclu. Ainsi, démontrer l'impossibilité de l'inexistence d'un objet ne constitue pas une démonstration constructive de son existence : il faut pour cela en exhiber un et expliquer comment le construire. Si une démonstration est constructive, on doit pouvoir lui associer un algorithme.
