نظرية البيانات: مسائل تدريبية مع حلول خطوة بخطوة

مسائل تدريبية مجانية في نظرية البيانات مع رسوم توضيحية وتلميحات وحلول مفصّلة كاملة. قيم جديدة في كل مرة، بثلاثة مستويات: الدرجات والحواف, مسارات أويلر والأشجار, أقصر المسارات والأشجار الممتدة.

مسألة تدريبية مجانيةسهلة

شجرة لها 12 رؤوس. كم حافة |E| لها؟

|V| = 12

إجابة دقيقة: عدد صحيح، دون تقريب.

المسألة التالية →
تدرّب على نظرية البيانات مجانًاتدرّب على نظرية البيانات الآن5 مسائل مجانية كل يوم. لا حاجة إلى بطاقة.

ما الذي تتدرّب عليه

  1. سهلةالدرجات والحواف
  2. متوسطةمسارات أويلر والأشجار
  3. صعبةأقصر المسارات والأشجار الممتدة

كيف تحلّ مسائل نظرية البيانات

  1. اكتب درجة كل رأس؛ مجموع الدرجات يساوي ضعف عدد الحواف.
  2. في أسئلة أويلر، تحقّق من أن البيان متصل وعُدّ الرؤوس ذات الدرجة الفردية.
  3. للأشجار استخدم n − 1 حافة ومبرهنة المصافحة.
  4. في ديكسترا احتفظ بجدول للمسافات المؤقتة وثبّت في كل جولة أصغر رأس غير مثبّت.
  5. لإيجاد شجرة ممتدة دنيا، رتّب الحواف بحسب الوزن وتخطَّ كل حافة تُغلق دورة (كروسكال)، أو أنمِ شجرة واحدة انطلاقًا من رأس البداية (برايم).

أخطاء شائعة

  • نسيان قسمة مجموع الدرجات على 2.
  • وصف بيان بأنه أويلري دون التحقق من الاتصال.
  • تثبيت رأس في ديكسترا قبل أن تصبح مسافته الأصغر.
  • أخذ أخف الحواف دون التحقق من الدورات.
  • عدّ دارات هاملتون في Kn على أنها n! بدل (n − 1)!/2.

الصيغ الأساسية

مبرهنة المصافحة
Σ deg(v) = 2|E|
البيانات التامة
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
البيان المنتظم
|E| = n·k/2
الشجرة والغابة
|E| = n − 1, |E| = n − c
أوراق الشجرة
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
أويلر
الدارة: كل الدرجات زوجية؛ المسار: درجتان فرديتان بالضبط
دارات هاملتون في Kn
(n − 1)!/2
تحديث ديكسترا
d(v) = min(d(v), d(u) + w(u, v))
المسارات (walks) بطول L
(Mᴸ)ij

تعلّم نظرية البيانات من البداية

قبل هذا: المجموعات والعلاقات والدوال

1الرؤوس والحواف والدرجات

يتكون البيان (graph) من رؤوس (نقاط) وحواف (خطوط بين رأسين). في البيان البسيط لا توجد حلقات ولا حواف مزدوجة.

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

Σ deg(v) = 2·|E|

نتيجتان: مجموع الدرجات زوجي دائمًا، وعدد الرؤوس ذات الدرجة الفردية زوجي أيضًا.

  • يصل البيان التام Kn كل زوج: n(n − 1)/2 حافة.
  • يصل البيان الثنائي التام Km,n كل رأس في جانب بكل رأس في الجانب الآخر: m·n حافة.
  • للبيان k-المنتظم على n رأسًا n·k/2 حافة.

في مصفوفة التجاور تكون 1 عند (i, j) عندما يكون i و j متصلين. وهي في البيان غير الموجَّه متناظرة، ومجموع الصف هو درجة، والمدخل (i, j) من Mᴸ يعدّ المسارات بطول L من i إلى j.

تحقّق ذاتي درجات بيان هي 3, 3, 2, 2, 2. كم حافة له؟
  1. 10
  2. 12
  3. 5
  4. 6

الإجابة: 6. مجموع الدرجات 12، وكل حافة تُعدّ مرتين، إذن هناك 12/2 = 6 حواف. أما 5 فهو عدد الرؤوس.

2أويلر وهاملتون

دارة أويلر تستخدم كل حافة مرة واحدة بالضبط وتعود إلى بدايتها. ومسار أويلر يستخدم كل حافة مرة واحدة لكنه قد ينتهي في مكان آخر. في بيان متصل:

  • كل الدرجات زوجية: توجد دارة أويلر؛
  • درجتان فرديتان بالضبط: يوجد مسار أويلر من أحد الرأسين الفرديين إلى الآخر؛
  • أكثر من درجتين فرديتين: لا هذه ولا تلك.

