ssmt-text (1006264), страница 13
Текст из файла (страница 13)
В отличие от этого, "непрерывное моделирование" будет моделирования деятельности, которые находятся под постоянным изменениям, например, трафик, проходящий по шоссе, космические корабли путешествия на другие планеты и т.д. непрерывного моделирования часто может быть удовлетворительно аппроксимируется дискретного моделирования с очень малыми интервалами времени между шагами, однако в таком случае мы, как правило, "синхронные" дискретного моделирования, в котором многие части системы слегка изменен в каждый дискретный интервал времени, и такие приложения обычно требует несколько иной тип организации, чем программы здесь рассматривается.
Программа, разработанная ниже имитирует лифт системы в здании математики из Калифорнийского технологического института. Результаты такого моделирования, возможно, быть полезным только для людей, которые делают достаточно частых визитов в Калифорнийском технологическом институте, и даже для них, это может быть проще, просто попробуйте использовать лифт несколько раз вместо написания компьютерной программы. Но, как обычно, с имитационные исследования, методы, которые мы будем использовать имеют гораздо больший интерес, чем ответов по программе. Методы, которые будут обсуждаться ниже, иллюстрируют типичные методы осуществления использоваться с дискретными программ моделирования.
Здание математики имеет пять этажей: суб-подвал, подвал, первый, второй, и третий. Существует один лифт, который имеет автоматический контроль и может остановиться на каждом этаже. Для удобства мы будем изменить нумерацию этажей 0, 1, 2, 3 и 4.
На каждом этаже Существуют две кнопки вызова, по одному для UP и один для ВНИЗ. (На самом деле слово 0 имеет только вверх и 4 этаж имеет только вниз, но мы можем игнорировать эту аномалию с избыточной кнопки никогда не будет использоваться.) В соответствии с этими кнопками, Есть десять переменных CALLUP [J] и CALLDOWN [J], 0 <= J <= 4.
Есть также переменные CALLCAR [J], 0 <= J <= 4, что составляет кнопки в лифте, которые направляют его на нужный этаж. Когда человек нажимает кнопку, соответствующую переменная установлена ??в 1, лифт очищает переменную в 0 после просьба была выполнена.
До сих пор мы описали лифт с точки зрения пользователя, ситуация более интересная, если смотреть на лифте. Лифт находится в одном из трех состояний: GOINGUP, G0INGD0WN, или нейтральным. (Текущее состояние указывается на пассажиров освещенные стрелками внутри лифта.) Если она находится в состоянии нейтральными и не на этаж 2, машина закроет свои двери и (если команда не дает времени свои двери закрыты) он изменится на GOINGUP или G0INGD0WN, направляясь к этаж 2. (Это "дом этаже", так как большинство пассажиров получить там.) На этаже 2 в нейтральном состоянии, двери, в конечном счете близких и машина будет ждать молча для другой команды. Первая команда получила еще пол множества машин GOINGUP или GOINGDOWN по мере необходимости, она остается в этом состоянии, пока Есть нет команды ожидания в том же направлении, а затем происходит переключение направления или переключается на нейтральной незадолго до открытия двери, в зависимости от того, что другие команды в CALL переменных. Лифт занимает определенное количество времени, чтобы открывать и закрывать свои двери, в целях ускорения и замедления, и чтобы попасть из одного этажа на другой. Все эти величины указаны в ниже алгоритм, который является гораздо более точным, чем неформальное описание может быть. Алгоритм Изучим теперь могут не отражать истинных принципов лифта работы, но это, как полагают, простейший набор правил, которые объясняют все явления, наблюдаемые в течение нескольких часов экспериментов автора во время написания этого раздела.
Перевод, выполненный трансфертной СМП
Машинный перевод отрывка (на основании СМП Промпт):
Как пример использования двунаправленных связанных списков, мы теперь рассмотрим запись дискретной программы моделирования. "Дискретное моделирование" означает моделирование системы, в которой все изменения в состоянии системы, как может предполагаться, происходят в определенные дискретные моменты времени. Моделируемая "система" обычно является рядом отдельных действий, которые в значительной степени независимы, хотя они взаимодействуют с друг другом; примеры - клиенты в хранилище, поставках в гавани, людях в корпорации. На дискретном моделировании мы продолжаем, делая независимо от того, что должно быть сделано в определенный момент моделируемого времени, затем усовершенствовать моделируемые часы к следующему разу, когда некоторое действие, как планируют, произойдет.
В отличие от этого, "непрерывное моделирование" было бы моделированием действий, которые находятся под непрерывными изменениями, такими как трафик, углубляющий магистраль, космические корабли, перемещающиеся в другие планеты, и т.д. Непрерывное моделирование может часто удовлетворительно приближаться дискретным моделированием с очень маленькими временными интервалами между шагами; однако, в таком случае у нас обычно есть "синхронное" дискретное моделирование, на котором много частей системы немного изменены в каждом интервале дискретного времени, и такое приложение обычно призывает к несколько различному типу организации программы чем вид, который рассматривают здесь.
Программа, разработанная ниже, моделирует систему лифта в здании Математики Калифорнийского Технологического института. Результаты такого моделирования будут, возможно, полезны только для людей, которые наносят разумно частые визиты в Калифорнийский технологический институт; и даже для них, может быть более просто только попытаться использовать лифт несколько раз вместо того, чтобы писать компьютерную программу. Но, как обычно с исследованиями моделирования, методы, которые мы будем использовать, имеют намного больше интереса чем ответы, данные программой. Методы, которые будут обсуждены ниже, иллюстрируют типичные методы реализации, используемые с дискретными программами моделирования.
У здания Математики есть пять этажей: подвал, подвал, во-первых, во-вторых, и треть. Есть единственный лифт, который имеет автоматические управления и может остановиться в каждом полу. Для удобства мы перенумеруем этажи 0, 1, 2, 3, и 4.
На каждом полу есть две кнопки вызова, один для и один для ВНИЗ. (Фактически пол 0 имеет только, и пол 4 имеет только ВНИЗ, но мы можем проигнорировать ту аномалию, так как избыточные кнопки никогда не будут использоваться.) Соответствие эти кнопки, есть десять ПРИВЛЕЧЕНИЙ переменных [j] и ВЫГОВОР [j], 0 <= j <= 4. Есть также переменные CALLCAR [j], 0 <= j <= 4, представляя кнопки в пределах автомобиля лифта, которые направляют это к целевому полу. Когда человек нажимает кнопку, соответствующая переменная установлена в 1; лифт очищает переменную к 0 после того, как запрос был выполнен.
До сих пор мы описали лифт с точки зрения пользователя; ситуация более интересна как просматривающийся лифтом. Лифт находится в одном из трех состояний: GOINGUP, G0INGD0WN, или НЕЙТРАЛЬНЫЙ. (Текущее состояние обозначено пассажирам освещенными стрелками в лифте.), Если это находится в НЕЙТРАЛЬНОМ состоянии а не на полу 2, машина закроет свои двери и (если никакая команда не будет дана к тому времени, когда ее двери закрыты), это изменится на GOINGUP или G0INGD0WN, направляясь в пол 2. (Это - "домашний пол,", так как большинство пассажиров входит там.) На полу 2 в НЕЙТРАЛЬНОМ состоянии, в конечном счете закроются двери, и машина будет ожидать тихо другой команды. Первая команда, полученная для другого пола, устанавливает машину GOINGUP или GOINGDOWN как соответствующую; это остается в этом состоянии, пока нет никаких команд, ожидающих в том же самом направлении, и затем это переключает направление или переключается на НЕЙТРАЛЬНЫЙ прежде, чем открыть двери, в зависимости от того, что другие команды находятся в переменных ВЫЗОВА. Лифт берет определенное количество времени, чтобы открыть и закрыть его двери, ускориться и замедлиться, и добраться от одного пола до другого. Все эти количества обозначены в алгоритме ниже, который намного более точен, чем неофициальное описание может быть. Алгоритм, который мы теперь изучим, возможно, не отражает истинные принципы лифта работы, но это, как полагают, самый простой ряд правил, которые объясняют все явления, наблюдаемые в течение нескольких часов экспериментирования автором во время записи этого раздела.
Перевод, выполненный человеком
Перевод сделанный профессиональным переводчиком (Кнут Д, 2002: 317):
В качестве примера использования дважды связанных списков рассмотрим программу дискретного моделирования. "Дискретное моделирование" означает моделирование системы, в которой предполагается, что все изменения состояния системы происходят в некоторые дискретно заданные моменты Моделируемая "система" обычно представляет собой набор отдельных действующих лиц, которые, хотя и могут взаимодействовать друг с другом, в основном, ведут себя независимо.
Например, это могут быть покупатели в магазине, корабли в гавани, сотрудники некоторого предприятия. При этом процесс моделирования заключается в выполнении определенных действий, предусмотренных для данного момента, для перехода к следующему моменту с дальнейшим выполнением других действий, запланированных для нового момента.
И наоборот, "непрерывное моделирование" означает моделирование действий, которые происходят непрерывно, например движение автомобилей по автостраде, полеты космических кораблей к другим планетам и т. д. Непрерывное
моделирование часто можно вполне удовлетворительно имитировать с помощью дискретного моделирования с очень малыми временными интервалами между соседними шагами. Но в таком случае получится "синхронное" дискретное моделирование, при котором многие части системы слегка изменяются на каждом дискретном временном интервале, и такое приложение обычно нуждается в организации программы несколько иного типа, чем тот, который рассмотрен здесь.
Приведенная ниже программа моделирует работу лифта в здании факультета математики Калифорнийского технологического института (Калтех). Результаты такого моделирования, вероятно, будут полезны только тем, кому часто приходится
посещать Калтех. И даже им, видимо, проще будет всего несколько раз воспользоваться этим лифтом, чем создавать специальную программу. Но, как обычно случается при изучении методов моделирования, используемые методы программирования гораздо интереснее, чем результаты выполнения программ. Рассматриваемые ниже методы иллюстрируют типичные методики, которые используются в программах дискретного моделирования.
Здание факультета математики имеет пять этажей: подвальный, цокольный, первый, второй и третий В нем находится один лифт с автоматическим управлением, который может останавливаться на каждом этаже. Для удобства перенумеруем
этажи в следующем порядке: 0, 1, 2, 3 и 4
На каждом этаже есть две кнопки вызова лифта: одна — для движения вверх (UP), а другая — для движения вниз (DOWN). (На самом деле на этаже 0 имеется только кнопка UP, а на этаже 4 — только кнопка DOWN, но эти особые случаи будут игнорироваться, потому что дополнительные кнопки никогда не будут использоваться)
Соответственно эти кнопки будут обозначаться десятью переменными CALLUP[j] и CALLDOWN[j], 0 <= j <= 4. Кроме того, переменные CALLCAR[j], 0 <= j <= 4, будут представлять кнопки внутри кабины лифта, которые обозначают этаж назначения. При нажатии кнопки соответствующей переменной присваивается значение 1, а после выполнения запроса (т е. после того как лифт достигнет заданного этажа) переменной присваивается значение 0.
До сих пор работа лифта описывалась с точки зрения пользователя, но ситуация станет более интересной, если рассмотреть ее с точки зрения лифта. Лифт может находиться в одном из трех следующих состояний: движение вниз (G0INGUP), движение вверх (G0INGDOWN) или нейтральное состояние (NEUTRAL) (Для человека текущее состояние обозначается светящимися стрелками внутри лифта.) Если лифт находится в нейтральном состоянии (NEUTRAL) и не на этаже 2, механизм лифта закроет двери и (если до закрытия дверей не дана никакая команда) лифт придет в состояние движения (G0INGUP или G0INGD0WN), направляясь к этажу 2. (Это его "базовый этаж", так как большинство людей входят в него именно здесь ) Если лифт находится на этаже 2 в состоянии NEUTRAL, двери со временем закроются и лифт будет ожидать следующей команды. Первая полученная и'м команда для перемещения на другой этаж приведет лифт в состояние движения G0INGUP или G0INGD0WN в зависимости от нажатой кнопки. Лифт будет находиться в этом состоянии, пока не остановится. Тогда, если поступили новые команды, произойдет смена направления или переход в нейтральное состояние (NEUTRAL) непосредственно перед открытием дверей в зависимости от того, какие команды находятся в вызываемой последовательности. Лифту требуется некоторое время для открытия и закрытия дверей, ускорения и замедления, а также для перемещения от одного этажа к другому. Все эти величины указаны в приведенном ниже алгоритме, который выглядит гораздо более строго, чем привычные нам простые правила пользования лифтом. Этот алгоритм может и не отражать истинный принцип действия лифта, но автор все же верит, что он является простейшим набором правил, которые могут объяснить все те явления, которые автор наблюдал в ходе длительных экспериментов с лифтом во время написания этого раздела.
Статистика (вместе с математическими символами):
| Параметр | Значение |
| строки | 67 |
| слова | 654 |
| символы | 5017 |
Отрывок 3
Оригинал
Отрывок из «Искусства программирования» (Knuth, 1997: 464).
Linking automata can easily simulate graph machines, taking at most a bounded number of steps per graph step. Conversely, however, it is unlikely that graph machines can simulate arbitrary linking automata without unboundedly increasing the running time, unless the definition is changed from undirected to directed graphs, in view of the restriction to vertices of bounded degree. The linking model is, of course, quite close to the operations available to programmers on real machines, while the graph model is not.
Some of the most interesting problems to solve for such devices would be to determine how fast they can solve certain problems, or how many nodes they need to solve certain problems (for example, to translate certain formal languages). At the time this chapter was first written, several interesting results of this kind had been obtained (notably by J. Hartmanis and R. E. Stearns) but only for special classes of Turing machines having multiple tapes and read/write heads. The Turing machine model is comparatively unrealistic, so these results tended to have little to do with practical problems.
We must admit that, as the number n of nodes created by a linking automaton approaches infinity, we don't know how to build such a device physically, since we want the machine operations to take the same amount of time regardless of the size of n; if linking is represented by using addresses as in a computer memory, it is necessary to put a bound on the number of nodes, since the link fields have a fixed size. A multitape Turing machine is therefore a more realistic model when n approaches infinity. Yet it seems reasonable to believe that a linking automaton as described above leads to a more appropriate theory of the complexity of algorithms than Turing machines do, even when asymptotic formulas for large n are considered, because the theory is more likely to be relevant for practical values of n. Furthermore when n gets bigger than 1030 or so, not even a one-tape Turing machine is realistic: It could never be built.
Relevance is more important than realism. Many years have passed since the author wrote most of the comments above, and everybody can be glad that substantial progress has indeed been made on the theory of linking automata (now called pointer machines). But of course much still remains to be done.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
