جنرال لواء

15 من أهم الخوارزميات التي ساعدت في تعريف الرياضيات والحوسبة والفيزياء


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

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

هؤلاء 15 من المرشحين الأكثر احتمالا.

ذات صلة: كيف تدير الخوارزميات العالم الذي نعيش فيه

تاريخ موجز للخوارزميات

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

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

استخدم المفكرون اليونانيون القدماء مثل إقليدس وأرخميدس وإراتوستينس الخوارزميات المبكرة للقيام بأشياء مثل تحديد القاسم المشترك الأكبر لأرقام مختلفة وتقريب Pi وحساب الأعداد الأولية.

بمرور الوقت ، ستؤدي مثل هذه الأعمال الفذة إلى ظهور رموز وقواعد تشارك في صياغة أنظمة التقييم.

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

لقبه ، اللاتينية كما الخوارزمية سيصبح مرادفًا للتعليمات الخاصة بإجراء العمليات الحسابية لتنفيذ المهام.

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

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

لكن الخوارزميات ستحصل على ترقية كبيرة مع عمل Emil Post و Alan Turing في الثلاثينيات من القرن الماضي ، مما سيؤدي في النهاية إلى ظهور الكمبيوتر الحديث. لا شيء سيكون كما هو مرة أخرى.

ما هي بعض أهم الخوارزميات؟

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

قائمة الخوارزميات التالية ليست شاملة وليست بترتيب معين.

1. الخوارزميات البابلية هي الأقدم على الإطلاق

المنشئ: مجهول

عندما تم إنشاؤه: حوالي 1600 قبل الميلاد

تأثيرها / انعكاساتها على العالم: أول خوارزمية معروفة في العالم

على الرغم من وجود بعض الأدلة على خوارزميات الضرب المبكرة في مصر (حوالي 2000-1700 قبل الميلاد) ، تم قبول أقدم خوارزمية مكتوبة على نطاق واسع على مجموعة من الألواح الطينية البابلية التي يعود تاريخها إلى ما يقرب من 1800-1600 ق.

ظهرت أهميتها الحقيقية فقط 1972، عندما نشر عالم الكمبيوتر وعالم الرياضيات دونالد إي. كنوث الترجمات الإنجليزية الأولى للعديد من الألواح الرياضية المسمارية.

فيما يلي بعض المقتطفات من كتابه 1972 مخطوطة تشرح هذه الخوارزميات المبكرة: -

"الحسابات الموصوفة في الأجهزة اللوحية البابلية ليست مجرد حلول لمشاكل فردية محددة ؛ إنها في الواقع إجراءات عامة لحل فئة كاملة من المشاكل." - الصفحات 672 إلى 673 من "الخوارزميات البابلية القديمة".

يبدو أيضًا أن الأجهزة اللوحية كانت شكلاً مبكرًا من دليل التعليمات: -

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

2. لا تزال خوارزمية إقليدس قيد الاستخدام حتى اليوم

المنشئ: إقليدس

عندما تم إنشاؤه: 300 ق

تأثيرها / انعكاساتها على العالم: تعد خوارزمية إقليدس واحدة من أقدم الخوارزميات التي تم إنشاؤها على الإطلاق ، ومع بعض التعديلات ، لا تزال أجهزة الكمبيوتر تستخدمها اليوم.

الخوارزمية الإقليدية هي إجراء يستخدم لإيجاد القاسم المشترك الأكبر (GCD) لعددين صحيحين موجبين. تم وصفه لأول مرة من قبل إقليدس في مخطوطته عناصر مكتوب حولها 300 ق.

إنها عملية حسابية فعالة للغاية لا تزال تستخدم حتى اليوم بواسطة أجهزة الكمبيوتر بشكل أو بآخر.

تتطلب خوارزمية إقليدس القسمة المتتالية وحساب الباقي حتى الوصول إلى النتيجة. من الأفضل وصفه باستخدام مثال:

ما هو GCD من 56 و 12؟

الخطوة 1 - قسّم الأكبر على الرقم الأصغر: -

56/12 = 4 (الباقي 8)

الخطوة 2 - قسّم المقسوم عليه على باقي الخطوة السابقة: -

12/8 = 1 (الباقي 4)

الخطوة 3 - تابع الخطوة 2 حتى لا يتبقى أي باقٍ (في هذه الحالة تكون عملية بسيطة من 3 خطوات): -

