Comparaison asymptotique

Résumé

En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction au voisinage d'un point ou à l'infini, en la comparant à celle d'une autre fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une échelle de référence, contenant en général au moins certaines fonctions dites élémentaires, en particulier les sommes et produits de polynômes, d'exponentielles et de logarithmes. Les notations correspondantes sont en particulier utilisées en physique et en informatique, par exemple pour décrire la complexité de certains algorithmes. Elles sont également utilisées en théorie analytique des nombres pour évaluer finement l'erreur commise en remplaçant une fonction irrégulière, comme celle comptant les nombres premiers, par une fonction de l'échelle choisie. La méthode a été introduite par les travaux de Paul du Bois-Reymond à partir de 1872 ; pour faciliter les

Source officielle

https://fr.wikipedia.org/wiki/Comparaison_asymptotique

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (34)

Publications associées

Chargement

Personnes associées (2)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (94)

thumb|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

En 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'arrive

En informatique, le tri fusion, ou tri dichotomique, est un algorithme de tri par comparaison stable. Sa complexité temporelle pour une entrée de taille n est de l'ordre de n log n, ce qui est asymp

Afficher plus

Concepts associés

Chargement

Cours associés (89)

Cours associés

Chargement

Séances de cours associées (185)

Séances de cours associées

Chargement

Disjoint crossings, positive speed and deviation estimates for first passage percolation

Ghurumuruhan Ganesan

Consider bond percolation on the square lattice Z(2) where each edge is independently open with probability p : For some positive constants p(0) is an element of( 0; 1); epsilon(1) and epsilon(2); the following holds: if p > p(0); then with probability at least 1 - epsilon(1) /n(4) there are at least epsilon(2)n/logn disjoint open left-right crossings in B-n : = 0; n each having length at most 2n; for all n >= 2 : Using the proof of the above, we obtain positive speed for first passage percolation with independent and identically distributed edge passage times {t(e(i))}(i) satisfying E (logt (e(1)))(+) < infinity; namely, lim sup(n) T-pl (0, n)/n

Univ Washington, Dept Mathematics2014

Chargement

Infection Spread In Random Geometric Graphs

Ghurumuruhan Ganesan

In this paper we study the speed of infection spread and the survival of the contact process in the random geometric graph G = G (n, r(n), f) of n nodes independently distributed in S = -1/2, 1/2 according to a certain density f(.). In the first part of the paper we assume that infection spreads from one node to another at unit rate and that infected nodes stay in the same state forever. We provide an explicit lower bound on the speed of infection spread and prove that infection spreads in G with speed at least D(1)nr(n)(2). In the second part of the paper we consider the contact process xi(t) on G where infection spreads at rate lambda > 0 from one node to another and each node independently recovers at unit rate. We prove that, for every lambda > 0, with high probability, the contact process on G survives for an exponentially long time; there exist positive constants c(1) and c(2) such that, with probability at least 1 - c(1)/n(4), the contact process xi(1)(t) starting with all nodes infected survives up to time t(n) = exp(c(2)n/log n) for all n.

Applied Probability Trust2015

Chargement

Theory and tool support for the formal verification of cryptographic protocols

Sébastien Briais

Cryptographic protocols are an essential component of network communications. Despite their relatively small size compared to other distributed algorithms, they are known to be error-prone. This is due to the obligation to behave robustly in the context of unknown hostile attackers who might want to act against the security objectives of the jointly interacting entities. The need for techniques to verify the correctness of cryptographic protocols has stimulated the development of new frameworks and tools during the last decades. Among the various models is the spi calculus: a process calculus which is an extension of the pi calculus that incorporates cryptographic primitives. Process calculi such as the spi calculus offer the possibility to describe in a precise and concise way distributed algorithms such as cryptographic protocols. Moreover, spi calculus offers an elegant way to formalise some security properties of cryptographic protocols via behavioural equivalences. At the time this thesis began, this approach lacked tool support. Inspired by the situation in the pi calculus, we propose a new notion of behavioural equivalence for the spi calculus that is close to an algorithm. Besides, we propose a "coq" formalisation of our results that not only validates our theoretical developments but also will eventually be the basis of a certified tool that would automate equivalence checking of spi calculus terms. To complete the toolchain, we propose a formal semantics for an informal notation to describe cryptographic protocols, so called protocol narrations. We give a rigorous procedure to translate protocol narrations into spi calculus terms; this constitutes the foundations of our automatic translation tool "spyer".

EPFL2008

Chargement