دليل دراسي · نحو 12 دقيقة قراءة

الخوارزميات

الخوارزمية وصفة دقيقة لحل مسألة. والخوارزمية الجيدة قد تحوّل مئة خطوة إلى سبع. اختر رقمًا سريًا وشاهد البحث الثنائي يجده بتنصيف المدى في كل مرة.

البحث الثنائي · من 1 إلى 100
1100
المدى 1-100. التخمين الأول: المنتصف.
لا أكثر من 7 تخمينات لـ100 رقم.

ما الخوارزمية، باختصار

الخوارزمية سلسلة محدودة وواضحة من الخطوات تحوّل مُدخلًا إلى مُخرج، كقائمة إلى قائمة مرتبة أو مكانين إلى أقصر طريق بينهما. ودراسة الخوارزميات تعني تصميم هذه الخطوات وقياس كيف تنمو كلفتها مع كبر المُدخل.

الكلمة مأخوذة من الخوارزمي، عالم الرياضيات الفارسي في بغداد في القرن التاسع، الذي صار اسمه المُلتَن «Algoritmi» يعني الحساب بالأرقام الهندية العربية.

يجب أن تكون
محدودة ودقيقة وفعّالة، بمُدخل ومُخرج واضحين
تُقاس بـ
الزمن والذاكرة مع نمو المُدخل (تدوين O الكبير)
الأقدم المعروفة
طريقة إقليدس للقاسم المشترك الأكبر، نحو 300 ق.م.
ليست هي نفسها
البرنامج، الذي هو تطبيق واحد لها
مفهوم أساسي

القائمة نفسها، ثلاث طرق لترتيبها

الترتيب هو مسألة الخوارزميات الكلاسيكية. اختر طريقة وشغّلها. راقب العدّادات: الاستراتيجيات المختلفة تبذل مقادير عمل مختلفة جدًا على الأرقام العشرة نفسها.

62941017385
عشرة أرقام غير مرتبة. اضغط تشغيل أو تقدّم خطوة خطوة.
0مقارنات
0تبديلات
ترتيب الفقاعاتقارن الجيران مرارًا وبدّلهم إن كانوا في غير ترتيبهم. تطفو الأرقام الكبيرة إلى النهاية كالفقاعات.O(n²): بسيط لكنه بطيء
مقارنةفي مكانه النهائيينتظر
تدوين O الكبير

لماذا يهم النمو أكثر من السرعة

يصف تدوين O الكبير كيف ينمو عدد الخطوات مع حجم المُدخل n. ارفع n وشاهد كم ستستغرق كل نوع من الخوارزميات على حاسوب ينفّذ مليار خطوة في الثانية.

O(1)الوصول إلى مصفوفة1 ns
O(log n)البحث الثنائي6 ns
O(n)البحث الخطي86 ns
O(n log n)الترتيب بالدمج553 ns
O(n²)ترتيب الفقاعات7.4 µs
O(2ⁿ)المجموعات الجزئية بالقوة الغاشمة10^9 years
تستخدم الأشرطة مقياسًا لوغاريتميًا؛ وإلا لما ظهر إلا الأخير. وتفترض الأزمنة n وn² وغيرها من الخطوات بالضبط عند 10⁹ خطوة في الثانية.
نماذج التصميم

خمس استراتيجيات وراء معظم الخوارزميات

الاستراتيجيةالفكرةتقابلها في
فرّق تسدقسّم المسألة نصفين، وحل كلًّا منهما، واجمع الإجابات.الترتيب بالدمج، البحث الثنائي، الضرب السريع
الجشعاختر الخيار الأفضل ظاهريًا في كل خطوة ولا تنظر إلى الوراء. سريع، لكنه ليس الأمثل دائمًا.إعطاء الباقي بالعملات، أقصر طرق ديكسترا
البرمجة الديناميكيةقسّم المسألة إلى مسائل فرعية متداخلة واحفظ كل إجابة كي تُحسب مرة واحدة.مسافة التحرير في التدقيق الإملائي، تخطيط المسارات، محاذاة DNA
البحث في المخططاتاستكشف الروابط بشكل منهجي، بالعرض أولًا أو بالعمق أولًا.الخرائط، الشبكات الاجتماعية، حل المتاهات والألغاز
القوة الغاشمةجرّب كل الاحتمالات. مضمونة النجاح، وغالبًا بطيئة جدًا.كسر كلمات المرور القصيرة، الألغاز الصغيرة، اختبار خوارزميات أخرى

أقدم من الحواسيب

كانت الخوارزميات تُكتب على الطين والبردي قبل ألفي عام من بناء أي آلة لتنفيذها.

نحو 1600 ق.م.الألواح البابليةإجراءات خطوة بخطوة للقسمة والجذور التربيعية، مضغوطة في الطين.
نحو 300 ق.م.خوارزمية إقليدستجد القاسم المشترك الأكبر لعددين. ولا تزال تُستخدم في التشفير اليوم.
c. 820Al-Khwārizmīأعطتنا كتبه عن الحساب الهندي العربي كلمة «خوارزمية».
1959الترتيب السريع (Quicksort)طريقة توني هور في الترتيب، ولا تزال من الأسرع عمليًا.
1977RSAجعل تشفير المفتاح العام لريفست وشامير وأدلمان المدفوعات الآمنة عبر الإنترنت ممكنة.
1998PageRankرتّب لاري بيج وسيرغي برين صفحات الويب بحسب الروابط المشيرة إليها.

قراءات إضافية

Introduction to Algorithms· Cormen, Leiserson, Rivest & Stein1990
The Art of Computer Programming· Donald Knuth1968-
Grokking Algorithms· Aditya Bhargava2016
Algorithms to Live By· Brian Christian & Tom Griffiths2016

التفكير الخوارزمي تفكير منطقي. قِس تفكيرك.

يغطي اختبار الذكاء الكامل لدينا الاستدلال المنطقي والعددي واللفظي والمكاني: 60 سؤالًا، نحو 30 دقيقة.

خذ اختبار الذكاء الكامل