Нота 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]} Примечание 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 в программе Лавлейс.)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]//Завершить позже

Реализация в псевдокоде подчеркивает тот факт, что компьютерные языки определяют переменные в стеке , что устраняет необходимость отслеживания и указания текущей итерации переменной. Кроме того, программа Лавлейс допускала определение переменных только путем выполнения сложения , вычитания , умножения или деления двух членов, которые ранее были определенными переменными. Современный синтаксис мог бы выполнять каждое вычисление более кратко. Это ограничение становится очевидным в нескольких местах, например, в команде 6 ( ). Здесь Лавлейс определяет до сих пор неопределенную переменную ( ) сама по себе, тем самым предполагая, что все неопределенные переменные автоматически равны 0, тогда как большинство современных языков программирования вернули бы ошибку или перечислили бы переменную как null . Она имела в виду " ", но ограничила себя использованием только переменных в качестве членов. Аналогично, в команде 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. В мемуарах ее инициалы были напечатаны с ошибкой: «ALL» ^[14]
3. Эти переменные технически относятся к столбцам дисков, по предложению Бэббиджа, именно так их следует обозначать. ^[20]

Ссылки

1. Демминг, Анна. "Ада Лавлейс". New Scientist . Получено 01.06.2022 .
2. Крыса, Иоасия. Ада Лавлейс - Никогда не было ноты G.
3. "Ада Лавлейс, первый провидец технологий". The New Yorker . 2013-10-15 . Получено 2022-06-02 .
4. Герц 2009, стр. 59.
5. "Чествование Ады Лавлейс: „первого в мире программиста“ - Short Sharp Science - New Scientist". 2009-03-27. Архивировано из оригинала 2009-03-27 . Получено 2022-06-01 .
6. "Ада Лавлейс | Двигатель Бэббиджа | Музей истории компьютеров". www.computerhistory.org . Получено 01.06.2022 .
7. "Ада Лавлейс | Биография, компьютер и факты". Encyclopedia Britannica . Получено 2022-06-01 .
8. "Ада Лавлейс: Первый программист". Mental Floss . 2015-10-13 . Получено 2022-06-02 .
9. Штейн 1984, стр. 44.
10. «Что на самом деле делала программа Ады Лавлейс?». twobithistory.org . Получено 01.06.2022 .
11. "Ада Лавлейс и история Note G". NYC Media Lab . Получено 2022-06-01 .
12. «Как заметки Ады Лавлейс об аналитической машине создали первую компьютерную программу». Журнал BBC Science Focus . Получено 01.06.2022 .
13. "Чарльз Бэббидж оставил компьютерную программу в Турине в 1840 году. Вот она". Wired . ISSN  1059-1028 . Получено 01.06.2022 .
14. "Математическое сокровище: заметки Ады Лавлейс об аналитической машине". Математическая ассоциация Америки . Архивировано из оригинала 2024-06-30 . Получено 2024-06-30 .
15. Лавлейс и Бэббидж и создание «Заметок» 1843 года
16. Штейн 1984, стр. 46.
17. "Ada Lovelace". Биография . 2 апреля 2014 г. Получено 2022-06-02 .
18. Тул, Бетти Александра (2004-09-23). ​​"Байрон, (Августа) Ада [имя жены (Августа) Ада Кинг, графиня Лавлейс] (1815–1852), математик и пионер компьютеров" . Оксфордский национальный биографический словарь . Том 1 (онлайн-ред.). Oxford University Press. doi :10.1093/ref:odnb/37253. ISBN 978-0-19-861412-8. (Требуется подписка или членство в публичной библиотеке Великобритании.)
19. "Ада Лавлейс - Биография, факты и фотографии" . Получено 2022-06-02 .
20. "Набросок аналитической машины". www.fourmilab.ch . Получено 2022-06-02 .
21. Вулли 1999.
22. "Celebrating Ada Lovelace". MIT Press. 2016-10-11 . Получено 2022-06-02 .
23. "Ада Лавлейс". История . 2021-02-26 . Получено 2022-06-02 .
24. "Ada Lovelace's Note G | Project Lovelace". projectlovelace.net . Получено 01.06.2022 .

Источники

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