خوارزمية غير حتمية

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
الموسوعة الحرة

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

تؤدي نماذج الحوسبة المختلفة إلى أسباب مختلفة تجعل الخوارزمية غير حتمية، وإلى طرق مختلفة لتقييم أدائها أو صحتها:

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

تاريخ

قبل صياغة مفهوم اللا حتمية في علوم الحاسوب، تمّت دراسة الخوارزميات الصريحة التي تستخدم العشوائية . في عام ١٩١٧، قدّم هنري سي. بوكلينغتون خوارزمية عشوائية تُعرف بخوارزمية بوكلينغتون لإيجاد الجذور التربيعية بكفاءة باستخدام الأعداد الأولية. [ ١ ] في ثلاثينيات القرن العشرين، أجرى إنريكو فيرمي تجارب على طريقة مونت كارلو أثناء دراسته لانتشار النيوترونات، لكنه لم ينشر هذا العمل. [ ٢ ] قام علماء في مختبر لوس ألاموس الوطني في أربعينيات وخمسينيات القرن العشرين بتطوير وتطبيق هذا المفهوم، مما أدى إلى ظهور أولى المنشورات المتعلقة بخوارزميات مونت كارلو. [ ٣ ] [ ٤ ]

قدّم مايكل أو. رابين ودانا سكوت مفهوم الأوتوماتونات المحدودة غير الحتمية (NFA) ووضعوا له صيغة رسمية في عام 1959. [ 5 ] في تلك الورقة، أظهرا تكافؤها مع الأوتوماتونات المحدودة الحتمية (DFA) من حيث قدرتها على تمييز اللغات. كما طبّقاها على آلات تورينج (TM)، مُقدّمين بذلك آلات تورينج غير الحتمية (NTM). وباستخدام الأوتوماتونات المحدودة غير الحتمية، تمكّنا من إعادة إثبات بعض خصائص الإغلاق للغات المنتظمة بطريقة أكثر تبسيطًا، وهي خصائص سبق أن أثبتها ستيفن سي. كلين وآخرون.

استخدم روبرت دبليو فلويد مصطلح الخوارزمية غير الحتمية في وقت مبكر من عام 1967. [ 6 ] تستخدم الورقة لغة الرسوم البيانية لمخططات التدفق، وهي طريقة مختلفة لصياغة الخوارزميات مقارنة بالآلات الآلية أو آلات تورينج، وكانت في ذلك الوقت أقرب إلى ممارسة البرمجة على أجهزة الكمبيوتر الإلكترونية.

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

مراجع

  1. ↑ ويليامز، إتش سي ؛ شاليت، جيه أو (1994)، "تحليل الأعداد الصحيحة قبل الحواسيب"، في غاوتشي، والتر (محرر)، رياضيات الحوسبة 1943-1993: نصف قرن من الرياضيات الحاسوبية؛ أوراق من ندوة التحليل العددي والندوة المصغرة حول نظرية الأعداد الحاسوبية التي عُقدت في فانكوفر، كولومبيا البريطانية، 9-13 أغسطس 1993 ، وقائع ندوات في الرياضيات التطبيقية، المجلد  48، الجمعية الأمريكية للرياضيات، بروفيدنس، رود آيلاند، الصفحات 481-531 ، doi : 10.1090/psapm/048/1314885 ، ISBN  978-0-8218-0291-5MR 1314885​ انظر الصفحة 504، "ربما يستحق بوكلينجتون أيضًا الفضل كمخترع للخوارزمية العشوائية".
  2. ^ متروبوليس، ن. (1987). “بداية طريقة مونت كارلو” (PDF) . علوم لوس ألاموس (عدد خاص لعام 1987 مخصص لستانيسلاف أولام): 125-130 .
  3. ↑ متروبوليس، ن .؛ أولام، س. ( 1949). "طريقة مونت كارلو". مجلة الجمعية الإحصائية الأمريكية . 44 (247): 335-341 . doi : 10.1080/01621459.1949.10483310 . JSTOR 2280232. PMID 18139350 .  
  4. ↑ متروبوليس، ن .؛ روزنبلث، أريانا و.؛ روزنبلث، مارشال ن.؛ تيلر، أوغستا هـ.؛ تيلر، إدوارد (1953). "حسابات معادلة الحالة باستخدام أجهزة الحوسبة السريعة" . مجلة الفيزياء الكيميائية . 21 (6): 1087. Bibcode : 1953JChPh..21.1087M . doi : 10.1063/ 1.1699114 . OSTI 4390578. S2CID 1046577 .  
  5. ↑ رابين، م.و.؛ سكوت، د. (أبريل 1959). "الآلات المحدودة ومشاكل اتخاذ القرار الخاصة بها". مجلة آي بي إم للبحوث والتطوير . 3 (2): 114-125 . doi : 10.1147/rd.32.0114 .
  6. ↑ روبرت دبليو. فلويد (أكتوبر 1967). "الخوارزميات غير الحتمية" . مجلة ACM . 14 (4): 636-644 . doi : 10.1145/321420.321422 . S2CID 1990464 . 

للمزيد من القراءة

  • كورمن، توماس هـ. (2009). مقدمة في الخوارزميات (  الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-262-03384-8.
  • "الخوارزمية غير الحتمية" . المعهد الوطني للمعايير والتكنولوجيا . تم الاطلاع عليه في 7 يوليو 2013 .
  • "الخوارزميات غير الحتمية" . قسم علوم الحاسوب، جامعة نيويورك . تم الاطلاع عليه في 7 يوليو 2013 .