الجزء الثالث

Data Structures
هياكل البيانات 

في الباب الأول عرفنا يعني إيه Algorithms , وازاي نعمل Analysis و Design لل Algorithms , وشفنا أول 2 Algorithms وهما ال Insertion sort وال Merge sort . في الجزء الثاني درسنا بالتفصيل مشكلة ال Sorting وشفنا Algorithms كتير بتحل المشكلة ومدى الفرق في ال Performance بين ال Algorithms دي.


في الجزء ده هنتعلم حاجتين:
- ازاي نعمل representation لل Data.
- ازاي نعمل operations على ال Data دي.


في الفصل السادس اتعرضنا لأول Data Structure وهي كانت ال Heap , وشفنا ازاي ال Data structure دي بتسهلنا تنفيذ عمليات على ال Data زي ال Sorting باستخدام ال Heap sort Algorithm , وزي ال extraction وال insertion وال updating elements باستخدام ال Priority Queue.


في الأول عايزين نعرف يعني إيه Mathematical set وإيه علاقتها بال Data structures? أولا Mathematical set هي مجموعة من العناصر المميزة(يعني مفيش عنصر متكرر), كمان ال Mathematical set مش بتتغير , زي مثلا مجموعة الأعداد الطبيعية هي مجموعة أعداد محددة لا ينفع تحذف منها أعداد ولا ينفع تضيف ليها أعداد لإن لو عملت كدة مش هتبقى مجموعة الأعداد الطبيعية. أما ال Sets اللي بنستخدمها في ال Computer science علشان نخزن أو ن represent ال Data هي عبارة عن Dynamic sets , يعني بتتغير , لإن إحنا مش مجرد عايزين نخزن ال Data إحنا عايزين نعمل عليها processing وال processing ده بالتأكيد ينتج منه تغيير لل Data زي مثلا إننا نضيف أو نحذف elements من ال Data. يعني تقدر تقول إن ال Data structures هي Dynamic sets.


Elements of a dynamic set
قلنا ان ال Sets هي عبارة عن مجموعة عناصر , بس يعني إيه عناصر في ال Computer science؟ هنا إحنا بنقصد مش مجرد مجموعة أعداد ولكن مجموعة records أو objects وال record دايما بيتكون من key data و satellite data , والجزئية دي اتشرحت بالتفصيل في مقدمة الجزء الثاني (ممكن ترجعلها). بعض ال Dynamic sets بتفرض ان  ال keys بتاعتها مرتبة, النوع ده من ال Sets اسمه totally-ordered sets . النوع ده بيسهل بعض العمليات زي ال Minimum وال Maximum وال Successor وال Predecessor والعمليات دي هنفهمها حالا.



Operations on dynamic sets
العمليات اللي بتتنفذ على ال Dynamic sets ممكن نقسمها لقسمين رئيسيين:
  • Queries
و كلمة query يعني (استفسار) وبالتالي النوع ده من العمليات مش بيغير في ال Dynamic set ولكن بيسأل عن معلومة معينة في ال Dynamic set.
  • Modifying operations
وكلمة modifying يعني تغيير وبالتالي النوع ده من العمليات بيغير في ال Dynamic set.


نشوف بقى أمثلة للعمليات دي:
1) Search(S, k)
العملية دي query بتسأل هل ال element اللي ال key بتاعه k موجود في ال Set S ولا ﻷ, لو ال element ده موجود المفروض نرجع reference أو pointer بيشاور على ال element ده ولو مش موجود المفروض نرجع NULL.
2) Insert(S, x)
العملية دي Modifying لإنها بتتضيف element جديد x لل Set S .
3) Delete(S, x)
العملية دي Modifying لإنها بتحذف element x من ال Sets S. لاحظ إن x هنا بتعبر عن ان اللي جايلنا ك argument هو العنصر نفسه أو pointer ليه مش ال key , لإن لو اللي جاي key هنضطر نعمل search الأول قبل منحذف.
* ال Dynamic set اللي بتوفر ال 3 عمليات دول بتسمى dictionary.
4) Minimum(S)
العملية دي query بترجع ال element صاحب أصغر key في ال Set S.
5) Maximum(S)
العملية دي query بترجع ال element صاحب أكبر key في ال Set S.
6) Successor(S, x)
العملية دي query بترجع ال element الي بعد ال element x في الترتيب من حيث ال key طبعا.
7) Predecessor(S, x)
العملية دي query بترجع ال element الي قبل ال element x في الترتيب.

