إعادة كتابة الرسوم البيانية

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

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

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

بشكل رسمي، يتكون نظام إعادة كتابة الرسوم البيانية عادةً من مجموعة من قواعد إعادة كتابة الرسوم البيانية على النحو التالي:ل→R{\displaystyle L\rightarrow R}، معل{\displaystyle L}ويُطلق عليه اسم الرسم البياني النمطي (أو الجانب الأيسر) وR{\displaystyle R}يُطلق عليها اسم الرسم البياني البديل (أو الجانب الأيمن من القاعدة). تُطبَّق قاعدة إعادة كتابة الرسم البياني على الرسم البياني الأصلي بالبحث عن ظهور الرسم البياني النمطي ( مطابقة الأنماط ، وبالتالي حل مشكلة تماثل الرسم البياني الفرعي ) واستبدال الظهور الذي تم العثور عليه بنسخة من الرسم البياني البديل. يمكن تنظيم قواعد إعادة الكتابة بشكل أكبر في حالة الرسوم البيانية المُصنَّفة ، كما هو الحال في قواعد الرسم البياني المنظمة بالسلاسل النصية.

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

أساليب إعادة كتابة الرسوم البيانية

أعلى: مثال على قاعدة إعادة كتابة الرسم البياني ( تحسين من بنية المُصرّف: استبدال الضرب في 2 بالجمع). أسفل: تطبيق القاعدة لتحسين "y=x*2" إلى "y=x+x".

النهج الجبري

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

من منظور نهج DPO، فإن قاعدة إعادة كتابة الرسم البياني هي زوج من التشكلات في فئة الرسوم البيانية وتشكلات الرسوم البيانية بينهما:ر=(ل←ك→R){\displaystyle r=(L\leftarrow K\rightarrow R)}مكتوب أيضًال⊇ك⊆R{\displaystyle L\supseteq K\subseteq R}، أينك→ل{\displaystyle K\rightarrow L}هي دالة حقنية . يُطلق على الرسم البياني K اسم الرسم البياني الثابت أو أحيانًا الرسم البياني للربط . تُعرَّف خطوة إعادة الكتابة أو تطبيق قاعدة r على الرسم البياني المضيف G بواسطة مخططين للدفع الخارجي ينشآن كلاهما من نفس التشكل.ك:ك→د{\displaystyle k\colon K\rightarrow D}حيث D هو رسم بياني سياقي (ومن هنا جاء اسم الدفع المزدوج ). تشاكل بياني آخرم:ل→جي{\displaystyle m\colon L\rightarrow G}يمثل هذا النموذج ظهور الحرف L في G ويُسمى تطابقًا . والفهم العملي لذلك هو أنل{\displaystyle L}هو رسم بياني فرعي مطابق منجي{\displaystyle G}(انظر مسألة تماثل الرسم البياني الفرعي )، وبعد العثور على تطابق،ل{\displaystyle L}يتم استبدالها بـR{\displaystyle R}في الرسم البياني المضيفجي{\displaystyle G}أينك{\displaystyle K}تُستخدم كواجهة، تحتوي على العقد والحواف التي يتم الحفاظ عليها عند تطبيق القاعدة. الرسم البيانيك{\displaystyle K}يلزم ربط النمط المراد مطابقته بسياقه: إذا كان فارغًا، فلا يمكن للمطابقة إلا أن تشير إلى مكون متصل كامل من الرسم البيانيجي{\displaystyle G}.

وعلى النقيض من ذلك، فإن قاعدة إعادة كتابة الرسم البياني لنهج SPO هي عبارة عن تشاكل واحد في فئة الرسوم البيانية المتعددة المصنفة والتعيينات الجزئية التي تحافظ على بنية الرسم البياني المتعدد:ر:ل→R{\displaystyle r\colon L\rightarrow R}وبالتالي، تُعرَّف خطوة إعادة الكتابة بمخطط دفع واحد . ويتشابه الفهم العملي لهذا مع منهجية DPO. ويكمن الاختلاف في عدم وجود واجهة بين الرسم البياني الأصلي G والرسم البياني G' الناتج عن خطوة إعادة الكتابة.

