هياكل البيانات غير الخطية | الوحدة الأولى | الدرس الثالث
هياكل البيانات غير الخطية هو عنوان الدرس الثالث من الوحدة الأولى التي تحمل اسم “أساسيات الذكاء الاصطناعي” من الفصل الدراسي الأولى من مقرر “الذكاء الاصطناعي”.
ستتعرف في هذا الموضوع على الفرق بين هيكل بيانات الشجرة وهيكل بيانات المُخطَّط، وتحديد خصائص هيكل بيانات الشجرة، وتطبيق هيكل بيانات الشجرة في لغة البايثون، وتحديد أنواع هياكل بيانات الشجرة الثنائية، والتمييز بين شجرة القرار والمخطَّطات في لغة البايثون، بالإضافة إلى تحديد أنواع المُخطَّطات لهياكل البيانات وتوضيح الأمثلة عليها.
لذا قم بقراءة أهداف التعلُّم بعناية، ثم أعد قراءتها وتأكَّد من تحصيل كافة محتوياتها بعد انتهائك من دراسة الموضوع.
أهداف التعلُّم
- معرفة هياكل البيانات غير الخطيَّة.
- تحديد الفرق بين هيكل بيانات الشجرة وهيكل بيانات المُخطَّط.
- تحديد خصائص هيكل بيانات الشجرة.
- تطبيق هيكل بيانات الشجرة في لغة البايثون.
- تحديد أنواع هياكل بيانات الشجرة الثنائية.
- التمييز بين شجرة القرار والمخطَّطات في لغة البايثون.
- تحديد أنواع المخطَّطات لهياكل البيانات.
هيا لنبدأ!
هياكل البيانات غير الخطية (Non-Linear Data Structures)
هي نوع من هياكل البيانات يتميز بإمكانية ربط عنصر بأكثر من عنصر واحد في الوقت نفسه.
من الأمثلة التوضيحية على هياكل البيانات غير الخطية:
- الأشجار.
- مخططات البيانات.
الشكل أدناه يوضح هيكل البيانات الخطية وهياكل البيانات غير الخطية.
لمعرفة المزيد من المعلومات عن هياكل البيانات غير الخطية، قم بالاطّلاع على الرابط التالي:
ما الفرق بين هيكلة البيانات الخطية وغير الخطية – إي عربي
الأشجار (Trees)
الأشجار هي نوع من هياكل البيانات غير الخطية.
تتكون الشجرة من مجموعة من العقد المرتبة في ترتيب هرمي.
ترتبط كل عقدة بواحدة أو أكثر من العُقد.
ترتبط العُقد مع الحواف في نموذج علاقة يربط بين الأصل (Parent) والفرع (Child).
تُستخدم الأشجار في العديد من مجالات علوم الحاسب، بما في ذلك:
- أنظمة التشغيل.
- الرسوميات.
- أنظمة قواعد البيانات.
- الألعاب.
- الذكاء الاصطناعي.
- شبكات الحاسب.
لمعرفة المزيد من المعلومات عن “هيكل بيانات الشجرة”، قم بالاطّلاع على الرابط التالي:
مصطلحات تقنية الشجرة المُستخدَمة في هيكل بيانات الشجرة (Tree Terminology Used in the Tree Data Structure)
- الجِذر (Root)
العُقدة الأولى والوحيدة في الشجرة التي ليس لها أصل وتأتي في المستوى الأول من الشجرة مثل العقدة A في الشكل أدناه.
- الفَرع (Child)
العُقدة المُرتبطة مباشرة بعُقدة في المستوى الأعلى، مثل العُقدة H هي فرع العُقدة D، والعقدتان C،B هما فرعا العُقدة A.
- الأصل (Parent)
العُقدة التي لها فرع أو أكثر في المستوى الأقل، مثل العُقدة B هي أصل العقدتين D وE.
- الورقة (Leaf)
العُقدة التي ليس لها أي عُقدة فرعية، مثل: الورقة F.
- الأشقاء (Siblings)
كل العقد الفرعية التي تنبثق من الأصل نفسه، مثل العقدتان D وE الشقيقتان.
- الحواف (Edges)
الروابط التي تصل بين العُقد والشجرة.
- الشجرة الفرعية (Sub-Tree)
الشجيرات التي توجد داخل الشجرة الأكبر حجمًا، مثل: الشجرة التي بها العُقدة D هي الأصل والعُقدتان H وI هما الفرعان.
تعريفات هامة
الشجرة (Tree)
الشجرة هي نوع من هياكل البيانات غير الخطية، وتتكون من مجموعة من العُقد المُرتَّبة في ترتيب هرمي.
الحافة (Edge)
الحافة تصل بين عُقد هيكل بيانات الشجرة.
معلومة
قد يكون لديك شجرة بسيطة تتكون من عُقدة واحدة. تكون هذه العُقدة في الوقت نفسه جِذر هذه الشجرة البسيطة؛ لأنّها ليس لها أصل.
وفيما يلي مثال على هيكل بيانات الشجرة:
معلومة
قد تكون العُقدة فرعًا وأصلًا في الوقت نفسه؛ فرع للعُقدة السابقة وأصل للعُقدة التالية.
بإمكانك مراجعة محتوى موضوع “هياكل البيانات غير الخطية” من بدايته وحتى هذه النقطة، من خلال الرابط التالي:
خصائص هيكل بيانات الشجرة Tree Data Structure Features
- يُستخدم لتمثيل المخطط الهرمي.
- يتميز بالمرونة، فمن السهل إضافة عنصر من الشجرة أو حذفه.
- سهولة البحث عن العناصر فيه.
- يعكس العلاقات الهيكلية بين البيانات.
مثال
تنظيم الملفات في نظام التشغيل هو مثال عملي على الشجرة. كما يتضح في الشكل أدناه، يوجد داخل مجلد المستندات (Documents) مجلد آخر اسمه مشروعات البايثون (Project Python) يحتوي على ملفين آخرين.
هيكل بيانات الشجرة في لغة البايثون (Tree Data Structure in Python)
لا تُوفر لغة البايثون نوعًا مُحددًا مسبقًا من البيانات لهيكل الشجرة، ومع ذلك، تُصمم الأشجار من القوائم والقواميس بسهولة.
يوضح الشكل أدناه تطبيقًا بسيطًا للشجرة باستخدام القاموس.
في هذا المثال، ستُنشئ شجرة باستخدام قاموس بايثون، ستُمثل عُقد الشجرة مفاتيح القاموس، ستكون القيمة المقابلة لكل مفتاح هي قائمة تحتوي على العُقد المُتصلة بحافة مباشرة من هذه العُقدة.
في المثال التالي، ستُنشئ شجرة مثل تلك الموضحة في الشكل أدناه:
بإمكانك مراجعة محتوى موضوع “هياكل البيانات غير الخطية” بدايةً من عنوان “هيكل بيانات الشجرة في لغة البايثون” وحتى هذه النقطة، من خلال الرابط التالي:
الشجرة الثنائية (Binary Tree)
الشجرة الثنائية هي نوع خاص من الأشجار، يكون لكل عقدة فيها فرعان على الأكثر: الفرع الأيمن والفرع الأيسر، الشكل التالي يعرض مثالاً للشجرة والشجرة الثنائية.
أمثلة على تطبيقات هياكل بيانات الشجرة (Example of Application of Tree Data Structure)
- تخزين البيانات الهرمية مثل: هياكل المجلدات.
- تعريف البيانات في لغة الترميز التشعبي HTML.
- تنفيذ الفهرسة في قواعد البيانات.
شجرة القرار (Decision Tree)
عبارة القرار if a: else b هي واحدة من العبارات الأكثر استخدامًا في لغة البايثون، ومن خلال تداخل وتجميع هذه العبارات، يُمكنك تصميم شجرة القرار.
تُستخدم أشجار القرار في الذكاء الاصطناعي من خلال إحدى تقنيات تعلم الآلة وتعرف باسم تعلم شجرة القرار (Decision Tree Learning).
العُقد الأخيرة في هذه التقنية تُسمى أيضًا الأوراق، وتحتوي على الحلول المحتملة للمشكلة.
كل عقدة باستثناء الأوراق ترتبط بحالة منطقية يتفرع منها احتمالاً بالإجابة نعم أو لا.
أشجار القرار تعد سهلة الفهم، والاستخدام، والتصوير، ويسهل التحقق منها.
على سبيل المثال، الشكل التالي يوضح شجرة القرار التي تحدد ما إذا كنت ستتقدم بطلب الالتحاق بجامعة محددة أم لا بناء على معيارين: المقررات الدراسية التي تُدرس في الجامعة، استيفاء متطلبات القبول.
بإمكانك مراجعة محتوى موضوع “هياكل البيانات غير الخطية” بدايةً من عنوان “الشجرة الثنائية” وحتى هذه النقطة، من خلال الرابط التالي:
المُخطَّطات (Graphs)
السمة الأكثر أهمية لهياكل البيانات غير الخطية هي أن البيانات الخاصة بها لا تتبع أي نوع من أنواع التسلسل، وذلك على خلاف القوائم المترابطة والمصفوفات، كما يُمكن ربط عناصرها بأكثر من عنصر وحيد.
الشجرة الجذرية (Rooted Tree) تبدأ بعقدة جذرية يمكن ربطها بالعقد الأخرى.
تتبع الأشجار قواعد محددة وهي:
- أن تكون عُقدة الشجرة متصلة.
- أن تكون الشجرة خالية من الحلقات (Loops) والحلقات الذاتية (Self Loops).
كما أن لبعض أنواع الأشجار قواعدها الخاصة مثلما في حالة الأشجار الثنائية، ولكن ماذا سيحدث إذا لم تتبع قواعد الأشجار؟
في هذه الحالة أنت لا تتحدث عن الأشجار، بل عن نوع جديد من هياكل البيانات المتغيرة التي تسمى المخططات.
في الحقيقة، الأشجار هي نوع من المخططات حيث أن المخطط هو الشكل العام لهيكل البيانات، بمعنى أن كل هياكل البيانات السابقة يمكن اعتبارها حالات خاصة من المخططات.
تعريف هام
المُخطَّط (Graph)
المُخطَّط هو هيكل البيانات المُكوَّن من مجموعة من العُقد ومجموعة من الخطوط التي تصل بين جميع العُقد، أو بعضها.
معلومة
كل الأشجار مخطَّطات، ولكن ليست كل المُخطَّطات أشجارًا.
الجدول التالي يوضح الفرق بين الأشجار والمُخططات.
أنواع المُخططات Types of Graphs
- المخطط الموجه (Direct Graph)
ترتبط العقد بالحواف الموجهة في المخطط الموجه، بحيث يكون للحافة اتجاه واحد.
- المخطط غير الموجه (Undirect Graph)
لا تحتوي الوصلات على اتجاه في المخطط غير الموجه، وهذا يعني أن الحواف تشير إلى علاقة ثنائية الاتجاه يمكن من خلالها عرض البيانات في كلا الاتجاهين.
الشكل التالي يعرض مُخططًا موجهًا، ومخططًا غير موجه يتكونان من ست عقد وست حواف.
لمعرفة المزيد من المعلومات عن أنواع المُخطَّطات، قم بالاطّلاع على الرابط التالي:
المُخطَّطات في الحياة اليومية (Graphs in Everyday Life)
شبكة الويب العالمية World Wide Web
تُعد شبكة الويب من أبرز الأمثلة للمخططات، يمكن اعتبارها بمثابة أحد أنواع المخططات الموجهة حيث تمثل الرؤوس (Vertices) صفحات الويب، وتمثل الارتباطات التشعبية الحواف الموجهة.
تنقيب بنية الويب (Web Structure Mining) هو اكتشاف المعرفة المفيدة من هيكل شبكة الويب الممثلة من خلال الارتباطات التشعبية والعلاقات التي تُنشئها بين صفحات الويب المختلفة.
الشكل التالي يعرض رسمًا توضيحيًا لشبكة الويب العالمية. باستخدام هذه المخططات يمكنك حساب الأهمية النسبية لصفحات الويب.
فيسبوك Facebook
فيسبوك هو مثال آخر على المخططات غير الموجهة، يظهر الشكل التالي العُقد التي تمثل مستخدمي فيسبوك، بينما تمثل الحواف علاقات الصداقة.
عندما تريد إضافة صديق، يجب عليه قبول طلب الصداقة، ولن يكون ذلك الشخص صديقك على الشبكة دون قبول طلب الصداقة.
العلاقة هنا بين اثنين من المستخدمين (عقدتين) هي علاقة ثنائية الاتجاه.
تستخدم خوارزمية مقترحات الأصدقاء في فيسبوك نظرية المخططات.
تدرس تحليلات الشبكات الاجتماعية العلاقات الاجتماعية باستخدام نظرية المخططات أو الشبكات من علوم الحاسب.
خرائط جوجل Google Maps
يستخدم تطبيق خرائط جوجل وكل التطبيقات المشابهة له المخططات لعرض أنظمة النقل والمواصلات لحساب المسار الأقصى بين الموقعين.
تستخدم هذه التطبيقات المخططات التي تحتوي على عدد كبير جدًا من العُقد والحواف التي لا يمكن تمييزها بالعين المجردة.
الشبكة العصبية Neural Network
الشبكة العصبية هي نوع مخطط تعلم الآلة الذي يُحاكي الدماغ البشري.
الشبكات العصبية يُمكن أن تكون شبكات موجهة أو غير موجهة وفقًا للغرض من التعلّم.
تتكون هذه الشبكان من الخلايا العصبية والأوزان الموزعة في الطبقات المختلفة.
تمثل الخلايا العصبية بالعقد، بينما تمثل الأوزان بالحواف.
يتم حساب تدفقات الإشارة وتحسينها في جميع أنحاء بنية الشبكات العصبية لتقليل الخطأ.
تستخدم الشبكات العصبية في العديد من التطبيقات الذكية مثل: الترجمة الآلية، تصنيف الصور، تحديد الكائنات والتعرف عليها.
المثال التالي يوضح هيكل الشبكات العصبية.
بإمكانك مراجعة محتوى موضوع “هياكل البيانات غير الخطية” بدايةً من عنوان “المُخطَّطات” وحتى هذه النقطة، من خلال الرابط التالي:
المُخطَّطات في لغة البايثون (Graphs in Python)
لا تُوفر لغة بايثون نوعًا محددًا مسبقًا من البيانات للأشجار، كما أنها لا تُوفر نوعًا محددًا مسبقًا من البيانات للمخططات (تذكر أن الأشجار هي نوع خاص من المخططات).
ومع ذلك، يمكن بناء المخططات باستخدام القوائم والقواميس.
في المثال التالي/ سنقوم بتنفيذ التالي:
- إنشاء مخطط موجه مثل الموضح بالشكل أدناه.
- إنشاء دالة لإضافة عقدة إلى المخطط.
- إنشاء كائن يحتوي على كل مسارات المخطط.
سيتولى البرنامج الرئيس:
- إنشاء المخطط.
- طباعة المخطط.
- استدعاء دالة الإضافة.
- طباعة كل مسارات المخطط.
ستستخدم القاموس الذي تُمثل مفاتيحه العقد بالمخطط. تكون القيمة المقابلة لكل مفتاح هي قائمة تحتوي على العقد المتصلة بحافة مباشرة من هذه العقدة.
بإمكانك مراجعة محتوى موضوع “هياكل البيانات غير الخطية” بدايةً من عنوان “المُخطَّطات في لغة البايثون” وحتى نهاية هذا القسم، قم بالاطّلاع على الرابط التالي:
اختبر تحصيلك لمحتوى الموضوع من خلال الرابط التالي:
الواجب الإلكتروني
إلى هنا يكون قد انتهى موضوع “هياكل البيانات غير الخطية”، لا تنسوا مراجعة أهداف التعلُّم أعلى المقال، وانتظرونا في الموضوع القادم!