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

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

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

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

ومن الأمثلة على الآلات المجردة المحددة التي تتسم بالحتمية آلة تورينج الحتمية والآلة المحدودة الحتمية .

هناك مجموعة متنوعة من العوامل التي قد تجعل الخوارزمية تتصرف بطريقة غير حتمية أو غير حتمية:

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

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

أدى انتشار المعالجات متعددة النوى إلى زيادة الاهتمام بالحتمية في البرمجة المتوازية، وقد تم توثيق تحديات عدم الحتمية بشكل جيد. ^{[ 1 ] [ 2 ]} وقد تم اقتراح عدد من الأدوات للمساعدة في التعامل مع هذه التحديات ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]} لمعالجة حالات الجمود وحالات التزامن .

في بعض الحالات، يُعدّ سلوك البرنامج غير الحتمي ميزة. فعلى سبيل المثال، يجب ألا يكون سلوك برنامج خلط أوراق اللعب المستخدم في لعبة البلاك جاك قابلاً للتنبؤ من قِبل اللاعبين، حتى لو كان رمز البرنامج المصدري متاحًا. غالبًا ما لا يكفي استخدام مولد أرقام شبه عشوائي لضمان عدم قدرة اللاعبين على التنبؤ بنتيجة الخلط. قد يُخمّن مقامرٌ ماهرٌ بدقة الأرقام التي سيختارها المولد، وبالتالي يُحدد محتويات مجموعة الأوراق بالكامل مسبقًا، مما يسمح له بالغش. على سبيل المثال، تمكّن فريق أمن البرمجيات في شركة Reliable Software Technologies من فعل ذلك لتطبيق لعبة تكساس هولدم بوكر التي تُوزّعها شركة ASF Software، مما سمح لهم بالتنبؤ بنتيجة الجولات مسبقًا باستمرار. ^{[ 7 ]} يمكن تجنّب هذه المشاكل، جزئيًا، من خلال استخدام مولد أرقام شبه عشوائي آمن تشفيريًا ، ولكن لا يزال من الضروري استخدام بذرة عشوائية غير قابلة للتنبؤ لتهيئة المولد. لهذا الغرض، يلزم وجود مصدر لعدم الحتمية، مثل ذلك الذي يوفره مولد الأرقام العشوائية للأجهزة .

تجدر الإشارة إلى أن الإجابة السلبية على مسألة P=NP لا تعني بالضرورة أن البرامج ذات المخرجات غير الحتمية أقوى نظريًا من تلك ذات المخرجات الحتمية. يمكن تعريف فئة التعقيد NP (التعقيد) دون أي إشارة إلى عدم الحتمية باستخدام التعريف القائم على المُدقِّق .

• خوارزمية عشوائية