نصائح الخوارزميات وبنى المعطيات 2

من ويكي الهندسة المعلوماتية
اذهب إلى: تصفح، ابحث

أفكار أساسية

  • في هذه المادة يجب التركيز على السرعة في الحل، لأن 99% من الطلاب يعانون من ضيق الوقت في الامتحان.
  • مادة الخوارزميات وبنى المعطيات 2 هي تكملة لسابقتها الخوارزميات وبنى المعطيات 1 كما هو واضح، إذاً فهي كسابقتها أساسية وهامة جداً بالنسبة لنا كمهندسين.
  • تهتم هذه المادة ببنى المعطيات بشكل أساسي خلافاً لسابقتها التي اهتمت بطرائق التفكير وأنواع الخوارزميات.
  • من أفضل الأساليب لإتقان هذه المادة برمجة بنى المعطيات التي نتعلمها والعمليات عليها، سواء أكان ذلك بواسطة البرمجة الإجرائية أو البرمجة كائنية التوجه، ولكن بما أننا تعلمنا البرمجة كائنية التوجه في البرمجة 3 في الفصل الأول، لذلك فإن استخدامها في نمذجة بنى المعطيات التي نتعلمها سيكون مفيداً وممتعاً.
  • الحضور مفيد لكنه ليس ضروري .
  • ينصح بدراستها من نوطة بلال السلاخ وهي موجودة بالمكتبة.


المحتوى العلمي

  • جدوال التقطيع وتوابع التقطيع Hash Table & Hash Functions


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


  • الأشجار المعممة والأشجار الثنائية :


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

- ومن الجدير ذكره أننا نلجأ إلى بنية المعطيات الأشجار عندما نريد تخزين كميات كبيرة من المعطيات ونريد إجراء معالجات عليها بتعقيد مقبول ؛ ففي الأشجار غالباً ما يكون التعقيد لوغاريتمي . طبعاً في حالة كمية معطيات كبيرة لا تنفع كثيراً جدوال التقطيع لأنها ستؤدي إلى تصادمات كثيرة وستدرس ذلك بالتفصيل .


  • اأشجار البحث الثنائية(Binary Search Trees (BST: : أشجار ثنائية ( كل أب له على الأكثر ابنان فقط ) ، بما أنها أشجار بحث فالمعطيات فيها تكون مرتبة ( مثلاً الصغير على يسار الأب والكبير على يمين الأب ) وبالتالي فإن تعقيد عمليات المعجم ( إضافة - بحث - حذف ) " ويمكن القول ان ارتفاع الشجرة هو تابع للـ " في أحسن الاحوال، وندرس أيضاً من أنواع أشجار البحث الثنائية الأشجار الكاملة والأشجار التامة والأشجار الخطية ونلاحظ أنه في أسوأ الحالات ( وهو الشجرة الخطية أن الارتفاع يكون تابع لـ ). وتحدث الشجرة الخطية عندما ياتي أحد الأشرار ويضيف إلى شجرة البحث الثنائي مجموعة من العناصر بشكل تصاعدي أو تنازلي وعندها نفشل في تحقيق تعقيد ثنائي .


- ترد اشجار البحث الثنائية وخوارزمياتها في الامتحان .

  • أشجار البحث المتوازنة AVL trees  :

- نحن في مسلسل الخوارزميات 2 نسعى دوماً لتعقيد أفضل :) ، لاحظنا في أشجار البحث الثنائية أن التعقيد يتراوح بين لكن هذا لا يرضينا ؛ لذلك أوجدنا فكرة الأشجار المتوازنة AVL trees ، حيث كيفما ما تمت إضافة العناصر (سواء تصاعدياً أو تنازلياً أو بشكل عشوائي فإنك بالنهاية ستحصل على شجرة ارتفاعها هو تابع لوغاريتمي ثنائي .. بمعنى أن تعقيد العمليات على هذه الشجرة هو دائماً ؛ يتحقق ذلك بإجراء ما يسمى الدورانات نجريها عند شروط معينة ونترك ذلك للمحاضرات لتحقيق عنصر التشويق :) ^_^ .. ما ياتي بالامتحان من أشجار AVL أن ترسم لك الدكتور شجرة AVL متوازنة وتطلب منك إضافة عنصر معين و\ أو حذف عنصر معين .. بحوالي 8 درجات :)


  • أشجار BAYER  :

