Voir

Comparaison entre modèle actuel et brouillon modifier

Algorithme A* modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme A*

Illustration d'une recherche A* pour trouver le chemin le plus court entre 2 nœuds

Découvreurs ou inventeurs	Peter E. Hart, Nils John Nilsson, Bertram Raphael
Date de publication	1968
Problèmes liés	Algorithme de recherche, algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme de Dijkstra
À l'origine de	Jump point search

Complexité en temps
Pire cas	$O(\|E\|)=O(b^{d})$

Complexité en espace
Pire cas	$O(\|V\|)=O(b^{d})$

nouveau modèle actuel modifier

Algorithme A*

Illustration d'une recherche A* pour trouver le chemin le plus court entre 2 nœuds

Découvreurs ou inventeurs	Peter E. Hart, Nils John Nilsson, Bertram Raphael
Date de publication	1968
Problèmes liés	Algorithme de recherche, algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme de Dijkstra
À l'origine de	Jump point search

Complexité en temps
Pire cas	$O(\|E\|)=O(b^{d})$

Complexité en espace
Pire cas	$O(\|V\|)=O(b^{d})$

RIPEMD modifier

nouveau modèle brouillon modifier

Brouillon!

RIPEMD

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1992
Problème lié	Fonction de hachage cryptographique
À l'origine de	RIPEMD-160, RIPEMD-256, RIPEMD-128, RIPEMD-320 (en)

nouveau modèle actuel modifier

RIPEMD

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1992
Problème lié	Fonction de hachage cryptographique
À l'origine de	RIPEMD-160, RIPEMD-256, RIPEMD-128, RIPEMD-320 (en)

RIPEMD-128 modifier

nouveau modèle brouillon modifier

Brouillon!

RIPEMD-128

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel modifier

RIPEMD-128

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

RIPEMD-160 modifier

nouveau modèle brouillon modifier

Brouillon!

RIPEMD-160

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel modifier

RIPEMD-160

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

RIPEMD-256 modifier

nouveau modèle brouillon modifier

Brouillon!

RIPEMD-256

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel modifier

RIPEMD-256

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

Médiane des médianes modifier

nouveau modèle brouillon modifier

Brouillon!

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972^[1]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps
Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(\log n)$

nouveau modèle actuel modifier

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972^[1]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps
Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(\log n)$

Algorithme de Hopcroft-Karp modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Hopcroft-Karp

Découvreurs ou inventeurs	John Hopcroft, Richard Karp, Alexander V. Karzanov (en)
Date de découverte	1973
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme hongrois

Complexité en temps
Pire cas	$O(E{\sqrt {V}})$

Complexité en espace
Pire cas	$O(V)$

nouveau modèle actuel modifier

Algorithme de Hopcroft-Karp

Découvreurs ou inventeurs	John Hopcroft, Richard Karp, Alexander V. Karzanov (en)
Date de découverte	1973
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme hongrois

Complexité en temps
Pire cas	$O(E{\sqrt {V}})$

Complexité en espace
Pire cas	$O(V)$

EdgeRank modifier

nouveau modèle brouillon modifier

Brouillon!

EdgeRank

Découvreur ou inventeur	Meta
Date de découverte	2007
Problème lié	Algorithme

nouveau modèle actuel modifier

EdgeRank

Découvreur ou inventeur	Meta
Date de découverte	2007
Problème lié	Algorithme

Arbre de Van Emde Boas modifier

nouveau modèle brouillon modifier

Brouillon!

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975

Complexité en temps
Pire cas	$O(log(log(M)))$
Moyenne	$O(log(log(M)))$
Meilleur cas	$O(log(log(M)))$

Complexité en espace
Pire cas	$O(M)$
Moyenne	$O(M)$
Meilleur cas	$O(M)$

nouveau modèle actuel modifier

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975

Complexité en temps
Pire cas	$O(log(log(M)))$
Moyenne	$O(log(log(M)))$
Meilleur cas	$O(log(log(M)))$

Complexité en espace
Pire cas	$O(M)$
Moyenne	$O(M)$
Meilleur cas	$O(M)$

Arbre B modifier

nouveau modèle brouillon modifier

Brouillon!

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972^[2]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps
Pire cas	$O(\log n)(insertion)$ , $O(\log n)(suppression)$ , $O(\log n)(recherche)$
Moyenne	$O(\log n)$ , $O(\log n)$ , $O(\log n)$

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(n)$

nouveau modèle actuel modifier

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972^[2]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps
Pire cas	$O(\log n)(insertion)$ , $O(\log n)(suppression)$ , $O(\log n)(recherche)$
Moyenne	$O(\log n)$ , $O(\log n)$ , $O(\log n)$

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(n)$

Algorithme de Las Vegas modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Las Vegas

Les exécutions d'un algorithme de Las Vegas donnent toujours un résultat correct ; c'est le temps d'exécution qui est aléatoire.

