Sur les autres projets Wikimedia : Algorithme d'Edmonds-Karp (en anglais), sur Wikibooks On part du réseau ci-dessous, à sept ... En informatique et en théorie des graphes, l'algorithme d'Edmonds-Karp (ou algorithme d'Edmonds et Karp) est une spécialisation ... Une autre propriété de cet algorithme est que la longueur du plus court chemin augmentant croît. Une démonstration de ... Algorithme de la théorie des graphes, Réseau de flot). ... Pour les articles homonymes, voir Algorithme d'Edmonds. ...

Algorithmes de connexité basés sur des pointeurs (pour les graphes non orientés) Algorithme de Floyd-Warshall Problème de plus ... L'algorithme de Warshall, parfois appelé algorithme de Roy-Warshall est un algorithme agissant sur un graphe. Il permet de ... Fermeture transitive : algorithme de Warshall », sur université du Québec à Montréal. ... Cet algorithme donne donc des informations sur les composantes connexes ou fortement connexes d'un graphe. L'algorithme doit ...

Ayant oublié ses notes de cours, Kosaraju improvise un algorithme, et c'est en se trompant qu'il aurait trouvé cet algorithme ... Cet algorithme a été élaboré par S. Rao Kosaraju, professeur d'algorithmique à l'université Johns-Hopkins. La légende raconte ... Rao Kosaraju de cet algorithme qui est publié par Micha Sharir (en) indépendamment en 1981. Cormen et al, Section 22.5. Jeff ... l'algorithme de Kosaraju est un algorithme de calcul des composantes fortement connexes d'un graphe orienté. Il effectue deux ...

Cet algorithme évite donc que des paquets dont la charge utile est très faible ne soient envoyés à la file. On peut résumer son ... L'algorithme de Nagle est un algorithme important pour le fonctionnement de TCP défini par John Nagle dans la RFC 896 (RFC 896 ... L'objectif de cet algorithme est d'améliorer l'efficacité du protocole en réduisant le nombre de paquets nécessaires à un ... Algorithme de Nagle et acquittements retardés Portail de l'informatique Portail des télécommunications (en) Request for ...

L'algorithme de Buchberger est un algorithme permettant de calculer une base de Gröbner pour un idéal polynomial à partir d'un ...

Ces algorithmes se prêtent naturellement à une implémentation polymorphe. Les algorithmes de tri sont souvent étudiés dans les ... Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets ... Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la ... En l'absence de précisions, on entend habituellement par « algorithme de tri » un algorithme de tri procédant par comparaisons ...

Les images ci-dessous montrent l'exécution de algorithme diamant-carré pour une matrice de taille 5. Ci-dessous un exemple ... que fin fonction Cet algorithme est largement utilisé pour la création de champs de hauteur (permettant ensuite la génération ...

