| dbo:abstract
|
- The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by John Myhill in 1957 and published (with a solution by John McCarthy and Marvin Minsky) in 1962 by Edward F. Moore. (en)
- 一斉射撃問題（いっせいしゃげきもんだい）は、計算機科学とセル・オートマトンにおける数学パズル的な問題の一つである。この問題の目標は、一つのセルのみが活動している状態から始めて、最終的に全てのセルが同時に特定の状態に到達するように、セル・オートマトンを設計することである。 この問題は1957年にジョン・マイヒル（en:John Myhill）によって提案された。出版物としては、1964年に、エドワード・ムーア（en:Edward F. Moore）の編集による、この問題が解法とともに収録された文献集が出版されている。 (ja)
- Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов. Впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу. Формулируется следующим образом: можно ли так запрограммировать одномерный клеточный автомат конечной длины, чтобы из стартового состояния G●●…●●● все клетки одновременно перешли в состояние FFF…FFF, независимо от длины цепочки, если обязательно правило перехода ●●●→● и его аналоги для концов цепочки ⌀●●→●, ●●⌀→●? Простым языком:
* роботов (конечных автоматов) с ружьями стоят шеренгой. У автоматов как минимум три состояния ●, G и F — «исходное», «командир» и «выстрел». Помимо этих трёх, можно добавить сколько угодно промежуточных состояний.
* Роботы действуют независимо по одной программе и общаются только по цепочке: по сигналам барабана (синхронизатора) в зависимости от своего состояния в момент и состояния двух соседей переходят в новое состояние. Исключение — крайние роботы, у которых только один сосед; у них собственные программы.
* Все три программы, если робот и его соседи в исходном состоянии, ничего не должны делать.
* Все роботы стоят в исходном состоянии и ничего не делают. В момент крайнего левого переводят в состояние «командир».
* Существуют ли такие три программы (набор состояний и три комплекта правил перехода — для командира, замыкающего и остальных роботов), чтобы при любом они одновременно (на одном ударе барабана) перешли в состояние «выстрел»? Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием . (ru)
- Problem synchronizacji plutonu egzekucyjnego – zagadnienie z zakresu informatyki, polegające na próbie konstrukcji takiego automatu komórkowego, który zaczynając od pojedynczej nieaktywnej komórki, osiągnie stan, w którym wszystkie komórki osiągną jednocześnie stan aktywności. Problem został sformułowany przez Johna Myhilla w 1957, a pierwsze jego rozwiązanie opublikował w 1962 r. Edward Moore. (pl)
- Задача синхронізації стрільців — завдання з області інформатики і клітинних автоматів, уперше запропонована Джоном Мейгіллом в 1957 році і опубліковане (з рішенням) в 1962 році Едвардом Муром. Формулюється таким чином: Розглянемо кінцеве, але довільне число кінцевих автоматів (стрільців), розташованих в ряд. У момент часу t = 0 кожен солдат перебуває у вихідному стані, за винятком найлівішого солдата (командира). Стан кожного солдата у момент часу t > 0 залежить від стану його самого і двох його сусідів у момент часу t − 1(за винятком самих крайніх солдатів, у яких лише один сусід). Якщо солдат і його сусіди знаходяться в початковому стані, то в цьому ж стані вони і залишаються в наступні моменти часу. Завдання полягає в тому, щоб знайти кінцевий набір станів і правил переходу між ними, які допускали б одночасний перехід усіх солдатів в необхідний стан (вогонь). (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8400 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
|
- Eiichi Goto (en)
- Patrick C. Fischer (en)
|
| dbp:first
| |
| dbp:last
| |
| dbp:title
|
- Firing Squad Problem (en)
|
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1962 (xsd:integer)
- 1965 (xsd:integer)
|
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by John Myhill in 1957 and published (with a solution by John McCarthy and Marvin Minsky) in 1962 by Edward F. Moore. (en)
- 一斉射撃問題（いっせいしゃげきもんだい）は、計算機科学とセル・オートマトンにおける数学パズル的な問題の一つである。この問題の目標は、一つのセルのみが活動している状態から始めて、最終的に全てのセルが同時に特定の状態に到達するように、セル・オートマトンを設計することである。 この問題は1957年にジョン・マイヒル（en:John Myhill）によって提案された。出版物としては、1964年に、エドワード・ムーア（en:Edward F. Moore）の編集による、この問題が解法とともに収録された文献集が出版されている。 (ja)
- Problem synchronizacji plutonu egzekucyjnego – zagadnienie z zakresu informatyki, polegające na próbie konstrukcji takiego automatu komórkowego, który zaczynając od pojedynczej nieaktywnej komórki, osiągnie stan, w którym wszystkie komórki osiągną jednocześnie stan aktywności. Problem został sformułowany przez Johna Myhilla w 1957, a pierwsze jego rozwiązanie opublikował w 1962 r. Edward Moore. (pl)
- Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов. Впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу. Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием . (ru)
- Задача синхронізації стрільців — завдання з області інформатики і клітинних автоматів, уперше запропонована Джоном Мейгіллом в 1957 році і опубліковане (з рішенням) в 1962 році Едвардом Муром. Формулюється таким чином: (uk)
|
| rdfs:label
|
- Firing squad synchronization problem (en)
- 一斉射撃問題 (ja)
- Problem plutonu egzekucyjnego (pl)
- Задача синхронизации стрелков (ru)
- Задача синхронізації стрільців (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