Découvreur ou inventeur	László Babai
Date de découverte	1979^[3]
Problème lié	Paradigme algorithmique (en)
À l'origine de	Algorithme de Davis-Putnam

Complexité en temps
Pire cas	$O(n^{2})$
Meilleur cas	$O(n\log(n))$

nouveau modèle actuel modifier

Algorithme de Las Vegas

Les exécutions d'un algorithme de Las Vegas donnent toujours un résultat correct ; c'est le temps d'exécution qui est aléatoire.

Découvreur ou inventeur	László Babai
Date de découverte	1979^[3]
Problème lié	Paradigme algorithmique (en)
À l'origine de	Algorithme de Davis-Putnam

Complexité en temps
Pire cas	$O(n^{2})$
Meilleur cas	$O(n\log(n))$

Algorithme de Johnson modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|^{2}\log \|V\|+\|V\|\|E\|)$

nouveau modèle actuel modifier

Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|^{2}\log \|V\|+\|V\|\|E\|)$

Algorithme d'Aho-Corasick modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme d'Aho-Corasick

exemple d'arbre préfixe (trie) généré dans l'application d'un algorithme d'Aho-Corasick

Découvreurs ou inventeurs	Alfred Aho, Margaret Corasick (d)
Date de découverte	1975^[4]
Problèmes liés	Exact string-matching algorithm (d), multiple string search algorithm (d)
À l'origine de	Algorithme de Commentz-Walter (en)

nouveau modèle actuel modifier

Algorithme d'Aho-Corasick

exemple d'arbre préfixe (trie) généré dans l'application d'un algorithme d'Aho-Corasick

Découvreurs ou inventeurs	Alfred Aho, Margaret Corasick (d)
Date de découverte	1975^[4]
Problèmes liés	Exact string-matching algorithm (d), multiple string search algorithm (d)
À l'origine de	Algorithme de Commentz-Walter (en)

Algorithme de Dijkstra modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Dijkstra

L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite. Il marque le sommet visité (en rouge) lorsqu'il a terminé avec les voisins.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1959^[5]
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), algorithme glouton, algorithme
Structure des données	Graphe
Basé sur	Algorithme de parcours en largeur
À l'origine de	Algorithme A*, link-state routing protocol (en), Open Shortest Path First, IS-IS

Complexité en temps
Pire cas	$O(\|E\|+\|V\|\log \|V\|)$ ^[6], $O(\|E\|+\|V\|\log \|V\|)$

nouveau modèle actuel modifier

Algorithme de Dijkstra

L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite. Il marque le sommet visité (en rouge) lorsqu'il a terminé avec les voisins.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1959^[5]
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), algorithme glouton, algorithme
Structure des données	Graphe
Basé sur	Algorithme de parcours en largeur
À l'origine de	Algorithme A*, link-state routing protocol (en), Open Shortest Path First, IS-IS

Complexité en temps
Pire cas	$O(\|E\|+\|V\|\log \|V\|)$ ^[6], $O(\|E\|+\|V\|\log \|V\|)$

algorithme de Bellman-Ford modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Bellman-Ford

Découvreurs ou inventeurs	Richard Bellman (1958), L. R. Ford, Jr. (1956), Edward F. Moore (1957)
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), concept mathématique (en)
Structure des données	Graphe
À l'origine de	Routing Information Protocol^[7], Babel^[8]

Complexité en temps
Pire cas	$\Theta (\|V\|\|E\|)$
Meilleur cas	$\Theta (\|E\|)$

Complexité en espace
Pire cas	$\Theta (\|V\|)$

nouveau modèle actuel modifier

Algorithme de Bellman-Ford

Découvreurs ou inventeurs	Richard Bellman (1958), L. R. Ford, Jr. (1956), Edward F. Moore (1957)
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), concept mathématique (en)
Structure des données	Graphe
À l'origine de	Routing Information Protocol^[7], Babel^[8]

Complexité en temps
Pire cas	$\Theta (\|V\|\|E\|)$
Meilleur cas	$\Theta (\|E\|)$

Complexité en espace
Pire cas	$\Theta (\|V\|)$

Algorithme de Borůvka modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Borůvka

Animation représentant l'algorithme de Borůvka, dans la version sans contraction.

Découvreur ou inventeur	Otakar Borůvka
Date de publication	1926
Problèmes liés	Algorithme de la théorie des graphes (d), concept mathématique (en)

nouveau modèle actuel modifier

Algorithme de Borůvka

Animation représentant l'algorithme de Borůvka, dans la version sans contraction.

Découvreur ou inventeur	Otakar Borůvka
Date de publication	1926
Problèmes liés	Algorithme de la théorie des graphes (d), concept mathématique (en)

algorithme de parcours en largeur modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de parcours en largeur

Ordre dans lequel les nœuds sont parcourus

Découvreur ou inventeur	Konrad Zuse
Date de découverte	1945
Problèmes liés	Uninformed search algorithm (d), parcours de graphe
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|+\|E\|)=O(b^{d})$

