اولین الگوریتم رایانه جهان

نویسنده (ها): باوش آگون

در ابتدا منتشر شده در به سمت هوش مصنوعیبشر

در دنیایی که هنوز هیچ رایانه ای وجود نداشته است ، ADA Lovelace اولین الگوریتم جهان را نوشت.

اولین نگاه اجمالی برنامه نویسی و پیچیدگی در دهه 1800

موتور تحلیلی الگوهای جبر را دقیقاً همانطور که ژاکارد لوم گلها و برگهای خود را بافته می کند. “
– Ada Lovelace ، 1843

وقتی به رایانه ها و الگوریتم ها فکر می کنیم ، تراشه های سیلیکون و اسکریپت های پایتون را می بینیم. اما نزدیک به 200 سال به عقب برگردید ، و داستان باورنکردنی Ada Lovelace را کشف خواهید کرد – شخص بینایی که دنیایی را تصور می کرد که ماشین ها می توانند هر چیزی را با استفاده از آن محاسبه کنند منطق ، حلقه ها و حافظه.

در سال 1843 ، ADA آنچه را که به طور گسترده مورد توجه قرار می گیرد ، ایجاد کرد اولین الگوریتم رایانه: یک مجموعه دستورالعمل های محاسبه برنولی اعداد با استفاده از رایانه مکانیکی فرضی چارلز باباژ – موتور تحلیلی.

در این وبلاگ ، ما الگوریتم او را به صورت مرحله به مرحله تجزیه می کنیم ، ریاضیات آن را کشف می کنیم ، جریان آن را می فهمیم و پیچیدگی محاسباتی آن را تجزیه و تحلیل می کنیم – همه در حالی که قدردانی می کنیم که واقعاً از زمان خود واقعاً بود.

اعداد برنولی چیست؟

برنولی شماره دنباله ای از اعداد منطقی مهم در تئوری تعداد ، حساب و تجزیه و تحلیل عددی است.

اعداد برنولی اعداد منطقی هستند که توسط عملکرد تولید تعریف می شوند:

آنها در فرمول هایی مانند:

• حساب (گسترش تیلور)
• مبالغ قدرتها (فرمول فالابر)
• روشهای عددی (فرمول اویلر-ماکلاورین)

ماهیت بازگشتی آنها باعث می شود کاندیدای کاملی برای نشان دادن قدرت الگوریتم – و این همان کاری است که آدا انجام داد.

Lovelace با استفاده از یک دوره بازگشت از ارزش ، روی اعداد عجیب و غریب متمرکز شده است:

خواص مهم:
1. همه دارای شاخص عجیب و غریب اعداد برنولی فراتر از B1 در تعریف مدرن صفر هستند.

2. Ada Lovelace از یک نسخه جایگزین استفاده کرد: B1 = -1/2 و محاسبه شده دارای شاخص عجیب و غریب مقادیری مانند B3 ، B5 ، B7 ،…

الگوریتم ADA Lovelace – ایده اصلی

Lovelace فقط نتایج دولت را نداشت – او نوشت یک روش رویه ای، با استفاده از آنچه اکنون می خواهیم به عنوان:

• عملیات حسابی
• حلقه
• دسترسی به حافظه نمایه شده
• پرش های مشروط

الگوریتم بازگشتی ADA:

ADA روی محاسبات متمرکز شده است اعداد برنولی با شاخص عجیب و غریب با استفاده از یک فرمول بازگشتی (از یادداشت G از ترجمه او):

چگونه کار می کند:

• اعداد آینده به اعداد برنولی که قبلاً محاسبه شده اند بستگی دارد.

هر اصطلاح در جمع توسط:

• ضریب دوتایی
• مخرج عادی سازی 2n – 2K+1

ADA با B1 = – 1/2 شروع می شود.

مثال: محاسبه B7:

برای محاسبه B7 ، ما استفاده می کنیم:

2n+1 = 7 ⇒ n = 3؛

مقادیر شناخته شده:

از جدول خود ADA (توجه داشته باشید G) ، شماره های برنولی که او استفاده می کرد عبارتند از:

• B1 = −1/2
• B3 = 1/6
• B5 = −1/30

اکنون فرمول را اعمال کنید:

هر اصطلاح را ساده کنید:

توضیح مهم:

تصحیح: مقدار واقعی B7IS 1/42. محاسبه اصلی Lovelace حاوی خطای جزئی (احتمالاً به دلیل رونویسی) بود ، اما روش او سالم بود.

