Embedded Files
الهدف من الأسبوع الحادي عشر:
الهدف من الأسبوع الحادي عشر:
1- التعرف على خوارزميات البحث Search Algorithms.
1- التعرف على خوارزميات البحث Search Algorithms.
2- التعمق في Binary Search Algorithm، وتعلم كيفية توظيفها في التفكير في حل المشاكل.
2- التعمق في Binary Search Algorithm، وتعلم كيفية توظيفها في التفكير في حل المشاكل.
3- التعرف على نوع جديد من مسائل المسابقات وهي Interactive Problems.
3- التعرف على نوع جديد من مسائل المسابقات وهي Interactive Problems.
هنتعلم ايه جديد؟
هنتعلم ايه جديد؟
- أول حاجة هنعرف يعني ايه خوارزميات البحث Search Algorithms من خلال التعريف البسيط دا:
- أول حاجة هنعرف يعني ايه خوارزميات البحث Search Algorithms من خلال التعريف البسيط دا:
- In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values (Wikipedia).
- In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values (Wikipedia).
مثالين لتوضيح التعريف:
مثالين لتوضيح التعريف:
1- لو بندور على رقم في array فيه خاصية معينة (مثلا أكبر رقم)، دي تعتبر search problem، بندور فيها على index الرقم اللي بيحقق الخاصية دي.
1- لو بندور على رقم في array فيه خاصية معينة (مثلا أكبر رقم)، دي تعتبر search problem، بندور فيها على index الرقم اللي بيحقق الخاصية دي.
2- لو بندور على الجذر التربيعي الموجب لرقم معين x، دي تعتبر search problem بندور فيها على رقم حقيقي مربعه بيساوي x.
2- لو بندور على الجذر التربيعي الموجب لرقم معين x، دي تعتبر search problem بندور فيها على رقم حقيقي مربعه بيساوي x.
- في مفهوم مهم جدا لازم نكون عارفينه كويس وهو Search Space: ومعناه فضاء البحث (أو مساحة البحث) ودا بكل بساطة هو الفضاء اللي فيه كل الإجابات الممكنة وبنبحث فيه عن الإجابة المناسبة لحل مشكلتنا بإستخدام خوارزمية البحث Search Problem ودا أول حاجة بنفكر فيها واحنا بنحل أي Search Problem.
- في مفهوم مهم جدا لازم نكون عارفينه كويس وهو Search Space: ومعناه فضاء البحث (أو مساحة البحث) ودا بكل بساطة هو الفضاء اللي فيه كل الإجابات الممكنة وبنبحث فيه عن الإجابة المناسبة لحل مشكلتنا بإستخدام خوارزمية البحث Search Problem ودا أول حاجة بنفكر فيها واحنا بنحل أي Search Problem.
توضيح أكتر لمفهوم فضاء البحث من خلال المثالين المذكورين فوق:
توضيح أكتر لمفهوم فضاء البحث من خلال المثالين المذكورين فوق:
1- في المثال رقم 1: الـ search space بتاعنا هو الـ indices من 0 لحد n - 1 حيث n هو عدد عناصر الـ array.
1- في المثال رقم 1: الـ search space بتاعنا هو الـ indices من 0 لحد n - 1 حيث n هو عدد عناصر الـ array.
2- في المثال رقم 2: الـ search space بتاعنا هو جميع الأعداد الحقيقية من 0 إلى x.
2- في المثال رقم 2: الـ search space بتاعنا هو جميع الأعداد الحقيقية من 0 إلى x.
- اتعرضنا قبل كدا كتير لـ Search Problems، ومكناش بنتعامل معاها بشكل خاص وبنحلها عادي زي باقي المسائل بدون خوارزميات محددة ودا بسبب إن الـ constraints كانت بتسمحلنا نكتب حل ليه complexity كبيرة بس بتعدي في الـ time limit، ولكن مش دايما المشاكل بتكون بالبساطة دي.
- اتعرضنا قبل كدا كتير لـ Search Problems، ومكناش بنتعامل معاها بشكل خاص وبنحلها عادي زي باقي المسائل بدون خوارزميات محددة ودا بسبب إن الـ constraints كانت بتسمحلنا نكتب حل ليه complexity كبيرة بس بتعدي في الـ time limit، ولكن مش دايما المشاكل بتكون بالبساطة دي.
- خوارزميات البحث Search Algorithms متعددة، ومنها:
- خوارزميات البحث Search Algorithms متعددة، ومنها:
1- Linear/Sequential Search.
1- Linear/Sequential Search.
2- Binary Search.
2- Binary Search.
3- Ternary Search.
3- Ternary Search.
- اتعرضنا كتير لمشاكل وحليناها باستخدام Linear Search ودا أبسطهم، ودا بنطبقه كتير جدا لما نكون عايزين نحسب أكبر رقم في array أو ندور على رقم معين ودايما الـ worst case إننا نمشي على كل الأرقام الموجودة في الـ array عشان نوصل للإجابة (O(n.
- اتعرضنا كتير لمشاكل وحليناها باستخدام Linear Search ودا أبسطهم، ودا بنطبقه كتير جدا لما نكون عايزين نحسب أكبر رقم في array أو ندور على رقم معين ودايما الـ worst case إننا نمشي على كل الأرقام الموجودة في الـ array عشان نوصل للإجابة (O(n.
- الهدف الأساسي إننا نتعرف على Binary Search Algorithm وهي أحد الـ Decrease & Conquer Algorithms، وفيها بنقلل فضاء البحث Search Space ونبدأ نقلل الـ Search Space الجديد مرة تانية لحد ما نوصل للإجابة.
- الهدف الأساسي إننا نتعرف على Binary Search Algorithm وهي أحد الـ Decrease & Conquer Algorithms، وفيها بنقلل فضاء البحث Search Space ونبدأ نقلل الـ Search Space الجديد مرة تانية لحد ما نوصل للإجابة.
- رغم إن Binary Search أسرع من Linear Search ولكن مش بنقدر نستعمله دائما لإنه بيعتمد على إن الـ Search Space يكون Monotonic، يعني مرتب تصاعديا أو تنازليا.
- رغم إن Binary Search أسرع من Linear Search ولكن مش بنقدر نستعمله دائما لإنه بيعتمد على إن الـ Search Space يكون Monotonic، يعني مرتب تصاعديا أو تنازليا.
- هنتعلم استخدام Binary Search في حل Optimization Problems والنوع دا من المشاكل بيكون مطلوب مننا فيه نلاقي أحسن إجابة ممكنة وبيظهر في صورتين وهما Maximization Problems وبتطلب مننا نلاقي أكبر حل ممكن، وMinimization Problems وبتطلب مننا نلاقي أصغر حل ممكن.
- هنتعلم استخدام Binary Search في حل Optimization Problems والنوع دا من المشاكل بيكون مطلوب مننا فيه نلاقي أحسن إجابة ممكنة وبيظهر في صورتين وهما Maximization Problems وبتطلب مننا نلاقي أكبر حل ممكن، وMinimization Problems وبتطلب مننا نلاقي أصغر حل ممكن.
- في الـ Optimization Problems غالبا الـ Search Space بتاعنا بيكون Domain لـ Function معينة، ودي نقطة مهمة جدا خليها في بالك دايما إن فضاء البحث مش دايما هيكون عبارة عن array ومعظم المشاكل هتكون بتتعامل مع Function ولازم تضمن إن الـ Function دي بتستوفي شروط الـ Search Algorithm اللي هتستخدمها في الحل.
- في الـ Optimization Problems غالبا الـ Search Space بتاعنا بيكون Domain لـ Function معينة، ودي نقطة مهمة جدا خليها في بالك دايما إن فضاء البحث مش دايما هيكون عبارة عن array ومعظم المشاكل هتكون بتتعامل مع Function ولازم تضمن إن الـ Function دي بتستوفي شروط الـ Search Algorithm اللي هتستخدمها في الحل.
- وأخيرا هنتعرف على نوع جديد من المشاكل بيظهر في المسابقات وهو Interactive Problems وهنعرف ازاي نتعامل معاها ونحلها.
- وأخيرا هنتعرف على نوع جديد من المشاكل بيظهر في المسابقات وهو Interactive Problems وهنعرف ازاي نتعامل معاها ونحلها.
Extra Tutorials on Binary Search:
Extra Tutorials on Binary Search:
ملاحظة هامة جدا:
ملاحظة هامة جدا:
- اتعلمنا قبل كدا Set وMap في أسابيع C++ STL وعرفنا إنهم عبارة عن Binary Search Tree، واتعلمنا إننا نقدر نعمل insert وdelete وfind في logarithmic time.
- اتعلمنا قبل كدا Set وMap في أسابيع C++ STL وعرفنا إنهم عبارة عن Binary Search Tree، واتعلمنا إننا نقدر نعمل insert وdelete وfind في logarithmic time.
السؤال دلوقتي: هل ينفع نستخدم lower_bound وupper_bound الموجودين في algorithms library مع Set وMap؟
السؤال دلوقتي: هل ينفع نستخدم lower_bound وupper_bound الموجودين في algorithms library مع Set وMap؟
الإجابة: ينفع ولكن الـ complexity هتكون linear بدلا من logarithmic، ودا بسبب إن الـ elements مش linear في الـ memory ومنقدرش نوصل لأي random element في (O(1 ولازم نعدي على الـ elements من خلال الـ iterators.
الإجابة: ينفع ولكن الـ complexity هتكون linear بدلا من logarithmic، ودا بسبب إن الـ elements مش linear في الـ memory ومنقدرش نوصل لأي random element في (O(1 ولازم نعدي على الـ elements من خلال الـ iterators.
طيب ايه الحل؟ الحل بسيط جدا وجاهز وهو إن في implementation مخصص لـ lower_bound وupper_bound مناسب للـ internal structure للـ Set وMap بحيث يضمن دائما logarithmic time والـ methods دي موجودة داخل Set Library وMap Library ومهم جدا تكون عارفهم وهتحتاجهم كتير.
طيب ايه الحل؟ الحل بسيط جدا وجاهز وهو إن في implementation مخصص لـ lower_bound وupper_bound مناسب للـ internal structure للـ Set وMap بحيث يضمن دائما logarithmic time والـ methods دي موجودة داخل Set Library وMap Library ومهم جدا تكون عارفهم وهتحتاجهم كتير.
Set:
Set:
http://www.cplusplus.com/reference/set/set/lower_bound/
http://www.cplusplus.com/reference/set/set/upper_bound/
Map:
Map:
الخطوة القادمة بعد مشاهدة الفيديوهات:
الخطوة القادمة بعد مشاهدة الفيديوهات:
1- الدخول إلى Training Group والتسجيل في Week #11 من خلال الضغط على كلمة Register ثم مواصلة خطوات التسجيل.
1- الدخول إلى Training Group والتسجيل في Week #11 من خلال الضغط على كلمة Register ثم مواصلة خطوات التسجيل.
2- بدء حل مسائل Week #11 بالترتيب.
2- بدء حل مسائل Week #11 بالترتيب.
ملاحظات هامة:
ملاحظات هامة:
1- المسائل كثيرة العدد إلى حد ما وتحتاج لبعض من التركيز.
1- المسائل كثيرة العدد إلى حد ما وتحتاج لبعض من التركيز.
2- ينتهي الأسبوع يوم الجمعة الساعة 9 مساء.
2- ينتهي الأسبوع يوم الجمعة الساعة 9 مساء.
3- ستبدأ المسابقة الأسبوعية يوم الجمعة الساعة 9 مساء ومدتها ساعتان.
3- ستبدأ المسابقة الأسبوعية يوم الجمعة الساعة 9 مساء ومدتها ساعتان.
4- لا تنسى تحديث بيانات تقدمك في Training Sheet بشكل دوري.
4- لا تنسى تحديث بيانات تقدمك في Training Sheet بشكل دوري.
5- لا تتردد في السؤال على FB Community Training Group إذا واجهتك مشكلة ما أو لم تستطع فهم سؤال ما أو أردت طلب مصادر إضافية.
5- لا تتردد في السؤال على FB Community Training Group إذا واجهتك مشكلة ما أو لم تستطع فهم سؤال ما أو أردت طلب مصادر إضافية.
Google Sites
Report abuse