Complexité en espace
Pire cas	$O(\|V\|)=O(b^{d})$

nouveau modèle actuel modifier

Algorithme de parcours en largeur

Ordre dans lequel les nœuds sont parcourus

Découvreur ou inventeur	Konrad Zuse
Date de découverte	1945
Problèmes liés	Uninformed search algorithm (d), parcours de graphe
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|+\|E\|)=O(b^{d})$

Complexité en espace
Pire cas	$O(\|V\|)=O(b^{d})$

Algorithme de Floyd-Warshall modifier

nouveau modèle brouillon modifier

Brouillon!

Algorithme de Floyd-Warshall

Découvreur ou inventeur	Bernard Roy
Date de découverte	1959
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|n\|^{3})$
Moyenne	$O(\|V\|^{3})$
Meilleur cas	$O(\|V\|^{3})$

Complexité en espace
Pire cas	$O(\|V\|^{2})$

nouveau modèle actuel modifier

Algorithme de Floyd-Warshall

Découvreur ou inventeur	Bernard Roy
Date de découverte	1959
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|n\|^{3})$
Moyenne	$O(\|V\|^{3})$
Meilleur cas	$O(\|V\|^{3})$

Complexité en espace
Pire cas	$O(\|V\|^{2})$

↑ ^{a et b} (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)
↑ ^{a et b} R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ novembre 1970, p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)
↑ ^{a et b} László Babai, « Monte-Carlo algorithms in graph isomorphism testing », [[Modèle:Article|{{Article}} : paramètre « titre » manquant, paramètre « périodique » manquant, paramètre « date » manquant]] : paramètre « périodique » manquant,‎ 1979
↑ ^{a et b} (en) Alfred V. Aho et Margaret J. Corasick, « Efficient string matching: an aid to bibliographic search », Communications of the ACM, New York, ACM, vol. 18, n^o 6,‎ 1^er juin 1975, p. 333-340 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/360825.360855)
↑ ^{a et b} (en) E. W. Dijkstra, « A note on two problems in connexion with graphs », Numerische Mathematik, Springer Science+Business Media, vol. 1, n^o 1,‎ décembre 1959, p. 269-271 (ISSN 0029-599X et 0945-3245, OCLC 1760917, DOI 10.1007/BF01386390, lire en ligne)
↑ ^{a et b} « http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf »
↑ ^{a et b} G. Malkin, RIP Version 2, (Request for comments), IETF, Novembre 1998, [lire en ligne], consulté le 28 mai 2022
↑ ^{a et b} J. Chroboczek, The Babel Routing Protocol, (Request for comments), IETF, Avril 2011, [lire en ligne], consulté le 28 mai 2022

[wikidata-8bfb307d4a12c04e302ae05e204046dea379a837Q55881151-1] {a et b} (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)

[wikidata-8b276371ef944464ae99b0d28d05e4f8c4a98c8dQ61783186-2] {a et b} R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ novembre 1970, p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)

[wikidata-e85a3db2503dd0cd0b9e769312655d15f9566734Q94972713-3] {a et b} László Babai, « Monte-Carlo algorithms in graph isomorphism testing », [[Modèle:Article|{{Article}} : paramètre « titre » manquant, paramètre « périodique » manquant, paramètre « date » manquant]] : paramètre « périodique » manquant,‎ 1979

[wikidata-82fe7c1b9186cbab57648736e8b3cbe36d934d5dQ55870932-4] {a et b} (en) Alfred V. Aho et Margaret J. Corasick, « Efficient string matching: an aid to bibliographic search », Communications of the ACM, New York, ACM, vol. 18, n^o 6,‎ 1^er juin 1975, p. 333-340 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/360825.360855)

[wikidata-79fa46f0eb95a8b1a259121600f393dd46f3bbe2Q21694527-5] {a et b} (en) E. W. Dijkstra, « A note on two problems in connexion with graphs », Numerische Mathematik, Springer Science+Business Media, vol. 1, n^o 1,‎ décembre 1959, p. 269-271 (ISSN 0029-599X et 0945-3245, OCLC 1760917, DOI 10.1007/BF01386390, lire en ligne)

[wikidata-d1c249ef5ef036159ce0fabf065af2a408384f46-6] {a et b} « http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf »

[wikidata-ec379cded6912fb6057f342578c273d3467891d8Q47484547-7] {a et b} G. Malkin, RIP Version 2, (Request for comments), IETF, Novembre 1998, [lire en ligne], consulté le 28 mai 2022

[wikidata-736b9255e0ac9a8da82403f13659bc7cf8a0e75dQ47322975-8] {a et b} J. Chroboczek, The Babel Routing Protocol, (Request for comments), IETF, Avril 2011, [lire en ligne], consulté le 28 mai 2022

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Utilisateur:Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 2

Comparaison entre modèle actuel et brouillon modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier