Примечание G

Компьютерный алгоритм

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

Примечание G ^[a] — это компьютерный алгоритм , написанный Адой Лавлейс , который был разработан для вычисления чисел Бернулли с использованием гипотетической аналитической машины . Примечание. G, как правило, считается первым алгоритмом, специально предназначенным для компьютера, ^{[1] [2] [3] [4]} и в результате Лавлейс считается первым программистом . ^{[5] [6] [7] [8]} Алгоритм был последней заметкой в ​​серии, обозначенной от A до G, которую она использовала в качестве наглядных пособий для сопровождения своего английского перевода французской транскрипции Луиджи Менабреа 1842 года лекции Чарльза Бэббиджа по аналитическому анализу. двигатель в Туринском университете , «Notions sur la Machine Analytique de Charles Babbage» («Элементы аналитической машины Чарльза Бэббиджа»). ^{[7] [9]} Note G Лавлейса никогда не тестировался, так как двигатель так и не был построен. Ее заметки вместе с переводом были опубликованы в 1843 году. ^{[6] [7]}

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

Источник

Ада Лавлейс

В 1840 году Чарльза Бэббиджа пригласили провести в Турине семинар , посвященный его аналитической машине, ^[12] единственное публичное объяснение, которое он когда-либо давал по поводу этой машины. ^[13] Во время лекции Бэббиджа математик Луиджи Менабреа написал отчет о двигателе на французском языке. ^[12] Друг Бэббиджа, Чарльз Уитстон , предложил Лавлейсу перевести отчет Менабреа, чтобы внести свой вклад. ^{[12] [14]} Бэббидж предложил ей дополнить отчет приложениями, которые она составила в конце своего перевода в виде серии из семи «примечаний», помеченных как AG. Ее перевод был опубликован в августе 1843 года, ^[12] в «Научных мемуарах Тейлора» , ^{[14] [15]} , где имя Лавлейс было подписано «AAL». ^{[12] [b]} В этих заметках Лавлейс описал возможности аналитической машины Бэббиджа, если бы ее можно было использовать для вычислений, изложив более амбициозный план для машины, чем даже сам Бэббидж. ^{[3] [15] [16]}

Примечания Лавлейса к статье были в три раза длиннее самой статьи. ^[17] В первых заметках она выходит за рамки числовых амбиций, которые Бэббидж имел в отношении машины, и предполагает, что машина могла бы воспользоваться преимуществами вычислений, чтобы справиться с сферами музыки, графики, ^[18] и языка. ^{[8] [19] [20]}

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

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

Она объясняет читателям , как аналитическая машина была отделена от более ранней разностной машины Бэббиджа ^[21] и сравнивает ее функцию с машиной Жаккарда ^[22] в том смысле, что она использовала двоичные перфокарты для обозначения машинного языка . В примечании C этот момент подкрепляется тем фактом, что машина может выполнять одновременные и повторяющиеся действия, гарантируя, что любая карта или набор карт может быть использована несколько раз для решения одной задачи, ^[20] по существу предвосхищая современные методы управления потоком и циклами. ^{[17] [23]} Эти идеи были доведены до апогея в последней заметке G, где Лавлейс стремился продемонстрировать пример вычислений .

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

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

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

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

Функция

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

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

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

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

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

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

Обозначения

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

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

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

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

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

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

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

Метод

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

Ошибка

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

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

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

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

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

В[1] = 1В[2] = 2V[3] = n (n = 4 в программе Лавлейса.)В[4] = В[4] - В[1]В[5] = В[5] + В[1]В[11] = В[5] / В[4]В[11] = В[11] / В[2]В[13] = В[13] - В[11]В[10] = В[3] - В[1]В[7] = В[2] + В[7]В[11] = В[6] / В[7]В[12] = В[21] * В[11]В[13] = В[12] + В[13]В[10] = В[10] - В[1]В[6] = В[6] - В[1]В[7]= В[1] + В[7]//Завершить позже

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

Примечания

1. Полностью озаглавлена ​​«Диаграмма вычислений с помощью машины чисел Бернулли», но синекдохально известна под «Примечанием G».
2. В мемуарах ее инициалы опечатаны как «ВСЕ» ^[14]
3. Эти переменные технически относятся к столбцам дисков, по предложению Бэббиджа, что именно так их и следует обозначать. ^[20]

Рекомендации

1. Демминг, Анна. «Ада Лавлейс». Новый учёный . Проверено 1 июня 2022 г.
2. Крыса, Иоасия. Ада Лавлейс - Никогда не было ноты G.
3. «Ада Лавлейс, первый технический провидец». Житель Нью-Йорка . 15 октября 2013 г. Проверено 2 июня 2022 г.
4. Герц 2009, с. 59.
5. «Празднование Ады Лавлейс:« первого в мире программиста » - Короткометражка Sharp Science - New Scientist» . 27 марта 2009 г. Архивировано из оригинала 27 марта 2009 г. Проверено 1 июня 2022 г.
6. «Ада Лавлейс | Двигатель Бэббиджа | Музей истории компьютеров» . www.computerhistory.org . Проверено 1 июня 2022 г.
7. «Ада Лавлейс | Биография, компьютер и факты». Британская энциклопедия . Проверено 1 июня 2022 г.
8. «Ада Лавлейс: первый программист». Ментальная нить . 13 октября 2015 г. Проверено 2 июня 2022 г.
9. Штейн 1984, с. 44.
10. «Что на самом деле делала программа Ады Лавлейс?». сайт twobithistory.org . Проверено 1 июня 2022 г.
11. «Ада Лавлейс и история ноты G». Нью-Йоркская медиалаборатория . Проверено 1 июня 2022 г.
12. «Как заметки Ады Лавлейс об аналитической машине создали первую компьютерную программу». Журнал BBC Science Focus . Проверено 1 июня 2022 г.
13. «Чарльз Бэббидж оставил компьютерную программу в Турине в 1840 году. Вот она» . Проводной . ISSN  1059-1028 . Проверено 1 июня 2022 г.
14. «Математическое сокровище: заметки Ады Лавлейс об аналитической машине | Математическая ассоциация Америки». www.maa.org . Проверено 2 июня 2022 г.
15. Лавлейс и Бэббидж и создание «Заметок» 1843 года.
16. Штейн 1984, с. 46.
17. "Ада Лавлейс". Биография . 2 апреля 2014 года . Проверено 2 июня 2022 г.
18. Тул, Бетти Александра (23 сентября 2004 г.). «Байрон, (Огаста) Ада [имя в браке (Аугуста) Ада Кинг, графиня Лавлейс] (1815–1852), математик и пионер компьютеров» . Оксфордский национальный биографический словарь . Том. 1 (онлайн-ред.). Издательство Оксфордского университета. doi : 10.1093/ref: odnb/37253. ISBN 978-0-19-861412-8. (Требуется подписка или членство в публичной библиотеке Великобритании.)
19. "Ада Лавлейс - Биография, факты и изображения" . Проверено 2 июня 2022 г.
20. «Эскиз аналитической машины». www.fourmilab.ch . Проверено 2 июня 2022 г.
21. Вулли 1999.
22. «Празднование Ады Лавлейс». МТИ Пресс. 11 октября 2016 г. Проверено 2 июня 2022 г.
23. "Ада Лавлейс". История . 26 февраля 2021 г. Проверено 2 июня 2022 г.
24. "Записка G Ады Лавлейс | Проект Лавлейс" . Projectlovelace.net . Проверено 1 июня 2022 г.

Источники

• Штейн, Дороти К. (1984). «Заметки леди Лавлейс: технический текст и культурный контекст». Викторианские исследования . 28 (1): 33–67. ISSN  0042-5222. JSTOR  3826758.
• Вулли, Бенджамин (февраль 1999 г.), Невеста науки: романтика, разум и дочь Байрона, Австралия: Пэн Макмиллан, 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.