ssmt-text (1006264), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

E2. [Это - нуль?] Если , алгоритм завершается, ; ответ.

E3. [Уменьшить.] Набор , , и возвращается к шагу E1.

Конечно, Евклид не представлял свой алгоритм только этим способом. Формат выше иллюстрирует стиль, в котором будут представлены все алгоритмы всюду по этой книге. Каждому алгоритму, который мы рассматриваем, дали букву идентификации (E в предыдущем примере), и шаги алгоритма идентифицированы этой буквой, сопровождаемой числом (эль, E2, E3). Главы разделены на пронумерованные разделы; в пределах раздела алгоритмы определяются по буквам только, но когда алгоритмы упомянуты в других разделах, соответствующее число раздела присоединено. Например, мы находимся теперь в Разделе 1.1; в пределах этого раздела алгоритм Евклида вызывают Алгоритмом E, в то время как в более поздних разделах это упоминается как Алгоритм 1.1E.

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

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

Понятие алгоритм является основным для всей области компьютерного программирования, поэтому начать мы должны с тщательного анализа этого термина. Слово «алгоритм» (algorithm) уже само по себе представляет большой интерес. На первый взгляд может показаться, будто кто-то собирался написать слово «логарифм» (logarithm), но случайно переставил первые четыре буквы. Этого слова еще не было в издании словаря Webster’s New World Dictionary, вышедшем в 1957 году. Мы находим там только устаревшую форму «algorism» — старинное слово, которое означает «выполнение арифметических действий с помощью арабских цифр». В средние века абакисты считали на абаках (счетных досках), а алгоритмики использовали «algorism». В эпоху Возрождения происхождение этого слова оказалось забытым. Одни лингвисты того времени пытались объяснить его значение путем сочетания слов algiros [больной] и arithmas [число], другие не соглашались с таким толкованием и утверждали, что это слово происходит от «King Algor of Castile». Наконец историки математики обнаружили истинное происхождение слова «algorism»: оно берет начало от имени автора знаменитого персидского учебника по математике, Abu ’Abd Allah Muhammad ibn Musa al-Khwarizml (Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми) (ок. 825 г.), означающего буквально «Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезма»*. Аральское море в Центральной Азии когда-то называлось озером Хорезм, и район Хорезма (Khwarizm) расположен в бассейне реки Амударьи южнее этого моря. Аль-Хорезми написал знаменитую книгу Kitab al-jabr wa’1-muqabala (Китаб аль-джебр валь-мукабала «Книга о восстановлении и противопоставлении»). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово — «алгебра». [О жизни и научной деятельности аль-Хорезми речь идет в работе Н. Zemanek, Lecture Notes in Computer Science 122 (1981), 1-81.]

Постепенно форма и значение слова algorism исказились; как объясняется в словаре Oxford English Dictionary, это слово «претерпело множество псевдоэтимологических искажений, включая последний вариант algorithm, где произошла путаница» с корнем слова греческого происхождения arithmetic. Этот переход от «algorism» к «algorithm» кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто. В старинном немецком математическом словаре Vollstandiges mathematisches Lexicon (Leipzig, 1747) дается следующее определение слова algorithmus: «Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении». Латинское выражение algorithmus infinitesimalis в то время использовалось для определения «способов выполнения действий с бесконечно малыми величинами, открытых Лейбницем (Leibniz)».

К 1950 году слово «алгоритм» чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм приведен в книге Евклида (Euclid) Начала (книга 7, предложения 1 и 2). Думаю, имеет смысл привести здесь описание этого алгоритма.

Алгоритм Е (Алгоритм Евклида). Даны два целых положительных числа и . Требуется найти их наибольший общий делитель, т. е. наибольшее целое положительное число, которое нацело делит оба числа и .

El. [Нахождение остатка.]

Разделим на ., и пусть остаток от деления будет равен . (где .).

Е2. [Сравнение с нулем.]

Если , то выполнение алгоритма прекращается; — искомое значение.

ЕЗ. [Замещение.]

Присвоить , ,и вернуться к шагу El.

Разумеется, у Евклида этот алгоритм сформулирован не совсем так. Приведенная выше формулировка иллюстрирует стиль, в котором алгоритмы будут представлены на протяжении всей этой книги.

Каждому рассматриваемому алгоритму присваивается идентифицирую- щая буква (в предыдущем примере использовалась буква Е), а шагам алгоритма — эта же буква в сочетании с числом (El, Е2, ЕЗ). Главы книги подразделяются на пронумерованные разделы; внутри раздела алгоритмы обозначаются только буквами. Но когда на эти алгоритмы делаются ссылки из других разделов, то к букве присоединяется номер соответствующего раздела. Например, сейчас мы находимся в разделе 1.1; внутри этого раздела алгоритм Евклида называется «Алгоритм Е», но ссылаться на него в последующих разделах мы будем как на алгоритм 1.1Е.