این نتیجه با ارزش مدرن، کجا: B7 = 0.

در تفاوت از تعریف اعداد برنولی ناشی می شود در زمان آدا او استفاده کرد دنباله برنولی عجیب و غریب غیر صفر بر اساس ظاهر آنها در فرمول های جمع برق و نه عملکرد تولید.

تجزیه و تحلیل پیچیدگی

پیچیدگی زمان:

فرمول بازگشتی است:

• حلقه بیرونی اجرا می شود حرف بار
• جمع داخلی تا حرف عناصر
• هر اصطلاح: حسابی زمان ثابت

پیچیدگی فضایی:

فقط فروشگاه ها حرف شماره های قبلی برنولی:

نمای مدرن از اعداد برنولی

در ریاضیات مدرن:

1. B1 = -1/2

2. همه اعداد برنولی با شاخص عجیب و غریب B {2n+1} ، برای N≥1 0 است:

پیاده سازی های مدرن استفاده می کنند:

• تولید توابع
• فرمول فالابر
• روشهای مبتنی بر FFT (مانند الگوریتم هاروی)

سهم آدا لایولاس در الگوریتم ها

ADA Lovelace در توسعه یک هدف عمومی خلاق ترین بود ، الگوریتم بازگشتی – شاید اولین مورد تاکنون نوشته شده با هدف دویدن روی یک دستگاه.

محاسبه او از اعداد برنولی نه تنها به جریان کنترل ساختاری اضافه شده ، به عنوان مثال حلقه ها ، حلقه های تو در تو و متغیرهای فهرست بندی شده ، اما همچنین به مدیریت حافظه پرداخته اند در محدودیت موتور تحلیلی.

او الگوریتم را برای اجرای نمادین ، ​​با فرمول های ریاضی که با آن تکامل می یابد ، انجام داد هر تکرار، تجسم مفهوم مدرن از برنامه نویسی و انتزاع.

الگوریتم ADA حسابی سخت نبود -این یک وسیله کلی برای محاسبه هر شماره برنولی با مرتبه بالاتر ، با جنبه های مشهود مدولار بودن ، قابلیت استفاده مجدد و بازگشت بود. کار او سالها قبل از وجود رایانه های دیجیتال ، او را به عنوان بنیادی در اندیشه الگوریتمی قرار می دهد.

پایان

الگوریتم Ada Lovelace فقط یک تمرین ریاضی نبود – بلکه اختراع برنامه نویسی بود. او با استفاده از منطق نمادین ، ​​بازگشت و یک روش رسمی تکرار ، او اولین الگوریتم قابل اجرا در ماشین را دهه ها قبل از اختراع رایانه توصیف کرد. اگرچه برخی از اعداد موجود در جدول شماره Bernoulli با مواردی که اکنون پذیرفته شده است متفاوت است ، اما خود الگوریتم او از نظر ریاضی صحیح و پیش از زمان خود بود.

عدم تطابق جزئی جدول بندی شده وی نتیجه تغییر کنوانسیون های نماد ریاضی است ، نه اشتباه در استدلال وی. کار او در واقع مفاهیم برنامه نویسی اساسی را معرفی کرد: حلقه ها ، شرط ها ، مدیریت حافظه و انتزاع.

مهمتر از همه ، Lovelace دورانی را پیش بینی می کرد که در آن رایانه ها می توانند برنامه ریزی شوند تا نه تنها اعداد ، بلکه ایده ها و نمادها را نیز اداره کنند. این پیش بینی ، که با سبک تفکر الگوریتمی دقیق خود ازدواج کرده است ، به همین دلیل است که او واقعاً سزاوار مونیکر به عنوان اولین برنامه نویس جهان است. برنامه شماره برنولی او صرفاً یک شروع کننده بود – این آغاز عصر دستگاه های قابل برنامه ریزی و به همراه آنها دنیای دیجیتال بود.

برخی از افزونه ها:
1. موتور تحلیلی هرگز ساخته نشده است

2. یادداشت های آدا http://www.fourmilab.ch/babbage/sketch.htmlبشر

لطفاً در بخش نظرات نظرات خود را به اشتراک بگذارید. پیشنهادات شما همیشه مورد استقبال قرار می گیرد.

منتشر شده از طریق به سمت هوش مصنوعی