Перевод, выполненный человеком

Перевод сделанный профессиональным переводчиком (Кнут Д, 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) непосредственно перед открытием дверей в зависимости от того, какие команды находятся в вызываемой последовательности. Лифту требуется некоторое время для открытия и закрытия дверей, ускорения и замедления, а также для перемещения от одного этажа к другому. Все эти величины указаны в приведенном ниже алгоритме, который выглядит гораздо более строго, чем привычные нам простые правила пользования лифтом. Этот алгоритм может и не отражать истинный принцип действия лифта, но автор все же верит, что он является простейшим набором правил, которые могут объяснить все те явления, которые автор наблюдал в ходе длительных экспериментов с лифтом во время написания этого раздела.

Статистика (вместе с математическими символами):

Отрывок 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.

Статистика:

Перевод, выполненный статистической СМП

Машинный перевод отрывка (на основании веб-сервиса Google Переводчик).

Образцы автоматы могут легко имитировать графа машин, принимая более ограниченным числом шагов в графе шаг. С другой стороны, однако, маловероятно, что граф машины могут моделировать произвольные Образцы автоматов без неограниченно возрастающая время работы, если определение изменяется от неориентированного на ориентированные графы, в силу ограничения на вершины ограниченной степени. Образцы модель, конечно, совсем близко от операций, доступных для программистов на реальных машинах, а граф модель не является.

Некоторые из наиболее интересных задач для решения таких устройств будет определить, как быстро они могут решить некоторые проблемы, или, как многие узлы им необходимо для решения определенных задач (например, перевод некоторых формальных языков). В то время эта глава впервые была написана, несколько интересных результатов такого рода были получены (в частности, Дж. Хартманис и RE Stearns), но только для специальных классов машин Тьюринга, имеющих несколько лент и головок чтения / записи. Модель машины Тьюринга сравнительно нереально, так что эти результаты как правило, имеют мало общего с практическими проблемами.

Мы должны признать, что, как число n узлов, созданных по Образцы бесконечности автомата подходы, мы не знаем, как построить такие устройства физически, так как мы хотим машинных операций принять столько же времени, независимо от размера n, если Образцы представлены с помощью адресов, как в памяти компьютера, необходимо поставить оценку числа узлов, так как ссылка поля имеют фиксированный размер. Тьюринга машина Поэтому более реалистичной модели, когда n стремится к бесконечности. Однако, как представляется разумным полагать, что связь автомата, как описано выше, приводит к более подходящей теории сложности алгоритмов, чем машины Тьюринга делать, даже если асимптотические формулы при больших n считаются, потому что теория, скорее всего, иметь отношение к практической значениях n. Кроме того, когда n становится больше, чем 1030 или около того, даже не одна машина Тьюринга является реалистичной: она никогда не может быть построена.

Соответствие является более важным, чем реализм. Много лет прошло с тех пор автор написал большую часть комментарии выше, и все может быть рад, что существенный прогресс действительно были сделаны на теории Образцы автоматов (сейчас он называется указатель машин). Но, конечно, многое еще предстоит сделать.

Перевод, выполненный трансфертной СМП

Машинный перевод отрывка (на основании СМП Промпт):

Соединение автоматов может легко моделировать машины графика, беря самое большее ограниченное число шагов на шаг графика. Наоборот, однако, маловероятно, что машины графика могут моделировать произвольные автоматы соединения, неограниченно не увеличивая время выполнения, если определение не изменено от неориентированного до направленных графиков, ввиду ограничения на вершины ограниченной степени. Соединяющаяся модель, конечно, вполне близко к операциям, доступным программистам на реальных машинах, в то время как модель графика нет.

Некоторые из самых интересных проблем решить для таких устройств состояли бы в том, чтобы определить, как быстро они могут решить определенные проблемы, или сколько узлов они должны решить определенные проблемы (например, чтобы преобразовать определенные формальные языки). В то время, когда эта глава была сначала записана, несколько интересных результатов этого вида были получены (особенно Дж. Хартмэнисом и Р. Э. Стернзом), но только для специальных классов Машин Тьюринга, имеющих многократные ленты и комбинированные головки. Модель Машины Тьюринга сравнительно нереалистична, таким образом, эти результаты имели тенденцию иметь мало общего с практическими проблемами.

