| http://dbpedia.org/ontology/abstract
|
Галакти́ческий алгори́тм (англ. galactic a … Галакти́ческий алгори́тм (англ. galactic algorithm) — алгоритм, превосходящий любой другой алгоритм для решения существенно больши́х задач, где «существенно большие» задачи означают настолько большой масштаб, что такой алгоритм не используется на практике. Галактические алгоритмы были так названы Ричардом Липтоном и Кеном Риганом, поскольку они никогда не будут применимы на любых «земных», привычных нам данных. Пример галактического алгоритма — самый быстрый из известных алгоритмов умножения двух чисел, который основан на 1729-мерном преобразовании Фурье. Он не достигнет заявленной эффективности до тех пор, пока эти числа не будут иметь по крайней мере 2172912 битов (по крайней мере 101038 цифр), что значительно превосходит число атомов в известной части Вселенной. Поэтому такой алгоритм никогда не используется на практике. Несмотря на свою непрактичность, галактические алгоритмы могут быть полезными в теоретической информатике:
* Даже непрактичный алгоритм может продемонстрировать новые техники, которые однажды могут быть использованы для разработки практических алгоритмов.
* Объёмы данных, обрабатываемых компьютерами, могут достичь определённого значения, при котором непрактичный алгоритм становится применимым на практике.
* Непрактичный алгоритм может продемонстрировать, что предполагаемые границы могут быть достигнуты, либо что предполагаемые границы неверны. Липтон утверждает: «Это само по себе может быть важным и часто является веской причиной для поиска таких алгоритмов. Например, если бы завтра случилось открытие, доказывающее, что существует алгоритм факторизации с огромной временно́й сложностью, но достоверно полиномиальной, это бы изменило наше представление о факторизации. Сам такой алгоритм, может, никогда бы не использовался, но он показал бы пути для дальнейших исследований в этой области». Аналогично: алгоритм со сложностью для решения задачи выполнимости булевых формул — хотя и неприменим на практике — решил бы проблему равенства классов P и NP, наиболее важную открытую проблему в теоретической информатике и одну из задач тысячелетия.й информатике и одну из задач тысячелетия.
, A galactic algorithm is one that outperfor … A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.l never be used on any data sets on Earth.
, Un algoritmo galáctico es aquel que supera … Un algoritmo galáctico es aquel que supera a cualquier otro algoritmo para problemas que son suficientemente grandes, pero cuando "suficientemente grande" es tan grande que el algoritmo nunca se usa en la práctica. Los algoritmos galácticos fueron nombrados así por Richard Lipton y Ken Regan, haciendo alusión a que "nunca se utilizarán en ninguno de los conjuntos de datos meramente terrenales que se pudieran manejar aquí en la Tierra".ue se pudieran manejar aquí en la Tierra".
, Un algorithme galactique est un algorithme … Un algorithme galactique est un algorithme de résolution d'un problème qui est plus rapide que tous les autres algorithmes quand le problème est suffisamment grand, mais dans le cas où « suffisamment grand » est tellement grand que l’algorithme n’est en pratique jamais utilisé. Les algorithmes galactiques ont été nommés ainsi par Richard Lipton et Ken Regan parce qu'ils ne seront jamais utilisés pour aucun ensemble de données trouvé sur Terre. Un exemple d'algorithme galactique est l'algorithme pour multiplier deux nombres qui est basé sur une transformée de Fourier à 1 729 dimensions. Cela signifie qu’elle ne sera pas la plus rapide tant que les nombres n’auront pas au moins 101038 chiffres, (considérablement) plus de chiffres qu’il n’y a d’atomes dans l’univers. Donc, cet algorithme n'est jamais utilisé dans la pratique. Malgré le fait qu’ils ne seront jamais utilisés, les algorithmes galactiques peuvent néanmoins contribuer à l'informatique :
* un algorithme, même s’il n’est pas utilisable, peut montrer de nouvelles techniques pouvant éventuellement être utilisées pour créer des algorithmes plus efficaces ;
* la puissance des ordinateurs peuvent rattraper la defaillance, de sorte qu'un algorithme auparavant peu pratique le devient ;
* un algorithme inutilisable peut toujours démontrer que des bornes conjecturées peuvent être obtenues, ou alternativement, montrer que les limites conjecturées sont fausses. Comme le dit Lipton, « En soi cet argument est suffisant pour donner d'excellentes raisons de trouver de tels algorithmes. Par exemple, s'il existait demain une découverte montrant qu'il existait un algorithme de factorisation avec une limite de temps énorme mais polynomiale, cela changerait nos connaissances sur la factorisation. L’algorithme pourrait ne jamais être utilisé, mais déterminerait certainement les recherches futures en factorisation. » De même, un algorithme O( N2100 ) pour le problème SAT, bien qu'inutilisable en pratique, réglerait le problème P = NP, qui est le problème ouvert le plus important en informatique. Un effet pratique immédiat serait l'obtention par le découvreur d'un prix d'un million de dollars par le Clay Mathematics Institute.dollars par le Clay Mathematics Institute.
, 银河式算法（Galactic Algorithm）不是某一种具体算法的名称，而是一类 … 银河式算法（Galactic Algorithm）不是某一种具体算法的名称，而是一类对于极大规模数据表现特别优异的复杂算法。这类算法在常规问题中往往无法展现出优势，甚至效率低于一般的解决方案，而当数据规模足够大时，效率将提升到不可思议的程度。这里的“足够大”实际上已经脱离了现实需求，以至于这类算法从未在实践中发挥作用。“银河式算法”一词首先由和提出，“银河式”意味着面对数据规模之大如银河中的繁星，且“不会与地球上的问题打交道”。 银河式算法的著名示例包括一种大整数乘法，其基于 维的快速傅里叶变换。这意味着只有当数值至少达到 （即 ）位十进制数字之后,这种算法的优势才能发挥出来，而这个数量级已经远远超过宇宙中原子的数量，因此这种算法从未被真正使用过。 即便银河式算法看起来没有用处，但有关这类算法的思想和讨论仍然对计算机科学大有裨益。
* 一种看似不切实际的算法所展现出来的新技术，可能会最终转变为比当下更好的实用算法。
* 计算机的高速发展可能会使解决一些原本不曾邂逅的大规模问题变得迫在眉睫，算力和存储空间的提升可能会为一些原本难以实施的复杂算法提供实践机会。
* 不切实际的算法会证明或证伪当下一些猜想的边界。据立普顿所说，“这一点非常重要，并且通常是我们找到此类算法的重要原因。例如，如果明天发现一个因式分解算法具有巨大但可证明的多项式时间复杂度，即使我们深信该算法可能永远不会使用，但仍会影响我们未来对于因式分解相关技术的研究，为更新颖、更可靠的想法提供经验。”同样，一种用于解决布尔可满足性问题的、时间复杂度为 的算法虽然在实践中不可用，但仍然有益于人们探索P=NP问题——这一计算机科学中最重要的开放性问题，也是千禧年大奖问题之一。人们探索P=NP问题——这一计算机科学中最重要的开放性问题，也是千禧年大奖问题之一。
|
| http://dbpedia.org/ontology/wikiPageID
|
60819045
|
| http://dbpedia.org/ontology/wikiPageLength
|
13260
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1122802425
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/P_versus_NP_problem +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Category:Mathematical_notation +
, http://dbpedia.org/resource/Traveling_salesman_problem +
, http://dbpedia.org/resource/Bor%C5%AFvka%27s_algorithm +
, http://dbpedia.org/resource/Simulated_annealing +
, http://dbpedia.org/resource/Millennium_Prize_Problems +
, http://dbpedia.org/resource/Knuth%27s_up-arrow_notation +
, http://dbpedia.org/resource/Claude_Shannon +
, http://dbpedia.org/resource/Expected_linear_time_MST_algorithm +
, http://dbpedia.org/resource/Boolean_satisfiability_problem +
, http://dbpedia.org/resource/Communication_channel +
, http://dbpedia.org/resource/Code +
, http://dbpedia.org/resource/Multiplication_algorithm +
, http://dbpedia.org/resource/Fourier_transform +
, http://dbpedia.org/resource/Metric_space +
, http://dbpedia.org/resource/Category:Analysis_of_algorithms +
, http://dbpedia.org/resource/Richard_Lipton +
, http://dbpedia.org/resource/Big_O_notation +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Category:Asymptotic_analysis +
, http://dbpedia.org/resource/Christofides_algorithm +
, http://dbpedia.org/resource/Minimum_spanning_tree +
, http://dbpedia.org/resource/Strassen_algorithm +
, http://dbpedia.org/resource/Advanced_Encryption_Standard +
, http://dbpedia.org/resource/Coppersmith%E2%80%93Winograd_algorithm +
, http://dbpedia.org/resource/Graph_minor +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Quote +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Short_description +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Asymptotic_analysis +
, http://dbpedia.org/resource/Category:Mathematical_notation +
, http://dbpedia.org/resource/Category:Analysis_of_algorithms +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Galactic_algorithm?oldid=1122802425&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Galactic_algorithm +
|
| owl:sameAs |
http://ru.dbpedia.org/resource/%D0%93%D0%B0%D0%BB%D0%B0%D0%BA%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC +
, https://global.dbpedia.org/id/9sj4T +
, http://fr.dbpedia.org/resource/Algorithme_galactique +
, http://dbpedia.org/resource/Galactic_algorithm +
, http://zh.dbpedia.org/resource/%E9%93%B6%E6%B2%B3%E5%BC%8F%E7%AE%97%E6%B3%95 +
, http://vi.dbpedia.org/resource/Thu%E1%BA%ADt_to%C3%A1n_thi%C3%AAn_h%C3%A0 +
, http://www.wikidata.org/entity/Q65072234 +
, http://es.dbpedia.org/resource/Algoritmo_gal%C3%A1ctico +
|
| rdfs:comment |
A galactic algorithm is one that outperfor … A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.l never be used on any data sets on Earth.
, Галакти́ческий алгори́тм (англ. galactic a … Галакти́ческий алгори́тм (англ. galactic algorithm) — алгоритм, превосходящий любой другой алгоритм для решения существенно больши́х задач, где «существенно большие» задачи означают настолько большой масштаб, что такой алгоритм не используется на практике. Галактические алгоритмы были так названы Ричардом Липтоном и Кеном Риганом, поскольку они никогда не будут применимы на любых «земных», привычных нам данных. Несмотря на свою непрактичность, галактические алгоритмы могут быть полезными в теоретической информатике:ыть полезными в теоретической информатике:
, Un algorithme galactique est un algorithme … Un algorithme galactique est un algorithme de résolution d'un problème qui est plus rapide que tous les autres algorithmes quand le problème est suffisamment grand, mais dans le cas où « suffisamment grand » est tellement grand que l’algorithme n’est en pratique jamais utilisé. Les algorithmes galactiques ont été nommés ainsi par Richard Lipton et Ken Regan parce qu'ils ne seront jamais utilisés pour aucun ensemble de données trouvé sur Terre. Malgré le fait qu’ils ne seront jamais utilisés, les algorithmes galactiques peuvent néanmoins contribuer à l'informatique :nt néanmoins contribuer à l'informatique :
, 银河式算法（Galactic Algorithm）不是某一种具体算法的名称，而是一类 … 银河式算法（Galactic Algorithm）不是某一种具体算法的名称，而是一类对于极大规模数据表现特别优异的复杂算法。这类算法在常规问题中往往无法展现出优势，甚至效率低于一般的解决方案，而当数据规模足够大时，效率将提升到不可思议的程度。这里的“足够大”实际上已经脱离了现实需求，以至于这类算法从未在实践中发挥作用。“银河式算法”一词首先由和提出，“银河式”意味着面对数据规模之大如银河中的繁星，且“不会与地球上的问题打交道”。 银河式算法的著名示例包括一种大整数乘法，其基于 维的快速傅里叶变换。这意味着只有当数值至少达到 （即 ）位十进制数字之后,这种算法的优势才能发挥出来，而这个数量级已经远远超过宇宙中原子的数量，因此这种算法从未被真正使用过。 即便银河式算法看起来没有用处，但有关这类算法的思想和讨论仍然对计算机科学大有裨益。 即便银河式算法看起来没有用处，但有关这类算法的思想和讨论仍然对计算机科学大有裨益。
, Un algoritmo galáctico es aquel que supera … Un algoritmo galáctico es aquel que supera a cualquier otro algoritmo para problemas que son suficientemente grandes, pero cuando "suficientemente grande" es tan grande que el algoritmo nunca se usa en la práctica. Los algoritmos galácticos fueron nombrados así por Richard Lipton y Ken Regan, haciendo alusión a que "nunca se utilizarán en ninguno de los conjuntos de datos meramente terrenales que se pudieran manejar aquí en la Tierra".ue se pudieran manejar aquí en la Tierra".
|
| rdfs:label |
Galactic algorithm
, Галактический алгоритм
, Algorithme galactique
, Algoritmo galáctico
, 银河式算法
|
