حساب العمليات

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

في علوم الحاسوب ، تُعدّ حسابات العمليات (أو جبر العمليات ) مجموعة متنوعة من المناهج المترابطة لنمذجة الأنظمة المتزامنة بشكل رسمي . توفر حسابات العمليات أدوات لوصف التفاعلات والاتصالات والتزامن بين مجموعة من العمليات المستقلة وصفًا عالي المستوى. كما توفر قوانين جبرية تسمح بمعالجة وتحليل أوصاف العمليات، وتتيح أيضًا الاستدلال الرسمي حول التكافؤات بين العمليات (مثل استخدام المحاكاة الثنائية ). من الأمثلة الرائدة على حسابات العمليات: CSP و CCS و ACP و LOTOS . [ 1 ] ومن الإضافات الأحدث إلى هذه المجموعة: حساب π ، وحساب البيئة ، و PEPA ، وحساب الاندماج ، وحساب الربط .

الميزات الأساسية

على الرغم من أن تنوع حسابات العمليات الحالية كبير جدًا (بما في ذلك المتغيرات التي تتضمن السلوك العشوائي ومعلومات التوقيت والتخصصات لدراسة التفاعلات الجزيئية)، إلا أن هناك العديد من السمات المشتركة بين جميع حسابات العمليات: [ 2 ]

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

رياضيات العمليات

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

  • التركيب المتوازي للعمليات
  • تحديد القنوات المستخدمة لإرسال واستقبال البيانات
  • تسلسل التفاعلات
  • إخفاء نقاط التفاعل
  • التكرار أو تكرار العملية

التركيب المتوازي

التركيب المتوازي لعمليتينP{\displaystyle {\mathit {P}}}وسؤال{\displaystyle {\mathit {Q}}}عادة ما تُكتبP|سؤال{\displaystyle P\vert Q}، هي الخاصية الأساسية التي تميز حسابات العمليات عن نماذج الحساب التسلسلي. يسمح التركيب المتوازي بالحساب فيP{\displaystyle {\mathit {P}}}وسؤال{\displaystyle {\mathit {Q}}}للمضي قدماً في وقت واحد وبشكل مستقل. ولكنه يسمح أيضاً بالتفاعل، أي التزامن وتدفق المعلومات منP{\displaystyle {\mathit {P}}}لسؤال{\displaystyle {\mathit {Q}}}(أو العكس) على قناة مشتركة بينهما. والأهم من ذلك، أنه يمكن ربط عملية ما بأكثر من قناة في الوقت نفسه.

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

تواصل

يمكن أن يكون التفاعل (ولكن ليس دائمًا) تدفقًا موجهًا للمعلومات. أي أنه يمكن التمييز بين المدخلات والمخرجات كعناصر تفاعل ثنائية. عادةً ما تُعرّف حسابات العمليات التي تُجري مثل هذه التمييزات عامل إدخال ( مثلًا) .x(v){\displaystyle x(v)}) وعامل إخراج ( مثلاًx⟨y⟩{\displaystyle x\langle y\rangle }وكلاهما يشير إلى نقطة تفاعل (هنا)x{\displaystyle {\mathit {x}}}) التي تستخدم للمزامنة مع عنصر تفاعل ثنائي.

في حال تبادل المعلومات، ستنتقل من عملية الإخراج إلى عملية الإدخال. سيحدد عنصر الإخراج البيانات المراد إرسالها.x⟨y⟩{\displaystyle x\langle y\rangle }هذه البيانات هيy{\displaystyle y}وبالمثل، إذا كان المدخل يتوقع استقبال بيانات، فسيعمل متغير واحد أو أكثر من المتغيرات المرتبطة كعناصر نائبة يتم استبدالها بالبيانات عند وصولها.x(v){\displaystyle x(v)}،v{\displaystyle v}يؤدي هذا الدور. ويُعد اختيار نوع البيانات التي يمكن تبادلها في التفاعل أحد السمات الرئيسية التي تميز حسابات العمليات المختلفة.

التركيب التسلسلي