Мы должны признать, что, поскольку номер n узлов, создаваемых соединяющимся автоматом, приближается к бесконечности, мы не знаем, как создать такое устройство физически, так как мы хотим, чтобы машинные операции заняли то же самое количество времени независимо от размера n; если соединение представлено при использовании адресов как в памяти компьютера, необходимо поместить привязанный число узлов, так как у полей ссылки есть фиксированный размер. Машина Тьюринга мультиленты _ поэтому более реалистическая модель, когда n приближается к бесконечности. Все же кажется разумным полагать, что соединяющийся автомат как описано выше приводит к более соответствующей теории сложности алгоритмов, чем Машины Тьюринга, даже когда асимптотические формулы для большого n рассматривают, потому что теория, более вероятно, будет важна для практических значений n. Кроме того, когда n становится больше чем приблизительно 1030, не, даже Машина Тьюринга с одной лентой реалистична: Это никогда не могло создаваться.

Уместность более важна чем реализм. Много лет передали, так как автор записал большинство комментариев выше, и все могут радоваться, что значительный прогресс был действительно сделан на теории соединения автоматов (теперь названным машинами указателя). Но конечно много все еще остается быть сделанным.

Перевод, выполненный человеком

Перевод сделанный профессиональным переводчиком (Кнут Д, 2002:511):

Связывающие автоматы могут легко моделировать машины графов, используя ограниченное сверху количество шагов на один шаг работы графа. Напротив, маловероятно, чтобы машины графов могли моделировать произвольные связывающие автоматы без неограниченного увеличения времени работы, если не перейти от неориентированных графов к ориентированным, чтобы работать с вершинами с ограниченной степенью. И, конечно, связывающая модель гораздо ближе к операциям, доступным программисту на реальной машине, в отличие от модели с использованием графа.

Самыми интересными проблемами, которые предстоит решить для такого рода устройств, являются определение скорости решения поставленных ими задач, т. е. подсчет количества узлов, требуемых для решения той или иной задачи (например, для трансляции какого-либо формального языка). В то время, когда автор приступил к работе над настоящей главой, были получены интересные результаты такого рода (отметим работы Ю. Хартманиса (J. Hartmanis) и Р.Э. Стирнса (R.Е. Stearns)), но только для специальных классов машин Тьюринга с множеством лент и головок чтения/записи. Модель машины Тьюринга сравнительно нереальна, а потому полученные результаты имеют мало общего с решением практических задач.

Следует признать, что при стремлении количества созданных связывающим автоматом узлов n к бесконечности неизвестно, как построить такое устройство физически, поскольку желательно, чтобы операции машины выполнялись за одно и то же время независимо от размера n. Если связывание представлено с использованием адресов в машинной памяти, необходимо определить границу для количества узлов, поскольку поля связей имеют фиксированный размер.

Многоленточная машина Тьюринга поэтому представляет собой более реалистичную модель при стремлении n к бесконечности. Представляется также обоснованной уверенность в том, что описанные выше связывающие автоматы приведут к созданию более приемлемой теории сложности алгоритмов, чем машина Тьюринга, даже при рассмотрении асимптотических формул для больших n, так как эта теория больше подходит для практических значений n. Кроме того, когда n становится больше, чем 1030 или около того, даже одноленточная машина Тьюринга не является реалистичной: она никогда не будет построена. Принципы важнее реалий. Со времени первого написания автором большинства приведенных выше комментариев утекло много воды, и можно порадоваться, что в теории связывающих автоматов (сегодня называемых машинами указателей (pointer machines)) достигнут определенный прогресс, хотя, конечно же, предстоит еще немало сделать в этой области.

Статистика:

Таблицы анализа

Ниже приведены таблицы анализа всех трех отрывков для каждой СМП. Строки таблицы имеют нумерацию в виде (n.m), где n - номер отрывка, m - номер предложения.

Список сокращений

ФС - функциональный стиль.

СМП - системы машинного перевода.

Условные обозначения

Условные обозначения, используемые в таблицах аналитической части.

· НА - начало абзаца;

· /* комментарий */ _ комментарии к отдельным участкам;

· *** _ линейки таблицы, которые хотелось бы обратить особое внимание;

· {{Термин}} - обозначаются термины;

· {{Термин}} - обозначаются термины, переведенные с недочетами;

· Участки, стилистически характерные для научного стиля;

· Участки, которые стилистически нельзя отнести к научному стилю;

· Участки, на которые хотелось бы обратить особое внимание;

· Участки, на в которых имеются недочеты;

Размещено на Allbest.ru