رسم بياني للتبعية

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

بالنظر إلى مجموعة من الأشياء${\displaystyle S}$وعلاقة متعدية${\displaystyle R\subseteq S\times S}$مع${\displaystyle (a,b)\in R}$عند نمذجة التبعية " أ يعتمد على ب " (" يحتاج أ إلى تقييم ب أولاً")، فإن مخطط التبعية هو رسم بياني${\displaystyle G=(S,T)}$مع${\displaystyle T\subseteq R}$الاختزال المتعدي لـ R.​

على سبيل المثال، لنفترض وجود آلة حاسبة بسيطة. تدعم هذه الآلة الحاسبة إسناد قيم ثابتة للمتغيرات وإسناد مجموع متغيرين فقط إلى متغير ثالث. إذا كانت لدينا عدة معادلات مثل " أ = ب + ج ؛ ب = ٥ + د ؛ ج = ٤؛ د = ٢"، فإن${\displaystyle S=\{A,B,C,D\}}$و${\displaystyle R=\{(A,B),(A,C),(B,D),(A,D)\}}$يمكنك استنتاج هذه العلاقة مباشرةً: يعتمد المتغير A على المتغيرين B و C ، لأنه لا يمكنك جمع متغيرين إلا إذا كنت تعرف قيم كليهما. لذا، يجب حساب B قبل حساب A. وبما أن B يعتمد على D ليتم حسابه، فيجب أن يعتمد A أيضًا على D ليتم حسابه قبله (ومن هنا تأتي خاصية التعدي المذكورة أعلاه). من ناحية أخرى، تُعرف قيم C و D مباشرةً، لأنهما قيم عددية.

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

لنفترض الآلة الحاسبة البسيطة من قبل. يحتوي نظام المعادلات " A = B ; B = D + C ; C = D + A ; D = 12; " على تبعية دائرية تتكون من A و B و C ، حيث يجب حساب B قبل A ، ويجب حساب C قبل B ، ويجب حساب A قبل C.

الترتيب الصحيح للتقييم هو الترقيم${\displaystyle n:S\rightarrow \mathbb {N} }$من بين الكائنات التي تشكل عقد الرسم البياني للتبعية بحيث تتحقق المعادلة التالية:${\displaystyle n(a)<n(b)\Rightarrow (a,b)\notin R}$مع${\displaystyle a,b\in S}$وهذا يعني أنه إذا كان الترقيم يرتب عنصرين${\displaystyle a}$و${\displaystyle b}$لهذا السبب.${\displaystyle a}$سيتم تقييمها قبل${\displaystyle b}$، ثم${\displaystyle a}$يجب ألا يعتمد على${\displaystyle b}$.

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

لنفترض مجددًا استخدام الآلة الحاسبة البسيطة المذكورة أعلاه. بالنظر إلى نظام المعادلات " أ = ب + ج ؛ ب = ٥ + د ؛ ج = ٤؛ د = ٢"، فإن ترتيب التقييم الصحيح هو ( د ، ج ، ب ، أ ). مع ذلك، فإن ( ج ، د ، ب ، أ ) هو أيضًا ترتيب تقييم صحيح.

يتوافق الرسم البياني للاعتمادية غير الدورية مع أثر أحادي الأثر كما يلي: ^{[ 1 ] : 12}

• وظيفة${\displaystyle \phi :S\to \Sigma }$قم بتسمية كل رأس برمز من الأبجدية${\displaystyle \Sigma }$
• هناك حافة${\displaystyle a\to b}$أو${\displaystyle b\to a}$إذا وفقط إذا${\displaystyle (\phi (a),\phi (b))}$يوجد في علاقة التبعية${\displaystyle D}$.
• يُعتبر الرسمان البيانيان متساويين إذا تطابقت تسمياتهما وحوافهما.

ثم فإن السلسلة المكونة من تسميات الرؤوس مرتبة حسب ترتيب التقييم الصحيح تتوافق مع سلسلة التتبع.

العملية المونيدية​${\displaystyle (S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})}$يأخذ الاتحاد المنفصل${\displaystyle S_{12}=S_{1}\sqcup S_{2}}$بالنسبة لمجموعات رؤوس رسمين بيانيين، يتم الحفاظ على الحواف الموجودة في كل رسم بياني، ويتم رسم حواف جديدة من الأول إلى الثاني حيث تسمح علاقة التبعية بذلك، ^{[ 1 ] : 14}

${\displaystyle R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}}$

العنصر المطابق هو الرسم البياني الفارغ.

تُستخدم مخططات التبعية في:

• برامج التثبيت الآلية : تقوم هذه البرامج بفحص الشبكة بحثًا عن حزم البرامج المطلوبة التي لم يتم تثبيتها بعد. وتُحدد التبعية من خلال ترابط الحزم.
• تتطلب برامج بناء البرمجيات، مثل Unix Make و Node npm install وphp composer و Twitter bower install و Apache Ant ، ​​معرفة الملفات التي تم تغييرها حتى يتم إعادة تجميع الملفات الصحيحة فقط.
• في تكنولوجيا المترجمات وتنفيذ اللغات الرسمية :
  • جدولة التعليمات : يتم حساب مخططات التبعية لمعاملات التجميع أو التعليمات الوسيطة وتستخدم لتحديد الترتيب الأمثل للتعليمات.
  • إزالة التعليمات البرمجية غير المستخدمة : إذا لم تعتمد أي عملية ذات تأثير جانبي على متغير، فسيتم اعتبار هذا المتغير غير مستخدم ويمكن إزالته.
• تحليلات الرسوم البيانية الديناميكية: يقوم كل من GraphBolt ^{[ 2 ]} و KickStarter ^{[ 3 ]} بالتقاط تبعيات القيمة للحوسبة التزايدية عند تغيير بنية الرسم البياني.
• الآلات الحاسبة في جداول البيانات . يجب أن تستنتج ترتيبًا صحيحًا للحسابات مشابهًا للترتيب المستخدم في المثال المذكور في هذه المقالة.
• معايير نماذج الويب مثل XForms لمعرفة العناصر المرئية التي يجب تحديثها في حالة تغيير البيانات في النموذج.
• ألعاب الفيديو، وخاصة ألعاب الألغاز والمغامرات ، والتي غالباً ما يتم تصميمها على شكل رسم بياني للعلاقات التابعة بين الإجراءات داخل اللعبة. ^{[ 4 ]}

تُعدّ مخططات التبعية أحد جوانب ما يلي:

• أنواع مصانع التصنيع : تتم معالجة المواد الخام وتحويلها إلى منتجات عبر عدة مراحل مترابطة.
• جدولة ورش العمل : مجموعة من المشكلات النظرية ذات الصلة في علوم الحاسوب.

• رسم بياني للمكالمات
• رسم بياني للأسبقية
• الفرز الطوبولوجي
• تبعية البيانات

• بالماس، فرانسواز (2001) عرض رسوم بيانية للتبعية: نهج هرمي. مؤرشف بتاريخ 11-02-2012 في Wayback Machine .wcre، ص 261، المؤتمر الثامن للعمل حول الهندسة العكسية (WCRE'01)