في بعض الأحيان، يجب ترتيب التفاعلات زمنيًا. على سبيل المثال، قد يكون من المستحسن تحديد خوارزميات مثل: أولًا، استلام بعض البيانات حولx{\displaystyle {\mathit {x}}}ثم أرسل تلك البياناتy{\displaystyle {\mathit {y}}}يمكن استخدام التركيب التسلسلي لهذه الأغراض . وهو معروف جيدًا من نماذج حسابية أخرى. في حسابات العمليات، عادةً ما يتم دمج عامل التسلسل مع المدخلات أو المخرجات، أو كليهما. على سبيل المثال، العمليةx(v)⋅P{\displaystyle x(v)\cdot P}سأنتظر رأيكم بشأنx{\displaystyle {\mathit {x}}}لن تبدأ العملية إلا بعد حدوث هذا الإدخالP{\displaystyle {\mathit {P}}}يتم تفعيلها، باستخدام البيانات المستلمة من خلالx{\displaystyle {\mathit {x}}}تم استبدال المعرفv{\displaystyle {\mathit {v}}}.

دلالات الاختزال

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

x⟨y⟩⋅P|x(v)⋅سؤال⟶P|سؤال[y/v]{\displaystyle x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]}

تفسير قاعدة التخفيض هذه هو:

  1. العمليةx⟨y⟩⋅P{\displaystyle x\langle y\rangle \cdot P}يرسل رسالة، هناy{\displaystyle {\mathit {y}}}على طول القناةx{\displaystyle {\mathit {x}}}. وبالمثل، فإن العمليةx(v)⋅سؤال{\displaystyle x(v)\cdot Q}يستقبل تلك الرسالة على القناةx{\displaystyle {\mathit {x}}}.
  2. بمجرد إرسال الرسالة،x⟨y⟩⋅P{\displaystyle x\langle y\rangle \cdot P}تصبح العمليةP{\displaystyle {\mathit {P}}}، بينماx(v)⋅سؤال{\displaystyle x(v)\cdot Q}تصبح العمليةسؤال[y/v]{\displaystyle Q[^{y}\!/\!_{v}]}، وهوسؤال{\displaystyle {\mathit {Q}}}مع العنصر النائبv{\displaystyle {\mathit {v}}}تم استبداله بـy{\displaystyle {\mathit {y}}}البيانات المستلمة فيx{\displaystyle {\mathit {x}}}.

فئة العمليات التيP{\displaystyle {\mathit {P}}}يُسمح لها بالتوسع حيث أن استمرار عملية الإخراج يؤثر بشكل كبير على خصائص الحساب.

إخفاء

لا تحد العمليات من عدد الاتصالات التي يمكن إجراؤها عند نقطة تفاعل معينة. لكن نقاط التفاعل تسمح بالتداخل (أي التفاعل). ولتوليف الأنظمة المدمجة والبسيطة والتركيبية، تُعد القدرة على الحد من التداخل أمرًا بالغ الأهمية. تسمح عمليات الإخفاء بالتحكم في الاتصالات التي تُنشأ بين نقاط التفاعل عند تركيب العمليات بالتوازي. يمكن التعبير عن الإخفاء بطرق متنوعة. على سبيل المثال، في حساب باي، يُشير إخفاء اسم إلى إخفاء اسم.x{\displaystyle {\mathit {x}}}فيP{\displaystyle {\mathit {P}}}يمكن التعبير عنها على النحو التالي(νx)P{\displaystyle (\nu \;x)P}بينما في لغة CSP قد تُكتب على النحو التاليP∖{x}{\displaystyle P\setminus \{x\}}.

التكرار والنسخ

تصف العمليات المعروضة حتى الآن تفاعلات محدودة فقط، وبالتالي فهي غير كافية للحوسبة الكاملة، التي تشمل السلوك غير المنتهي. التكرار والنسخ عمليتان تسمحان بوصف محدود لسلوك غير محدود. التكرار معروف جيدًا في مجال الأنظمة التسلسلية.!P{\displaystyle !P}يمكن فهمها على أنها اختصار للتركيب المتوازي لعدد لا نهائي قابل للعد منP{\displaystyle {\mathit {P}}}العمليات:

!P=P|!P{\displaystyle !P=P\mid !P}

عملية فارغة

