Analyse de la complexité des algorithmesvignette|Représentation d'une recherche linéaire (en violet) face à une recherche binaire (en vert). La complexité algorithmique de la seconde est logarithmique alors que celle de la première est linéaire. L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme. Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier.
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
George PólyaGeorge (György) Pólya, né à Budapest (Hongrie) le dans une famille juive hongroise convertie au catholicisme en 1886 et mort à Palo Alto (États-Unis) le , est un mathématicien américain d'origine hongroise et suisse. Après des études secondaires classiques, il est admis en 1905 à l'université de Budapest où il passe du droit à la linguistique, à la philosophie et finalement à la physique et aux mathématiques. En 1910-1911, il poursuit ses études à l'université de Vienne puis retourne à Budapest pour un doctorat de mathématiques, et séjourne bientôt à Göttingen puis à Paris en 1914.
Corps algébriquement closEn mathématiques, un corps commutatif K est dit algébriquement clos si tout polynôme de degré supérieur ou égal à un, à coefficients dans K, admet (au moins) une racine dans K. Autrement dit, c'est un corps qui n'a pas d'extension algébrique propre. Si K est algébriquement clos, tout polynôme non constant à coefficients dans K est scindé dans K, c'est-à-dire produit de polynômes du premier degré. Le nombre de ses racines dans K (comptées avec leur ordre de multiplicité) est donc exactement égal à son degré.
Plus grand commun diviseurEn arithmétique élémentaire, le plus grand commun diviseur ou PGCD de deux nombres entiers non nuls est le plus grand entier qui les divise simultanément. Par exemple, le PGCD de 20 et de 30 est 10, puisque leurs diviseurs communs sont 1, 2, 5 et 10. Cette notion s'étend aux entiers relatifs grâce aux propriétés de la division euclidienne. Elle se généralise aussi aux anneaux euclidiens comme l'anneau des polynômes sur un corps commutatif. La notion de PGCD peut être définie dans tout anneau commutatif.
RéfutabilitéLa réfutabilité (également désignée par le recours à l'anglicisme falsifiabilité) a été introduite par Karl Popper et est considérée comme un concept important de l'épistémologie, permettant d'établir une démarcation entre les théories scientifiques et celles qui ne le sont pas. Une affirmation, une hypothèse, est dite réfutable si et seulement si elle peut être logiquement contredite par un test empirique ou, plus précisément, si et seulement si un énoncé d'observation (vrai ou faux) ayant une interprétation empirique (respectant ou non les lois actuelles et à venir) contredit logiquement la théorie.
Ensemble finiEn mathématiques, un ensemble fini est un ensemble qui possède un nombre fini d'éléments, c'est-à-dire qu'il est possible de compter ses éléments, le résultat étant un nombre entier. Un ensemble infini est un ensemble qui n'est pas fini. Ainsi l'ensemble des chiffres usuels (en base dix) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} qui possède 10 éléments, est fini. De même l'ensemble des lettres de l'alphabet qui possède 26 éléments. L'ensemble de tous les nombres entiers naturels {0, 1, 2, 3,..., 10,..., 100,...
Ensemblevignette|Ensemble de polygones dans un diagramme d'Euler En mathématiques, un ensemble désigne intuitivement un rassemblement d’objets distincts (les éléments de l'ensemble), « une multitude qui peut être comprise comme une totalité » pour paraphraser Georg Cantor qui est à l'origine de la théorie des ensembles. Dans une approche axiomatique, la théorie des ensembles est une théorie de l'appartenance (un élément d'un ensemble est dit « appartenir » à cet ensemble).
Luca PacioliLuca Bartolomes Pacioli OFM, dit Luca di Borgo (vers 1447 à Borgo Sansepolcro en Toscane - entre avril et octobre 1517, probablement dans la même ville), est un religieux franciscain italien, vulgarisateur des mathématiques, mathématicien et fondateur de la comptabilité. Il est considéré comme le père du principe connu sous le nom de . Luca Pacioli ou Luca di Borgo commence ses études à Borgo Sansepolcro en Toscane. En 1464, il les poursuit à Venise où il suit les cours de Domenico Bragadino, lecteur public de la République de Venise.
Hypothèse du continuEn théorie des ensembles, l'hypothèse du continu (HC), due à Georg Cantor, affirme qu'il n'existe aucun ensemble dont le cardinal est strictement compris entre le cardinal de l'ensemble des entiers naturels et celui de l'ensemble des nombres réels. En d'autres termes : tout ensemble strictement plus grand, au sens de la cardinalité, que l'ensemble des entiers naturels doit contenir une « copie » de l'ensemble des nombres réels.
