| 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
| |
| dbo:wikiPageLength
|
- 14541 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| 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
| |
| prop-fr:isbn
| |
| prop-fr:journal
|
- Journal of the ACM (fr)
- Journal of the ACM (fr)
|
| prop-fr:langue
| |
| prop-fr:lieu
|
- Cambridge (fr)
- Cambridge (fr)
|
| prop-fr:nom
|
- Drmota (fr)
- Szpankowski (fr)
- Drmota (fr)
- Szpankowski (fr)
|
| prop-fr:numéro
| |
| prop-fr:numéroD'édition
| |
| prop-fr:pages
| |
| 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
| |
| 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 | |
