| Attributes | Values |
|---|
| rdfs:label
| - Fibonacci heap (en)
- Tas de Fibonacci (fr)
- Фибоначчиева куча (ru)
- Фібоначчієва купа (uk)
|
| rdfs:comment
| - En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. (fr)
|
| rdfs:seeAlso
| |
| sameAs
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| dbo:wikiPageWikiLink
| |
| Link from a Wikipage to an external page
| |
| page length (characters) of wiki page
| |
| dct:subject
| |
| prop-fr:wikiPageUsesTemplate
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| prop-fr:titre
| - Implémentation en C d'un tas de Fibonacci (fr)
|
| prop-fr:url
| |
| thumbnail
| |
| foaf:isPrimaryTopicOf
| |
| dbo:discoverer
| |
| named after
| |
| has abstract
| - En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. Le nom de tas de Fibonacci vient des nombres de Fibonacci, qui sont utilisés pour calculer son temps d'exécution. En particulier, les opérations insertion, trouver le minimum, décroître une clé, et union ont toutes un coût amorti constant. Les opérations supprimer et supprimer le minimum ont un coût amorti en O(log n). C'est-à-dire qu'en partant d'une structure vide, n'importe quelle séquence de a opérations du premier groupe et b opérations du second groupe prendrait un temps O(a + (b log n)). Dans un tas binomial, une telle séquence d'opérations prendrait un temps O((a + b)(log n)). Il devient donc plus intéressant d'utiliser un tas de Fibonacci plutôt qu'un tas binomial lorsque b est asymptotiquement plus petit que a. (fr)
|
| is dbo:wikiPageWikiLink
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
