Примечание G

Эта статья о компьютерном алгоритме. Чтобы узнать о музыкальной высоте, см. G (музыкальная нота) .

Примечание G, первоначально опубликованное в книге «Очерк аналитической машины, изобретенной Чарльзом Бэббиджем».

Примечание G — компьютерный алгоритм , написанный Адой Лавлейс и предназначенный для вычисления чисел Бернулли с использованием гипотетической аналитической машины . Примечание G принято считать первым алгоритмом, специально предназначенным для компьютера. Лавлейс считается первым программистом . и в результате Алгоритм был последней заметкой в ​​серии, обозначенной от A до G, которую она использовала в качестве наглядного пособия для сопровождения своего английского перевода Луиджи Менабреа 1842 года французской транскрипции лекции Чарльза Бэббиджа об аналитической машине в Туринском университете «Понятия на машине». analytique de Charles Babbage» («Элементы аналитической машины Чарльза Бэббиджа»). Note G Лавлейса никогда не тестировался, поскольку двигатель так и не был построен. Ее заметки вместе с переводом были опубликованы в 1843 году.

В современную эпоху , благодаря более доступному компьютерному оборудованию и ресурсам программирования, алгоритм Лавлейса был протестирован после «перевода» на современные языки программирования. Эти тесты независимо пришли к выводу, что в сценарии произошла ошибка из-за незначительной опечатки, что сделало алгоритм в его исходном состоянии непригодным для использования.

Происхождение

Ада Лавлейс

В 1840 году Чарльз Бэббидж был приглашен провести в Турине семинар по своей аналитической машине. единственное публичное объяснение, которое он когда-либо давал по поводу двигателя. Во время лекции Бэббиджа математик Луиджи Менабреа написал описание двигателя на французском языке. Друг Бэббиджа, Чарльз Уитстон , предложил Лавлейс, чтобы внести свой вклад, перевести отчет Менабреа. Бэббидж предложил ей дополнить отчет приложениями, которые она составила в конце своего перевода в виде серии из семи «примечаний», помеченных как AG. Ее перевод был опубликован в августе 1843 года. в «Научных мемуарах Тейлора » где имя Лавлейс было подписано «AAL». В этих заметках Лавлейс описал возможности аналитической машины Бэббиджа, если бы ее можно было использовать для вычислений, изложив более амбициозный план создания машины, чем даже сам Бэббидж.

Примечания Лавлейса к статье были в три раза длиннее самой статьи. В первых заметках она выходит за рамки числовых амбиций, которые Бэббидж имел в отношении машины, и предполагает, что машина может использовать преимущества вычислений, чтобы справиться с сферами музыки, графики и т. д. и язык.

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

- Ада Лавлейс, Заметки к мемуарам «Очерк аналитической машины, изобретенной Чарльзом Бэббиджем», написанные переводчиком Адой Августой, графиней Лавлейс, Примечание А.

Она объясняет читателям, почему аналитическая машина была отделена от более ранней разностной машины Бэббиджа . и сравнивает свою функцию с жаккардовой машиной , использовались двоичные перфокарты в том смысле, что для обозначения машинного языка . В примечании C этому моменту способствует тот факт, что одновременные и повторяющиеся действия, гарантируя, что любая карта или набор карточек могут быть использованы несколько раз для решения одной задачи. машина может выполнять по сути, предвосхищая современные методы управления потоками и циклами. Эти идеи были доведены до апогея в последней ноте G, где Лавлейс стремилась продемонстрировать пример вычислений .

Примечание G использовало только четыре арифметических операции : сложение, вычитание, умножение и деление, реализация видения Бэббиджа:

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

- Чарльз Бэббидж, «Очерк аналитической машины, изобретенной Чарльзом Бэббиджем»

Он также использует идею Бэббиджа о хранении информации в столбцах дисков, каждый из которых обозначается $V$ (для переменной ) и номер нижнего индекса , обозначающий, к какому столбцу относится ссылка.

Функция

Лавлейс использовала рекурсивное уравнение для расчета чисел Бернулли: при этом она использовала предыдущие значения в уравнении для создания следующего. ее метод заключался в следующем:

$B_{n}=-\sum _{k=0}^{n-1}{\frac {n!}{(n+1-k)!\cdot k!}}$

