Программа по нахождению чисел бернулли на вычислительной машине бэббиджа острая О. В., Гайфулина Д. А., Хакимова Э. Р



Скачать 126.58 Kb.
Дата29.04.2016
Размер126.58 Kb.
АДА ЛАВЛЕЙС И ЕЁ ПРОГРАММА ПО НАХОЖДЕНИЮ ЧИСЕЛ БЕРНУЛЛИ НА ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ БЭББИДЖА
Острая О.В., Гайфулина Д.А., Хакимова Э.Р.

ГОУ ВПО «Оренбургский государственный университет»


Августа Ада Байрон (Лавлейс) известна как математик, с поэтичным псевдонимом «Леди цифр».

Известна она, прежде всего, тем, что составила описание вычислительной машины, разработанной Чарльзом Бэббиджем, и написала для этой машины первую в мире программу. Вследствие этого Ада Лавлейс считается первым программистом в истории человечества [13].

Родилась Ада 10 декабря 1815 года в Лондоне. Она была единственным ребенком в семье поэта Джорджа Гордона Байрона, а свое увлечение математикой девочка переняла у матери – Анны Изабеллы Байрон (Анабеллы), которую называли «Королевой Параллелограммов» [7]. Отец Ады видел ее всего лишь раз в жизни – через месяц после ее рождения, после чего подписал заявление о разводе и навсегда уехал из Англии.

Первое имя – Огаста (Августа) – девочка получила в честь сестры Байрона. Но мать и другие родственники никогда не называли её этим именем, а также постарались ограничить любое влияние отца на судьбу дочери и изъяли все книги Байрона из семейной библиотеки [8].

Анна Изабелла Байрон наняла для дочери лучших учителей и репетиторов. Например, математике Аду обучал Огастес де Морган, известный шотландский математик. Также в числе учителей была его жена Мэри Сомервиль, которая перевела с французского языка «Трактат о небесной механике», написанный Лапласом [7]. Именно Мэри стала для Ады Лавлейс примером для подражания.

Мать Ады, не желая для дочери пути отца, подозревала ее в сочинении стихов, и когда Ада стала вечерами запираться в своей комнате, рассердилась и потребовала отчета от девушки, на что та показала чертежи летательного аппарата собственной конструкции [12].

Когда Аде исполнилось семнадцать лет, она получила возможность выезжать в свет и впервые была представлена королю и королеве. В это же время она впервые услышала имя Чарльза Бэббиджа (1791-1871) – выдающегося английского математика – за обеденным столом от Мэри Сомервилль. Спустя несколько недель, 5 июня 1833 года, они впервые увиделись на научно-технической выставке [7]. В двадцатилетнем возрасте Ада вышла замуж за лорда Кинга, который стал впоследствии графом Лавлейс, поэтому сама Ада Байрон стала знаменитой как графиня Ада Лавлейс.

Чарльз Бэббидж родился в 1791 году в семье банкира. Будучи студентом, он уже начал интересоваться вычислительными методами [9]. В момент знакомства с Адой Чарльз Бэббидж занимал должность профессора кафедры математики Кембриджского университета. С 1822 он работал над постройкой разностной машины, которая была задумана для табулирования, то есть составления вычислительных таблиц [6]. Для вычисления значения функции её необходимо было представить в виде композиции конечного числа функций, а затем производить расчёт значений каждой из этих функций. При этом оператор машины должен был вручную вводить все значения регистров. Чертёж с многочисленными валиками и шестерёнками, которые приводились в движение рычагом, был представлен премьер-министру. В 1823 году была выплачена первая субсидия на постройку так называемого первого компьютера, который сейчас известен под названием «Большая разностная машина Бэббиджа» (Difference Engine) [7]. Однако в 1833 году ее финансирование было прекращено из-за сложности конструкции.