Статистика (приводятся цифры для оригинального издания, без учета алгоритма Евклида):

Параметр	Значение
строки	52
слова	480
символы	4059

Отрывок 2

Оригинал

Отрывок из «Искусства программирования» (Knuth, 1997: 282).

As an example of the use of doubly linked lists, we will now consider the writing of a discrete simulation program. "Discrete simulation" means the simulation of a system in which all changes in the state of the system may be assumed to happen at certain discrete instants of time. The "system" being simulated is usually a set of individual activities that are largely independent although they interact with each other; examples are customers at a store, ships in a harbor, people in a corporation. In a discrete simulation, we proceed by doing whatever is to be done at a certain instant of simulated time, then advance the simulated clock to the next time when some action is scheduled to occur.

By contrast, a "continuous simulation" would be simulation of activities that are under continuous changes, such as traffic moving on a highway, spaceships traveling to other planets, etc. Continuous simulation can often be satisfactorily approximated by discrete simulation with very small time intervals between steps; however, in such a case we usually have "synchronous" discrete simulation, in which many parts of the system are slightly altered at each discrete time interval, and such an application generally calls for a somewhat different type of program organization than the kind considered here.

The program developed below simulates the elevator system in the Mathematics building of the California Institute of Technology. The results of such a simulation will perhaps be of use only to people who make reasonably frequent visits to Caltech; and even for them, it may be simpler just to try using the elevator several times instead of writing a computer program. But, as is usual with simulation studies, the methods we will use are of much more interest than the answers given by the program. The methods to be discussed below illustrate typical implementation techniques used with discrete simulation programs.

The Mathematics building has five floors: sub-basement, basement, first, second, and third. There is a single elevator, which has automatic controls and can stop at each floor. For convenience we will renumber the floors 0, 1, 2, 3, and 4.

On each floor there are two call buttons, one for UP and one for DOWN. (Actually floor 0 has only UP and floor 4 has only DOWN, but we may ignore that anomaly since the excess buttons will never be used.) Corresponding to these buttons, there are ten variables CALLUP [ j] and CALLDOWN [ j], 0 <= j <= 4.

There are also variables CALLCAR[j], 0 <= j <= 4, representing buttons within the elevator car, which direct it to a destination floor. When a person presses a button, the appropriate variable is set to 1; the elevator clears the variable to 0 after the request has been fulfilled.

So far we have described the elevator from a user's point of view; the situation is more interesting as viewed by the elevator. The elevator is in one of three states: GOINGUP, G0INGD0WN, or NEUTRAL. (The current state is indicated to passengers by lighted arrows inside the elevator.) If it is in NEUTRAL state and not on floor 2, the machine will close its doors and (if no command is given by the time its doors are shut) it will change to GOINGUP or G0INGD0WN, heading for floor 2. (This is the "home floor," since most passengers get in there.) On floor 2 in NEUTRAL state, the doors will eventually close and the machine will wait silently for another command. The first command received for another floor sets the machine GOINGUP or GOINGDOWN as appropriate; it stays in this state until there are no commands waiting in the same direction, and then it switches direction or switches to NEUTRAL just before opening the doors, depending on what other commands are in the CALL variables. The elevator takes a certain amount of time to open and close its doors, to accelerate and decelerate, and to get from one floor to another. All of these quantities are indicated in the algorithm below, which is much more precise than an informal description can be. The algorithm we will now study may not reflect the elevator's true principles of operation, but it is believed to be the simplest set of rules that explain all the phenomena observed during several hours of experimentation by the author during the writing of this section.

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

Параметр	Значение
строки	57
слова	729
символы	4400

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

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

В качестве примера использования дважды связанные списки, мы рассмотрим написание отдельной программы моделирования. "Дискретное моделирование" означает моделирование системы, в которой все изменения в состоянии системы можно считать произойти при определенных дискретные моменты времени. "Система" моделируемой обычно набор отдельных мероприятий, которые в значительной степени независимы, хотя они взаимодействуют друг с другом; примеры клиентов в магазине, корабли в порту, люди в корпорации. В дискретного моделирования, мы проведем делать то, что должно быть сделано в определенный момент времени моделирования, то заранее моделируется часы, чтобы в следующий раз, когда какое-либо действие планируется произойти.

Характеристики

Список файлов ВКР