En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner.

Property Value
dbo:abstract
  • En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner. L'énoncé sur les expressions asymptotiques de ces récurrences a été nommé « master theorem » dans la version anglaise du manuel Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein; dans sa traduction française, le théorème est appelé le « théorème général ». L'approche a été présentée notamment en 1980 par Jon Bentley, Dorothea Haken, et James B. Saxe. Le théorème couvre un certain nombre de types de récurrences ; une extension à d'autres expressions est fournie par ce que l’on appelle la méthode d'Akra-Bazzi. (fr)
  • En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner. L'énoncé sur les expressions asymptotiques de ces récurrences a été nommé « master theorem » dans la version anglaise du manuel Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein; dans sa traduction française, le théorème est appelé le « théorème général ». L'approche a été présentée notamment en 1980 par Jon Bentley, Dorothea Haken, et James B. Saxe. Le théorème couvre un certain nombre de types de récurrences ; une extension à d'autres expressions est fournie par ce que l’on appelle la méthode d'Akra-Bazzi. (fr)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 8793546 (xsd:integer)
dbo:wikiPageLength
  • 14541 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 188026323 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:année
  • 2001 (xsd:integer)
  • 2002 (xsd:integer)
  • 2013 (xsd:integer)
prop-fr:auteur
  • Thomas H. Cormen (fr)
  • Roberto Tamassia (fr)
  • Charles E. Leiserson (fr)
  • Clifford Stein (fr)
  • Ronald L. Rivest (fr)
  • Michael T. Goodrich (fr)
  • Thomas H. Cormen (fr)
  • Roberto Tamassia (fr)
  • Charles E. Leiserson (fr)
  • Clifford Stein (fr)
  • Ronald L. Rivest (fr)
  • Michael T. Goodrich (fr)
prop-fr:id
  • CLRS (fr)
  • CLRS (fr)
prop-fr:isbn
  • 0 (xsd:integer)
prop-fr:journal
  • Journal of the ACM (fr)
  • Journal of the ACM (fr)
prop-fr:langue
  • en (fr)
  • en (fr)
prop-fr:lieu
  • Cambridge (fr)
  • Cambridge (fr)
prop-fr:nom
  • Drmota (fr)
  • Szpankowski (fr)
  • Drmota (fr)
  • Szpankowski (fr)
prop-fr:numéro
  • 3 (xsd:integer)
prop-fr:numéroD'édition
  • 2 (xsd:integer)
prop-fr:pages
  • 1 (xsd:integer)
prop-fr:pagesTotales
  • 708 (xsd:integer)
  • 1180 (xsd:integer)
prop-fr:passage
  • 73 (xsd:integer)
  • 268 (xsd:integer)
prop-fr:prénom
  • Michael (fr)
  • Wojciech (fr)
  • Michael (fr)
  • Wojciech (fr)
prop-fr:titre
  • Introduction to Algorithms (fr)
  • A Master Theorem for Discrete Divide and Conquer Recurrences (fr)
  • Algorithm Design : Foundation, Analysis, and Internet Examples (fr)
  • Introduction to Algorithms (fr)
  • A Master Theorem for Discrete Divide and Conquer Recurrences (fr)
  • Algorithm Design : Foundation, Analysis, and Internet Examples (fr)
prop-fr:titreChapitre
  • Sections 4.3 et 4.4 (fr)
  • Sections 4.3 et 4.4 (fr)
prop-fr:url
prop-fr:volume
  • 60 (xsd:integer)
prop-fr:wikiPageUsesTemplate
prop-fr:éditeur
dct:subject
rdfs:comment
  • En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner. (fr)
  • En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner. (fr)
rdfs:label
  • Master theorem (fr)
  • Master-Theorem (de)
  • Teorema maestro (es)
  • Twierdzenie o rekurencji uniwersalnej (pl)
  • Основная теорема о рекуррентных соотношениях (ru)
  • النظرية الرئيسة (تحليل الخوارزميات) (ar)
  • Майстер-метод (uk)
  • 主定理 (zh)
  • Master theorem (fr)
  • Master-Theorem (de)
  • Teorema maestro (es)
  • Twierdzenie o rekurencji uniwersalnej (pl)
  • Основная теорема о рекуррентных соотношениях (ru)
  • النظرية الرئيسة (تحليل الخوارزميات) (ar)
  • Майстер-метод (uk)
  • 主定理 (zh)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:basedOn of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of