In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function.
| Attributes | Values |
|---|
| rdfs:label
| - Kombinatorická exploze (cs)
- Lehertze konbinatorio (eu)
- Combinatorial explosion (en)
- Explosión combinatoria (es)
- Explosion combinatoire (fr)
- 組合せ爆発 (ja)
- Комбинаторный взрыв (ru)
- Комбінаторний вибух (uk)
|
| rdfs:comment
| - Kombinatorická exploze je v matematice neformální označení jevu, kdy složitost daného problému silně vzrůstá spolu s tím, jak se vzhledem k rostoucímu vstupu velice rychle rozšiřuje kombinatorické jádro problému, typicky počet kombinací, které by mohly být řešením. (cs)
- In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function. (en)
- En matemáticas, una explosión combinatoria consiste en el crecimiento muy rápido de la complejidad de un problema debido a cómo se ve afectado por las condiciones iniciales, restricciones y límites del propio problema. La explosión combinatoria se utiliza a veces para justificar la intrazabilidad de ciertos problemas. Hay muchos ejemplos de tales problemas, que incluyen ciertas funciones, el análisis de algunos rompecabezas y juegos y algunos ejemplos patológicos que pueden ser modelizados, como la Función de Ackermann. (es)
- 組合せ爆発（くみあわせばくはつ、英: combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。 (ja)
- Lehertze konbinatorioa konbinatoria baliatuz egoera bat aztertu edo problema bat ebazterakoan, hartzen den elementu kopurua gehitu ahala, aztertu beharreko konbinazio posible eta emaitzen kopuruan gertatzen den gehikuntza itzela adierazteko erabiltzen den terminoa da. Ondorioz, bere baitan erlatiboki hain handia ez den elementu kopurua hartzen duen problema baten azterketa zaildu egiten da. Adibidez, n elementu ezberdin n! (n faktorial) eratara ordena daitezke; elementu kopurua banan banan gehitu ahala, ordena ezberdinen kopurua gero eta azkarrago doa gehitzen, leherketa batean gertatzen denaren antzera: (eu)
- L'explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, est le fait qu'un petit changement du nombre de données à considérer dans un problème par ailleurs trivial peut suffire à rendre sa solution très difficile, voire impossible dans certains cas avec les ordinateurs actuels. Des exemples parlant d'explosion combinatoire sont ceux de la fonction d'Ackermann ou du problème du voyageur de commerce. (fr)
- Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи. Более точно это означает, что рассматриваемый алгоритм не является полиномиальным, то есть время решения задачи не ограничено никаким многочленом от длины входа. Обычно такие задачи имеют экспоненциальную или даже сверхэкспоненциальную сложность. Для обхода проблемы комбинаторного взрыва ищут специальные методы решения, в частности, применяют эвристические алгоритмы. (ru)
- Комбінаторний вибух — термін, який використовується для опису ефекту різкого («вибухового») зростання часової складності алгоритму при збільшенні розміру вхідних даних задачі. Більш точно це означає, що алгоритм не є поліноміальним, тобто час розв'язування задачі не обмежується ніяким многочленом від довжини входу. Зазвичай такі задачі мають експоненціальну або навіть надекспоненціальну складність. Для обходу проблеми комбінаторного вибуху шукають спеціальні методи розв'язування, зокрема, застосовують евристичні алгоритми. (uk)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Kombinatorická exploze je v matematice neformální označení jevu, kdy složitost daného problému silně vzrůstá spolu s tím, jak se vzhledem k rostoucímu vstupu velice rychle rozšiřuje kombinatorické jádro problému, typicky počet kombinací, které by mohly být řešením. (cs)
- In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function. (en)
- Lehertze konbinatorioa konbinatoria baliatuz egoera bat aztertu edo problema bat ebazterakoan, hartzen den elementu kopurua gehitu ahala, aztertu beharreko konbinazio posible eta emaitzen kopuruan gertatzen den gehikuntza itzela adierazteko erabiltzen den terminoa da. Ondorioz, bere baitan erlatiboki hain handia ez den elementu kopurua hartzen duen problema baten azterketa zaildu egiten da. Adibidez, n elementu ezberdin n! (n faktorial) eratara ordena daitezke; elementu kopurua banan banan gehitu ahala, ordena ezberdinen kopurua gero eta azkarrago doa gehitzen, leherketa batean gertatzen denaren antzera: 1!=12!=23!=64!=245!=1206!=720.......10!:3628800 (eu)
- En matemáticas, una explosión combinatoria consiste en el crecimiento muy rápido de la complejidad de un problema debido a cómo se ve afectado por las condiciones iniciales, restricciones y límites del propio problema. La explosión combinatoria se utiliza a veces para justificar la intrazabilidad de ciertos problemas. Hay muchos ejemplos de tales problemas, que incluyen ciertas funciones, el análisis de algunos rompecabezas y juegos y algunos ejemplos patológicos que pueden ser modelizados, como la Función de Ackermann. (es)
- L'explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, est le fait qu'un petit changement du nombre de données à considérer dans un problème par ailleurs trivial peut suffire à rendre sa solution très difficile, voire impossible dans certains cas avec les ordinateurs actuels. Des exemples parlant d'explosion combinatoire sont ceux de la fonction d'Ackermann ou du problème du voyageur de commerce. L'explosion combinatoire peut être jugulée efficacement dans quelques cas par des limitations de bon sens dans les valeurs (relatives ou absolues) des variables à considérer, ou par des considérations plus générales sur les fonctions en question (la programmation dynamique met à profit par exemple le cas où les fonctions sont de type monotones croissantes). Outre ces considérations théoriques, un procédé plus informatique consiste, dans le cas où des calculs identiques et longs risquent d'être répétés souvent, de mettre en mémoire les résultats intermédiaires pour éviter ces recalculs, mais aussi de veiller à ne pas faire des calculs qui ne servent à rien (évaluation paresseuse). (fr)
- 組合せ爆発（くみあわせばくはつ、英: combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。 (ja)
- Комбінаторний вибух — термін, який використовується для опису ефекту різкого («вибухового») зростання часової складності алгоритму при збільшенні розміру вхідних даних задачі. Більш точно це означає, що алгоритм не є поліноміальним, тобто час розв'язування задачі не обмежується ніяким многочленом від довжини входу. Зазвичай такі задачі мають експоненціальну або навіть надекспоненціальну складність. Походження назви пов'язане з тим, що для розв'язування задачі не вдається знайти іншого способу, крім повного перебору всіх можливих варіантів. У цьому випадку час, що потрібен для розв'язування, пропорційний до кількості всіх можливих конфігурацій, яка визначається на основі тих чи інших комбінаторних міркувань (сполучення, перестановки). Для обходу проблеми комбінаторного вибуху шукають спеціальні методи розв'язування, зокрема, застосовують евристичні алгоритми. (uk)
- Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи. Более точно это означает, что рассматриваемый алгоритм не является полиномиальным, то есть время решения задачи не ограничено никаким многочленом от длины входа. Обычно такие задачи имеют экспоненциальную или даже сверхэкспоненциальную сложность. Происхождение названия связано с тем, что для решения задачи не удается найти иного способа, кроме полного перебора всех возможных вариантов. В этом случае время, требуемое для решения, пропорционально количеству всех возможных конфигураций, которое определяется из тех или иных комбинаторных соображений (сочетания, перестановки). Для обхода проблемы комбинаторного взрыва ищут специальные методы решения, в частности, применяют эвристические алгоритмы. (ru)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is rdfs:seeAlso
of | |
| is Link from a Wikipage to another Wikipage
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)