دارة هاملتون تزور كل رأس مرة واحدة بالضبط. لا يوجد اختبار بسيط بالدرجات لها. في Kn توجد (n − 1)!/2 دارة هاملتون مختلفة: ثبّت البداية، ورتّب الرؤوس الـ n − 1 الأخرى، واقسم على 2 للاتجاهين.

تحقّق ذاتي بيان متصل درجاته 2, 3, 4, 3, 2. ماذا يملك؟
  1. دارة أويلر ومسار أويلر ليس دارة معًا
  2. دارة أويلر
  3. لا هذه ولا تلك
  4. مسار أويلر، لكن دون دارة أويلر

الإجابة: مسار أويلر، لكن دون دارة أويلر. رأسان بالضبط ذوا درجة فردية (العددان 3)، فيوجد مسار أويلر بينهما، لكن لا توجد دارة.

3الأشجار

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

لغابة من c شجرة على n رأسًا n − c حافة. يحتفظ بيان متصل ذو m حافة بـشجرة ممتدة بعد حذف m − n + 1 حافة.

تعدّ مبرهنة المصافحة الأوراق: Σ deg = 2(n − 1). وصيغة مختصرة هي L = 2 + Σ (d − 2) على الرؤوس ذات الدرجة d ≥ 3. شجرة فيها رأسان من الدرجة 3 وبقية الرؤوس أوراق لها 2 + 1 + 1 = 4 أوراق.

4ديكسترا والأشجار الممتدة الدنيا

خوارزمية ديكسترا تجد أقصر المسافات من رأس بداية في بيان أوزانه غير سالبة.

  1. أعطِ مسافة البداية 0 وكل رأس آخر ∞.
  2. ثبّت الرأس غير المثبّت ذا أصغر مسافة؛ تصبح مسافته نهائية.
  3. لكل جار v حدّث d(v) = min(d(v), d(u) + w(u, v)).
  4. كرّر حتى يُثبَّت الهدف.

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

مثال محلول

جد أقصر مسافة من A إلى E في البيان أدناه.

1

البداية

412581ABCDE

d(A) = 0. جيرانه يأخذون d(B) = 4 و d(C) = 1.

2

ثبّت C (1)

عبر C: d(B) = min(4, 1 + 2) = 3 و d(E) = 1 + 8 = 9.

3

ثبّت B (3)

عبر B: d(D) = 3 + 5 = 8.

4

ثبّت D (8)

عبر D: d(E) = min(9, 8 + 1) = 9. لا تحسّن، تعادل.

5

ثبّت E (9)

تم تثبيت E: مسافته نهائية.

الإجابة

أقصر مسافة هي d(E) = 9 على المسار A → C → E. المسار A → C → B → D → E له الطول نفسه، 1 + 2 + 5 + 1 = 9.

تحقّق ذاتي أخذت خوارزمية كروسكال الحواف ذات الأوزان 1 و2 و3. الحافة التالية الأخف، وزنها 4، تصل رأسين متصلين أصلًا. ماذا يحدث؟
  1. تتوقف الخوارزمية
  2. تُؤخذ لأنها الأخف المتبقية
  3. تُتخطى لأنها ستُغلق دورة
  4. تُحذف الحافة ذات الوزن 3 بدلًا منها

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

5أخطاء شائعة

  • نسيان قسمة مجموع الدرجات على 2 للحصول على عدد الحواف.
  • اختبار وجود دارة أويلر دون التحقق من أن البيان متصل.
  • تثبيت رأس في ديكسترا قبل أن تصبح مسافته المؤقتة الأصغر.
  • أخذ أخف n − 1 حافة دون التحقق من الدورات.
  • عدّ دارات هاملتون في Kn على أنها n! بدل (n − 1)!/2.

6كيف تبدو أسئلة الامتحان

  • سهل: الدرجات والحواف. تستخدم مبرهنة المصافحة، وتعدّ حواف Kn وKm,n والبيانات المنتظمة والأشجار، وتقرأ مصفوفة تجاور، أو تنقر على الرأس ذي الدرجة المعطاة.
  • متوسط: مسارات أويلر والأشجار. تحدد هل لبيان دارة أو مسار أويلر، وتعدّ أوراق شجرة، وتعدّ الحواف الواجب حذفها للحصول على شجرة ممتدة، أو تعدّ دارات هاملتون في Kn.
  • صعب: أقصر المسارات والأشجار الممتدة. تنفّذ خوارزمية ديكسترا، وتجد الرأس المثبَّت في جولة معينة، وتجد وزن شجرة ممتدة دنيا، وتنقر على الحافة التي يضيفها كروسكال أو برايم تاليًا، أو تعدّ المسارات (walks) بمصفوفة التجاور.