8/4 = 2 (لا يوجد باق)

في هذه الحالة ، يكون GCD هو 4.

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

3. إن غربال إراتوستينس هو خوارزمية قديمة وبسيطة

المنشئ: إراتوستينس

عندما تم إنشاؤه: 200 ق

تأثيرها / انعكاساتها على العالم: يعتبر غربال إراتوستينس أحد أقدم الخوارزميات على الإطلاق. يسمح لك بالعثور على جميع الأعداد الأولية في جدول بأرقام معينة (بقدر ما تريد تضمينه).

لإجراء ذلك ، يمكنك العثور على جميع الأرقام الأكبر من 2 ، ثم شطب الأرقام القابلة للقسمة على 2. ثم تفعل الشيء نفسه للأرقام غير المشطوبة التي تزيد عن 3 ، وهكذا دواليك لا نهاية حتى يتم شطب جميع الأرقام المركبة (غير الأولية).

4. كان الجبر المنطقي (الثنائي) أساس عصر المعلومات

المنشئ: جورج بول

عندما تم إنشاؤه: 1847

تأثيرها / انعكاساتها على العالم: تُعرف هذه الخوارزمية على نطاق واسع بأنها أساس ترميز الكمبيوتر الحديث. لا يزال قيد الاستخدام اليوم ، خاصة في دوائر الكمبيوتر.

قد تكون على دراية بمصطلح Boolean من الرياضيات والمنطق وترميز الكمبيوتر.

الجبر البولي هو فرع من فروع الجبر حيث لا يمكن أن يكون المتغير صحيحًا أو خاطئًا - ما يسمى بقيم الحقيقة (عادةً ما يكون ثنائيًا 1 أو 0). تم اختراعه لأول مرة بواسطة جورج بول في كتابه 1845 عمل تحقيق في قوانين الفكر.

يُنسب إلى الجبر البوليني على نطاق واسع باعتباره الأساس لعصر المعلومات.

5. كانت خوارزمية Ada Lovelace هي أول برنامج كمبيوتر

المنشئ: آدا لوفليس

عندما تم إنشاؤه: 1842

تأثيرها / انعكاساتها على العالم: يتم التعرف على هذه الخوارزمية على نطاق واسع كأول برنامج كمبيوتر.

أمضت آدا لوفليس الجزء الأكبر من العام في ترجمة إحدى محاضرات تشارلز باباج (التي نقلها مهندس إيطالي إلى الفرنسية) إلى الإنجليزية. خلال هذه العملية ، أضافت بإخلاص ملاحظات توضيحية إضافية خاصة بها.

تم تصنيف ملاحظاتها A - G ، مع وصف الأخير خوارزمية لـ "محرك تحليلي" لحساب أرقام برنولي. أصبحت Note G مقبولة الآن على نطاق واسع باعتبارها أول مثال مسجل لرمز الكمبيوتر - مما يجعلها أول مبرمجة كمبيوتر على الإطلاق.

لم يتم بناء المحرك أبدًا ، وبالتالي ، لم يتم اختبار خوارزميتها مطلقًا خلال حياتها. أعيد اكتشاف عملها في 1953 عندما أعيد نشر ملاحظاتها.

6. تحويل فورييه السريع يكسر الإشارات إلى الترددات

المنشئ: كارل جاوس وجوزيف فورييه وجيمس كولي وجون توكي

عندما تم إنشاؤه: 1802, 1822, 1965

تأثيرها / انعكاساتها على العالم: تُستخدم هذه الخوارزمية لتقسيم الإشارة إلى الترددات التي تتكون منها - مثل الكثير من الوتر الموسيقي الذي يمكن التعبير عنه في الترددات ، أو النغمات ، لكل نغمة فيها.

يمكن لخوارزمية تحويل فورييه السريع (FTT) تتبع أصولها إلى كارل جاوس ، الذي أنشأها لأول مرة لحساب مسارات الكويكبات. تم توسيع الصيغة لاحقًا بواسطة جوزيف فورييه في 1822.

ولكن الشكل الأكثر حداثة واستخدامًا للخوارزمية تم إنشاؤه ونشره بواسطة James Cooley و John Tukey في 1965. هذا الإصدار هو الخوارزمية الأكثر شمولاً في الرياضيات التطبيقية ، وقد أحدث ثورة في معالجة الإشارات.