$B_{k}=-\sum _{k=0}^{n-1}{\binom {n}{k}}{\frac {B_{k}}{n+1-k}}$

где ${\binom {n}{k}}$ – биномиальный коэффициент ,

$\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$.

Числа Бернулли можно рассчитать разными способами , но Лавлейс сознательно выбрала сложный метод, чтобы продемонстрировать мощность двигателя. В примечании G она заявляет: «Мы завершим эти примечания, детально проследив шаги, с помощью которых машина могла вычислить числа Бернулли, поскольку это (в той форме, в которой мы выведем их) довольно сложный пример полномочия». Конкретный алгоритм, использованный Лавлейсом в примечании G, генерирует восьмое число Бернулли (обозначенное как $B_{7}$, как она начала с $B_{0}$.)

Обозначения

В таблице алгоритма каждая команда упорядочена. Каждая команда обозначает одну операцию , выполняемую над двумя терминами. Во втором столбце указывается только используемый оператор. Переменные обозначаются как " $V$", где верхний индекс перед ним представляет количество различных значений, которым была присвоена переменная, а нижний индекс после него представляет порядковый номер переменной, то есть, какая это переменная. (Например, ${}^{2}V_{4}$ относится ко второму присвоению переменной номера 4. Любые переменные, до сих пор не определенные, имеют верхний индекс 0.) Переменные нумеруются, начиная с $V_{0}$. Третий столбец сообщает компьютеру, какая именно команда выполняется (например, в строке 1 выполняется команда « ${}^{1}V_{2}\times {}^{1}V_{3}$" - первая итерация переменной 2 умножается на первую итерацию переменной 3.) и включает только одну операцию между двумя терминами в строке. В столбце 4 - "Переменные, получающие результаты" указывается, где находится результат операции в столбце 3. Таким образом, у любых переменных в этом столбце их верхний индекс каждый раз увеличивается на единицу (например, в строке 1 — результат. ${}^{1}V_{2}\times {}^{1}V_{3}$ присваивается переменным $V_{4}$, $V_{5}$, и $V_{6}$.)

В столбце 5 указывается, была ли изменена какая-либо из переменных, используемых в работе команды. Заключенные в фигурные скобки две строки на команду помещают исходную переменную слева от знака равенства, а новую переменную - с другой стороны - то есть, если переменная была изменена, ее верхний индекс увеличивается на единицу, а если нет, оно остается прежним. (например, третья строка присваивает результат ${}^{1}V_{5}+{}^{1}V_{1}$ ко второй итерации переменной $V_{5}$, и пятый столбец отражает это, отмечая;

${\begin{Bmatrix}{}^{1}V_{5}={}^{2}V_{5}\\{}^{1}V_{1}={}^{1}V_{1}\end{Bmatrix}}$

$V_{5}$ изменилось, но $V_{1}$ нет.

В столбце 6 «Отчет о результатах» результат, присвоенный переменной в столбце 4, отображается в его точном значении, основанном на значениях двух ранее присвоенных терминов. (например, в строке 1 - ${}^{1}V_{2}\times {}^{1}V_{3}$ - $V_{2}$ изначально было установлено, что это $2$, и $V_{3}$ было установлено в качестве переменной $n$. Поэтому, ${}^{1}V_{2}\times {}^{1}V_{3}=2n$, в математической записи .) Этот столбец якобы не вычисляется движком и, по-видимому, больше предназначен для ясности и способности читателя следовать шагам программы. (Например, в строке 5 есть дробь, разделенная на два, что обозначается как умножение на половину, вероятно, для согласованности и типографской сложности вложенной дроби.) В ней также используется отдельная запись переменных вне программы. , $A$ и $B$ переменные, которые последовательно умножаются, чтобы найти окончательное значение, $B_{7}$, таким образом:

$B_{7}=-1(A_{0}+B_{1}A_{1}+B_{3}A_{3}+B_{5}A_{5})$

Помимо этого, в каждом последующем столбце показаны значения данной переменной с течением времени. Каждый раз, когда переменная либо изменяется, либо ее значение становится значимым из-за ее присутствия в качестве одного из терминов в текущей команде, ее значение указывается или пересчитывается в соответствующем столбце. В противном случае оно помечается многоточием, чтобы обозначить его нерелевантность. Это, по-видимому, имитирует потребность компьютера в только соответствующей информации, тем самым отслеживая значение переменной при анализе программы .

Метод

Программа стремилась вычислить то, что в современной традиции известно как восьмое число Бернулли, обозначаемое как $B_{7}$, как Лавлейс начинает отсчет с $B_{0}$.

Ошибка

В операции 4 предположительно происходит разделение" ${}^{2}V_{5}\div {}^{2}V_{4}$", который будет сохранен в переменной ${}^{1}V_{11}$. Однако в «Отчете о результатах» сказано, что разделение должно быть:

${\frac {2n-1}{2n+1}}$

На самом деле разделение происходит наоборот; $2n-1$ это вторая итерация $V_{4}$, как видно из операции 2. Аналогично, $2n+1$ это вторая итерация $V_{5}$, как видно из операции 3. Таким образом, операция 4 не должна ${}^{2}V_{5}\div {}^{2}V_{4}$, скорее ${}^{2}V_{4}\div {}^{2}V_{5}$. Эта ошибка означает, что если бы движок когда-либо запускал этот алгоритм в этом состоянии, он не смог бы правильно сгенерировать числа Бернулли и нашел бы свое конечное целевое значение ( восьмое число Бернулли, $-{\tfrac {1}{30}}$) быть $-{\tfrac {25621}{630}}$.

Современные реализации

Программа Лавлейс может быть реализована на современном языке программирования , однако из-за указанной выше ошибки при точной расшифровке она вернет неправильное конечное значение для $B_{7}$. Исходная программа, обобщенная в псевдокоде, выглядит следующим образом:

V[1] = 1
V[2] = 2
V[3] = n (n = 4 in Lovelace's program.)

V[4] = V[4] - V[1]
V[5] = V[5] + V[1]
V[11] = V[5] / V[4]
V[11] = V[11] / V[2]
V[13] = V[13] - V[11]
V[10] = V[3] - V[1]
V[7] = V[2] + V[7]
V[11] = V[6] / V[7]
V[12] = V[21] * V[11]
V[13] = V[12] + V[13]
V[10] = V[10] - V[1]
V[6] = V[6] - V[1]
V[7]= V[1] + V[7]
//Finish Later
 

Реализация в псевдокоде подчеркивает тот факт, что компьютерные языки определяют переменные в стеке , что устраняет необходимость отслеживания и указания текущей итерации переменной. Кроме того, программа Лавлейс позволяла определять переменные только путем выполнения сложения , вычитания , умножения или деления двух членов, которые ранее были определенными переменными. Современный синтаксис позволит выполнять каждое вычисление более кратко. Это ограничение проявляется в нескольких местах, например в команде 6 ( $V_{13}=V_{13}-V_{11}$). Здесь Лавлейс определяет до сих пор неопределенную переменную ( $V_{13}$) сам по себе, предполагая тем самым, что все неопределенные переменные автоматически равны 0, тогда как большинство современных языков программирования вернут ошибку или перечислят переменную как null . Она имела в виду следующее: « $0-V_{11}$", но ограничилась использованием только переменных в качестве терминов. Аналогично, в команде 8 ( $V_{7}=V_{2}+V_{7}$), строгая запись двучленной арифметики становится громоздкой, так как для определения $V_{7}$ как 2, Лавлейс присваивает значение (0) себе плюс $V_{2}$(2). Именно из-за этих ограничительных обозначений $V_{7}$ определяется так.

Источники

• Штейн, Дороти К. (1984). «Заметки леди Лавлейс: технический текст и культурный контекст» . Викторианские исследования . 28 (1): 33–67. ISSN   0042-5222 . JSTOR   3826758 .
• Вулли, Бенджамин (февраль 1999 г.), Невеста науки: романтика, разум и дочь Байрона , AU: Pan Macmillan, ISBN  978-0-333-72436-1 , получено 7 апреля 2013 г.
• Герц, Пол (2009). «Искусство, код и двигатель перемен» . Художественный журнал . 68 (1): 58–75. дои : 10.1080/00043249.2009.10791336 . ISSN   0004-3249 . JSTOR   40598953 . S2CID   194010431 .