تعلّمه خطوة بخطوة في التطبيقتعلّمه خطوة بخطوة في التطبيق

أمثلة محلولة

مثال 1سهلة
AABBCCDDEE0010000001100010000101110

مصفوفة التجاور لبيان بسيط غير موجَّه معروضة. كم حافة |E| للبيان؟

المطلوب: |E|

أظهر التلميحات
  1. المدخل (i, j) يساوي 1 عندما يتصل الرأسان i وj بحافة.
  2. كل حافة {i, j} تعطي واحدين: واحدًا عند (i, j) وواحدًا عند (j, i).
  3. تحتوي المصفوفة 8 آحاد.
أظهر الإجابة والحل خطوة بخطوة

الدرجات: درجة الرأس هي عدد الحواف التي تلتقي عنده. لكل حافة طرفان، فتساوي الدرجات مجتمعةً ضعف عدد الحواف: Σ deg(v) = 2|E| (مبرهنة المصافحة). وعدد الرؤوس ذات الدرجة الفردية زوجي إذن. للبيان Kn عدد n(n − 1)/2 حافة، وللبيان k-المنتظم على n رأسًا nk/2، وللشجرة على n رأسًا n − 1 حافة.

عُدّ الآحاد

مجاميع الصفوف: 1 + 1 + 2 + 1 + 3 = 8
|E| = 8/2 = 4

الإجابة

|E| = 4
مثال 2متوسطة
ABCDEFGدارة أويلرمسار أويلر دون دارةلا هذه ولا تلك

هل للبيان المتصل دارة أويلر، أم مسار أويلر ليس دارة، أم لا هذه ولا تلك؟ انقر على إجابتك.

|V| = 7|E| = 10
  1. 1دارة أويلر
  2. 2مسار أويلر دون دارة
  3. 3لا هذه ولا تلك
أظهر التلميحات
  1. مبرهنة أويلر تحتاج فقط إلى درجات الرؤوس (البيان متصل).
  2. كل الدرجات زوجية: دارة أويلر. درجتان فرديتان بالضبط: مسار أويلر بينهما. أكثر: لا هذه ولا تلك.
  3. عُدّ الرؤوس ذات الدرجة الفردية.
أظهر الإجابة والشرح

أويلر وهاملتون والأشجار: لبيان متصل دارة أويلر (كل حافة مرة واحدة، والعودة إلى البداية) عندما تكون لكل رأس درجة زوجية، ومسار أويلر ليس دارة عندما تكون لرأسين بالضبط درجة فردية؛ ويسير المسار عندئذ من أحد الرأسين الفرديين إلى الآخر. تزور دارة هاملتون كل رأس مرة واحدة؛ وفي Kn منها (n − 1)!/2. للشجرة على n رأسًا n − 1 حافة، ويحتفظ بيان متصل ذو m حافة بشجرة ممتدة بعد حذف m − n + 1 حافة.

الدرجات

deg(A) = 1, deg(B) = 4, deg(C) = 2, deg(D) = 4, deg(E) = 4, deg(F) = 2, deg(G) = 3

الرؤوس الفردية

A, G → 2
مسار أويلر دون دارة

الإجابة

مسار أويلر دون دارة

يبدأ مسار أويلر عند أحد الرأسين الفرديين وينتهي عند الآخر.

مثال 3صعبة
ABCDEF

كم مسارًا مغلقًا (closed walk) بطول 3 يبدأ وينتهي عند E؟ يجوز للمسار تكرار الرؤوس والحواف. سمِّ العدد N.

M = مصفوفة التجاورL = 3

المطلوب: N

أظهر التلميحات
  1. مع مصفوفة التجاور M، عدد المسارات بطول L من i إلى j هو المدخل (i, j) من Mᴸ.
  2. عُدّ المسارات بطول 2 من E إلى كل رأس أولًا، ثم خذ خطوة إضافية.
  3. المسارات بطول 2 من E: A: 2, B: 1, C: 0, D: 2, E: 4, F: 1.
أظهر الإجابة والحل خطوة بخطوة