في الجزء ده إن شاء الله هنشوف أمثلة لل Data structures اللي بتوفر العمليات دي وهنشوف الفرق في ال performance بينهم.



 



تعليقات

إرسال تعليق

المشاركات الشائعة من هذه المدونة

الفصل الرابع

صورة
Recurrences مقدمة أخدنا في الفصل التاني طريقتين ( Approaches ) لتصميم (Designing) ال algorithms أول طريقة كانت ال incremental وشفنا مثال عليها ال insertion sort والطريقة التانية كانت divide-and-conquer وشفنا مثال عليها ال merge sort , وعرفنا ايه هو ال recursion اللي مبني عليه طريقة ال divide-and-conquer وقلنا انه ببساطة ال function او ال algorithms بتنادي (call) نفسها علشان كدة مسمينه recursion( العودية ) يعني بيرجع ينادي نفسه , في الفصل التالت شفنا بعض ال notations لوصف ال running time لأي algorithm وهي ال asymptotic notations زي ال Θ وال O وال Ω وال o وال ω . في الفصل الرابع هنبدأ ناخد طرق لحساب ال running time ل algorithms شغالة بال recursion. أولا يعني إيه عنوان الفصل؟ يعني ايه recurrence ? كلمة recurrence معناها بالعربي مبيوفيش معناها بالانجليزي , يعني ايه؟ يعني هي مصطلح كامل مفيش كلمة واحدة في اللغة العربية بنفس معناها , علشان كدة أنا مش مترجم إسم الفصل على عكس الفصول اللي عدت , المهم يعني إيه recurrence? ببساطة recurrence يعني معادلة بتوصف function بناءا ...
قراءة المزيد

الفصل السادس

صورة
Heapsort مقدمة اتعرضنا في الباب الأول لل insertion sort algorithm وقلنا ان أهم ميزة فيه هي الـ storage لانه sort in place يعني بيرتب في نفس الـ array مش بيحتاج يحجز memory زيادة ولكن مشكلته ان الـ running time بتاعه O(n 2 ) , واتعرضنا لل merge sort algorithm وقلنا ان أهم ميزة فيه هي الـ speed لان الـ running time بتاعه O(nlgn) ولكن مشكلته انه مش sort in place لانه بيحتاج يحجز memory زيادة عن الـ array اللي بيرتبها ( الـ algorithm بيكون sort in place لو بيحجز في الـ memory عدد أماكن زيادة عن الـ data structure بتاعته متزدش عن انها constant لكن لو بيحجز عدد متناسب مع الدخل يعني n أو n/2 أو lgn فده ميعتبرش sort in place) , في الفصل ده هنتعرض لل heapsort algorithm وده algorithm بيجمع الميزة اللي في الـ insertion sort بانه sort in place والميزة اللي في الـ merge sort بان الـ running time بتاعه O(nlgn) . الـ heapsort بيقدم design approach جديدة غير الـ incremental بتاعة الـ insertion sort وغير الـ divide-and-conquer بتاعة الـ merge sort , الـ design approach الجدي...
قراءة المزيد

الفصل الثامن

صورة
Sorting in Linear Time   مقدمة في الفصول اللي عدت شفنا أكتر من algorithm بيحل مشكلة ال sorting , بداية من ال Insertion sort لل Merge sort لل Heap sort لل Quicksort , ولكن إيه أفضل performance وصلناله من حيث ال running time ؟ الإجابة هي إن أفضل running time وصلناله هو O(nlgn) في ال worst case , السؤال بقى هل فيه أفضل من كدة؟ هل نقدر نعمل design ل Sorting algorithm يشتغل في running time أقل من O(nlgn) ؟ الإجابة أه نقدر , بس لازم نغير الطريقة اللي بنفكر بيها , طيب هي إيه الطريقة اللي بنفكر بيها ومحتاجين نفكر بطريقة غيرها؟ أو السؤال بشكل تاني إيه المتشابه في كل ال algorithms اللي شفناها لغاية دلوقتي؟ في كل ال algorithms اللي شفناها لغاية دلوقتي أحنا بنحاول نجيب ال sorted order من خلال المقارنة ( comparing ) بين ال elements أو الأرقام اللي احنا بنرتبها , يعني في كل algorithm بنعمل عملية comparing بين ال elements وبعضها ومن خلال ال comparing بنعرف ال relative order يعني مين أكبر من مين وبالتالي نوصل لل sorted order , في الفصل ده هنشوف إن أي algorithm بيشتغ...
قراءة المزيد