تتضمن حسابات العمليات عمومًا عملية صفرية (يشار إليها بشكل مختلف باسمنأنال{\displaystyle {\mathit {nil}}}،0{\displaystyle 0}،SتيياP{\displaystyle {\mathit {STOP}}}،دلتا{\displaystyle \delta }(أو أي رمز مناسب آخر) لا يحتوي على نقاط تفاعل. إنه غير نشط تمامًا، وغرضه الوحيد هو العمل كمرساة استقرائية يمكن من خلالها توليد عمليات أكثر إثارة للاهتمام.

جبر العمليات المنفصلة والمستمرة

تمت دراسة جبر العمليات في الزمن المتقطع والزمن المستمر (الزمن الحقيقي أو الزمن الكثيف). [ 4 ]

تاريخ

في النصف الأول من القرن العشرين، طُرحت العديد من النماذج الرسمية لتجسيد المفهوم غير الرسمي للدالة القابلة للحساب ، ولعلّ الدوال التكرارية من النوع μ ، وآلات تورينج ، وحساب لامدا، هي أشهر الأمثلة المعروفة اليوم. والأمر المثير للدهشة هو تكافؤها الجوهري، بمعنى إمكانية ترميزها جميعًا في بعضها البعض، مما يدعم فرضية تشرش-تورينج . وهناك سمة مشتركة أخرى نادرًا ما يُشار إليها: وهي أنها جميعًا تُفهم بسهولة كنماذج للحساب التسلسلي . وقد استلزم التوطيد اللاحق لعلم الحاسوب صياغةً أكثر دقة لمفهوم الحساب، ولا سيما التمثيلات الصريحة للتزامن والتواصل. وقد انبثقت من هذا المسار البحثي نماذج للتزامن مثل حسابات العمليات، وشبكات بيتري عام 1962، ونموذج الممثل عام 1973.

بدأ البحث الجاد في حسابات العمليات مع العمل الرائد لروبن ميلنر حول حساب الأنظمة المتصلة (CCS) خلال الفترة من 1973 إلى 1980. ظهرت عمليات الاتصال التسلسلي (CSP) لكار هوار لأول مرة عام 1978، ثم تطورت لاحقًا إلى حساب عمليات متكامل خلال أوائل الثمانينيات. وشهد تطور حسابي CCS وCSP تبادلًا كبيرًا للأفكار. في عام 1982، بدأ يان بيرغسترا ويان ويليم كلوب العمل على ما عُرف لاحقًا باسم جبر العمليات المتصلة (ACP)، وقدّما مصطلح جبر العمليات لوصف عملهما. [ 1 ] تُشكّل CCS وCSP وACP الفروع الرئيسية الثلاثة لعائلة حسابات العمليات، إذ يُمكن تتبع جذور معظم حسابات العمليات الأخرى إلى أحد هذه الحسابات الثلاثة.

البحوث الحالية

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

  • تطوير حسابات العمليات الجديدة لتحسين نمذجة الظواهر الحسابية.
  • إيجاد حسابات فرعية ذات سلوك جيد ضمن حساب عملية معين. تكمن أهمية ذلك في أمرين: (1) أن معظم الحسابات تتسم بالعمومية ، إذ لا يمكن تحديد الكثير عن العمليات العشوائية؛ و(2) أن التطبيقات الحاسوبية نادرًا ما تستغل كامل نطاق الحساب، بل تستخدم فقط عمليات ذات شكل محدد للغاية. ويتم دراسة تقييد شكل العمليات في الغالب من خلال أنظمة الأنواع .
  • منطق العمليات الذي يسمح للمرء بالتفكير في الخصائص (الأساسية) التعسفية للعمليات، باتباع أفكار منطق هوار .
  • النظرية السلوكية: ما معنى أن تكون عمليتان متطابقتين؟ كيف يمكننا تحديد ما إذا كانت عمليتان مختلفتين أم لا؟ هل يمكننا إيجاد نماذج تمثل فئات تكافؤ العمليات؟ عمومًا، تُعتبر العمليات متطابقة إذا لم يتمكن أي سياق، أي عمليات أخرى تعمل بالتوازي، من رصد أي اختلاف. لسوء الحظ، فإن جعل هذه البديهية دقيقة أمر معقد، وغالبًا ما ينتج عنه توصيفات غير عملية للمساواة (والتي في معظم الحالات تكون غير قابلة للتقرير أيضًا، نتيجة لمشكلة التوقف ). تُعدّ المحاكاة الثنائية أداة تقنية تُساعد في التفكير المنطقي حول تكافؤ العمليات.
  • قدرة التعبير في الحسابات. تُظهر تجربة البرمجة أن بعض المشكلات أسهل حلًا في لغات برمجة معينة مقارنةً بلغات أخرى. تستدعي هذه الظاهرة توصيفًا أكثر دقة لقدرة التعبير في الحسابات التي تُحاكي الحوسبة، مقارنةً بما تُقدمه فرضية تشيرش-تورينج . إحدى طرق القيام بذلك هي دراسة التشفيرات بين نظامين رسميين، وملاحظة الخصائص التي يُمكن لهذه التشفيرات الحفاظ عليها. كلما زاد عدد الخصائص التي يُمكن الحفاظ عليها، زادت قدرة التعبير للهدف المُشفّر. بالنسبة لحسابات العمليات، تُشير النتائج البارزة إلى أن حساب باي المتزامن أكثر قدرة على التعبير من نظيره غير المتزامن، وله نفس القدرة التعبيرية لحساب باي ذي الرتبة الأعلى ، [ 5 ] ولكنه أقل من حساب باي المحيط .
  • يُستخدم حساب العمليات لنمذجة الأنظمة البيولوجية (حساب باي العشوائي، وBioAmbients، وBeta Binders، وBioPEPA، وحساب الأغشية). ويعتقد البعض أن التركيبية التي توفرها أدوات نظرية العمليات يمكن أن تساعد علماء الأحياء على تنظيم معارفهم بشكل أكثر منهجية.

تطبيقات البرمجيات

أدت الأفكار الكامنة وراء جبر العمليات إلى ظهور العديد من الأدوات، بما في ذلك:

العلاقة بنماذج التزامن الأخرى

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

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

انظر أيضاً

مراجع

  1. 1 2 بايتن، جي سي إم (2004). “لمحة تاريخية عن عملية الجبر” (PDF) . تقرير المسؤولية الاجتماعية للشركات 04-02 . فاكجروب إنفورماتيكا، الجامعة التقنية في أيندهوفن.
  2. ↑ بيرس، بنجامين (21-12-1996). "الحسابات الأساسية للغات البرمجة". دليل علوم وهندسة الحاسوب . مطبعة سي آر سي. الصفحات 2190-2207 . ISBN  0-8493-2909-4.
  3. ↑ بايتن، جيه سي إم؛ برافيتي، إم. (أغسطس 2005). "جبر العمليات العام" . حسابات العمليات الجبرية: الخمسة والعشرون عامًا الأولى وما بعدها (سلسلة ملاحظات بريكس NS-05-3) . بيرتينورو، فورلي، إيطاليا: بريكس، قسم علوم الحاسوب، جامعة آرهوس . تاريخ الاسترجاع: 29 ديسمبر 2007 .
  4. ↑ بايتن، جيه سي إم؛ ميدلبيرغ، كاليفورنيا (2000). "جبر العمليات مع التوقيت: الوقت الحقيقي والوقت المتقطع". دليل جبر العمليات : 627-684 . CiteSeerX 10.1.1.42.729 . 
  5. ↑ سانجيورجي، دافيد (1993). "من حساب باي إلى حساب باي ذي الرتبة الأعلى - والعودة". في: غوديل، م. -س.؛ جوانو، ج. -ب. (محرران). TAPSOFT'93: نظرية وممارسة تطوير البرمجيات . سلسلة محاضرات في علوم الحاسوب. المجلد 668. سبرينغر برلين هايدلبرغ. الصفحات 151-166 . doi : 10.1007/3-540-56610-4_62 . ISBN   9783540475989.
  6. ↑ مازوركيويتش، أنطوني (1995). "مقدمة في نظرية الأثر" . في: ديكرت، ف.؛ روزنبرغ، ج. (محرران). كتاب الآثار . سنغافورة: وورلد ساينتيفيك. ص 3-41 . ISBN  981-02-2058-8أُرشف من النسخة الأصلية (PostScript) بتاريخ 13 يونيو 2011. تم الاطلاع عليه بتاريخ 29 أبريل 2009 .

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