الدرجات: درجة الرأس هي عدد الحواف التي تلتقي عنده. لكل حافة طرفان، فتساوي الدرجات مجتمعةً ضعف عدد الحواف: Σ deg(v) = 2|E| (مبرهنة المصافحة). وعدد الرؤوس ذات الدرجة الفردية زوجي إذن. للبيان Kn عدد n(n − 1)/2 حافة، وللبيان k-المنتظم على n رأسًا nk/2، وللشجرة على n رأسًا n − 1 حافة.

مصفوفة التجاور

A: 0 1 1 0 0 0
B: 1 0 0 1 1 0
C: 1 0 0 0 1 0
D: 0 1 0 0 1 1
E: 0 1 1 1 0 1
F: 0 0 0 1 1 0

خطوة إضافية

(M³)EE = 2·0 + 1·1 + 0·1 + 2·1 + 4·0 + 1·1 = 4

الإجابة

N = 4

أسئلة وأجوبة

ما هو نظرية البيانات؟

يتكون البيان (graph) من رؤوس (نقاط) وحواف (خطوط بين رأسين). في البيان البسيط لا توجد حلقات ولا حواف مزدوجة.

نتيجتان: مجموع الدرجات زوجي دائمًا، وعدد الرؤوس ذات الدرجة الفردية زوجي أيضًا.

كيف تحل مسائل نظرية البيانات خطوة بخطوة؟
  1. اكتب درجة كل رأس؛ مجموع الدرجات يساوي ضعف عدد الحواف.
  2. في أسئلة أويلر، تحقّق من أن البيان متصل وعُدّ الرؤوس ذات الدرجة الفردية.
  3. للأشجار استخدم n − 1 حافة ومبرهنة المصافحة.
  4. في ديكسترا احتفظ بجدول للمسافات المؤقتة وثبّت في كل جولة أصغر رأس غير مثبّت.
  5. لإيجاد شجرة ممتدة دنيا، رتّب الحواف بحسب الوزن وتخطَّ كل حافة تُغلق دورة (كروسكال)، أو أنمِ شجرة واحدة انطلاقًا من رأس البداية (برايم).
ما الأخطاء الشائعة في نظرية البيانات؟
  • نسيان قسمة مجموع الدرجات على 2.
  • وصف بيان بأنه أويلري دون التحقق من الاتصال.
  • تثبيت رأس في ديكسترا قبل أن تصبح مسافته الأصغر.
  • أخذ أخف الحواف دون التحقق من الدورات.
  • عدّ دارات هاملتون في Kn على أنها n! بدل (n − 1)!/2.
ماذا تغطي تمارين نظرية البيانات؟
  • سهلة: الدرجات والحواف
  • متوسطة: مسارات أويلر والأشجار
  • صعبة: أقصر المسارات والأشجار الممتدة

لكل مسألة قيم جديدة، فتتعلّم الطريقة بدلًا من حفظ إجابة. هل علِقت؟ افتح تلميحًا صغيرًا أولًا، والشرح الكامل فقط عندما تحتاج إليه.

كيف يعمل التدريب

  • لكل مسألة قيم جديدة، فتتعلّم الطريقة بدلًا من حفظ إجابة.
  • هل علِقت؟ افتح تلميحًا صغيرًا أولًا، والشرح الكامل فقط عندما تحتاج إليه.
  • يُحفظ تقدّمك وأخطاؤك ومسائلك المحفوظة، لتتمكّن من مراجعتها قبل الامتحان.

مواضيع قبل هذا الموضوع وبعده

تعلّم أولاً

المجموعات والعلاقات والدوال

مقرّرات تتضمّن هذا الموضوع

هياكل البيانات والخوارزمياتأساسيات علوم الحاسوبالرياضيات المتقطعة

مواضيع أخرى في الرياضيات والإحصاء

النهاياتالمشتقاتالتحسين (القيم القصوى)التكاملاتالمتتاليات والمتسلسلاتالتفاضل والتكامل لعدة متغيراتالمعادلات التفاضليةالأعداد المركبةالطرائق العدديةالمصفوفات والمحدداتالمتّجهات: الضرب القياسي والاتجاهيالمنطق القضوي والبراهينالمجموعات والعلاقات والدوالنظرية الأعداد والحساب المودوليالاحتمالالإحصاء الوصفيالتوزيع الطبيعيفترات الثقةاختبارات الفرضيات وفترات الثقةالانحدار الخطي والارتباطاختبارات مربع كاي

ورقة عمل قابلة للطباعة

ورقة عمل نظرية البيانات مع الإجابات
تدرّب على نظرية البيانات مجانًاتدرّب على نظرية البيانات الآن5 مسائل مجانية كل يوم. لا حاجة إلى بطاقة.