| dbo:abstract
|
- The British Museum algorithm is a general approach to finding a solution by checking all possibilities one by one, beginning with the smallest. The term refers to a conceptual, not a practical, technique where the number of possibilities is enormous. Newell, Shaw, and Simon called this procedure the British Museum algorithm "... since it seemed to them as sensible as placing monkeys in front of typewriters in order to reproduce all the books in the British Museum." (en)
- L´algorithme du British Museum est une approche générale qui vise à trouver une solution à un problème en cherchant toutes les possibilités les unes après les autres, en commençant par les plus petites. Le terme se réfère à un concept, plutôt qu'à une technique pratique pour des problèmes où le nombre de possibilités est énorme. Par exemple, on peut en théorie trouver le plus petit programme qui résout un problème particulier de la façon suivante : Générer tous les codes sources possibles de la longueur d'un caractère. On les vérifie ensuite chacun afin de vérifier si le problème est résolu par le code source. Tester ces programmes peut éventuellement poser des problèmes, comme des boucles infinies, etc. Si les programmes ne marchent pas, on génère et on vérifie tous les programmes de longueur de deux caractères, puis trois caractères, etc. Conceptuellement, cet algorithme permet de trouver le plus petit programme mais en pratique il tend à prendre un temps d'exécution inacceptable pour certains problèmes. Cet algorithme est devenu un clin d'œil dans le milieu informatique lorsque l'on parle d'un très mauvais algorithme pour un problème donné fondé sur le calcul de toutes les solutions[réf. nécessaire]. Par exemple en synthèse d'image un algorithme du British Museum pour calculer la radiosité dans une scène 3D consisterait pour chaque source lumineuse à calculer tous les rayons s'en échappant en échantillonnant l'espace autour de la source. Pour chaque point touché par les rayons lumineux on calcule tous les rayons réémis et ainsi de suite jusqu'à ce que les éclairages soient calculés en tout point de la scène. (fr)
- Een British Museum-algoritme is een algoritme dat een oplossing probeert te vinden door alle mogelijkheden te bekijken, beginnend bij de kleinste. Met deze term wordt vaak een conceptuele maar niet praktische aanpak bedoeld om een oplossing te vinden in situaties waar zeer veel mogelijkheden zijn. De naam verwijst naar het British Museum, een museum in Londen dat een van de grootste collecties ter wereld bezit. Het British Museum-algoritme kan worden gebruikt om aan te tonen dat bepaalde optimalisaties, het of spraakherkenning mogelijk of onmogelijk zijn. (nl)
- Алгоритм Британского музея заключается в переборе всех возможных вариантов, начиная с самого маленького по размеру, пока верное решение не будет найдено. Данный алгоритм почти не применим на практике, являясь лишь принципом, в теории применимым к любой задаче с большим числом возможных вариантов. Например, с помощью алгоритма можно найти самую короткую программу, решающую поставленную задачу, следующим образом. Сначала создаются все возможные программы с исходным кодом длиной в один символ. Затем осуществляется проверка, решает ли каждая из программ задачу. (Такая проверка значительно затрудняется проблемой остановки). Если ни одна из программ не справляется с задачей, рассматриваются все программы длиной в два символа, три символа и так далее. В теории в результате искомая программа действительно будет найдена, однако на практике алгоритм будет работать чрезмерно долго (во многих случаях время работы может превысить продолжительность существования Вселенной). Пользуясь аналогичными выкладками, алгоритм можно использовать для доказательства оптимизаций, теорем, тестирования систем распознавания языков и для иных целей. Американские учёные Аллен Ньюэлл, Клифф Шоу и Герберт Саймоннарекли данную процедуру «алгоритмом Британского музея», поскольку «[идея] показалась им столь же безумной, как и попытка рассаживать обезьян перед печатными машинками в надежде, что они воспроизведут все книги из Британского музея» (ru)
- 大英博物館算法或稱大英博物館技巧，即是以窮舉法，從最小的組合開始找答案。嚴格而言，這只是一個解題的概念而非一個可實作的算法，而且以窮舉法列出所有可能的話，運算時間和空間上並不划算。 大英博物館算法可以下例說，假設有一問題，希望得到一個最短的程式來解決，則求此程式的方法如下：先從長度為n=1開始，產生所有長度n的原始碼，再檢查當中有否可解決此問題的程式（因停機問題，此檢查過程不可能實作），若否，則測試n=2，如此類推，最終必會找到該最短程式，然而此方法卻須花費非常長的時間（大部分問題所須的時間比宇宙的生命還長）。 類似方法可用以證明例如優化、公式證明、辨別等問題可解還是不可解。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1402 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- The British Museum algorithm is a general approach to finding a solution by checking all possibilities one by one, beginning with the smallest. The term refers to a conceptual, not a practical, technique where the number of possibilities is enormous. Newell, Shaw, and Simon called this procedure the British Museum algorithm "... since it seemed to them as sensible as placing monkeys in front of typewriters in order to reproduce all the books in the British Museum." (en)
- Een British Museum-algoritme is een algoritme dat een oplossing probeert te vinden door alle mogelijkheden te bekijken, beginnend bij de kleinste. Met deze term wordt vaak een conceptuele maar niet praktische aanpak bedoeld om een oplossing te vinden in situaties waar zeer veel mogelijkheden zijn. De naam verwijst naar het British Museum, een museum in Londen dat een van de grootste collecties ter wereld bezit. Het British Museum-algoritme kan worden gebruikt om aan te tonen dat bepaalde optimalisaties, het of spraakherkenning mogelijk of onmogelijk zijn. (nl)
- 大英博物館算法或稱大英博物館技巧，即是以窮舉法，從最小的組合開始找答案。嚴格而言，這只是一個解題的概念而非一個可實作的算法，而且以窮舉法列出所有可能的話，運算時間和空間上並不划算。 大英博物館算法可以下例說，假設有一問題，希望得到一個最短的程式來解決，則求此程式的方法如下：先從長度為n=1開始，產生所有長度n的原始碼，再檢查當中有否可解決此問題的程式（因停機問題，此檢查過程不可能實作），若否，則測試n=2，如此類推，最終必會找到該最短程式，然而此方法卻須花費非常長的時間（大部分問題所須的時間比宇宙的生命還長）。 類似方法可用以證明例如優化、公式證明、辨別等問題可解還是不可解。 (zh)
- L´algorithme du British Museum est une approche générale qui vise à trouver une solution à un problème en cherchant toutes les possibilités les unes après les autres, en commençant par les plus petites. Le terme se réfère à un concept, plutôt qu'à une technique pratique pour des problèmes où le nombre de possibilités est énorme. (fr)
- Алгоритм Британского музея заключается в переборе всех возможных вариантов, начиная с самого маленького по размеру, пока верное решение не будет найдено. Данный алгоритм почти не применим на практике, являясь лишь принципом, в теории применимым к любой задаче с большим числом возможных вариантов. Пользуясь аналогичными выкладками, алгоритм можно использовать для доказательства оптимизаций, теорем, тестирования систем распознавания языков и для иных целей. Американские учёные Аллен Ньюэлл, Клифф Шоу и Герберт Саймоннарекли данную процедуру «алгоритмом Британского музея», поскольку (ru)
|
| rdfs:label
|
- British Museum algorithm (en)
- Algorithme du British Museum (fr)
- British Museum-algoritme (nl)
- Алгоритм Британского музея (ru)
- 大英博物館算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