Несмотря на неудачу с разностной машиной, Бэббидж в 1834 году задумался о создании другой машины, которая бы позволяла решать весь класс вычислительных задач. Для этого алгоритм такой машины должен задаваться извне, а не быть «жёстко зашитым» в её конструкцию [6]. Сама же машина должна уметь управлять ходом вычислений. Новую вычислительную машину Бэббидж назвал Аналитической – Analytical Engine [15].

«Шесть месяцев я разрабатывал проект машины более совершенной, чем первая. Я сам поражен вычислительной мощностью, которой она будет обладать!», пишет Чарльз Бэббидж [3].

Основными частями Аналитической машины являлись:


  1. «склад»  устройство для хранения чисел, то есть память в современной терминологии;

  2. «мельница» или «фабрика»  устройства для выполнения арифметических действий (арифметическое устройство);

  3. «контора» – устройство, управляющее операциями машины (устройство управления);

  4. устройства ввода и вывода.

Обмен данными осуществлял набор зубчатых реек. Каждое из колес регистров могло останавливаться в одном из десяти положений и запоминать десятичный знак. Операции умножения и деления в свою очередь представлялись как последовательные сложения или вычитания [15].

Для ввода данных в память и управления работой машины Бэббидж задумал использовать перфокарты, которые впервые начали применяться в ткацких станках Жаккарда в 1808 году. Жозеф Мари Жаккард (1752-1834) – французский изобретатель станка для выработки крупноузорчатых тканей. Этот станок является ярким примером машины с программным управлением [5].

Аналитическая машина выполняла две операции с перфокартами,  одна давала задание для «мельницы», вторая же управляла переносом данных между «мельницей» и «складом». Карты проходили под щупами, которые, при попадании в отверстия, приводили в движение механизмы передачи данных со «склада» на «фабрику». Результат машина возвращала обратно на «склад» [6].

Также в Аналитической машине была предусмотрена возможность организации условий и циклов. Для этого механизм переноса последнего разряда мог заставить цикл повторить действие либо пропустить его [6].

Аналитическая машина была описана в статье Луиджи Фредериго Менабреа (1809-1896). Бэббидж попросил графиню Лавлейс перевести записи Менабреа на английский и сопроводить текст комментариями. Именно эта работа стала причиной появления на свет первой в мире программы и первого программиста.

Сама Ада писала Бэббиджу о своей программе: «Я хочу ввести пример в одно из примечаний: вычисление чисел Бернулли в качестве примера вычисления машиной неопределенной функции без предварительного решения ...» [14].

В 1843 г. Адой Лавлейс для машины Бэббиджа была написана первая в мире достаточно сложная программа вычисления чисел Бернулли. Наряду с этим, Лавлейс популяризировала идеи Бэббиджа и сама проектировала некоторые узлы машины. Графиня Лавлейс помогла Бэббиджу прояснять его собственные идеи и служила источником вдохновения изобретателя, заражая своим энтузиазмом. Но даже ее дара оказалось недостаточно, чтобы решить основную проблему на пути создания аналитической машины. Ее просто невозможно было сконструировать и запустить в работу, ведь она должна была быть не меньше железнодорожного локомотива [11]. Внутри же машина представляла бы собой хаотичное нагромождение деталей, часовых механизмов, приводимых в действие паровым двигателем. Любая нестабильность крошечной детали приводила бы к приумноженным нарушениям в других частях, и тогда вся машина пришла бы в «бешенство».

Аналитическая машина так и не была построена. Ее наследие – это ворох чертежей, а также небольшая часть арифметического устройства и печатающее устройство, собранное сыном Бэббиджа [15].

Несмотря на то, что машина Бэббиджа так и не была сконструирована при жизни Ады, написанная ею программа по вычислению чисел Бернулли по праву считается первой программой, специально реализованной для воспроизведения на вычислительной машине. Обратимся теперь к этой программе и подробнее изложим порядок ее работы на машине Бэббиджа.

