| http://dbpedia.org/ontology/abstract
|
Les algorithmes d’énumération sont des alg … Les algorithmes d’énumération sont des algorithmes qui ont pour but de calculer ou afficher une liste de toutes les réponses à un problème donné ; alors que les algorithmes « classiques » cherchent plutôt une solution (problèmes d’optimisation) ou à tester la vérité d’une affirmation (problèmes de décision).Par exemple, un algorithme listant toutes les cliques d’un graphe est un algorithme d’énumération. Cette distinction est faite pour pouvoir construire des classes de complexité propres aux problèmes d’énumération. Par exemple, la classe des algorithmes d’énumérations dont le temps entre l’affichage de deux résultats est borné par un polynôme en la taille de l’entrée. par un polynôme en la taille de l’entrée.
, In computer science, an enumeration algori … In computer science, an enumeration algorithm is an algorithm that enumerates the answers to a computational problem. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to function problems. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the total time required to produce all solutions, or in terms of the maximal delay between two consecutive solutions and in terms of a preprocessing time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with output-sensitive algorithms. is done with output-sensitive algorithms.
|
| http://dbpedia.org/ontology/wikiPageID
|
60842845
|
| http://dbpedia.org/ontology/wikiPageLength
|
9056
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1121637743
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Hypergraph_%28mathematics%29 +
, http://dbpedia.org/resource/Boolean_satisfiability_problem +
, http://dbpedia.org/resource/Vertex_enumeration_problem +
, http://dbpedia.org/resource/Function_problems +
, http://dbpedia.org/resource/Backtracking +
, http://dbpedia.org/resource/RE_%28complexity%29 +
, http://dbpedia.org/resource/Union_%28set_theory%29 +
, http://dbpedia.org/resource/Greedoid +
, http://dbpedia.org/resource/Algorithm +
, http://dbpedia.org/resource/Database_query +
, http://dbpedia.org/resource/Clique_problem +
, http://dbpedia.org/resource/Polytope +
, http://dbpedia.org/resource/Witness_%28mathematics%29 +
, http://dbpedia.org/resource/Database_theory +
, http://dbpedia.org/resource/Category:Algorithms +
, http://dbpedia.org/resource/Computability_theory +
, http://dbpedia.org/resource/String_%28computer_science%29 +
, http://dbpedia.org/resource/Cut_%28graph_theory%29 +
, http://dbpedia.org/resource/NP_%28complexity%29 +
, http://dbpedia.org/resource/Disjunctive_normal_form +
, http://dbpedia.org/resource/Polynomial_time +
, http://dbpedia.org/resource/Vertex_%28geometry%29 +
, http://dbpedia.org/resource/Negation_normal_form +
, http://dbpedia.org/resource/Constant_time +
, http://dbpedia.org/resource/Polynomial_delay +
, http://dbpedia.org/resource/Linear_inequality +
, http://dbpedia.org/resource/Sorting +
, http://dbpedia.org/resource/Boolean_function +
, http://dbpedia.org/resource/Conjunctive_normal_form +
, http://dbpedia.org/resource/Linear_time +
, http://dbpedia.org/resource/Recursively_enumerable +
, http://dbpedia.org/resource/Bron%E2%80%93Kerbosch_algorithm +
, http://dbpedia.org/resource/Partition_%28mathematics%29 +
, http://dbpedia.org/resource/Minimal_transversal +
, http://dbpedia.org/resource/Monotone_dualization +
, http://dbpedia.org/resource/Computational_problem +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/OBDD +
, http://dbpedia.org/resource/Self-reducible +
, http://dbpedia.org/resource/Enumeration +
, http://dbpedia.org/resource/Class_%28complexity_theory%29 +
, http://dbpedia.org/resource/Complexity_class +
, http://dbpedia.org/resource/Output-sensitive_algorithm +
, http://dbpedia.org/resource/Boolean_circuit +
, http://dbpedia.org/resource/Binary_decision_diagram +
, http://dbpedia.org/resource/Hash_table +
, http://dbpedia.org/resource/Monadic_second-order +
, http://dbpedia.org/resource/Path_%28graph_theory%29 +
, http://dbpedia.org/resource/Conjunctive_query +
, http://dbpedia.org/resource/Cartesian_product +
, http://dbpedia.org/resource/Knowledge_compilation +
, http://dbpedia.org/resource/System_of_equations +
, http://dbpedia.org/resource/Computational_complexity_theory +
, http://dbpedia.org/resource/Computer_science +
, http://dbpedia.org/resource/Matroid +
, http://dbpedia.org/resource/Alphabet_%28computer_science%29 +
, http://dbpedia.org/resource/Independent_set_%28graph_theory%29 +
, http://dbpedia.org/resource/Decision_problem +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Visible_anchor +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Algorithms +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Enumeration_algorithm?oldid=1121637743&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Enumeration_algorithm +
|
| owl:sameAs |
http://dbpedia.org/resource/Enumeration_algorithm +
, http://www.wikidata.org/entity/Q21405405 +
, https://global.dbpedia.org/id/22ePA +
, http://fr.dbpedia.org/resource/Algorithme_d%27%C3%A9num%C3%A9ration +
|
| rdfs:comment |
Les algorithmes d’énumération sont des alg … Les algorithmes d’énumération sont des algorithmes qui ont pour but de calculer ou afficher une liste de toutes les réponses à un problème donné ; alors que les algorithmes « classiques » cherchent plutôt une solution (problèmes d’optimisation) ou à tester la vérité d’une affirmation (problèmes de décision).Par exemple, un algorithme listant toutes les cliques d’un graphe est un algorithme d’énumération.un graphe est un algorithme d’énumération.
, In computer science, an enumeration algori … In computer science, an enumeration algorithm is an algorithm that enumerates the answers to a computational problem. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to function problems. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the total time required to produce all solutions, or in terms of the maximal delay between two consecutive solutions and in terms of a preprocessing time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each indie size of the input, the size of each indi
|
| rdfs:label |
Algorithme d'énumération
, Enumeration algorithm
|