"يعتمد FFT على استراتيجية فرق تسد لتقليل الأعمال الروتينية ظاهريًا O (N2) إلى O (N log N) مرح. ولكن على عكس Quicksort ، فإن التنفيذ (للوهلة الأولى) غير بديهي وأقل من مباشر. هذا في أعطى علم الكمبيوتر دفعة للتحقيق في التعقيد المتأصل في المشاكل الحسابية والخوارزميات. " - باري إيه سيبرا.

7. يمكن أن تكون خوارزمية ترتيب Google (PageRank) هي الخوارزمية الأكثر استخدامًا

المنشئ: لاري بيدج (بشكل رئيسي) وسيرجي برين

عندما تم إنشاؤه: 1996

تأثيرها / انعكاساتها على العالم: يمكن القول إن نظام ترتيب الصفحات هو الخوارزمية الأكثر استخدامًا في العالم اليوم. إنه ، بالطبع ، أساس ترتيب الصفحات على محرك بحث Google.

ومن المثير للاهتمام أن PageRank سميت باسم Larry Page بدلاً من أن تعني حرفياً "o ترتيب صفحات الويب". إنها ليست الخوارزمية الوحيدة التي تستخدمها Google في الوقت الحاضر لترتيب الصفحات في نتائج البحث الخاصة بها ، ولكنها الأقدم والأكثر شهرة.

تم تصميم PageRank بواسطة Larry Page و Sergey Brin أثناء دراستهما في جامعة ستانفورد كجزء من مشروعهما البحثي حول نوع جديد من محركات البحث.

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

تعطى خوارزمية PageRank بالصيغة التالية:

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))

أين:

  • PR (A) هو ترتيب الصفحات للصفحة A ،
  • PR (Ti) هو تصنيف الصفحات Ti الذي يرتبط بالصفحة A ،
  • C (Ti) هو عدد الروابط الصادرة على الصفحة Ti و ؛
  • d هو عامل التخميد الذي يمكن ضبطه بين 0 و 1.

يمكننا أن نرى أن هذه الخوارزمية لا تصنف مواقع الويب ككل ولكنها ترتب كل صفحة على حدة. يمكن أيضًا تشبيهه بـ "مخطط هرمي يتم فيه ترتيب صفحة معينة بشكل متكرر اعتمادًا على ما ترتبط به الصفحات الأخرى.

لقد فقد نظام ترتيب الصفحات PageRank في السنوات الأخيرة ولكنه لا يزال يستخدم كجزء من مجموعة عامة من الخوارزميات الأخرى في Google.

8. تم استخدام طريقة مونت كارلو (خوارزمية متروبوليس) في لوس ألاموس

المنشئ: جون فون نيومان وستان أولام ونيك متروبوليس

عندما تم إنشاؤه: 1946

تأثيرها / انعكاساتها على العالم: تم استخدامه ككلمة رمز لوس ألاموس لعمليات المحاكاة العشوائية المطبقة لبناء قنابل ذرية أفضل بعد الحرب العالمية الثانية.

يتم تعريف طريقة مونت كارلو على النحو التالي: "مونت كارلو هو فن تقريب توقع بواسطة متوسط ​​العينة لدالة متغيرات عشوائية محاكية."

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

تُستخدم الخوارزمية على نطاق واسع في المشكلات الفيزيائية والرياضية وتكون أكثر فائدة عندما يكون من الصعب أو المستحيل استخدام أساليب أخرى.

تُستخدم طرق مونت كارلو بشكل أساسي في ثلاث فئات مشكلة: التحسين والتكامل العددي وتوليد السحب من توزيع الاحتمالية.

9. الطريقة البسيطة للبرمجة الخطية تم تبنيها على نطاق واسع من قبل الصناعة

المنشئ: جورج دانتزيغ

عندما تم إنشاؤه: 1947

تأثيرها / انعكاساتها على العالم: تعد طريقة simplex للبرمجة الخطية واحدة من أنجح الخوارزميات على الإطلاق. تم استخدامه على نطاق واسع في عالم الصناعة أو أي حالة أخرى يعتمد فيها البقاء الاقتصادي على القدرة على زيادة الكفاءة إلى أقصى حد ضمن الميزانية و / أو قيود أخرى.

ابتكرها جورج دانتزيغ في عام 1947 ، أصبحت هذه الخوارزمية واحدة من أكثر الخوارزمية انتشارًا في التاريخ ، على الرغم من حقيقة أن معظم مشاكل العالم الحقيقي نادرًا ما تكون خطية بطبيعتها.