Для этого нужно разобраться в таком понятии как «Числа Бернулли», открытые швейцарским математиком и механиком Якобом Бернулли (1759-1789) [3]. Числа Бернулли – это последовательность рациональных чисел полученная путем суммирования последовательных чисел возведенных в одну и ту же степень [4]:



;

;

…………………………….

.

С помощью формулы бинома Ньютона:

,

последовательно возводим двучлен в первую, вторую, третью и т.д. степень; затем напишем тождество:



Предположим, что , сложим почленно получившиеся равенства и получим:

.

Отсюда вытекает рекуррентное соотношение:

.

Так можем получить сумму , если знаем все предыдущие суммы: [2].

Чтобы окончательно разобраться, что же такое числа Бернулли, найдем несколько сумм:

; ; .

Числами Бернулли будут называться коэффициенты, которые стоят перед n в первой степени [2]. Следовательно, из найденных нами сумм последовательностей мы можем сделать вывод, что: .

Чтобы получить саму формулу вычисления чисел Бернулли, воспользуемся найденным рекуррентным соотношением и разделим его на n:

.

При вычислениях чисел Бернулли Ада Лавлейс использует формулу, представленную в виде:



,

(1)

которую также можно записать в общей форме:

, где и т.д. являются функциями n, которые, соответственно, относятся к и т.д. [1].

Каждое слагаемое после -го равно нулю, а -е слагаемое всегда равно . Это позволяет находить значения (числовые или алгебраические) любого n-го числа Бернулли , с учетом знания всех предыдущих.

Для вычисления каждого последующего числа Бернулли необходимо руководствоваться несложной последовательностью вычислений:

1-я серия: Пусть , и вычислить сумму (1) для этого значения. Результат – .

2-я серия: Пусть . Вычислить сумму (1) для этого значения n, подставляя только что полученное значение . В результате – .

3-я серия: Пусть . Вычислить сумму (1) для этого значения n, подставляя полученные значения , . В результате . И так далее, до некоторой степени.

К Заметкам Ады прилагаются диаграммы и таблицы, содержащие данные для вычисления (,, являются предположительно заданными). Рассмотрим подробнее одну из этих схем, которая демонстрирует вычисление (в данном случае ) [1].

Рисунок 1. – Схема вычисления чисел Бернулли на вычислительной машине Бэббиджа.


В этом случае в качестве исходных необходимо взять шесть численных данных – 1, 2, , , , . Для потребуется дополнительная величина , для и т.д. Таким образом, фактическое количество необходимых данных всегда будет , причем данных являются последовательными числами Бернулли.

Карты Операций 1, 2, 3, 4, 5, 6 подготовят . Карта 1 умножает два на n, и три карты Переменных, получающих результат, (обозначаются , , ) дают результат 2n. При Операции 6, положительная величина превращается в отрицательную величину путем простого вычитания величины из столбца, содержащего только нули.

Если мы будем рассчитывать для , в операции 6 будет завершено вычисление , и потом либо вовсе остановится, либо начнет операции 1–7 заново для значения , для того, чтобы ввести вычисление .

Карты 8, 9, 10 производят вычисление .

Карта 12 выполняет ту же роль, что и Карта 7 в предыдущем разделе; и, если бы n было равно двум, Операция 11 завершила бы вычисление .

Карты 13-20 считают . Поскольку всегда состоит из -ого коэффициента. имеет три коэффициента: Карты 13-16 высчитывают второй из этих коэффициентов, а затем умножают его на первый; Карты 17-20 вычисляют третий коэффициент, а затем умножают на произведение двух предыдущих коэффициентов [1].

Карта 23 имеет роль Карт 7 и 12, так как, если n было бы равно 3, 21-ая и 22-я операции завершили бы вычисление . В нашем случае с , вычисление будет продолжаться еще один этап, и теперь мы должны обратить внимание на то, что для того, чтобы вычислить надо просто точно повторить группы Операций с 13 до 20; а затем, чтобы завершить вычисление , повторить Операции 21 и 22.

