Voir

Comparaison entre ancien et nouveau modèle modifier

Problème lié	Base de données
Structure des données	arbre

Découvreur ou inventeur	Andrew Viterbi<img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" data-file-width="600" data-file-height="600">
Problème lié	Algorithme<img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" data-file-width="600" data-file-height="600">

Découvreur ou inventeur	Andrew Viterbi<img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" data-file-width="600" data-file-height="600">
Problème lié	Algorithme<img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" data-file-width="600" data-file-height="600">

Algorithme de Viterbi modifier

ancien modèle modifier

Pas de modèle

nouveau modèle brouillon modifier

Brouillon!

nouveau modèle actuel modifier

Arbre B modifier

ancien modèle 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^[1]
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^[1]
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)$

RIPEMD-160 modifier

ancien modèle modifier

RIPEMD-160

Problème lié	fonction de hachage

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 modifier

ancien modèle modifier

Pas de modèle utilisé

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)

EdgeRank modifier

ancien modèle modifier

EdgeRank

nouveau modèle brouillon modifier

Brouillon!

EdgeRank

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

nouveau modèle actuel modifier

EdgeRank

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

Arbre de Van Emde Boas modifier

ancien modèle modifier

Arbre de Van Emde Boas

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

Structure des données	Arbre non binaire

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)$

Médiane des médianes modifier

ancien modèle modifier

Médiane des médianes

Problème lié	Algorithme de sélection
Structure des données	Tableau

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^[2]
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^[2]
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)$

Quickselect modifier

ancien modèle modifier

Quickselect

Problème lié	Algorithme de sélection
Structure des données	Tableau

nouveau modèle brouillon modifier

Brouillon!

Quickselect

Visualisation animée de l'algorithme de sélection rapide. Sélection de la 22ème plus petite valeur.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problème lié	Algorithme de sélection
Structure des données	Tableau
À l'origine de	Médiane des médianes

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

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

nouveau modèle actuel modifier

Quickselect

Visualisation animée de l'algorithme de sélection rapide. Sélection de la 22ème plus petite valeur.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problème lié	Algorithme de sélection
Structure des données	Tableau
À l'origine de	Médiane des médianes

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

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

Algorithme de Hopcroft-Karp modifier

ancien modèle modifier

Algorithme de Hopcroft-Karp

Problème lié	Couplage (théorie des graphes)
Structure des données	Graphe biparti

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)$

Algorithme de Johnson modifier

ancien modèle modifier

Algorithme de Johnson

Problème lié	Plus courts chemins entre tous les sommets
Structure des données	Graphe

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\|)$

exemple modifier

ancien modèle modifier

nouveau modèle brouillon modifier

Brouillon!

Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 1

nouveau modèle actuel modifier

Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 1

↑ ^{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} (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-1] {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-8bfb307d4a12c04e302ae05e204046dea379a837Q55881151-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)

[1]

[2]

Découvreur ou inventeur	Andrew Viterbi
Problème lié	Algorithme

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

Comparaison entre ancien et nouveau modèle modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier

ancien modèle modifier

nouveau modèle brouillon modifier

nouveau modèle actuel modifier