من الناحية العملية، يكمن الفرق الرئيسي بين DPO وSPO في كيفية تعاملهما مع حذف العقد ذات الحواف المتجاورة، وتحديدًا كيفية تجنب ترك "حواف معلقة" بعد هذا الحذف. لا يحذف أسلوب DPO العقدة إلا إذا نصت القاعدة على حذف جميع الحواف المجاورة لها ( ويمكن التحقق من شرط الحواف المعلقة في حالة تطابق معينة)، بينما يتخلص أسلوب SPO ببساطة من الحواف المجاورة دون الحاجة إلى تحديد صريح.

هناك أيضًا نهج آخر يشبه الجبر لإعادة كتابة الرسوم البيانية، يعتمد بشكل أساسي على الجبر البولياني وجبر المصفوفات، ويسمى قواعد الرسم البياني للمصفوفات . [ 1 ]

إعادة كتابة الرسم البياني المحدد

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

إعادة كتابة مخطط المصطلحات

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

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

يركز مؤتمر TERMGRAPH [ 3 ] بالكامل على البحث في إعادة كتابة مخطط المصطلحات وتطبيقاتها.

فئات قواعد الرسم البياني ونظام إعادة كتابة الرسوم البيانية

تُصنَّف أنظمة إعادة كتابة الرسوم البيانية تلقائيًا إلى فئات وفقًا لنوع تمثيل الرسوم البيانية المستخدمة وكيفية التعبير عن عمليات إعادة الكتابة. ويُستخدم مصطلح "قواعد الرسم البياني"، الذي يُعادل نظام إعادة كتابة الرسوم البيانية أو نظام استبدال الرسوم البيانية، في أغلب الأحيان في التصنيفات. ومن الأنواع الشائعة ما يلي:

التطبيقات والتنفيذات

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

  • أدوات محايدة لمجال التطبيق:
    • AGG ، نظام قواعد الرسم البياني المنسوب ( جافا ).
    • GP 2 هي لغة برمجة رسومية بصرية قائمة على القواعد مصممة لتسهيل الاستدلال الرسمي على برامج الرسوم البيانية.
    • تم أرشفة GMTE في 13 مارس 2018 على موقع Wayback Machine ، وهو محرك مطابقة وتحويل الرسوم البيانية . وهو تطبيق لتوسيع خوارزمية ميسمر باستخدام لغة C++ .
    • GrGen.NET ، مولد إعادة كتابة الرسوم البيانية، أداة لتحويل الرسوم البيانية تُصدر كود C# أو تجميعات .NET.
    • GROOVE ، وهي مجموعة أدوات قائمة على Java لتحرير الرسوم البيانية وقواعد تحويل الرسوم البيانية، واستكشاف مساحات الحالة لقواعد الرسم البياني، والتحقق من نماذج مساحات الحالة هذه؛ ويمكن استخدامها أيضًا كمحرك لتحويل الرسوم البيانية.
    • Verigraph ، وهو نظام لتحديد مواصفات البرامج والتحقق منها يعتمد على إعادة كتابة الرسوم البيانية ( هاسكل ).
  • أدوات لحل مهام هندسة البرمجيات (وخاصةً MDA ) باستخدام إعادة كتابة الرسوم البيانية:
  • أدوات الهندسة الميكانيكية
    • GraphSynth هو مترجم وبيئة واجهة مستخدم لإنشاء قواعد نحوية بيانية غير مقيدة، بالإضافة إلى اختبار وبحث متغيرات اللغة الناتجة. يحفظ الرسوم البيانية وقواعد النحو البياني كملفات XML ، وهو مكتوب بلغة C# .
    • Soley Studio [ تمت إزالة الرابط ] ، هي بيئة تطوير متكاملة لأنظمة تحويل الرسوم البيانية. وينصب تركيزها الرئيسي على تحليل البيانات في مجال الهندسة.
  • تطبيقات علم الأحياء
  • الذكاء الاصطناعي / معالجة اللغة الطبيعية
  • لغة برمجة الحاسوب
    • تُنفذ لغة البرمجة النظيفة باستخدام إعادة كتابة الرسوم البيانية .

انظر أيضاً

مراجع

الاقتباسات

مصادر