الفكرة هنا : أننا في عقدة من الشجرة نخزن مصفوفة عناصر وليس عنصر واحد كما كنا نفعل في AVL أو BST وهذا ما يفيد جداً جداً عندما نريد تعقيد امثلي لكميات هائلة من المعطيات فمثلاً قاموس يحوي 50000 كلمة فإن عمليات المعالجة تستهلك وقت أقل على أشجار باير منها على أشجار AVL وكلما زاد عدد العناصر في العقدة ( التي أصبحنا نسميها في باير " صفحة " ) أصبح التعقيد أفضل والسبب هو نقس ارتفاع الشجرة . امتحانياً : باير قد ترد كرسمة وتضيف عليها أو تحذف منها وقد ترد مرتبطة بمسألة فهرسة . ولكن لن ترد ككتابة خوارزمية( الكلام عن الاضافة أو الحذف ) وستعرف السبب حين تبرمج خوارزميات هذه الشجرة الجميلة:) وكذلك بالنسبة لـ AVL .


  • البيان graph  : بنية معطيات شجرية وما يختلف فيها عن الأشجار أنه لا يوجد تراتب عائلي مثلاً ( أب ثم ابن ثم حفيد وهكذا ) ، ببساطة البيان هو مجموعة عقد ومجموعة روابط تربط بينها ، ويقسم إلى قسمين بيان موجه وبيان غير موجه ، وستتعلم كيفية الـ implementation للبيان بطريقتين ، طريقة المصفوفة الثنائية وطريقة السلسلة الخطية ومن استخدامات البيان أن تمثل مثلاً ( مجموعة بلدان ( هي العقد) ومجموع الطرق الواصلة بينها ( العقد ) ) وتتعلم عدة خوارزميات في مسح البيان منها المسح بالعمق أولاً أو المسح بالعرض أولاً ، ومن الخوارزميات الجميلة التي تتعلمها هي خوارزمية الفرز الطبولوجي " مثلاً لديك مجموعة مواد تعتمد على بعضها ( بمعنى لا يمكنك أن تفهم مادة البرمجة2 دون أن تفهم مادة البرمجة 1 بالتالي مادة البرمجة 2 تعتمد على مادة البرمجة1 " فبتطبيق الفرز الطبولجي على عدة مواد تعتمد على بعضها ممثلة كبيان ستعطيك الخوارزمية المادة التي يجب ان تأخذها أولاً ثم المادة التالية وهكذا .. ومن تطبيقات البيان الحصول على الطريق الاقصر بين عقدتين .

ويرد بالامتحان ..


  • الملفات وتنظيمها :

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


  • الفهرسة Indexing  : الفكرة أننا لدينا ملف معطيات ، كالملف الذي درسناه في البحث السابق ، لكن كما اتفقنا أن سلسلة خ2 دائماً تسعى لتعقيد أفضل لذلك فإننا لوصول أفضل إلى ملف المعطيات سنقوم بفهرسته ، فالفهرس بحد ذاته هو ملف آخر لا يحوي معطيات إنما يحو مفاتيح ومؤشرات على المعطيات الموجودة في ملف المعطيات او ما يسمى الـ main file .

ندرس عدة أنواع لملفات الفهرسة  : الفهرس الأجوف ISAM ، فهرس التقطيع، فهرس الكومة ، الفهارس الكثيفة ...

ما يجب عليك أن تأخذه من هذا البحث هو أن تحفظ تعقيد كل عملية ( إضافة - بحث - حذف - تعديل) على كل نوع من انواع الفهارس كما يجب عليك ان تعرف خطوات خوارزمية كل عملية على كل نوع .. فإن لم تتعرف عليها الآن ستتعرف عليها في الامتحان ..!


آاراء شخصية

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


  • الحضور غير مهم كثيراً بالنسبة للنظري ، لكن مهم بالنسبة للعملي ، والسبب هو توسع المهندسين في الشرح وإعطاء مسائل جيدة وبعض أسئلة الدورات ، فضلاً عن ان الحضور عليه علامات وأنّه لديك الكثير من الكويزات :) حوالي 4 او 5 كويزات .. !


  • من الجيد جداً أن تحل المسائل الموجودة خلف كل درس بيدك ، فهي ليست بهذه الصعوبة ... وترد بعض الأحيان في الامتحان .


  • بالنسبة للامتحان : حاول أولاً أن تحل أسئلة دورة او دورتين لتأخذ فكرة عن كيفية قدوم الأسئلة ولأن الأسئلة والأفكار تتكرر بعض الأاحيان .

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