Certains algorithmes avec de mauvaises performances dans le pire des cas sont couramment utilisés, car ils ne présentent de ... Moins de trois articles lui sont liés (novembre 2021). Vous pouvez aider en ajoutant des liens vers [[Algorithme de l'autruche ... Des exemples typiques sont l'⁣algorithme du simplexe et l'algorithme d'inférence de type pour le standard ML. Des problèmes ...

Parmi les variantes existantes de cet algorithme nous évoquerons l'algorithme GEM (generalized EM) qui permet de simplifier le ... Algorithme espérance-maximisation L'algorithme espérance-maximisation (en anglais expectation-maximization algorithm, souvent ... Cet algorithme est particulièrement utile lorsque la maximisation de L est très complexe mais que, sous réserve de connaître ... abrégé EM) est un algorithme itératif qui permet de trouver les paramètres du maximum de vraisemblance d'un modèle probabiliste ...

L´algorithme de Boehm est un algorithme utilisé dans le tracé des B-splines. Il sert à "affiner" la courbe en augmentant le ... Algorithme de Boehm » : Bing Cairn DuckDuckGo E. Universalis Gallica Google G. Books G. News G. Scholar Persée Qwant (zh) Baidu ...

En théorie des graphes, l'algorithme de Tarjan permet de déterminer les composantes fortement connexes d'un graphe orienté. Il porte le nom de son inventeur, Robert Tarjan. L'algorithme de Tarjan est de complexité linéaire, comme l'algorithme de Kosaraju, mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux. L'algorithme prend en entrée un graphe orienté et renvoie une partition des sommets du graphe correspondant à ses composantes fortement connexes. Le principe de l'algorithme est le suivant : on lance un parcours en profondeur depuis un sommet arbitraire. Les sommets explorés sont placés sur une pile P. Un marquage spécifique permet de distinguer certains sommets : les racines des composantes fortement connexes, c'est-à-dire les premiers sommets explorés de chaque composante (ces racines dépendent de l'ordre dans lequel on fait le parcours, elles ne sont pas fixées de façon absolue sur le graphe). Lorsqu'on termine l'exploration d'un sommet racine v, on ...

Les nombres obtenus via cet algorithme ont tous la même forme, soit un multiple de 99. En effet, posons un nombre formé de 3 ... En mathématiques, l'algorithme de Kaprekar est un algorithme qui transforme un nombre entier en un autre, de façon répétitive ... Il existe aux moins trois variantes de cet algorithme suivant la façon dont on compte les chiffres avant de les arranger en ...

Cet article est une ébauche concernant l'algèbre. Vous pouvez partager vos connaissances en l'améliorant (comment ?) selon les recommandations des projets correspondants. L'algorithme de Berlekamp est une méthode de factorisation des polynômes à coefficients dans un corps fini, qui repose sur des calculs de PGCD de polynômes et des opérations matricielles. Il a été découvert par Elwyn Berlekamp en 1967, et est resté l'algorithme le plus performant concernant ce problème jusqu'en 1981, et la découverte de l'algorithme de Cantor-Zassenhaus. L'algorithme exige de travailler sur un polynôme unitaire f(x) sans facteur carré, c'est-à-dire que les exposants des facteurs dans la décomposition en irréductibles de f valent tous 1. On note n son degré et q le nombre d'éléments du corps fini Fq sur lequel on se place. Le point central est la recherche et l'utilisation de polynômes g tels que gq - g soit divisible par f. Dans l'anneau quotient Fq[x]/(f(x)), les images de ces polynômes ...

Cet algorithme s'est montré très efficace dans des réseaux avec un taux de perte de paquets élevé. Phil Karn, Craig Partridge ...

Algorithme de Kruskal Algorithme de Borůvka Portail des mathématiques Portail de l'informatique théorique (Portail: ... L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non ... En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe ...

Certains algorithmes de dualité peuvent être interprétés comme des algorithmes proximaux. Ces algorithmes de dualité ... Certains algorithmes peuvent être interprétés comme des algorithmes proximaux. Il en est ainsi de la méthode des ... Pour certains algorithmes, cette propriété est une aubaine, permettant d'accélérer leur convergence et de mieux la contrôler. ... En analyse numérique et plus précisément en optimisation mathématique, l'algorithme proximal (ou algorithme du point proximal) ...

L'algorithme de Fortune est un algorithme pour calculer le diagramme de Voronoï d'un ensemble de points. C'est un algorithme de ... un algorithme incrémental de complexité quadratique, et l'algorithme de Shamos et Hoey, un algorithme en O(n log n) de type ... L'algorithme est dû à Steven Fortune (1987, Laboratoires Bell AT&T). D'autres algorithmes pour le problème sont l'algorithme de ...

... Un algorithme de même nom est mentionné dans Job Shop Scheduling (en) En informatique, l'algorithme de ... à illustrer Algorithme, Article utilisant l'infobox Algorithme, Article utilisant une Infobox, Article contenant un appel à ... Algorithme de Johnson pour les graphes peu denses », p. 616-620 dans : Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest ... retourner d La complexité en temps de cet algorithme est, en utilisant un tas de Fibonacci pour l'implémentation de ...

L'analyse de cet algorithme est due à Nicos Christofides and Anatoliy I. Serdyukov, qui l'ont découvert indépendamment en 1976 ... Pour lequel on peut utiliser par exemple les algorithmes polynomiaux de Prim, Kruskal ou Borůvka. Par exemple avec l'algorithme ... L'algorithme de Christofides est un algorithme d'approximation pour le problème du voyageur de commerce, dans le cas métrique, ... cet algorithme est en fait une heuristique, cependant dans le cas métrique, on peut montrer que la solution est au plus 3/2 ...

Il existe d'autres algorithmes pour le problème de l'arbre couvrant minimal, par exemple l'algorithme de Prim et l'algorithme ... Ivan Lavallée, « Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe », RAIRO-Operations ... Il est aussi appelé algorithme de Sollin. En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes ... Algorithme de Borůvka Animation représentant l'algorithme de Borůvka, dans la version sans contraction. L'algorithme de Borůvka ...

Par conséquent, l'utilisation des algorithmes randomisés peut accélérer un algorithme déterministe lent. Le meilleur algorithme ... Une analyse simple de cet algorithme montre une complexité en temps de O(n2) qui bat l'algorithme déterministe classique en O( ... En pratique, il illustre également la supériorité des algorithmes probabilistes dans certains problèmes. Il pourrait être ... le meilleur algorithme connu de produit matriciel (dans le cas où les matrices sont de taille identique à n) s'exécute en temps ...

Les algorithmes AC antérieurs sont souvent considérés comme trop peu efficaces, et beaucoup des suivants sont difficiles à ... Moins de trois articles lui sont liés (mars 2023). Vous pouvez aider en ajoutant des liens vers [[Algorithme AC-3]] dans les ... cet algorithme est garanti de se terminer. A titre d'illustration, voici un exemple de problème de contrainte très simple : X ( ...

Il existe des algorithmes pour passer de l'un à l'autre. L'algorithme de Thompson permet d'aller de l'expression à l'automate, ... En informatique théorique plus précisément en théorie des langages, l'algorithme de Thompson est un algorithme qui, étant donné ... Algorithme de Thompson » [archive du 28 mai 2016], sur Blog Kérios (consulté le 25 janvier 2016) Portail de l'informatique ...

Il est possible d'améliorer cet algorithme et d'atteindre un algorithme optimal en nombre de bits aléatoires utilisés. ... écrire un algorithme efficace qui utilise un tableau de taille 2 n + 1 {\displaystyle 2n+1} et qui fait n − 1 {\displaystyle n- ... Mais ces formules ne permettent pas de dériver un algorithme efficace de génération aléatoire. L'idée de Rémy consiste à non ... dont la principale application est un algorithme efficace de génération aléatoire d'arbres binaires. L'algorithme doit son nom ...

En mathématiques, l'algorithme d'Odlyzko-Schönhage est un algorithme d'évaluation rapide de la fonction zêta de Riemann ζ : z ... n = 1 + ∞ 1 n z {\displaystyle \zeta ~:~z\mapsto \sum _{n=1}^{+\infty }{\frac {1}{n^{z}}}} . Cet algorithme, présenté en 1988 ...

Les scores obtenus par cet algorithme sont parfois utilisés dans les critiques de pairs pour vérifier la validité des ... 30, no 2,‎ 1981, p. 239-45 (PMID 7249508, DOI 10.1038/clpt.1981.154) Algorithme de Naranjo (en anglais) Calculateur en ligne ...

Cet algorithme est nommé ainsi car il reproduit le modèle du prêt à des clients par un banquier. On considère un système ... L'algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965 pour éviter les problèmes ... Algorithme : Soit r e m a i n i n g {\displaystyle remaining} le vecteur de taille n {\displaystyle n} qui indique la quantité ...

2000 Un livre généraliste sur le calcul quantique Information quantique Algorithme de Grover Algorithme de Deutsch-Jozsa Une ... Un algorithme quantique pour résoudre le problème de recherche d'ordre. Prendre un nombre pseudo-aléatoire a < N Calculer PGCD( ... En arithmétique modulaire et en informatique quantique, l'algorithme de Shor est un algorithme quantique conçu par Peter Shor ... Comme la plupart des algorithmes pour calculateur quantique, l'algorithme de Shor est probabiliste : il donne la réponse ...

Cette description montre que l'algorithme fait partie de la famille des algorithmes à directions de descente. Les algorithmes ... L'algorithme du gradient, aussi appelé algorithme de descente de gradient, désigne un algorithme d'optimisation différentiable ... à directions de descente ou de sauvegarde dans les algorithmes à régions de confiance. Le principe de cet algorithme remonte au ... Cet algorithme structurellement très simple repose sur le fait que, dans le voisinage d'un point x {\displaystyle x} , la ...

Algorithmes de Markov » (consulté le 29 août 2013) Vincent Laviron, « Algorithmes de Markov » (consulté le 29 août 2013) (en) ... Les algorithmes de Markov ont été nommées d'après le mathématicien Andreï Markov. Refal est un langage de programmation basé ... Il a été démontré que les algorithmes de Markov étaient Turing-complets, ce qui signifie qu'ils constituent un modèle de calcul ... En informatique théorique, un algorithme de Markov est un système de réécriture de chaîne qui utilise des règles de grammaire ...