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.
Hypothèse calculatoireEn cryptographie, une hypothèse de difficulté calculatoire est une hypothèse qui sert à évaluer et à démontrer la robustesse des primitives cryptographiques. Dans certains cas, la sécurité est dite inconditionnelle si elle ne repose sur aucune hypothèse de difficulté calculatoire ; un exemple courant est la technique dite du masque jetable, où le masque est aussi grand que le message. Cependant, il est souvent impossible d'atteindre une forme de sécurité aussi forte ; dans de tels cas, les cryptographes doivent s'en remettre à une forme de sécurité dite « calculatoire ».
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
Marine biogeochemical cyclesMarine biogeochemical cycles are biogeochemical cycles that occur within marine environments, that is, in the saltwater of seas or oceans or the brackish water of coastal estuaries. These biogeochemical cycles are the pathways chemical substances and elements move through within the marine environment. In addition, substances and elements can be imported into or exported from the marine environment. These imports and exports can occur as exchanges with the atmosphere above, the ocean floor below, or as runoff from the land.
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 .
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 .
Schéma d'approximation en temps polynomialEn informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.
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.
Cycle du carbonevignette|redresse=2|Schéma du cycle du carbone : l'immense réservoir de carbone est la lithosphère qui stocke 80 000 000 Gigatonnes (Gt) de carbone minéral, sous forme de roches carbonatées et 14 000 Gt de carbone dans la matière organique fossile (réévaluation par rapport aux données du schéma). L'hydrosphère est un réservoir intermédiaire qui stocke 39 000 Gt de carbone sous forme de . L’atmosphère et la biosphère sont des petits réservoirs : le premier stocke 750 Gt principalement sous forme de , le second deux à trois fois plus selon les auteurs.
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.
PlanteLes plantes (Plantae) sont des organismes photosynthétiques et autotrophes, caractérisés par des cellules végétales. Elles forment l'un des règnes des Eukaryota. Ce règne est un groupe monophylétique comprenant les plantes terrestres. La science des plantes est la botanique, qui dans son acception classique étudie aussi les algues et les cyanobactéries (qui n'appartiennent pas au règne des Plantae). L'ancien « règne végétal » n'existe plus dans les classifications modernes (cladistes ou évolutionnistes).
Polynôme symétriqueEn mathématiques, un polynôme symétrique est un polynôme en plusieurs indéterminées, invariant par permutation de ses indéterminées. Ils jouent notamment un rôle dans les relations entre coefficients et racines. Soit A un anneau commutatif unitaire. Un polynôme Q(T, ..., T) en n indéterminées à coefficients dans A est dit symétrique si pour toute permutation s de l'ensemble d'indices {1, ..., n}, l'égalité suivante est vérifiée : Exemples Pour n = 1, tout polynôme est symétrique.
Hamiltonian path problemIn the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete.
Cycle de l'eauLe cycle de l'eau, ou cycle hydrologique correspond à l'ensemble des transferts d'eau (liquide, solide ou gazeuse) entre les réservoirs d'eau sur Terre (les océans, l'atmosphère, les lacs, les cours d'eau, les nappes d'eau souterraine et les glaciers). Le « moteur » de ce cycle est l'énergie solaire qui, en favorisant l'évaporation de l'eau, entraîne tous les autres échanges. La science qui étudie le cycle de l’eau est l’hydrologie.
Cycle biogéochimiqueUn cycle biogéochimique est le processus de transport et de transformation cyclique (recyclage) d'un élément ou composé chimique entre les grands réservoirs que sont la géosphère, l'atmosphère, l'hydrosphère, dans lesquels se retrouve la biosphère. Un tel cycle induit souvent des passages de l'état organique à l'état minéral au sein de la biosphère. Les divers cycles en interaction confèrent à la biosphère une capacité de régulation, appelée homéostasie.
Problème de la cliquethumb|upright=1.5|Recherche exhaustive d'une 4-clique dans ce graphe à 7 sommets en testant la complétude des C(7,4)= 35 sous-graphes à 4 sommets. En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées.
Lattice-based cryptographyLattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.
Théorème fondamental des fonctions symétriquesEn mathématiques, et plus particulièrement en algèbre commutative, le théorème fondamental des fonctions symétriques, souvent appelé « théorème fondamental des polynômes symétriques » ou « théorème de Newton », stipule que tout polynôme symétrique en n indéterminées à coefficients dans un anneau (commutatif) A s'exprime de façon unique par une fonction polynomiale des n polynômes symétriques élémentaires. Autrement dit, les n polynômes symétriques élémentaires forment une partie génératrice de l'algèbre des polynômes symétriques en n indéterminées sur A et sont algébriquement indépendants sur A.
Sécurité inconditionnelleEn cryptologie, la sécurité inconditionnelle est un critère de sécurité important dans le cadre des algorithmes de chiffrement. Cette sécurité est intimement liée à la théorie de l'information et la notion d'entropie, elle a été définie dans le cadre des travaux de Claude Shannon à la fin des années 1940. Si le critère est rempli, un attaquant ne récupère aucune information sur le texte clair à partir du texte chiffré. À ce jour, seul le masque jetable remplit cette condition sous des hypothèses strictes.
Problème de réseauIn computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes.