Таким образом, каждая единица, прибавляющаяся к n в , влечет за собой дополнительные повторения Операций 13-23 для вычисления .

Остается только передать значения на и , уменьшить , , до нуля, и добавить один к , чтобы двигатель был готов начать вычисления . Эти действия выполняют Операции 24 и 25 [1].

Следует отметить, что, когда группа 13-23 повторяется, происходят изменения в некоторых верхних индексах в ходе повторения: например, станет и .

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

Таким образом, мы видим, что, когда , используются девять карт Операций; – четырнадцать; при – двадцать пять. Этих двадцати пяти карт достаточно для последовательного вычисления всех чисел от до включительно. В среднем необходимо еще три дополнительных карты каждой Операции для оценки. В соответствии с этим, расчет потребует двадцать семь карт Переменных; – сорок две таких карты; – семьдесят пять карт; и за каждые последующие после – тридцать три дополнительных карт Переменных (поскольку после каждого повторения группы 13-23 добавляется одиннадцать – число операций, необходимых для вычисления предыдущей В).

Те же семьдесят пять карт Переменных могут повторяться для вычисления каждого последующего числа, по тому же принципу как повторение тридцати трех карт Переменных Операций 13-23 в расчете любого одного Числа. Таким образом, существует цикл в цикле карт Переменных [1].

Можно выразить операций для вычисления чисел Бернулли следующим образом:

(1…7), (24, 25) …………………….......…. дает = 1-ое значение; ().

(1…7), (8…12), (24, 25) …………………….... = 2-ое значение; ().

(1…7), (8…12), (13…23), (24, 25) ……...…...... = 3-е значение; ().

(1…7), (8…12), 2(13…23), (24, 25) ………........ = 4-е значение; ().

…………………………………………………………………………………

(1…7), (8…12), (13…23), (24, 25) = n-ое значение;().

Идеи графини Лавлейс удалось реализовать только с наступлением эры вычислительной техники. Ада скончалась от рака 27 ноября 1852 года и была похоронена в фамильном склепе Байронов, рядом со своим отцом, которого не видела никогда в жизни [7].

В наше время многие разработки Лавлейс и Бэббиджа пытались проверить на современном уровне. Так в 1991 году английские ученые по чертежам Чарльза Бэббиджа построили механическую вычислительную машину. Работает эта машина очень медленно, по сравнению с современными компьютерами: одна операция умножения или деления занимает 2-3 минуты. А в 1978 году в Дубне в вычислительную машину БЭСМ-6 была введена программа Ады Лавлейс, закодированная на языке программирования «Фортан». При проверке работоспособности была найдена всего одна опечатка и одна ошибка, но программа требовала меньшего количество перфокарт, тем самым экономя память.

В 1975 году Министерством обороны США была предложена идея о создании универсального языка программирования. Проект был одобрен и данный язык назвали в честь графини Лавлейс – язык «Ада» [7]. Синтаксис языка «Ада» 1983 года был похож на синтаксис таких современных языков программирования, как Паскаль или Algol, но в 1995 году в него были добавлены элементы объектно-ориентированного программирования. В настоящее время этот язык используется для больших и сложных проектов, не только военного плана.

В честь Ады Лавлейс отмечается два праздника: день 7 октября так и называется днем Ады Лавлейс, и проводится в целях популяризации научной деятельности женщин [10]. В этот день люди всего мира рассказывают о наиболее замечательных научных открытиях, сделанных женщинами. Существует также неофициальный праздник «День программиста», который отмечается несколько раз в году, отмечаются и две даты, связанные с именем Ады Лавлейс: это 10 декабря – день её рождения и 17 октября – день, когда она написала свою первую программу для вычислительной машины.