ومع ذلك ، فإنه يوفر طريقة بسيطة وأنيقة لاشتقاق حلول للمشكلات. لاحظ البعض أنه يمكن أن يتأثر بالتأخيرات المتسارعة ولكنه ذو كفاءة عالية - عادة ما يستغرق 2م (أين م هو عدد قيود المساواة) حتى 3م التكرارات لإكمال.

إنه يعمل عن طريق استخدام استراتيجية منهجية لإنشاء حلول قمة الرأس المرشحة والتحقق منها داخل برنامج خطي. في كل تكرار ، تختار الخوارزمية المتغير الذي يقوم بإجراء أكبر تعديل نحو حل أقل تكلفة.

يحل هذا المتغير بعد ذلك محل أحد متغيراته المشتركة ، والذي يحد منه بشكل كبير ، وبالتالي يتم تحويل طريقة simplex إلى جزء آخر من مجموعة الحلول ونحو الحل النهائي.

10. لا تزال طرق التكرار في الفضاء الجزئي Krylov مستخدمة اليوم

الخالق (إذا كان معروفًا):Magnus Hestenes و Eduard Stiefel و Cornelius Lanczos

متى تم إنشاؤه (إذا كان معروفًا): 1950

تأثيرها / انعكاساتها على العالم: تعد طريقة التكرار في الفضاء الجزئي Krylov واحدة من أهم عشر فئات للطرق العددية في العالم.

طرق التكرار للمساحة الجزئية Krylov هي مجموعة من الخوارزميات التي تم تطويرها في معهد التحليل العددي في المكتب الوطني للمعايير في الخمسينيات. يتناولون المهمة البسيطة المخادعة المتمثلة في حل المعادلات بالصيغة Ax = b.

بالطبع ، الأمر ليس بهذه البساطة ، A عبارة عن مصفوفة ضخمة n على n. هذا ، بالتالي ، يعني أن الإجابة الجبرية x = b / A ليست لعبة أطفال يجب حسابها.

"الطرق التكرارية - مثل حل المعادلات بالصيغة Kxأنا + 1 = كوكسأنا + b - Axi مع مصفوفة أبسط K تكون مثالية "قريبة" من A - تؤدي إلى دراسة فضاء Krylov الجزئي. تمت تسميتها على اسم عالم الرياضيات الروسي نيكولاي كريلوف ، وتمتد مساحات كريلوف الفرعية بواسطة قوى مصفوفة مطبقة على ناقل أولي "الباقي" r0 = ب - الفأس0. "- باري إيه سيبرا.

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

تم تعديل هذه الخوارزميات باستمرار على مدار الخمسين عامًا الماضية. تتضمن التكرارات الحالية للأنظمة غير المتماثلة طريقة الحد الأدنى المعمم المتبقية (GMRES) وطريقة Biconjugate المتدرجة المستقرة (Bi-CGSTAB).

11. يعتبر مرشح كالمان رائعًا للتنبؤ بالمستقبل ، نوعًا ما

المنشئ :رودولف إي كالمان

متى تم إنشاؤه (إذا كان معروفًا): 1958-1961

تأثيرها / انعكاساتها على العالم: يعد مرشح كالمان أداة عامة وقوية لدمج المعلومات في حالة عدم اليقين.

ترشيح كالمان ، المعروف أيضًا باسم التقدير التربيعي الخطي (LQE) ، عبارة عن خوارزمية تستخدم سلسلة من القياسات التي تمت ملاحظتها بمرور الوقت وتتضمن الضوضاء الإحصائية ، لإنتاج تقدير لمتغيرات غير معروفة عبر توزيع احتمالي مشترك.

بعبارة أخرى ، يساعدك هذا على تكوين تخمين مدروس لما سيفعله النظام بعد ذلك ، في حدود المعقول بالطبع. تعتبر مرشحات Kalman رائعة في المواقف التي تتغير فيها الأنظمة باستمرار.

شيء عظيم آخر حول هذه الخوارزمية هو أنها خفيفة على "الذاكرة". مطلوب فقط نتيجة الخطوة السابقة للتقدم ، مما يجعلها سريعة جدًا ومناسبة بشكل مثالي لحل المشكلات في الوقت الفعلي.

12. أثبتت خوارزميات الاستجابة السريعة لحساب القيم الذاتية أنها مفيدة بشكل لا يصدق

المنشئ: جون ج.ف.فرانسيس وفيرا ن.كوبلانوفسكايا بشكل مستقل

عندما تم إنشاؤه: أواخر الخمسينيات

تأثيرها / انعكاساتها على العالم: تعمل خوارزمية QR على تبسيط حسابات القيم الذاتية (وهي أهم الأرقام المرتبطة بالمصفوفات). بعد تطويره ، أصبح حساب هذه الأرقام المزعجة مهمة روتينية وليس عملية شاقة وكثيفة العمالة.

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

وتتمثل وظيفتها الأساسية في إجراء تحلل QR ، وكتابة مصفوفة كمنتج لمصفوفة متعامدة ومصفوفة مثلثة عليا ، وضرب العوامل بالترتيب العكسي والتكرار.

13. يمكن أن تكون صياغة مترجم فورتران الأمثل أهم حدث في تاريخ البرمجة

المنشئ: John Backus (وفريق IBM)

عندما تم إنشاؤه: 1957

تأثيرها / انعكاساتها على العالم: من المحتمل جدًا أن تكون الخوارزمية / الحدث الأكثر أهمية في برمجة الكمبيوتر.

تم تطوير Fortran بواسطة John Backus وفريقه في IBM في أواخر الخمسينيات من القرن الماضي ، وقد مكّن العلماء والمستخدمين الآخرين من إخبار الكمبيوتر بما يريدون فعله دون الحاجة إلى "التعثر" في تفاصيل كود الآلة . يعتبر مترجم تحسين فورتران متواضعًا وفقًا لمعايير العصر الحديث مع "23500 تعليمات لغة التجميع - كان المترجم المبكر قادرًا على إجراء حسابات معقدة بشكل مدهش." - باري إيه سيبرا.

سيعترف باكوس بأهميته بالنسبة للعالم لاحقًا ، في عام 1998 ، عندما استذكر تاريخ فورتران الأول والثاني والثالث حوليات IEEE لتاريخ الحوسبة. قال باكوس: "أنتج المترجم كودًا بهذه الكفاءة لدرجة أن مخرجاته ستذهل المبرمجين الذين درسوها".

14. Quicksort رائع في المساعدة على فرز الأشياء

المنشئ: توني هور من شركة إليوت براذرز المحدودة ، لندن

عندما تم إنشاؤه: 1962

تأثيرها / انعكاساتها على العالم: لقد وفرت وسيلة لفرز القوائم بسرعة وكفاءة أبجديًا ورقميًا.

لطالما كان فرز كمية معينة من الأشياء بالترتيب أبجديًا أو رقميًا مهمة شاقة ومملة. تمكن توني هور ، في 1962، لإنتاج خوارزمية لأداء هذه المهمة بسرعة.

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

إنه يعمل عن طريق اختيار عنصر واحد ليكون "المحور". يتم بعد ذلك فرز كل العناصر الأخرى إلى أكوام "أكبر" و "أصغر" من العناصر بالنسبة إلى المحور.

ثم تتكرر هذه العملية في كل كومة.

"على الرغم من أنه من الممكن أن تتعثر في إجراء جميع مقارنات N (N - 1) / 2 (خاصة إذا كنت تستخدم العنصر الأول في قائمة تم فرزها كمحور بالفعل!) ، فإن Quicksort يعمل في المتوسط ​​بكفاءة O (N log N) . " - باري إيه سيبرا.

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

15. تعد ملفات JPEG وخوارزميات ضغط البيانات الأخرى مفيدة للغاية

المنشئ: مجموعة خبراء التصوير المشتركة ، IBM ، Mitsubishi Electric ، AT&T ، Canon Inc. ، ITU-T Study Group 16

عندما تم إنشاؤه: 1992

تأثيرها / انعكاساتها على العالم: تُستخدم خوارزميات ضغط البيانات ، مثل JPEG أو MP3 أو zip أو MPEG-2 ، على نطاق واسع في جميع أنحاء العالم. أصبح معظمهم بحكم الواقع معيار لتطبيقهم الخاص. لقد جعلوا أنظمة الكمبيوتر أرخص وأكثر كفاءة بمرور الوقت.

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


شاهد الفيديو: العلاقة بين الرياضيات و العلوم (كانون الثاني 2022).