Ада высказала одну из идей, которая дала направление развитию вычислительной техники в целом: «Суть и предназначение машины зависят от того, какую информацию мы в нее вложим. Машина сможет писать музыку, рисовать картины и покажет науке такие пути, которые мы никогда и нигде не видели» [14]. Этим утверждением она подтолкнула развитие вычислительной техники в новых направлениях. Ада Лавлейс одна из первых предположила, что машины можно использовать не только для вычислений, но и для решения других задач.
Список использованной литературы:

  1. Menabrea, L.F., Lovelace, A.A. Sketch of The Analitycal Engine Invented by Charles Babbage / L.F Menabrea, A.A. Lovelace– Bibliothèque Universelle de Genève. – october, 1842. – № 82.

  2. Абрамович, В.С. Числа Бернулли [Текст] / В.С. Абрамович // журнал «Квант» – 1974. – № 6. – C. 10-14.

  3. Белл, Э.Т. Творцы математики. Предшественники современной математики [Текст] / Э.Т. Белл [и др.] // Творцы математики: пособие для учителей. – М., 1979. 256 c.

  4. Брокгауз, Ф.А. Энциклопедический словарь Брокгауза и Ефрона. Жаккард, Жозеф-Мари [Текст] [в 86 т.] Т.1А / под ред. Ф.А. Брокгауза, И.А. Ефрона – СПб.: Питер, 1891.

  5. Брокгауз, Ф.А. Энциклопедический словарь Брокгауза и Ефрона. Бернуллиевы числа [Текст] [в 86 т.] Т.3 / под ред. Ф.А. Брокгауза, И.А. Ефрона – СПб.: Питер, 1894.
  6. Гутер, Р.С. От абака до компьютера [Текст] / Р.С. Гутер, Полунов Ю.Л. – М.: Знание, 1981. 137 с.


  7. Казак, В.М. Великие женщины-математики [Электронный ресурс] / Социальная сеть работников образования nsportal.ru – Электрон, дан. 2012. – С. 6-7. – Режим доступа: http://nsportal.ru/shkola/algebra/library/2012/03/10/velikie-zhenshchiny-matematiki

  8. Кувшинова, М.Ю. Алгебра и гармония Ады Байрон [Текст] / М.Ю. Кувшинова // журнал «Ах...» – 2000. – № 7.

  9. Коростелева, М.В. История развития вычислительной техники. Чарльз Бэббидж [Электронный ресурс] / История развития вычислительной техники – Электрон, дан. – 2008. – Режим доступа: http://istrasvvt.narod.ru/mex_bebbidg.htm

  10. Лебешева, М.А. Язык Ады Байрон [Электронный ресурс] / Ежеквартальный журнал для педагогов, психологов и родителей «Дети в информационном обществе» – Электрон, дан. – 2012. – Режим доступа: http://detionline.com/assets/files/journal/10/imena_10.pdf

  11. Майстров, Л.Е. Ч. Бэббедж и его разностная машина / Л.Е. Майстров, И.С. Эдлин // Наука и техника: (Вопросы истории и теории).  Л.:1973. – № 8. – с.33-36.

  12. Рогоза, В.А. Графиня Лавлейс  дьявол или ангел? Судьба дочери лорда Байрона [Электронный ресурс] / Ежедневный познавательный журнал «Школа жизни.ру» – Электрон, дан. – 2009. – Режим доступа: http://shkolazhizni.ru/archive/0/n-32669/

  13. Смолянский, А.Д. Лавлейс Ада (урождённая Байрон) [Текст]: энцикл. слов. Британика / под ред. А.Д. Смолянского – М.: 1994.

  14. Травников, Ю.А. Ада Лавлейс: Полет на крыльях математики [Электронный ресурс] / Библиофонд. Электронная библиотека. – Электрон, дан. – 2002. – Режим доступа: http://bibliofond.ru/view.aspx?id=445204

  15. Черняк, Л.А. Чарльз Бэббидж – изобретатель и... политэконом [Текст] / Л.А. Черняк // «Computerworld Россия». – 2001. – №17.


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница